Techniques for efficiently authenticating multiple objects and clustering objects based on access patterns are provided. For example, in an illustrative aspect of the invention, a technique for generating and/or reading authentication information, wherein the authentication information provides evidence that a plurality of objects were one of generated and sent by an entity, comprises using one or more object access patterns indicative of whether at least two of the plurality of objects are accessed within a similar time period to group objects together to reduce an overhead for at least one of generating and reading the authentication information.