Method and apparatus for facilitating efficient authenticated encryption

Abstract

In some embodiments, a key shared between communicating parties is mapped to a key variant using a block cipher. The key variant is mapped into a sequence of basis offsets using shifts and conditional xors. A nonce-dependent base offset is formed, and a sequence of offsets is constructed by starting with the base offset and then xoring, for each offset, an appropriate basis offset. Each message block is combined with a corresponding offset, enciphered, and then combined again with the offset, yielding a ciphertext block. The message fragment is xored with a computed pad to give a ciphertext fragment. A checksum is formed using the message blocks, the message fragment, and the pad, and is then combined with an offset and enciphered to yield a tag. The encrypted message includes the ciphertext blocks, the ciphertext fragment, and the tag.

What is claimed is: 
     
         1 . A computer-implemented method for authenticated-encryption that encrypts a plaintext into a ciphertext without padding the plaintext, the method comprising:
 partitioning the plaintext into a first plaintext portion having a multiple of n bits and a second plaintext portion having n−1 or fewer bits;   using a nonce to generate a sequence of offsets;   computing a first ciphertext portion having the same length as the first plaintext portion from the first plaintext portion, the sequence of offsets, and an n-bit block cipher;   computing a second ciphertext portion having the same length as the second plaintext portion from the second plaintext portion, an offset from the sequence of offsets, and the n-bit block cipher;   computing an n-bit authentication tag by using the n-bit block cipher to encipher a value that depends on the plaintext and an offset from the sequence of offsets; and   defining the ciphertext as the first ciphertext portion, the second ciphertext portion, and a portion of the n-bit authentication tag.   
     
     
         2 . The method of  claim 1  wherein the n-bit authentication tag further depends on a string of non-confidential associated data. 
     
     
         3 . The method of  claim 1  wherein the nonce is a counter that gets incremented with every message encrypted. 
     
     
         4 . The method of  claim 1  wherein each non-initial offset from the sequence of offsets is determined by xor-ing the prior offset with one of a plurality of key-dependent values. 
     
     
         5 . A non-transitory computer-readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method for authenticated-encryption that encrypts a plaintext into a ciphertext without padding the plaintext, the method comprising:
 partitioning the plaintext into a first plaintext portion having a multiple of n bits and a second plaintext portion having n−1 or fewer bits;   using a nonce to generate a sequence of offsets;   computing a first ciphertext portion having the same length as the first plaintext portion from the first plaintext portion, the sequence of offsets, and an n-bit block cipher;   computing a second ciphertext portion having the same length as the second plaintext portion from the second plaintext portion, an offset from the sequence of offsets, and the n-bit block cipher;   computing an n-bit authentication tag by using the n-bit block cipher to encipher a value that depends on the plaintext and an offset from the sequence of offsets; and   defining the ciphertext as the first ciphertext portion, the second ciphertext portion, and a portion of the n-bit authentication tag.   
     
     
         6 . The non-transitory computer-readable storage medium of  claim 5 , wherein the n-bit authentication tag further depends on a string of non-confidential associated data. 
     
     
         7 . The non-transitory computer-readable storage medium of  claim 5 , wherein the nonce is a counter that gets incremented with every message encrypted. 
     
     
         8 . The non-transitory computer-readable storage medium of  claim 5 , wherein each non-initial offset from the sequence of offsets is determined by xor-ing the prior offset with one of a plurality of key-dependent values. 
     
     
         9 . A circuit to perform authenticated-encryption that encrypts a plaintext into a ciphertext without padding the plaintext, the circuit comprising:
 circuitry to partition the plaintext into a first plaintext portion having a multiple of n bits and a second plaintext portion having n−1 or fewer bits;   circuitry to use a nonce to generate a sequence of offsets;   circuitry to compute a first ciphertext portion having the same length as the first plaintext portion from the first plaintext portion, the sequence of offsets, and an n-bit block cipher;   circuitry to compute a second ciphertext portion having the same length as the second plaintext portion from the second plaintext portion, an offset from the sequence of offsets, and the n-bit block cipher;   circuitry compute an n-bit authentication tag by using the n-bit block cipher to encipher a value that depends on the plaintext and an offset from the sequence of offsets; and   circuitry to define the ciphertext as the first ciphertext portion, the second ciphertext portion, and a portion of the n-bit authentication tag.   
     
     
         10 . The circuit of  claim 9 , wherein the n-bit authentication tag further depends on a string of non-confidential associated data. 
     
     
         11 . The circuit of  claim 9 , wherein the nonce is a counter that gets incremented with every message encrypted. 
     
     
         12 . The circuit of  claim 9 , wherein each non-initial offset from the sequence of offsets is determined by xor-ing the prior offset with one of a plurality of key-dependent values. 
     
     
         13 . The circuit of  claim 9 , wherein the circuit is an application-specific integrated circuit (ASIC). 
     
     
         14 . The circuit of  claim 9 , wherein the circuit is a field-programmable gate array (FPGA).