Patent Publication Number: US-9425952-B2

Title: Algebraic manipulation detection codes from algebraic curves

Description:
TECHNICAL FIELD 
     This application is directed to error detection and protection from side channel attacks with block cipher cryptographic algorithms. 
     DISCUSSION OF THE RELATED ART 
     A block cipher is a deterministic cryptographic algorithm that operates on fixed-length groups of bits, called blocks, with an unvarying transformation that is specified by a symmetric key. Block ciphers typically carry out encryption in multiple rounds, each of which uses a different subkey derived from the original key. A block cipher uses two paired algorithms, one for encryption and an inverse algorithm for decryption. Both algorithms accept two inputs: an input block of size n bits and a key of size k bits; and both yield an n-bit output block. For example, a block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext. The exact transformation is controlled using a second input —the secret key. Decryption is similar: the decryption algorithm takes, in this example, a 128-bit block of ciphertext together with the secret key, and yields the original 128-bit block of plain text. Each key selects one permutation from the possible set of all permutations over the set of input blocks. Today, there is a palette of attack techniques against which a block cipher must be secure, in addition to being robust against brute force attacks. A multitude of modes of operation have been designed to allow block ciphers to be repeatedly and securely used, commonly to achieve the security goals of confidentiality and authenticity. 
     One example of a block cipher is the Advanced Encryption Standard (AES), a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001 which uses blocks of 2 7 =128 bits. Other block ciphers include the Data Encryption Standard (DES), Triple DES, the International Data Encryption Algorithm (IDEA), RC5, and Blowfish. The AES has been adopted by the U.S. government and is now used worldwide. All known direct attacks on the AES are computationally infeasible. However, there are several known side-channel attacks on certain implementations of AES, which do not attack the underlying cipher, but rather attack implementations of the cipher on systems which inadvertently leak data. Power consumption, electro-magnetic radiation, execution time, and behavior in the presence of faults can all be used to drastically decrease the complexity of cryptanalysis. Mobile cryptographic devices such as smartcards and mobile computers are especially vulnerable since the physical hardware implementing the algorithms, and hence the side-channel information, is easily accessible. Side channel attacks can use information obtained from an incorrectly functioning implementation of an algorithm to derive the secret information. Incorrect operation can result from faults within a circuit which may be due to natural effects or may be maliciously induced. 
     The concept of non-probabilistic error detection codes for protecting data against adversarial error injection was introduced by Kulikowski, et al. (K. J. Kulikowski, M. G. Karpovsky, and A. Tubing, “Robust Codes and Robust, Fault Tolerant Architectures of the Advanced Encryption Standard”, J. of System Architecture, Vol. 53, pp. 138-149, 2007, the contents of which are herein incorporated by reference in their entirety), and that of probabilistic algebraic manipulation detection (AMD) codes was introduced by Cramer, et al. (R. Cramer, Y. Dodis, S. Fehr, C. Padro, and D. Wichs, “Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors”, Cryptography ePrint Archive, Report 2008/030, 2008, the contents of which are herein incorporated by reference in their entirety). An AMD code can probabilistically encode a plaintext source string s from a set S as an element of a group G, with a unique decodability. In a case of an adversary intentionally flipping bits of data for revealing a secret of the AES, a technique known as intentional fault injection, AMD codes can detect a worst case bit-flipping error with high probability. Redundancy can be added to guarantee the detection of the worst-case error. Kulikowski propose the use of weak AMD codes, in which security holds only for a random sεS, rather than an arbitrary string, and which are derived from perfect nonlinear functions. However, Kulikowski assumes that the injected error is added (modulo 2) to the valuable data, and that the error checking is performed on x+e, where x is the original data, while the injected error e does not depend on the choice of x. This checking could require calculations on very large finite fields. Cramer focuses on the use of strong AMD codes from the evaluation of polynomials. However, Cramer&#39;s methods also require working in very large finite fields if a large number of bits need to be protected, even if the miss probability is modest. For example, to protect 2 16  bits with a miss probability of 1%, calculations are performed in F 2     19   . 
     SUMMARY 
     Exemplary embodiments of the disclosure as described herein generally include systems and methods for the use of algebraic curves to reduce complexity and the required field size of AMD error detection codes with a block cipher algorithms. Embodiments of the disclosure can efficiently provide protection to very large chunks of data, e.g. chunks larger than about 2 15  bits, which is 256 AES blocks, before the data is encrypted, where the allowed miss probability is of order 10 −2  to 10 −3 . Embodiments of the disclosure can perform protection simultaneously on several block cipher blocks. 
     According to an aspect of the invention, there is provided a method for protecting data from algebraic manipulation, including receiving a data word s εF q   d  to be protected, wherein q is a prime power and F q   d  is a vector space over the finite field F q  including vectors (x 1 , x 2 , . . . , x d ) with x i  εF q  for all iε{1, . . . , d}, fixing a basis {1, b 1 , . . . , b d } for a Riemann-Roch space L(m d Q) as an F q -vector space, wherein Q is a distinct place of degree 1 of an algebraic function field F/F q  of one variable with full constant field F q  and with genus g and m d  is a pole number of Q, uniformly drawing an index i from a set I:={1, . . . , n}, and encoding s as (s, i, f s (P i ))εF q   d ×I n ×F q , wherein f s (P i ) is defined as f s :=x [f(d)] +Σ j=1   d s j b j , wherein r(d):=min{j|∃×εL(m j Q):∀σεΦ,σ≠id: σ(x)−xεL(m j Q)|L(m d Q)}, Φ is a subgroup of Aut D,Q (F/F q ):={σεAut(F/F q )|σ(Q)=Q and σ(D)=D}, Aut(F/F q ) is a group of automorphisms of F over F q , D:=P 1 + . . . +P n  wherein Q, P 1 , . . . , P n  are pairwise distinct places of F/F q  of degree 1, and x [r(d)]  is an element of L(m r(d) Q) for which σ(x [r(d)] )−x [r(d)] εL(m e Q)\L(m d Q) for all σεΦ, σ≠id, and for a minimum possible e≧d+1, wherein a received triple r:=(  ĩ, {tilde over (v)})εF q   d ×I n ×F q  is valid iff {tilde over (v)}=f {tilde over (s)} (P ĩ ). 
     According to a further aspect of the invention, the method includes protecting the index i with a weak AMD code, wherein an error is detected in ( , ĩ, {tilde over (v)})) by checking the index ĩ, and if the ĩ-check passes, checking whether {tilde over (v)}=f {tilde over (s)} (P ĩ ). 
     According to a further aspect of the invention, the weak AMD code is constructed from a perfect nonlinear function. 
     According to a further aspect of the invention, wherein q is a square and the number of places of degree 1 is q r  for some integer r, the perfect non-linear function 
                 F   q   r     ≅     F     q       2   ⁢           ⁢   r         →     F     q             
is constructed as (x 1 , . . . , x 2r ) x 1 x 2 +x 3 x 4 + . . . +x 2r−1 x 2r .
 
     According to a further aspect of the invention, the method includes encoding the data word s using a block cipher. 
     According to a further aspect of the invention, the block cipher is selected from a group comprising AES, DES, Triple DES, IDEA, RC5, and Blowfish. 
     According to an aspect of the disclosure, there is provided a computer processor configured to execute a program of instructions to perform method steps for protecting encoded data from algebraic manipulation, the method including receiving a data word see to be protected, where K is a finite field of q elements for a square prime power q and a predetermined d, randomly selecting two integers a ε{0, . . . , q−1} and bε{0, . . . ,√q−1}, finding a point (α, β) on a Hermitian curve over a field F q  that corresponds to the randomly selected integers (a, b) from a mapping (a, b) (α, β)=( u a , u a   √q+1 z+v b ), where 
               u   a     :=     {           0             if   ⁢           ⁢   a     =   0     ,               γ   1     a   -   1           otherwise         ,           ⁢       V   b     :=     {           0             if   ⁢           ⁢   b     =   0     ,               γ   2     b   -   1           otherwise         ,                   
and z is a pre-selected element of the field F q  of unit trace, and where γ 1  is a pre-selected fixed primitive element of the field F q  and γ 2  is a pre-determined fixed element of the field F q  which is a primitive element of a field F √q   ⊂ F q , and calculating a sum f s (α, β)=α i     d+1   β j     d+1   +Σ k=1   d s k α i     k   β j     k    for an appropriate set of d+1 integers pairs I={(i k ,j k )} k=1   d+1 , where the encoded word is a triple (s, (α, β), f s (α, β)).
 
     According to a further aspect of the disclosure, the Hermitian curve   over F q , is defined by point pairs (α, β) where  ={(α, β)εF q ×F q |β √q +β=α √q+1 }, where √q=2 m/2  is an integer for an even m. 
     According to a further aspect of the disclosure, the method includes calculating q and the dimension d based on a number uεN* of information bits to be protected and a maximum allowed miss probability, 2 −κ , for κεN, where q and d satisfy log(q d )≧u. 
     According to a further aspect of the disclosure, calculating q and the dimension d includes initializing m=2κ, and if 
                 ⌈     u   m     ⌉     ≤       2       3   ⁢     m   /   2       -   κ       -     2     m   -   1       -     2       m   /   2     -   1           ,         
setting
 
               d   =     ⌈     u   m     ⌉       ,         
where q=2 m .
 
     According to a further aspect of the disclosure, if 
                 ⌈     u   m     ⌉     &gt;       2       3   ⁢     m   /   2       -   κ       -     2     m   -   1       -     2       m   /   2     -   1           ,         
the method includes incrementing m by 2 and repeating the step of setting
 
               d   =     ⌈     u   m     ⌉       ,         
if
 
     
       
         
           
             
               ⌈ 
               
                 u 
                 m 
               
               ⌉ 
             
             ≤ 
             
               
                 2 
                 
                   
                     3 
                     ⁢ 
                     
                       m 
                       / 
                       2 
                     
                   
                   - 
                   κ 
                 
               
               - 
               
                 2 
                 
                   m 
                   - 
                   1 
                 
               
               - 
               
                 
                   2 
                   
                     
                       m 
                       / 
                       2 
                     
                     - 
                     1 
                   
                 
                 . 
               
             
           
         
       
     
     According to a further aspect of the disclosure, γ 2 =γ 1   √q+1 , and z is determined by scanning γ 1 , γ 1   2 , . . . , until an element of unit trace is found, where an element of unit trace z satisfies z √q +z=1. 
     According to a further aspect of the disclosure, the method includes finding a (d+1)-th pole number, m d , of a place Q of F/F q  of degree 1, where a set of pole numbers of place Q is {i√q+j(√q+1)|i≧0, 0≦j≦√q−1}, where exponents I 1 ={(i k ,j k )} k=1   d ={(i,j)εN×N|i+j&lt;i*+j* and j≦√{square root over (q)}−1}∪{(i,j)εN×N|i+j=i*+j* and j≦j*} 
     are a pre-calculated set of all pairs (i, j)εN×N that correspond to pole numbers m 1 , m 2 , . . . , m d , i*εN, j*ε{0, . . . , √{square root over (q)}−1} are unique integers such that m d =i*√{square root over (q)}+j*(√{square root over (q)}+1) and exponents (i d+1 , j d+1 ) are pre-calculated from 
     
       
         
           
             
               ( 
               
                 
                   i 
                   
                     d 
                     + 
                     1 
                   
                 
                 , 
                 
                   j 
                   
                     d 
                     + 
                     1 
                   
                 
               
               ) 
             
             := 
             
               { 
               
                 
                   
                     
                       
                         ( 
                         
                           
                             
                               i 
                               * 
                             
                             + 
                             2 
                           
                           , 
                           
                             j 
                             * 
                           
                         
                         ) 
                       
                     
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                         ∤ 
                         
                           j 
                           * 
                         
                       
                     
                   
                   
                     
                       
                         ( 
                         
                           
                             
                               i 
                               * 
                             
                             + 
                             1 
                           
                           , 
                           
                             
                               j 
                               * 
                             
                             + 
                             1 
                           
                         
                         ) 
                       
                     
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                         ∣ 
                         
                           j 
                           * 
                         
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
     According to a further aspect of the disclosure, if d≧g=(√q−1)√q/2, then the (d+1)-th pole number m d  is m d =2g+(d−g)=d+g, and if dε{0, . . . , g−1}, the method includes finding a largest positive integer l such that 
                   l   ×     (     l   +   1     )       2     ≤     d   +   1       ,         
where if
 
                   l   ×     (     l   +   1     )       2     =     d   +   1       ,         
then m d =i*√q+j*(√q+1) for i*=0 and j*=l−1, otherwise m d =i*√q+j*(√q+1) for j*=d−l(l+1)/2ε{0, . . . , l≦√q−2} and i*l−j*≧0.
 
     According to a further aspect of the disclosure, the method includes encoding the data word s using a block cipher. 
     According to a further aspect of the disclosure, the block cipher may be selected from a group comprising AES, DES, Triple DES, IDEA, RC5, and Blowfish. 
     According to a further aspect of the disclosure, the computer processor is a hardware implementation that encodes the program of instructions to perform the method steps for protecting encoded data from algebraic manipulation. 
     According to a further aspect of the disclosure, the computer processor may be one of an application specific integrated circuit, or a field programmable gate array. 
     According to another aspect of the disclosure, there is provided a computer processor configured to encode and execute a program of instructions to perform the method steps for protecting encoded data from algebraic manipulations, the method including receiving a triple (s, (α, β), γ) that is an element of F q   d ×F q   2 ×F q , where s is an encoded data word, and q and d are predetermined constants, determining whether β √q +β=α √q+1 , and if β √q +β=α √q+1 , determining whether a sum f s (α, β)=γ, where f s (α, β)=α i     d+1   βd j     +1   +Σ k=1   d s k α i     k   β j     k    for an appropriate set of d+1 integers pairs I={(i k ,j k )} k=1   d+1 , where if either β √q +β≠α √q+1  or f s (α, β)≠γ, declaring an error, otherwise declaring that no error was injected into s. 
     According to a further aspect of the disclosure, the method includes calculating q and the dimension d based on a number uεN* of information bits being protected and a maximum allowed miss probability, 2 −κ , for κεN, where q and d satisfy log(q d )≧u. 
     According to a further aspect of the disclosure, calculating q and the dimension d includes initializing m=2κ, and if 
                 ⌈     u   m     ⌉     ≤       2         3   ⁢   m     2     -   κ       -     2     m   -   1       -     2       m   2     -   1           ,         
setting
 
               d   =     ⌈     u   m     ⌉       ,         
where q=2 m  for even m.
 
     According to a further aspect of the disclosure, if 
                 ⌈     u   m     ⌉     &gt;       2       3   ⁢     m   /   2       -   κ       -     2     m   -   1       -     2       m   /   2     -   1           ,         
the method further comprises incrementing m by 2 and repeating the step of setting
 
               d   =     ⌈     u   m     ⌉       ,         
if
 
     
       
         
           
             
               ⌈ 
               
                 u 
                 m 
               
               ⌉ 
             
             ≤ 
             
               
                 2 
                 
                   
                     3 
                     ⁢ 
                     
                       m 
                       / 
                       2 
                     
                   
                   - 
                   κ 
                 
               
               - 
               
                 2 
                 
                   m 
                   - 
                   1 
                 
               
               - 
               
                 
                   2 
                   
                     
                       m 
                       / 
                       2 
                     
                     - 
                     1 
                   
                 
                 . 
               
             
           
         
       
     
     According to a further aspect of the disclosure, the method includes finding a (d+1)-th pole number, m d , of a place Q of F/F q  of degree 1, where a set of pole numbers of place Q is {i√q+j(√q+1)|i≧0, 0≦j≦√q−1}, where exponents I 1 ={(i k ,j k )} k=1   d {(i,j)εN×N|i+j&lt;i*+j* and j≦√{square root over (q)}−1}∪{(i,j)εN×N|i+j=i*+j* and j≦j*} 
     are a pre-calculated set of all pairs (i, j)εN×N corresponding to pole numbers m 1 , m 2 , . . . , m d , and exponents (i d+1 , j d+1 ) are pre-calculated from 
     
       
         
           
             
               ( 
               
                 
                   i 
                   
                     d 
                     + 
                     1 
                   
                 
                 , 
                 
                   j 
                   
                     d 
                     + 
                     1 
                   
                 
               
               ) 
             
             := 
             
               { 
               
                 
                   
                     
                       
                         ( 
                         
                           
                             
                               i 
                               * 
                             
                             + 
                             2 
                           
                           , 
                           
                             j 
                             * 
                           
                         
                         ) 
                       
                     
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                         ∤ 
                         
                           j 
                           * 
                         
                       
                     
                   
                   
                     
                       
                         ( 
                         
                           
                             
                               i 
                               * 
                             
                             + 
                             1 
                           
                           , 
                           
                             
                               j 
                               * 
                             
                             + 
                             1 
                           
                         
                         ) 
                       
                     
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                         ∣ 
                         
                           j 
                           * 
                         
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
     According to a further aspect of the disclosure, if d≧g=(√q−1)√q/2, then the (d+1)-th pole number m d  is m d =2g+(d−g)=d+g, and if dε{0, . . . , g−1}, the method further comprises finding a largest positive integer l such that 
                   l   ×     (     l   +   1     )       2     ≤     d   +   1       ,         
where if
 
                   l   ×     (     l   +   1     )       2     =     d   +   1       ,         
then m d =i*√q+j*(√q+1) for i*=0 and j*=l−1, otherwise m d =i*√q+j*(√q+1) for j*=d−l(l+1)/2ε{0, . . . , l≦√q−2} and i*=l−j*≧0.
 
     According to a further aspect of the disclosure, the data word s was encoded using a block cipher. 
     According to a further aspect of the disclosure, the block cipher may be selected from a group comprising AES, DES, Triple DES, IDEA, RC5, and Blowfish. 
     According to a further aspect of the disclosure, the computer processor is a hardware implementation that encodes the program of instructions to perform the method steps for protecting encoded data from algebraic manipulation. 
     According to a further aspect of the disclosure, the computer processor may be one of an application specific integrated circuit, or a field programmable gate array. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  depicts an overall protected word, including data s, the index of point P, and the parity bits, in addition to index protection bits, according to an embodiment of the disclosure. 
         FIG. 2  depicts data corrupted by flipping some of the bits, by replacing the original data s with data s′, and by flipping some of the redundancy bits, according to an embodiment of the disclosure. 
         FIG. 3  depicts Δ 1  for the part of the additive error that influences the “index protection” field, Δ 2  for the part that influences the “index of point” field, and Δ 3  for the part that influences the “parity bits” field, according to an embodiment of the disclosure. 
         FIGS. 4A-B  are flowcharts of methods for encoding and decoding data using pre-AMD codes, according to an embodiment of the invention. 
         FIG. 5  is a table of comparisons of the AMD codes of Cramer, et al., and of AMD Hermitian codes according to an embodiment of the disclosure. 
         FIGS. 6A-B  are flowcharts of methods for encoding and decoding data using AMD Hermitian codes, according to an embodiment of the disclosure. 
         FIG. 7  is a block diagram of a system for the use of algebraic curves to reduce complexity and the required field size of AMD error detection codes with block cipher cryptographic algorithms, according to an embodiment of the disclosure. 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
     Exemplary embodiments of the invention as described herein generally provide systems and methods for the use of algebraic curves to reduce complexity and the required field size of AMD error detection codes with a block cipher cryptographic algorithm. While embodiments are susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit the invention to the particular forms disclosed, but on the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention. 
     Algebraic manipulations may be defined as follows: suppose there is some data s to be protected with some redundancy r appended to s for detecting manipulations. The adversary is allowed to: (1) replace s by some s′ of his/her will, possibly depending on s; and (2) Add some error A to r, where A may depend on s. Hence, the original data (s, r) is modified to be (s′,r+Δ). Note that it is assumed that r sits in some abelian group and the “+” in “r+Δ” is the addition of this group. Typically, the abelian group is just the underlying abelian group of F 2   n . 
     According to an embodiment of the disclosure, to protect data sεK d , where K is a finite field, one can select a random point P of an algebraic curve, where the point is represented by a tuple of elements from K, and calculate the parity bits
 
parity bits( s,P )= f   d+1 ( P )+Σ k=1   d   s   k   ·f   k ( P ),
 
where the f i , 1≦i≦d+1, are appropriately chosen rational, typically polynomial, functions that map curve points to elements of K. The overall protected word includes the data s, the index of point P, and the parity bits, in addition to index protection bits, as shown in  FIG. 1 . The index of point P, the index protection bits, and the parity bits are known as redundancy bits. The index protection bits include parity bits on the index itself, and may use weak AMD codes, or codes derived from Hermitian curves. Now, an adversary may corrupt the data by replacing the original data s with data s′, and may flip any portion of the redundancy bits, as shown in  FIG. 2 . For convenience, as shown in  FIG. 3 , one may write Δ 1  for the part of the additive error that influences the “index protection” field, Δ 2  for the part that influences the “index of point” field, and Δ 3  for the part that influences the “parity bits” field.
 
     Upon receipt of a corrupted word, a receiver may first check for the integrity of the index using the index protection field. This check may amount to checking a standard weak AMD code, or could amount to checking if a pair is a point on a Hermitian curve, as will be described in detail below. If this check fails, an error may be declared; otherwise a second check may be performed. In the second check, the parity bits are compared:
 
parity bits( s′,P+Δ   2 )==(parity bits+Δ 3 )?
 
If these bits are not equal, an error may be declared, otherwise it may be determined that no error was injected.
 
Construction of AMP codes
 
     Let q be a prime power and let F/F q  be an algebraic function field of one variable with frill constant field F q  and with genus g. Let Q, P 1 , . . . , P n  be pairwise distinct places of F/F q  of degree 1, and write D:=P 1 + . . . +Write
 
 Aut   D,Q   :={σεAut ( F/F   q )|σ( Q )= Q  and σ( D )= D} 
 
where Aut(F/F q ) is the group of automorphisms of F over F q ; the definition of Aut D,Q  says that the action of this group on the set of places of F/F q  fixes Q and permutes P 1 , . . . , P n .
 
     For a place R of F/F q , one may write v R  for the discrete valuation associated with R. For a divisor G of F/F q , let L(G) be the Riemann-Roch space defined by L(G):={fεF*|(f)+G≧0}∪{0}, where (f) represents the principal divisor of f. L(G) is a vector space over F q , and by the Riemann-Roch theorem one has dim(L(G))≧deg(G)−g+1, with equality if deg(G)≧2g−1, where deg(G) is the degree of G. 
     Let m 0 :=0&lt;m 1 &lt;m 2 &lt; . . . be the pole numbers of Q. So, for all i, L((m i −1)Q) /⊂ L(m i Q). According to the Riemann-Roch theorem, starting from 2g, all integers are pole numbers, and there are exactly g gaps (integers that are not pole numbers) in {1, . . . , 2g−1}. In addition, for all xεL(m i Q)\L(m i−1 Q) and all σεAut D,Q , σ(x) is also in L(m i Q)\L(m i−1 Q). 
     Let Φ ⊂ Aut D,Q (F/F q ) be a subgroup. For d&gt;1, the dimension of the information set, let
 
 r ( d ):=min{ j|∃εL ( m   j   Q ):∀σεΦ,σ≠ id :σ( x )− xεL ( m   j   Q )\ L ( m   d   Q )}   (1)
 
and let x [r(d)]  be some element in L(m r(d) Q) for which σ(x [r(d)] )−x [r(d)] εL(m e Q)\L(m d Q) for all σεΦ, σ≠id, and for the minimum possible e≧d+1, which will be known as e(d). Note that if Φ={id}, then there is no restriction on x [r(d)] , and therefore x [r(d)]  may be chosen freely, e.g., one may choose x [r(d)] =0.
 
     It is implicit in the definition of r(d) that the set from which the minimum element in the right-hand side of EQ. (1) is taken is non-empty. For the Hermitian case, conditions for this to hold will be found in the following section. For the general case, where an arbitrary function field is used, note again that if Φ={id}, then the condition in EQ. (1) is always met, and hence one may always take x [r(d)] =0. 
     Before constructing the target AMD codes, one begins by constructing weaker codes, which may be referred to as pre-AMD codes. A flowchart of a method of encoding data using pre-AMD codes is presented in  FIG. 4A . Referring now to the figure, at step  41 , let sεF q   d  be the information to be protected. Fix some basis {1, b 1 , . . . , b d } for L(m d Q) as an F q -vector space at step  42 , and define
 
 f   s   :=x   [r(d)] +Σ j=1   d   s   j   b   j .
 
     A code according to an embodiment of the disclosure may be defined as follows. An index i is drawn uniformly from the set I n :={1, . . . , n} at step  43 , and the data word s is encoded as (s, i, f s (P i ))εF q   d ×I n ×F q  at step  44 , where f s  is defined as above. It may be assumed in some embodiments that an adversary knows s, but not i and f s (P i ). The allowed manipulations for this pre-AMD code are: (1) replace s by some s′εF q   d , (2) add a constant in F q  to f s (P i ), and (3) apply to i a constant permutation πεS n  that corresponds to the action of some σεΦ on {P 1 , . . . , P n }. According to an embodiment of the disclosure, this may be known as a defined code C d . A code according to an embodiment of the disclosure can protect against manipulations of type (1) and (2) for any choice of x [r(d)] . However, if an element x [r(d)]  satisfies the above conditions imposed by Φ, then a code according to an embodiment of the disclosure can protect against the manipulations on the index part described by manipulations of type (3). So, a code according to an embodiment of the disclosure encodes log(q d ) bits of information to obtain an encoded word of length log(q d )+log(n)+log(q)=log(nq d+1 ). Note here that all logs are to the base of 2, thus a base subscript will be omitted hereinbelow. A decoder according to an embodiment of the disclosure works as follows, with reference to the flowchart of  FIG. 4B : receive a triple r:=( , ĩ, {tilde over (v)})εF q   d ×I n ×I n ×F q  at step  46 ; check if {tilde over (v)}=f {tilde over (s)} (P ĩ ) at step  47 ; declare r valid if the check passes, at step  48 ; otherwise, at step  49 , declare r to be invalid. In other words, a received triple r:=( {tilde over (l)},{tilde over (v)})εF q   d ×I n ×F q  is valid iff {tilde over (v)}=f {tilde over (s)} (P ĩ ). 
     Theorem 1. For the set of manipulations described above, the miss probability of the pre-AMD code C d  is not above m e /n≦(e+g)/n, where e=e(d). 
     Proof. For simplicity and without loss of generality, it may be assumed that after drawing i, the encoding is of the form s (s, P i , f s (P i )). Note that specifying i in the second coordinate is like specifying P i . For an arbitrary fixed s, it is desired to find an upper bound on the probability (over i) that an adversary succeeds, that is, that for s′≠sεF q   d , some fixed ΔεF q  and some fixed σεΦ, there is f s′ (σ(P i ))=f s (P i )+Δ. In detail, one would like to bound the number of possible choices of i for which
 
 x   [r(d)] (σ P   i )− x   [r(d)] ( P   i )+Σ j=1   d   s′   j   b   j (σ P   i )−Σ j=1   d   s   j   b   j ( P   i )−Δ=0.  (2)
 
If σ=id, then EQ. (2) becomes
 
(Σ j=1   d ( s′   j   −s   j ) b   j −Δ)( P   i )=0.
 
Because Σ j=1   d (s′ j −s j )b j −Δ is a non-zero element of L(m d Q), as s≠s′, it has at most m d &lt;m e  zeros.
 
     Otherwise, if a is not the identity, then since for all u with v σP     i   (u)≧0 one has u(σP i )=σ −1 (u)(P i ), because for all τεAut(F/F q ) and all u with v P     i   (u)≧0, τ(u)(τ(P i ))=u(P i ); one obtains that for all i,
 
 x   [r(d)] (σ P   i )− x   [r(d)] ( P   i )=(σ −1 ( x   [r(d)] )− x   [r(d)] )( P   i )= z ( P   i ) for some  zεL ( m   e   Q )\ L ( m   d   Q )
 
by the definition of x [r(d)]  and e=e(d). Also,
 
                   ∑     j   =   1     d     ⁢       s   j   ′     ⁢       b   j     ⁡     (     σ   ⁢           ⁢     P   i       )           -       ∑     j   =   1     d     ⁢       s   j     ⁢       b   j     ⁡     (     P   i     )           -   Δ     =         ∑     j   =   1     d     ⁢       (         s   j   ′     ⁢       σ     -   1       ⁡     (     b   j     )         -       s   j     ⁢     b   j       -   Δ     )     ⁢     (     P   i     )         =     w   ⁡     (     P   i     )                             ⁢         for   ⁢           ⁢   some   ⁢           ⁢   w     ∈     L   ⁡     (       m   d     ⁢   Q     )         ,     possibly   ⁢           ⁢   0.             
Note that for all τεAut D,Q , all u εF and all mεN* (where N* is the set of positive integers), uεL(mQ) τuεL(mQ)). Since m e &gt;m d , it follows from the strict triangle inequality that for all i, the left-hand side of EQ. (2) is of the form u(P i ) for some uεL(m e Q)\L(m d Q) that does not depend on i. Since the number of places P i  such that u(P i )=0 is not greater than m e , the proof is complete. ▪
 
     Next, drop the restriction that the manipulations on the i part may only come from automorphisms of the function field. This will be done in detail for the Hermitian case in the following section. 
     In general, one can move from pre-AMD codes to AMD codes by adding protection on the index i. In one option according to an embodiment of the disclosure, Φ={id}, and so the protection should detect with high probability any constant additive error on the (typically binary) vector representing i. In another option according to an embodiment of the disclosure, Φ {id}, and the protection is allowed to miss those additive errors that correspond to automorphisms from Φ. This option is used in the Hermitian case described below. In the first option according to an embodiment of the disclosure, Φ={id} and there are no restriction on x [r(d)] , and one may choose x [r(d)] =0, resulting in f s =Σ j=1   d s j b j . To replace and enhance the lost protection of the index part against the manipulations of type (3), embodiments of the disclosure may include an explicit protection on the index-field, in the form of a weak AMD code. The miss probability will then be at most max {δ, m d /n≦(d+g)/n}, where δ is the probability of missing an error on i. Here, i is first checked, and if the check passes, f s (P i ) is checked. If the i-check fails, an error may be declared. If an adversary injects an error on i, then this error itself may already be detected with probability δ, regardless of the other errors. So, the i-check will be transparent if δ≦(d+g)/n. Because g/n is at least about 1/√q, it is enough to assure that δ is not above about 1/√q. In general, this can be achieved by using a perfect non-linear function with codomain F √q . So, for a fixed q, even if n grows to infinity using an optimal tower of function fields, the redundancy required for protecting i does not grow. Note also that if q is a square and the number of places of degree 1 is q r  for some integer r, then there is a very simple way to construct a perfect non-linear function 
     
       
         
           
             
               
                 F 
                 q 
                 r 
               
               ≅ 
               
                 F 
                 
                   q 
                 
                 
                   2 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   r 
                 
               
             
             → 
             
               
                 F 
                 
                   q 
                 
               
               ⁢ 
               
                 : 
               
               ⁢ 
               
                   
               
               ⁢ 
               take 
               ⁢ 
               
                   
               
               ⁢ 
               
                 ( 
                 
                   
                     x 
                     1 
                   
                   , 
                   … 
                   ⁢ 
                   
                       
                   
                   , 
                   
                     x 
                     
                       2 
                       ⁢ 
                       r 
                     
                   
                 
                 ) 
               
             
             ↦ 
             
               
                 
                   x 
                   1 
                 
                 ⁢ 
                 
                   x 
                   2 
                 
               
               + 
               
                 
                   x 
                   3 
                 
                 ⁢ 
                 
                   x 
                   4 
                 
               
               + 
               … 
               + 
               
                 
                   x 
                   
                     
                       2 
                       ⁢ 
                       r 
                     
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                   
                     x 
                     
                       2 
                       ⁢ 
                       r 
                     
                   
                   . 
                 
               
             
           
         
       
     
     The construction of the codes according to embodiments of the current disclosure can also be described in terms of error-correcting codes. Let C ⊂ F q   n  be a code with |C|=q k  for some k≦n, and let c:F q   k →C be a bijection (an encoding function). A permutation σεS n , where S n  is the symmetric group on n letters, may be called a quasi-automorphism of C if for all uεC there exists u′εC and a constant vector d=(Δ, . . . , Δ)εF q   n  such that σu=u′+d, where σu:=(u σ(1) , . . . , u σ(n) ). 
     Suppose that the set of indices I:={1, . . . , n} of C is embedded in some abelian group A via an injective function t:I→A (it is not required that the image of I is a subgroup of A), so that one may think of the indices as elements of A. For simplicity, consider I as a subset of A, without explicit reference to the injection t. 
     Given a message sεF q   k , an index iεI may be chosen at random, and the encoded message may be defined to be the triple (s, i, [c(s)] i ), where for a vector v, [v] i  represents the i-th coordinate of v. Decoding works as follows: given a triple (s′, a, y)εF q   k ×A×F q , one first checks whether αεI (this check is only necessary if I is a proper subset of A), and then, if this check succeeds, one checks whether y=[c(s′)] α . The message is declared valid if and only if the two tests are successful. 
     The need to effectively cope with injected errors of the form (s, i, [c(s)] i ) (s′,i+Δ 2 , [c(s)] i +Δ 3 ), where s′εF q   k ,Δ 2 εA, Δ 3 εF q , and s′, Δ 2 , Δ 3  are allowed to depend on s, imposes some constraints on the possible codes C to be used:
         1. For the case where Δ 2 =0, for all distinct codewords c(s), c(s′) and for all Δ 3 εF q , the number of choices of i for which [c(s′)] i =[c(s)] i +Δ 3  should be small. Put differently, for all distinct codewords u, u′ of C, the Hamming distance between u and any shift of u′ by a constant vector should be large. In particular, the minimum Hamming distance of C should be large. To meet this requirement C should not contain more than one constant vector.   2. For the case where Δ 2 ≠0 and i+Δ 2 εI, the map i i−Δ 2  should not be a quasi-automorphism of C, for otherwise, for all s, there exist s′εF q   k  and Δ 3 εF q  such that for all i, [c(s)] 1−Δ     2   =[c(s′)] i −Δ 3 , that is, [c(s′)] i+Δ     2   =[c(s)] i +Δ 3 .       

     The construction of the AMD codes according to embodiments of the current disclosure may also be described as follows. The algebraic-geometry codes C L  (P 1 + . . . +P n , m d  Q) (as defined, e.g., in Definition II.2.1, p. 42-43 of H. Stichtenoth,  Algebraic Function Fields and Codes , Springer Universitext, 1993, the contents of which are herein incorporated by reference in their entirety) are useful because these codes have a large minimum Hamming distance. However, without some changes, these codes do not meet conditions 1 and 2 above. So, to meet condition 1, use a subcode spanned by non-constant functions: starting with the basis {1, b 1 , . . . , b d } of L(m d Q), keep only the non-constant functions {b 1 , . . . , b d }. To meet condition 2, use an appropriate coset, C: the coset containing the evaluation of x [r(d)] . 
     True AMD Codes from the Hermitian Function Field 
     For a square prime power q, a Hermitian function field H/F q  is defined as H=F q (x, y) with x transcendental over F q  and with x and y satisfying y √q +y=x √q+1 . There i+y is only one Hermitian function field over F q , up to isomorphism. The Hermitian function field has q√q+1 places of degree one: the common pole Q of x and y, and for each (α, β) εF q ×F q  with β √q +β=α √q+1 , there is a unique place P α,β  of H of degree one such that x(P α,β )=α and y(P α,β )=β. Also, v Q (x)=−√{square root over (q)}, v Q (y)=−(√{square root over (q)}+1), and for all mεN, the set
 
{ x   i   y   j   |i≧ 0,0≦ j≦√q− 1, i√q+j ( √{square root over (q)}+ 1)≦ m} 
 
is a basis for L(mQ). Hence, the set (semigroup) {i√q+j(√q+1)|i≧0, 0≦j≦√q−1} of pole numbers of Q can be described as a set of non-negative integers r with └r/√{square root over (q)}┘≧r mod √q (write i√q+j(√q+1)=(i+j)√q+j)). So: 0, (√q,√q+1), (2√q, 2√q+1, 2√q+2), . . . . The genus of H/F q  is g=√q(√q−1)/2.
 
     Define
 
 :={(α,β)ε F   q   ×F   g |β √q +β=α √q+1 }
 
for a Hermitian curve over F q .
 
     The automorphism group Aut ΣP     α,γ     ,Q  is generated by automorphisms {τ ε } εεF     q     *  and   defined by
 
τ ε ( x )=ε x  and τ ε ( y )=ε √q+1   y  for all εεF q *,
 
and
 
σ δ,μ ( x )= x +δ and σ δ,μ ( y )= y+δ   √q   x +μ, for all (δ,μ)␣ .
 
     For a construction according to an embodiments of the disclosure, take all places of degree one other than Q as the P i , so that n=q√q. Note that   can be thought as an index set for the places P α,β  of degree one, replacing the previous index set I. 
     In addition, take the subgroup Φ⊂Aut ΣP     α,β     ,Q  to be the subgroup generated by all the σ δ,μ (x) with δ=0. It can be verified that the composition of two permutations of the form σ 0,μ  is again of the form σ 0,μ , and therefore Φ includes all √q permutations x x, y y+μ with μ √q +μ=0, so that Φ is just the Galois group of H/F q (x). Note that in characteristic 2, μ √{square root over (q)} +μ=0 if and only if μεF √{square root over (q)} . 
     To continue, the following issues should be considered. 
     1. For all d, determine r(d) and e(d), and explicitly describe x [r(d)] . 
     2. Move from pre-AMD codes to AMD codes, which provide protection against all additive manipulations on the index part i. 
     The next proposition and its corollary address the first point. 
     Proposition 2. Let jε{ 1 , . . . , √q−1}, and suppose that p:=char(F q ) does not divide j. Then for all integers i≧0 and for all σεΦ, σ≠id, one has
 
− v   Q (σ( x   i   y   j )− x   i   y   j )=− v   Q ( x   i   y   j )−√ q− 1.
 
Proof. For μ≠0 with μ √q =0, the action of a general automorphism σ 0,μ εΦ, σ 0,μ ≠id, on x i y j  is described by
 
                       σ     0   ,   μ       ⁡     (       x   i     ⁢     y   j       )       =       ⁢         x   i     ⁡     (     y   +   μ     )       j                 =       ⁢       x   u     ⁢       ∑     a   =   0     j     ⁢       (         j           a         )     ⁢     y   a     ⁢     μ     j   -   a                         =       ⁢         x   i     ⁡     (       y   j     +     j   ⁢           ⁢   μ   ⁢           ⁢     y     j   -   1         +     lower   ⁢           ⁢   order   ⁢           ⁢   terms       )       .                 
Subtracting x i y j , one gets jμx i y k−1 +lower order terms. Since j, μ≠0 by assumption, the proof is complete by the strict triangle inequality. ▪
 
Corollary 3. Let d N*, and write m d =i*√q+j*(√q+1) for i*≧0 and for 0≦j*≦√q−1. Then,
 
     1. If p j*, define i(d):=i*+2 and j(d):=j*, so that −v Q (x i(d) y i(d) )=m d +2√q. Then, by Proposition 2, for all σεΦ, σ≠id, one has
 
− v   Q (σ( x   i(d)   y   i(d) )− x   i(d)   y   j(d) )= m   d +2√ q−√q− 1= m   d   +√q− 1.
 
By definition, the last number is some pole number m e′(d) , with d+1≦e′(d)≦d+√q−1. Then the results of Theorem 1 will hold if x [r(d)]  is replaced by x i(d) y j(d)  and e(d) is replaced by e′(d).
 
     2. If p|j*, so that j*≠√q−1, take i(d):=i*+1 and j(d)=j*+1, so that p j(d). It then follows from Proposition 2 that for all σεΦ, σ≠=id, one has
 
− v   Q (σ( x   i(d)   y   j(d) )− x   i(d)   y   j(d) )= m   d 2√ q+ 1−√ q− 1= m   d   +√q.  
 
Again, the last number is some pole number m e′ (d), now with d+1≦e′(d)≦d+√q, and the results of Theorem 1 hold if x [r(d)]  is replaced by x i(d) )y j(d)  and e(d) is replaced by e′(d).
 
     So, in any case, the bound on the miss probability in Theorem 1 holds if m e  is replaced by m d +√q or e(d) by d+√q. 
     The second issue concerns modifying the pre-AMD codes of the previous section to become true AMD codes. According to an embodiment of the disclosure, this issue can be handled in the following way. Given the information sεF q   d , draw some (α,β)ε and map s to (s, (α,β),f s (P α,β )). The resulting code may be known as C d   H . 
     At a first glance, a Hermitian encoding procedure according to an embodiment of the disclosure looks like an encoding according to an embodiment of the disclosure from the previous section, but there is a subtle difference: Instead of using a minimum required log(| |)=log(q√q) bits for storing the index from  , a full pair (α, β) is used, requiring log(q 2 ) bits. This extra redundancy moves from a pre-AMD code to an AMD code according to an embodiment of the disclosure. 
     According to an embodiment of the invention, the decoding can work as follows: For a vector r:=({tilde over (s)}({tilde over (α)},{tilde over (β)}),γ)εF q   d ×F q   2 ×F q  to be checked, the following two steps may be performed: 
     Curve Test Step: Check whether ({tilde over (α)}, {tilde over (β)})ε , that is, check whether β √q +{tilde over (β)}={tilde over (α)} √{square root over (q)}+1 . If ({tilde over (α)}, {tilde over (β)})∉ , declare that the vector r is illegal, meaning an adversary modified the original stored value. Otherwise, continue to the following step. 
     Error Detection Step: Check whether f {tilde over (s)} (P {tilde over (α)},{tilde over (β)} )=γ, that is, check whether substituting ({tilde over (α)},{tilde over (β)}) in x i(d) y j(d) +Σ k {tilde over (s)} k b k  gives γ, where the b k  are of the form x i     k   y j     k    for appropriately chosen pairs (i k , j k ), to be described below. If not, declare that r is illegal. Otherwise, declare that r is legal, that is, that an adversary did not modify the original stored value. 
     Before proceeding, the action of Aut ΣP     α,β     ,Q  on the places {P α,β } will be described. There exists a matrix MεGL 2 (F q ) and a vector bεF q   2  such that 
                     (           σ   ⁡     (   x   )                 σ   ⁡     (   y   )             )     =       M   ⁡     (         x           y         )       +     b   .               (   3   )               
It is desired to find a ({tilde over (α)},{tilde over (β)})ε  such that σ −1 P α,β =P {tilde over (α)},{tilde over (β)} . Such {tilde over (α)}, {tilde over (β)} exist by the definition of Aut ΣP     α,β     ,Q . Recalling the relation τ(z)(τP)=z(P) for z with v P (z)≧0, where P is a place of degree 1, and reducing both sides of EQ. (3) modulo P α,β , one gets
 
                     (             σ   ⁡     (   x   )       ⁢     (     σ   ⁡     (       σ     -   1       ⁢     P     α   ,   β         )       )                   σ   ⁡     (   y   )       ⁢     (     σ   ⁡     (       σ     -   1       ⁢     P     α   ,   β         )       )             )     =       (           x   ⁡     (       σ     -   1       ⁢     P     α   ,   β         )                 y   ⁡     (       σ     -   1       ⁢     P     α   ,   β         )             )     =       (           α   ~               β   ~           )     =       M   ⁡     (         α           β         )       +     b   .                   (   4   )               
This means that the affine functions that take (x, y) to (σ(x), σ(y)) may also be used to take (α,β) to ({tilde over (α)},{tilde over (β)}):
 
{tilde over (α)}=εα+δ,{tilde over (β)}=ε √{square root over (q)}+1 β+ε √{square root over (q)} α+μ.
 
     As described above, the encoding of C d   H  appends to an arbitrary message sεF q   d  a random redundancy part in F q   2 ×F q . 
     Theorem 4: For any replacement of the message part and for any additive error on the redundancy part of the output of the encoder of C d   H , the probability δ of miss-detecting the error is bounded by 
             δ   ≤     max   ⁢       {       1     q       ,       d     q   ⁢     q         +     1     2   ⁢     q         +     1     2   ⁢   q           }     .             
In particular, the code C d   H  is a (q d , q d+3 , δ)-AMD code over F q , with
 
             δ   ≤     max   ⁢       {       1     q       ,       d     q   ⁢     q         +     1     2   ⁢     q         +     1     2   ⁢   q           }     .             
In particular, if d≧g=q/2−√q/2, then
 
             δ   ≤       d     q   ⁢     q         +     1     2   ⁢     q         +       1     2   ⁢   q       .             
Proof: The encoded word is of the form (s, (α,β), f s (P α,β )), where sεF q   d  is the information, and (α,β) is drawn uniformly from  . Suppose an adversary transforms this encoded word into the corrupted word r:=(s′, (α+Δ 1 , β+Δ 2 ),f s (P α,β )+Δ 3 ) for some s′εF q , s′≠s, and some Δ 1 , Δ 2 , Δ 3 εF q . Two cases may be distinguished.
 
     Case 1: Δ 1 ≠0. In this case, the probability that r passes the Curve Test Step is exactly 1/√q. To show this, show that for all Δ 1 , Δ 2 εF q  with Δ 1 ≠0, 
                          {         (     α   ,   β     )     ∈     ❘       (       α   +     Δ   1       ,     β   +     Δ   2         )     ∈       }          =     q   =       n     q       .               (   5   )               
For all (α,β)ε , one has
 
                           ⁢           (     β   +     Δ   2       )       √   q       +     (     β   +     Δ   2       )       =       (     α   +     Δ   1       )         √   q     +   1                 (   6   )                 ⇔       β     √   q       +     Δ   2     √   q       +   β   +     Δ   2         =         (       α     √   q       +     Δ   1     √   q         )     ⁢     (     α   +     Δ   1       )       =           α       √   q     +   1       +       α     √   q       ⁢     Δ   1       +       Δ   1     √   q       ⁢   α     +     Δ   1       √   q     +   1         ⁢     
     ⁢           ⇔       Δ   2     √   q       +     Δ   2         =         α     √   q       ⁢     Δ   1       +       Δ   1     √   q       ⁢   α     +       Δ   1       √   q     +   1       .                   (   7   )               
Now, the last equation can be written as
 
 Tr (Δ 1   √q α)= Tr (Δ 2 )− N (Δ 1 ),   (8)
 
where
 
             Tr   =       Tr       F   q     /     F     q           =     (     a   ↦       a     √   q       +   a       )             
is the trace map and
 
             N   =       N       F   q     ⁢     /     ⁢     F     q           =     (     a   ↦     a     I   +     √   q           )             
is the norm map. Since the trace is an onto F √q -linear map F q →F √q , there are exactly √q choices for Δ 1   √q  α for which EQ. (8) is satisfied. Since Δ 1 ≠0, this means that there are √q values of a satisfying EQ. (8). For each of these choices of α, all √q choices of βεF q  for which Tr(β)=N(α) can be used in a pair (α, β) satisfying EQ. (6), as there is no constraint on β in EQ. (7).
 
     Thus, there are q pairs (α,β)ε  that are shifted by (Δ 1 , Δ 2 ) to another point of  , as desired. 
     Case 2: Δ 1 =0. Substituting Δ 1 =0 in EQ. (7), one obtains
 
∀(α,β)ε :(α+0,β+Δ 2 )ε (0,Δ 2 )ε .
 
This means that if (0, Δ 2 )∉ , then the miss probability is 0, since the Curve Test Step will not pass for all choices of (α,β)ε . Otherwise, if (0, Δ 2 )ε , then an adversary is in fact applying an automorphism from Φ on the places of degree 1, and therefore the bound δ≦(e(d)+g/n) from Theorem 1 may be used. Substituting e(d)≦d+√q (Corollary 3) completes the proof. ▪
 
     EXAMPLE 
     Suppose one would like to protect u=2 20  information bits with a miss probability of no more than 2 −κ  for κ=10. That is, the miss probability should not exceed about 10 −3 . The code of Cramer et al. requires working in F 2     26    and using 52 bits of redundancy on top of the 2 20  information bits. 
     The parameters of a code C d   H  according to an embodiment of the disclosure can now be found. Writing q=2 m  for m even, the requirements are: 
     1. Information size: and md≧u=2 20    
     2. Probability of miss:
         (a) ½ m/2 ≦2 −κ =2 −10      (b) d/2 3m/2 +½ m/2+1 +½ m+1 ≦2 −κ =2 −10  
 
An exemplary, non-limiting value for a smallest possible m that satisfies condition 2(a) is m=20. Now condition 2(b) becomes d/2 30 +½ 11 +½ 21 ≦2 −10 , that is, d/2 30 ≦2 −11 −2 −21 . Combining with condition 1, one gets
       

     
       
         
           
             
               
                 
                   
                     
                       4 
                       5 
                     
                     ⁢ 
                     
                       2 
                       16 
                     
                   
                   = 
                   
                     
                       
                         2 
                         20 
                       
                       20 
                     
                     ≤ 
                     d 
                     ≤ 
                     
                       
                         2 
                         19 
                       
                       - 
                       
                         
                           2 
                           9 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     The minimum d satisfying EQ. (9) is d=┌2 20 /20┐=52429. So, for the choice of m=2 20  and d=52429, all conditions are satisfied, and so one may get a code with the required parameters using 3 m=60 bits of redundancy while working in the field F 2     20   . 
       FIG. 5  is a table of comparisons of the AMD codes of Cramer, et al., and of AMD Hermitian codes according to an embodiment of the disclosure. The triples in the last two columns are of the form (required finite field, number of redundancy bits, value of d). 
     Hermitian AMD Code Operations 
     A detailed description of the operations for working with Hermitian AMD codes follows below. For simplicity, the case of characteristic 2 will be considered, as the other cases are similar as will be apparent to those of skill in the art. First, a high level description of the offline stages is provided. 
     Offline stage 1: The size q=2 m  for even m of the finite field and the dimension d are calculated based on the number uεN* of bits to be protected and the maximum allowed miss probability, 2 −κ , for κεN. The q and d calculated in this stage satisfy log(q d )≧u, and so one may think of information vectors, originally vectors in F 2   u , as vectors in F q   d . 
     Offline stage 2: Recall that encoding includes drawing a random point from the Hermitian curve   over F q , defined by
 
 ={(α,β)ε F   q   ×F   q |β √q +β=α √q+1 },
 
where m is even, and therefore √q=2 m/2  is an integer. This curve has q√q points, and it is not possible to store the whole curve. In the second offline stage, one stores the appropriate constants needed for efficiently producing the i-th curve point given a random index iε{0, . . . q√q−1}.
 
     Offline stage 3: In later online stages, given the information vector sεF q   d  and a point (α, β)ε , a sum is calculated of the form
 
 f   s (α,β)=α i     d=1   β j     d+1   +Σ k=1   d   s   k α i     k   β j     k      (10)
 
for an appropriate set I={(i k ,j k )} k=1   d+1  of d+1 pairs of integers. The entire set of pairs I may be specified by a relatively small set of integers, and this small set may be calculated and stored in the third offline stage.
 
Detailed Description of Encoding and Decoding
 
Offline Stage 1
 
     As discussed in the example above, the parameters m and d should satisfy the following constraints, where u is the number of information bits to be protected, and the maximum allowed miss probability is 2 −κ : 
     1. Information size: md≧u, that is, d≧u/m. 
     2. Probability of miss:
         (a) ½ m/2 ≦2 −κ , that is, m≧2κ.   (b) d/2 3m/2 +½ m/2+1 +½ m+1 ≦2 −κ , that is, d≦2 3m/2−κ −2 m−1 −2 m/2−1  
 
The above conditions can be summarized as follows:
 
 m≧ 2κ and  u/m≦d≦ 2 3m/2−κ −2 m−1 −2 m/2−1    (11)
 
Write L(m):=u/m and U(m):=2 3m/2−κ −2 m−1 −2 m/2−1 . According to an embodiment of the disclosure, to work in a smallest possible finite field, and for this finite field, to work with a smallest possible d, one can find m and d as follows:
       

     1. Set m:=2κ. 
     2. If ┌L(m)▴≦U(m), set d:=┌L(m)┐ and output m and d. Otherwise, increase m by 2, since m is even, and repeat this step. 
     Note that an algorithm according to an embodiment of the disclosure will halt after a finite number of steps, because U(m) increases exponentially with m and L(m) decreases with m. 
     Offline Stage 2 
     In this stage, enough information is stored to support an efficient online mapping of a pair (a, b) of integers aε{0, . . . , q−1} and bε{0, . . . √q−1} to a point of  . More precisely, one would like to store enough constants to support an efficient online computation of a bijection {0, . . . , q−1}×{0, . . . √q−1}→ . 
     Recall that   includes all pairs (α, β)εF q ×F q  that satisfy β √q +β=α √q+1 . Now, because β β √q +β is a surjective (onto) F √q -linear map F q →F √q , which is the trace map, and because α √q+1 εF √q  for all αεF q , for each fixed αεF q  there are exactly √q choices of βεF q  such that (α, β)ε . Moreover, if a single β*εF q  is found such that (α, β*)ε  for a fixed α, then the set of all β fitting α is β*+F √q , because the kernel of the above trace map in characteristic 2 is F √q . 
     Now, it can be verified by substitution that if zεF q  is an element of unit trace, that is, z √q +z=1, then a possible choice for β* is β*=β*(α)=α √q+1 z. So, in a current offline stage according to an embodiment of the disclosure, the following constants will be stored:
         Some fixed primitive element γ 1  of F q  and some fixed element γ 2 εF q  which is a primitive element of F √q   ⊂ F q . Note that given γ 1 , one may take γ 2 :=γ 1   √q+1 .   Some fixed element zεF q  of unit trace. This may be found by scanning γ 1 , γ 1   2 , . . . , until an element of unit trace is found.       

     For future reference, a bijection h: {0, . . . q−1}×{0, . . . , √q−1}→  according to an embodiment of the disclosure may be described as follows: 
     First, for a ε{0, . . . , q−1}, define 
               u   a     :=     {           0             if   ⁢           ⁢   a     =   0     ,               γ   1     a   -   1           otherwise         ,             
so that F q ={u 0 , . . . , u q−1 }. Similarly, for bε{0, . . . , √q−1}, define
 
               V   b     :=     {           0             if   ⁢           ⁢   b     =   0     ,               γ   2     b   -   1           otherwise         ,             
so that F √q ={v 0 , . . . , v √q−1 }. Now a bijection h according to an embodiment of the disclosure is given by
 
 h ( a,b )=( u   a   ,u   a   √q+1   z+v   b ),   (12)
 
where β*(u a )=u a   √q+1 z.
 
Offline Stage 3
 
     In this stage enough information is stored to reproduce the exponentials for calculating EQ. (10). For this, one first finds the (d+1)-th pole number, m d , of the place Q defined above. Here, the set W of pole numbers, which is a Weierstrass semigroup of the place Q, is {i√q+j(√q+1)|i≧0, 0≦j≦√g−1}. Writing an integer of the form i√q+j(√q+1) as (i+j)√q+j, it may be seen that W is the set of integers k with └k/√{square root over (q)}┘≧k mod √q:
 
0,(√ q,√q+ 1),(2√ q, 2√+1,2√ q+ 2), . . . .
 
Note that starting from (√q−1)√q, there are no gaps. So, m 0 =0, m 1 =√q, etc.
 
     Recalling that genus g=(√q−1)√q/2, note that starting from 2g, there are no gaps, while in the range 0, . . . , 2g−1, there are exactly g gaps and g pole numbers. This follows from the general Weierstrass Gap Theorem, or, for the current Hermitian case, by noting that the number of pole numbers is 1+2+ . . . +(√q−1)=g. 
     This means that if d≧g, then the (d+1)-th pole number m d  is given by m d =2g+(d−g)=d+g, because starting from m g =2g, each number is a pole number. Writing d+g=a√q+j* for integer a≧0 (actually, a≧√q−1 in this case) and 0≦j*≦√q−1, then m d =i*√q+j*(√q+1) for i*:=a−j*≧0. 
     Now, if dε{0, . . . , g−1}, one needs to find in which “chunk” m d  sits. For this, a largest positive integer l may be found such that 1+2+ . . . +l≦d+1, that is, such that 
     
       
         
           
             
               
                 
                   
                     
                       l 
                       × 
                       
                         ( 
                         
                           l 
                           + 
                           1 
                         
                         ) 
                       
                     
                     2 
                   
                   ≤ 
                   
                     d 
                     + 
                     1. 
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     Write l* for the maximal such l, which may be found by solving a quadratic equation. If l* satisfies EQ. (13) with equality, then m d =(l*−1)√q+l*−1=i*√q+j*(√q+1) for i*=0 and j*=l*−1. Otherwise, setting j*:=d−l*(l*+1)/2ε{0, . . . , l*≦√q−2} and i*=l*−j*≧0, then m d =i*√q+j*(√q+1). 
     The set of exponents I 1 :={i k ,j k )} k=1   d  for the rightmost sum of EQ. (10) is the set of all pairs (i, j)εN×N corresponding to all pole numbers m 1 , m 2 , . . . , m d , where m 0  is excluded, that is, the set of all pairs (i, j)εN×N with j≦√q−1 such that some pole number m a  with 1≦a≦d can be written as i√q+j(√q+1). Thus, according to an embodiment of the disclosure,
 
 I   1 ={( i,j )ε N×N|i+j&lt;i*+j*  and  j≦√{square root over (q)}− 1} 520  {( i,j )ε N×N|i+j=i*+j*  and  j≦j*} 
 
Graphically, in the ij plane, I 1  comprises diagonal lines of slope −45 degrees with a constant sum i+j bounded from the left by the vertical line i=0, from above by the line j=√q−1, and from below by the line j=0. On the rightmost diagonal line that corresponds to i+j=i*+j*, typically only a subset of the points are included, defined by the upper limit j ≦j*, while all other lines are only restricted by the vertical line i=0 from the left and the horizontal lines j=0 and j=√q−1 from below and from above, respectively. According to an embodiment of the disclosure, for defining I 1 , it is enough to store i* and j*, assuming that √q is known.
 
     Until this point only the rightmost sum in EQ. (10) has been considered. It remains to consider the pair of exponents (i d+1 , j d+1 ) appearing in the right-hand side of EQ. (10). Note that this pair does not necessarily correspond to m d+1 . Using Corollary 3, above, (i d+1 , j d+1 ) can be calculated as follows: 
     
       
         
           
             
               ( 
               
                 
                   i 
                   
                     d 
                     + 
                     1 
                   
                 
                 , 
                 
                   j 
                   
                     d 
                     + 
                     1 
                   
                 
               
               ) 
             
             := 
             
               { 
               
                 
                   
                     
                       ( 
                       
                         
                           
                             i 
                             * 
                           
                           + 
                           2 
                         
                         , 
                         
                           j 
                           * 
                         
                       
                       ) 
                     
                   
                   
                     
                       
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                       ∤ 
                       
                         j 
                         * 
                       
                     
                   
                 
                 
                   
                     
                       ( 
                       
                         
                           
                             i 
                             * 
                           
                           + 
                           1 
                         
                         , 
                         
                           
                             j 
                             * 
                           
                           + 
                           1 
                         
                       
                       ) 
                     
                   
                   
                     
                       
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                       ∣ 
                       
                         j 
                         * 
                       
                     
                   
                 
               
             
           
         
       
     
     Note that in the second case, j* is strictly smaller than √q−1. The calculated pair (i d+1 , j d+1 ) may be stored. 
     Encoding (Online) 
       FIG. 6A  is a flowchart of a method for encoding data using AMD Hermitian codes, according to an embodiment of the disclosure. Referring now to the figure, given an information vector sεF q   d  received at step  50 , the following steps may be performed: 
     Step  61 : For drawing a random point P from  , draw two integers aε{0, . . . , q−1} and bε{0, . . . , √q−1}. Equivalently, draw a single integer from {0, . . . q√q−1} and perform the appropriate mod and floor operations. 
     Step  62 : Use the stored information from Offline Stage 2 to find a corresponding point (α, β)ε  using EQ. (12). 
     Step  63 : Calculate the sum f s (α, β) from EQ. (10), using the information from Offline Stage 3 for producing the appropriate power pairs (i k , j k ). 
     Step  64 : Output as the encoded word the triple (s, (α, β), f s (α, β)). 
     Decoding (Check for Errors Online) 
       FIG. 6B  is a flowchart of a method for decoding data using AMD Hermitian codes, according to an embodiment of the disclosure. Referring now to the figure, given a triple (s′, (α′, β′), γ)εF q   d ×F q   2 ×F q  received at step  65 , perform the following two steps:
         Step  66 : (Curve Test Step) Check whether β′ √q +β′=α′ √q+1 . If not, an error may be declared at step  58 . Otherwise, proceed to a next step.   Step  67 : (Error Detection Step) Calculate the sum f s′ (α′,β′) from EQ. (10), again, using the information from Offline Stage 3 for producing power pairs (i k , j k ). If f s′ (α′; β′)≠γ′, an error may be declared at step  68 . Otherwise, at step  69 , declare that no error was injected in s′.
 
External Protection Against Fault Injections
       

     As an example, consider an AES encryption block that works per sectors of 2 15  bits. The encryption block divides the sector internally into chunks of 128 bits and performs encryption, and the encrypted output is released sector-by-sector. In a side channel attack, an adversary injects errors during the encryption process and uses the faulty outputs to retrieve the secret key. Protecting internal AES blocks is relatively simple, except that fault can be injected between checks. For example, if check i checks the i-th round of AES, in which parity is calculated before the round and then checked after the round, then fault can be injected between the parity check of round i and the parity calculation of round i+1. On the other hand, error injection can be checked externally, in the sector level. If a fault is injected before the parity calculation, then the wrong data will be encrypted, but there will be no faulty states during encryption, so that the secret key cannot be retrieved. In such an application, it is reasonable to allow a rather modest miss probability of about 0.1-1% on the entire sector, especially since it is possible to disable encryption if a pre-defined number of faults, or a pre-defined fault rate, is detected. 
     One solution is to decrypt the encrypted sector and compare it to the input plaintext. The encrypted sector is revealed only if the plaintext=decrypt(encrypt(plaintext)). This probably has a very low miss probability, but requires storing the entire plaintext sector for comparison. 
     However, a solution with reduced storage is to use an embodiment of the disclosure to perform error detection with AMD codes. The redundancy bits of the Hermitian AMD code are calculated for the plaintext sector, and only the redundancy bits are stored, which is typically a couple of tens of bits. Then, encrypt, decrypt, and AMD-check the following vector: [decrypt(encrypt(plaintext)), redundancy bits]. 
     System Implementations 
     It is to be understood that embodiments of the present disclosure can be implemented in various forms of hardware, software, firmware, special purpose processes, or a combination thereof. In one embodiment, the present disclosure can be implemented in hardware as an application-specific integrated circuit (ASIC), or as a field programmable gate array (FPGA). In another embodiment, the present disclosure can be implemented in software as an application program tangible embodied on a computer readable program storage device. The application program can be uploaded to, and executed by, a machine comprising any suitable architecture. 
       FIG. 7  is a block diagram of a system for the use of algebraic curves to reduce complexity and the required field size of AMD error detection codes with a block cipher code, according to an embodiment of the disclosure. Referring now to  FIG. 7 , a computer system  71  for implementing the present invention can comprise, inter alia, a central processing unit (CPU)  72 , a memory  73  and an input/output (I/O) interface  74 . The computer system  71  is generally coupled through the I/O interface  74  to a display  75  and various input devices  76  such as a mouse and a keyboard. The support circuits can include circuits such as cache, power supplies, clock circuits, and a communication bus. The memory  73  can include random access memory (RAM), read only memory (ROM), disk drive, tape drive, etc., or a combinations thereof. The present disclosure can be implemented as a routine  77  that is stored in memory  73  and executed by the CPU  72  to process the signal from the signal source  78 . As such, the computer system  71  is a general purpose computer system that becomes a specific purpose computer system when executing the routine  77  of the present invention. Alternatively, as described above, embodiments of the present disclosure can be implemented as an ASIC or FPGA  77  that is in signal communication with the CPU  72  to process the signal from the signal source  78 . 
     The computer system  71  also includes an operating system and micro instruction code. The various processes and functions described herein can either be part of the micro instruction code or part of the application program (or combination thereof) which is executed via the operating system. In addition, various other peripheral devices can be connected to the computer platform such as an additional data storage device and a printing device. 
     It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying figures can be implemented in software, the actual connections between the systems components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings of the present invention provided herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention. 
     While the present invention has been described in detail with reference to exemplary embodiments, those skilled in the art will appreciate that various modifications and substitutions can be made thereto without departing from the spirit and scope of the invention as set forth in the appended claims.