Preliminary

4.1 Preliminary

The trusted authority determines three polynomials C(x),D(x) and E(x) over prime finite field F_q for the readers, where

C(x)	= c₁x + c₀	(1)
D(x)	= d₁x + d₀	(2)
E(x)	= e₂x² + e₁x + e₀	(3)

Then, the trusted authority chooses universal polynomials A(x,y) and B(x,y) over the same prime finite field F_q for every tags, where

A(x,y)	= a_1,1xy + a_1,0x + a_0,1y + a_0,0	(4)
B(x,y)	= b_1,1xy + b_1,0x + b_0,1y + b_0,0	(5)

, such that

A(x,y) ⋅ C(x) + B(x,y) ⋅ D(x) = E(x)

(6)

In order to satisfy the previous equation 6, the equalities in the following linear system need to hold:

a_1,1c₁ + b_1,1d₁	= 0	(7)
a_1,1c₀ + a_0,1c₁ + b_1,1d₀ + b_0,1d₁	= 0	(8)
a_0,1c₀ + b_0,1d₀	= 0	(9)
a_1,0c₁ + b_1,0d₁ - e₂	= 0	(10)
a_1,0c₀ + a_0,0c₁ + b_1,0d₀ + b_0,0d₁ - e₁	= 0	(11)
a_0,0c₀ + b_0,0d₀ - e₀	= 0	(12)

C(x),D(x) and E(x) are remains the same value when they are preloaded on to a reader, i.e., c₁,c₀,d₁,d₀,e₂,e₁,e₀ have been predetermined. Therefore, the authority can always find A(x,y) and B(x,y) to satisfy equation 6, since equations 7 through 12 become a linear equation system regarding unknown coefficients of A(x,y) and B(x,y). The number of unknowns, i.e., 8 unknown variables, is greater than the number of equations, i.e., 6 equations. Thus, it is infeasible for a naive attacker to break this linear equation system.

4.1.1 Hash

A hash function h is an one-way function that maps an arbitrary length input to a k-bit output, i.e. h : {0,1}^*→{0,1}^k. The typical requirement for this cryptographic checksum functions are

Pre-image resistance: for any given input x, it is computationally efficient to compute h(x). However, given an arbitrary output y, it is computationally infeasible to find an input such that h(x) = y.
2nd pre-image resistance: given x, it is computationally infeasible to find x′≠x, such that h(x) = h(x′)
Collision resistance: it is computationally infeasible to find any pair of distinct inputs x and x’, such that h(x) = h(x′)

4.1.2 Symbols and Notations

The bolded symbols are distinctly chosen in random for each session, e.g., γ2,λ. The specifically underlined parameter are transmitted from the user side, for instance, A(x,u). A good example of combination would be A(γ2,u), which represents a user function that need to feed an input at different session.

A function with a hat means it is a elliptic curve point multiplied with output of the function. An example of this would be Ĉ(x) = α×C(x), where α is an elliptic curve point.

[next] [front] [up]