Algebraic manipulation detection codes from algebraic curves

摘要

A method for protecting encoded data from algebraic manipulation includes receiving a data word sεKd 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 Fq that corresponds to the randomly selected integers (a, b) from a mapping (a, b)(α, β)=(ua, ua√q+1z+vb), where;ua:={0if⁢⁢a=0,γ1a-1otherwise,⁢Vb:={0if⁢⁢b=0,γ2b-1otherwise,
and z is an element of the field Fq of unit trace, and where γ1 is a fixed primitive element of the field Fq and γ2 is a primitive element of a field F√q⊂Fq, and calculating a sum fs(α, β)=αid+1βjd+1+Σk=1dαikβkjk for a set of d+1 integers pairs I ={(ik,jk)}k=1d+1, where the encoded word is a triple (s, (α, β),fs(α, β)).

主权项

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 εFqd, at the application specific integrated circuit, from a communications channel to be protected, wherein q is a prime power and Fqd is a vector space over the finite field Fq including vectors (x1, x2, . . . , xd) with xi εFq for all i ε{1, . . . , d}; the application specific integrated circuit fixing a basis {1, b1, . . . , bd} for a Riemann-Roch space L(mdQ) as an Fq-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 Fq and with genus g and md 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, fs(Pi)) εFqd ×In×Fq, wherein fs(Pi) is defined as fs:=x[r(d)]+Σj=1dsjbj, wherein r(d):=min{j|∃x εL(mjQ): ∀σεΦ, σ≠id: σ(x)−x εL(mjQ)|L(mdQ)}, is a subgroup of AutD,Q(F/Fq):={σεAut(F/Fq)|σ(Q)=Q and σ(D)=D}, Aut(F/Fq) is a group of automorphisms of F over Fq, D:=P1+ . . . +Pn wherein Q, P1, . . . , Pn are pairwise distinct places of F/F q of degree 1, and X [r(d)] is an element of L(mr(d)Q) for which σ(x[r(d)])−x[r(d)]εL(meQ)/L(mdQ) 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)}) εFqd×In×Fq 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ĩ).