Algebraic manipulation detection codes from algebraic curves
A method for protecting encoded data from algebraic manipulation includes receiving a data word sεK d to be protected, 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 an element of the field F q of unit trace, and where γ 1 is a fixed primitive element of the field F q and γ 2 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 α i k βk j k for a 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 (α, β)).
1. An application specific integrated circuit tangibly encoding a program of instructions executable by the integrated circuit to perform a method for protecting data from algebraic manipulation, the method comprising the steps of:
receiving a data word s εF q d , at the application specific integrated circuit, from a communications channel 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};
the application specific integrated circuit 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;
the application specific integrated circuit executing instructions for drawing an index i from a set I :={1, . . . , n};
encoding, by the application specific integrated circuit, 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 [r(d)] +Σ j=1 d s j b j , wherein r(d):=min{j|∃x ε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,
protecting the index i against fault injection attack with a weak algebraic manipulation detection (AMD) code, wherein a received triple r:=({tilde over (s)}, ĩ, {tilde over (v)}) εF q d ×I n ×F q is valid iff {tilde over (v)}=f {tilde over (s)} (P ĩ ); and
declaring an error if the received triple r is invalid, wherein
an error is detected in ({tilde over (s)}, ĩ, {tilde over (v)}) by checking the index ĩ, and if the ĩ-check passes, checking whether {tilde over (v)}=f {tilde over (s)} (P ĩ ).
2. The method of claim 1 , wherein the weak AMD code is constructed from a perfect nonlinear function.
3. The method of claim 2 , 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 .
4. The method of claim 1 , further comprising encoding the data word s using a block cipher.
5. The method of claim 4 , wherein the block cipher is selected from a group comprising AES, DES, Triple DES, IDEA, RC5, and Blowfish.
6. An application specific integrated circuit tangibly encoding a program of instructions executable by the integrated circuit to perform a method for protecting encrypted data from algebraic manipulation, the method comprising the steps of:
receiving a data word sεK d , at the application specific integrated circuit, from a communications channel to be protected, wherein K is a finite field of q elements for a square prime power q and a predetermined d;
the application specific integrated circuit randomly selecting two integers a ε{0, . . . , q−1} and b ε{0, . . . , √q−1};
the application specific integrated circuit executing instructions for 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 ), wherein
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 wherein γ 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, by the application specific integrated circuit, 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 ,
outputting, by the application specific integrated circuit, a triple (s, (α, β),f s (α, β)) as an encoded word, wherein said encoded word is protected from side-channel attacks during transmission.
7. The method of claim 6 , wherein said Hermitian curve over F q , is defined by point pairs (α, β) wherein
={(α, β) εF q ×F q |β √q +β=α √q+1 }, wherein √q=2 m/2 is an integer for an even m.
8. The method of claim 6 , further comprising 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, wherein q and d satisfy log(q d )≧u.
9. The method of claim 8 , wherein calculating q and the dimension d comprises:
initializing m=2κ; and
if
⌈
u
m
⌉
≤
2
3
m
/
2
-
κ
-
2
m
-
1
-
2
m
/
2
-
1
,
setting
d
=
⌈
u
m
⌉
,
wherein q=2 m .
10. The method of claim 9 , wherein if
⌈
u
m
⌉
>
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
.
11. The method of claim 6 , wherein γ 2 =γ 1 √q+1 , and z is determined by scanning γ 1 ,γ 1 2 , . . . , until an element of unit trace is found, wherein an element of unit trace z satisfies Z √q +z=1.
12. The method of claim 6 , further comprising finding a (d+1)-th pole number, m d , of a place Q of F/F q of degree 1, wherein a set of pole numbers of place Q is {i√q+j(√q+1)|i≧0, 0≦j≦√q−1},
wherein exponents
I 1 ={( i k ,j k )} k=1 d ={( i,j ) ε N×N|i+j<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
*
.
13. The method of claim 12 , wherein, 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
,
wherein 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.
14. The method of claim 6 , further comprising encoding said data word s using a block cipher.
15. The method of claim 14 , wherein the block cipher is selected from a group comprising AES, DES, Triple DES, IDEA, RC5, and Blowfish.
16. An application specific integrated circuit tangibly encoding a program of instructions executable by the integrated circuit to perform a method for protecting encrypted data from algebraic manipulations, the method comprising the steps of:
receiving a triple (s, (α, β), γ), at the application specific integrated circuit, from a communications channel that is an element of F q d ×F q 2 ×F q , wherein s is an encoded data word, and q and d are predetermined constants;
the application specific integrated circuit decoding the encoded data word using algebraic manipulation detection (AMD) Hermitian codes by determining whether β √q +β=α √q+1 ; and
if β √q +β=α √q+1 , further determining, by the application specific integrated circuit, whether a sum f s (α, β)=γ, wherein
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 ,
wherein if either β √q +β≠α √q+1 or f s (α,β)≠γ, declaring an error, otherwise declaring that no error was injected into s.
17. The method of claim 16 , further comprising 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, wherein q and d satisfy log(q d ) ≧u.