Methods and apparatus for generating authenticated error correcting codes

• US 9,496,897 B1
• Filed: 03/31/2014
• Issued: 11/15/2016
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Triandopoulos, Nikolaos, Juels, Ari, Tamassia, Roberto, Kelley, James Alan
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Dorman, Christian
• Application Number:
  US14/230,655
• Time in Patent Office: 960 Days
• Field of Search: 714/752
• US Class Current: 1/1
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H03M 13/63 Joint error correction and other techniques H03M13/31 and H03M13/33 take precedence
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 63/04 for providing a confidential data exchange among entities communicating through data packet networks
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 9/00 Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083

Abstract

Methods and apparatus are provided for encoding and decoding via authenticated error correcting codes, such as secure LT codes, secure Raptor codes, block codes and/or rateless codes. Encoded symbols are generated via an authenticated error correcting code by applying a Luby Transform (LT) code to a plurality of message symbols to produce one or more intermediate symbols using a pseudo random number generator (PRNG) to select the plurality of message symbols to combine to produce the intermediate symbols; encrypting the intermediate symbols to produce encrypted symbols; computing an authentication value, such as a message authentication code (MAC), over one or more of the one or more encrypted symbols; and appending the authentication value to the corresponding encrypted symbols to form the encoded symbols. Block scalable and random scalable constructions are also provided, as well as decoding techniques for all of the constructions.

Claims

1. A method performed by an encoder for generating one or more encoded symbols via an authenticated error correcting code, comprising:

applying a Luby Transform (LT) code to a plurality of message symbols to produce one or more intermediate symbols using a cryptographic pseudo random number generator (PRNG) to select the plurality of message symbols to combine to produce said one or more intermediate symbols;

encrypting said one or more intermediate symbols to produce one or more encrypted symbols;

computing an authentication value over one or more of said one or more encrypted symbols using a secret-key scheme based on a secret key shared by said encoder and a decoder of said one or more encoded symbols; and

appending said authentication value to said corresponding one or more encrypted symbols to form said one or more encoded symbols.

2. The method of claim 1, wherein said plurality of message symbols are divided into a plurality of blocks, wherein said LT code is applied to each block independently to obtain a corresponding set of one or more intermediate symbols for each of said blocks, wherein said encrypting and computing steps are applied to said corresponding set of one or more intermediate symbols for each of said blocks to collectively form said one or more encoded symbols and wherein said method further comprises the step of permuting said one or more encoded symbols from said plurality of blocks to form one or more permuted encoded symbols.

3. The method of claim 1, wherein said plurality of message symbols are divided into a plurality of blocks, wherein one or more encoded symbols associated with a given block are generated in an order of a final position of said one or more encoded symbols following a permutation, and wherein a desired one of said one or more encoded symbols is generated by (i) independently applying said LT code to said block which said desired one of said one or more encoded symbols is associated with to produce said intermediate symbol associated with said desired one of said one or more encoded symbols;

(ii) encrypting said intermediate symbol associated with said desired one of said one or more encoded symbols to produce said encrypted symbol associated with said desired one of said one or more encoded symbols;

(iii) computing said authentication value over said encrypted symbol associated with said desired one of said one or more encoded symbols; and

(iv) appending said authentication value to said encrypted symbol associated with said desired one of said one or more encoded symbols to form said desired one of said one or more encoded symbols.

4. The method of claim 1, wherein said plurality of message symbols are divided into a plurality of blocks, wherein an LT encoder is associated with each of said blocks, wherein an LT encoder is randomly selected to generate each successive symbol of said one or more encoded symbols, and wherein each of said LT encoders performs said steps of (i) independently applying said LT code to produce said one or more intermediate symbols;

(ii) encrypting said at least one intermediate symbol to produce said one or more encrypted symbols;

(iii) computing said authentication value over said one or more of said encrypted symbols; and

(iv) appending said authentication value to said corresponding encrypted symbols to form said successive symbol of said one or more encoded symbols.

5. The method of claim 1, wherein said cryptographic PRNG generates a sequence of pseudo-random bits based on a seed s.

6. The method of claim 1, wherein said authenticated error correcting code comprises one or more of a secure LT code, a secure Raptor code, a block code and a rateless code.

7. The method of claim 6, wherein said authenticated error correcting code comprises said secure Raptor code, and wherein said method for said secure Raptor code further comprises the step of applying a pre-code to said plurality of message symbols prior to said step of applying an LT code.

8. The method of claim 1, wherein said authentication value comprises one or more of a message authentication code (MAC) and a secret key signature scheme.

14. A computer program product comprising a tangible non-transitory machine-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed perform the steps of the method of claim 1.

9. A method performed by a decoder for processing a plurality of received encoded symbols generated via an authenticated error correcting code, comprising:

evaluating the integrity of one or more symbols from said plurality of received encoded symbols by verifying an authentication value appended to said one or more symbols from said plurality of received encoded symbols, wherein said appended authentication value is computed by an encoder over one or more encrypted symbols using a secret-key scheme based on a secret key shared by said encoder and a decoder of said one or more encoded symbols;

if said integrity evaluation succeeds, decrypting said one or more symbols from said plurality of received encoded symbols to produce one or more authenticated decrypted received symbols; and

decoding said one or more authenticated decrypted received symbols using a Luby Transform (LT) decoder that employs a cryptographic pseudo random number generator (PRNG) to select the one or more authenticated decrypted received symbols that are combined to produce one or more decoded symbols using said secret-key scheme based on said secret key shared by said decoder and said encoder of said received encoded symbols.

10. The method of claim 9, wherein a plurality of message symbols were divided into a plurality of blocks during an encoding stage, and wherein said method further comprises the steps of:

(a) permuting said plurality of received encoded symbols;

(b) independently decoding at least a portion of said plurality of received encoded symbols corresponding to a given one of said plurality of blocks by performing said steps of

(i) evaluating the integrity of one or more symbols from said portion of said plurality of received encoded symbols by verifying an authentication value appended to said one or more symbols from said portion of said plurality of received encoded symbols;

(ii) if said integrity evaluation succeeds, decrypting said one or more symbols from said portion of said plurality of received encoded symbols to produce said one or more authenticated decrypted received symbols; and

(iii) decoding said one or more authenticated decrypted received symbols using said LT decoder to produce said one or more decoded symbols; and

(c) concatenating said one or more decoded symbols from each decoded block of said plurality of blocks to produce a final decoded message.

11. The method of claim 10, wherein said step of permuting said plurality of received encoded symbols further comprises the step of determining which block from said plurality of blocks a given received encoded symbol belongs to and providing said given received encoded symbol to a given LT decoder associated with said determined block, and wherein said given LT decoder associated with said determined block independently operates to update a partial decoding for said determined block.

12. The method of claim 9, wherein a plurality of message symbols were divided into a plurality of blocks during an encoding stage, and wherein said method further comprises the steps of:

(a) determining a block from said plurality of blocks that a given received encoded symbol from said plurality of received encoded symbols belongs to;

(b) providing one or more of the received encoded symbols of a given block from said plurality of blocks to an LT decoder associated with said given block, and wherein said LT decoder associated with each given block decodes said given block by performing said steps of;

(i) evaluating an integrity of one or more symbols from said one or more received encoded symbols of said given block by verifying an authentication value appended to said one or more symbols from said one or more received symbols of said given block;

(ii) if said integrity evaluation succeeds, decrypting said symbols to produce said one or more authenticated decrypted received symbols; and

(iii) decoding said one or more authenticated decrypted received symbols using said LT decoder associated with said given block to produce said one or more decoded symbols; and

(c) concatenating said one or more decoded symbols from each decoded block from said plurality of blocks to produce a final decoded message.

13. The method of claim 9, wherein said authenticated error correcting code comprises one or more of a secure LT code, a secure Raptor code, a block code and a rateless code.

15. An encoder apparatus for generating one or more encoded symbols via an authenticated error correcting code, comprising:

a memory; and

at least one hardware device, coupled to the memory, operative to;

apply a Luby Transform (LT) code to a plurality of message symbols to produce one or more intermediate symbols using a cryptographic pseudo random number generator (PRNG) to select the plurality of message symbols to combine to produce said one or more intermediate symbols;

encrypt said one or more intermediate symbols to produce one or more encrypted symbols;

compute an authentication value over one or more of said one or more encrypted symbols using a secret-key scheme based on a secret key shared by said encoder apparatus and a decoder of said one or more encoded symbols; and

append said authentication value to said corresponding one or more encrypted symbols to form said one or more encoded symbols.

16. The apparatus of claim 15, wherein said plurality of message symbols are divided into a plurality of blocks, wherein said LT code is applied to each block independently to obtain a corresponding set of one or more intermediate symbols for each of said blocks, wherein said encryption and computation are applied to said corresponding set of one or more intermediate symbols for each of said blocks to collectively form said one or more encoded symbols and wherein said at least one hardware device is further configured to permute said one or more encoded symbols from said plurality of blocks to form one or more permuted encoded symbols.

17. The apparatus of claim 15, wherein said plurality of message symbols are divided into a plurality of blocks, wherein one or more encoded symbols associated with a given block are generated in an order of a final position of said one or more encoded symbols following a permutation, and wherein a desired one of said one or more encoded symbols is generated by (i) independently applying said LT code to said block which said desired one of said one or more encoded symbols is associated with to produce said intermediate symbol associated with said desired one of said one or more encoded symbols;

(ii) encrypting said intermediate symbol associated with said desired one of said one or more encoded symbols to produce said encrypted symbol associated with said desired one of said one or more encoded symbols;

(iii) computing said authentication value over said encrypted symbol associated with said desired one of said one or more encoded symbols; and

(iv) appending said authentication value to said encrypted symbol associated with said desired one of said one or more encoded symbols to form said desired one of said one or more encoded symbols.

18. The apparatus of claim 15, wherein said plurality of message symbols are divided into a plurality of blocks, wherein an LT encoder is associated with each of said blocks, wherein an LT encoder is randomly selected to generate each successive symbol of said one or more encoded symbols, and wherein each of said LT encoders performs said steps of (i) independently applying said LT code to produce said one or more intermediate symbols;

(ii) encrypting said at least one intermediate symbol to produce said one or more encrypted symbols;

(iii) computing said authentication value over said one or more of said encrypted symbols; and

(iv) appending said authentication value to said corresponding encrypted symbols to form said successive symbol of said one or more encoded symbols.

19. The apparatus of claim 15, wherein said cryptographic PRNG generates a sequence of pseudo-random bits based on a seed s.

20. The apparatus of claim 15, wherein said authenticated error correcting code comprises one or more of a secure LT code, a secure Raptor code, a block code and a rateless code.

21. The apparatus of claim 20, wherein said authenticated error correcting code comprises said secure Raptor code, and wherein said at least one hardware device is further configured to apply a pre-code to said plurality of message symbols prior to said application of an LT code for said secure Raptor code.

22. The apparatus of claim 15, wherein said authentication value comprises one or more of a message authentication code (MAC) and a secret key signature scheme.

23. A decoder apparatus for processing a plurality of received encoded symbols generated via an authenticated error correcting code, comprising:

a memory; and

at least one hardware device, coupled to the memory, operative to;

evaluate the integrity of one or more symbols from said plurality of received encoded symbols by verifying an authentication value appended to said one or more symbols from said plurality of received encoded symbols, wherein said appended authentication value is computed by an encoder over one or more encrypted symbols using a secret-key scheme based on a secret key shared by said encoder and a decoder of said one or more encoded symbols;

if said integrity evaluation succeeds, decrypt said one or more symbols from said plurality of received encoded symbols to produce one or more authenticated decrypted received symbols; and

decode said one or more authenticated decrypted received symbols using a Luby Transform (LT) decoder that employs a cryptographic pseudo random number generator (PRNG) to select the one or more authenticated decrypted received symbols that are combined to produce one or more decoded symbols using said secret-key scheme based on said secret key shared by said decoder and said encoder of said received encoded symbols.

24. The apparatus of claim 23, wherein a plurality of message symbols were divided into a plurality of blocks during an encoding stage, and wherein said at least one hardware device is further configured to:

(a) permute said plurality of received encoded symbols;

(b) independently decode at least a portion of said plurality of received encoded symbols corresponding to a given one of said plurality of blocks by performing said steps of

(i) evaluate the integrity of one or more symbols from said portion of said plurality of received encoded symbols by verifying an authentication value appended to said one or more symbols from said portion of said plurality of received encoded symbols;

(ii) if said integrity evaluation succeeds, decrypt said one or more symbols from said portion of said plurality of received encoded symbols to produce said one or more authenticated decrypted received symbols; and

(iii) decode said one or more authenticated decrypted received symbols using said LT decoder to produce said one or more decoded symbols; and

(c) concatenate said one or more decoded symbols from each decoded block of said plurality of blocks to produce a final decoded message.

25. The apparatus of claim 24, wherein said permutation of said plurality of received encoded symbols further comprises determining which block from said plurality of blocks a given received encoded symbol belongs to and providing said given received encoded symbol to a given LT decoder associated with said determined block, and wherein said given LT decoder associated with said determined block independently operates to update a partial decoding for said determined block.

26. The apparatus of claim 23, wherein a plurality of message symbols were divided into a plurality of blocks during an encoding stage, and wherein said at least one hardware device is further configured to:

(a) determine a block from said plurality of blocks that a given received encoded symbol from said plurality of received encoded symbols belongs to;

(b) provide one or more of the received encoded symbols of a given block from said plurality of blocks to an LT decoder associated with said given block, and wherein said LT decoder associated with each given block decodes said given block by performing said steps of;

(i) evaluate an integrity of one or more symbols from said one or more received encoded symbols of said given block by verifying an authentication value appended to said one or more symbols from said one or more received symbols of said given block;

(ii) if said integrity evaluation succeeds, decrypt said symbols to produce said one or more authenticated decrypted received symbols; and

(iii) decode said one or more authenticated decrypted received symbols using said LT decoder associated with said given block to produce said one or more decoded symbols; and

(c) concatenate said one or more decoded symbols from each decoded block from said plurality of blocks to produce a final decoded message.

27. The apparatus of claim 23, wherein said authenticated error correcting code comprises one or more of a secure LT code, a secure Raptor code, a block code and a rateless code.