This invention relates to a method and apparatus for generating a cryptographic authentication code of a set of plaintext blocks, while allowing incremental updates to the set of plaintext blocks. Additionally, an aspect of the invention, allows the updated authentication code to be computed in a highly parallelizable manner.Another embodiment of the present invention defines a new class of authentication trees in which the updated authentication tree, although requiring log(n) block cryptographic operations, allows for the log(n) block cryptographic operations to be computed in parallel.Another embodiment of the present invention provides encryption and verification authentication tree schemes, as well as, an apparatus that generates, updates, and verifies such authentication trees.Another embodiment of the present invention provides authentication tree schemes in which the individual cryptographic operations are block cipher invocations as opposed to hash function invocations.A method according to an embodiment of the present invention, for implementing a parallelizable authentication tree is provided within the application. The method comprises the steps of recursively initializing an authentication tree to include nodes, inputting plaintext blocks into an authentication tree modifier, inputting the initialized authentification tree into the authentification tree modifier, processing the plaintext blocks and the initialized authentication tree by the authentication tree modifier, and outputting a modified authentication tree from the authentication tree modifier. tree modifier, inputting the initialized authentication tree into the authentication tree modifier, processing the plaintext blocks and the initialized authentication tree by the authentication tree modifier, and outputting a modified authentication tree from the authentication tree modifier.