Scheme for authentication of at least one prover by a verifier

Claim 2

Method for authenticating a prover by a verifier based on a cryptographic technique using a secret key, a public key and a zero-knowledge protocol, the method comprising the steps of: generating a secret key S for the prover using constrained linear equations; generating a public key P based on said secret key; sending plural messages between the prover and the verifier; and authenticating the prover by the verifier based on said secret key S, said public key P and said plural messages.

Claim 3

Method for authenticating a prover by a verifier based on a cryptographic technique using a secret key, a public key and a zero-knowledge protocol, the method comprising the steps of: a) generating a secret key, including at least one vector S of dimension n having coordinates chosen from a set X, b) generating a matrix M of dimensions m×n whose coefficients are chosen at random from integer values from 0 to d-1, where d is a prime integer close to the square of a number c, c) generating a public key comprising at least one vector P such that P=g(M(S)), where g is a function defined by said set X and a subgroup G of a set of integers (1, 2, . . . d-1) and which associates an element g(x) of G to each coordinate x of the at least one vector P such that x is described uniquely as a product of g(x) and an element k(x) of X; d) generating at least two random vectors by the prover; e) generating plural commitments by applying a cryptographic hash function to functions of S, M and the at least two random numbers; f) exchanging plural messages between the prover and the verifier based on said public key and said secret key; and g) authenticating the prover by the verifier based on said plural messages, said public key and said secret key.

Claim 4

Method for authenticating a prover by a verifier based on a cryptographic technique using a secret key, a public key and a zero-knowledge protocol, the method comprising the steps of: a) generating a secret key, including at least one vector S of dimension n having coordinates chosen from a set X, b) generating a matrix M of dimensions m×n whose coefficients are chosen at random from integer values from 0 to d-1, where d is a prime integer close to the square of a number c, c) generating a public key comprising at least one vector P such that P=g(M(S)), where g is a function defined by said set X and a subgroup G of a set of integers (1, 2, . . . d-1) and which associates an element g(x) of G to each coordinate x of the at least one vector P such that x is described uniquely as a product of g(x) and an element k(x) of X; d) generating at least two random vectors by the prover; e) generating plural commitments by applying a cryptographic hash function to functions of S, M and the at least two random numbers; f) exchanging plural messages between the prover and the verifier based on said public key and said secret key; and g) authenticating the prover by the verifier based on said plural messages, said public key and said secret key.

Claim 5

Method according to claim 2, further comprising the step of repeating steps d-g a number of times to provide a higher level of security.

Claim 6

Method according to claim 2, wherein the step of generating at least two random vectors comprises generating two random vectors U and V, of dimensions m and n, respectively, composed of integers from 0 to d-1 and generating two permutations p and q respectively of m and n elements.

Claim 7

Method according to claim 2, wherein m=n.

Claim 8

Method according to claim 2, wherein d=257 and n=20.

Claim 9

Method according to claim 2, further comprising the step of revealing an identity of the prover by sending a signed public key of the prover to the verifier.

Claim 10

Method according to claim 2, wherein the steps d-g are iterated t times, where t increases with an increasing level of security required, and wherein the step of authenticating the prover by the verifier only succeeds if in comparisons all iterations are successful.

Claim 11

Method according to claim 2, wherein the step of generating plural commitments comprises calculating commitments h1 and h2 based on a hash function H according to: h1=H(p, q, MU+P*V) h2=H(U.p, V.q) wherein P*V designates a term-by-term product, modulo d, of the vectors P and V; wherein the step f) of exchanging plural messages comprises the sub steps of: f)(i) choosing a random number a from 0 to d-1 by the verifier; f)(ii) sending the random number a from the verifier to the prover; f)(iii) calculating, by the prover, plural vectors Y and Z according to: Y=(aS+U).p Z=(aT-V).q, where T=k(M(S)); f)(iv) sending the plural vectors (Y,Z) from the prover to the verifier; f)(v) choosing, by the verifier, a random bit b; f)(vi) sending the random number bit b to the prover; f)(vii) returning a reply r such that if the random bit b=0, then the reply r includes p and q, whereas if the random bit b=1, then the reply r includes vectors U'=S.p and V'=T.q; and f)(viii) receiving the reply r at the verifier from the prover; and wherein the step g) of authenticating the prover by the verifier comprises the sub-steps of: g)(i) calculating, if b=0, vectors Y' and Z' such that (Y').p=Y and (Z').q=Z, and vector M(Y')-P*Z'; g)(ii) comparing, if b=0, if h1=H(p, q, M(Y')-P*Z'); g)(iii) calculating, if b=1, vectors Y-aU' and aV'-Z; g)(iv) comparing, if b=1, if h2=H(Y-aU, aV'-Z) and if the vectors U' and V' contain only elements of X; and g)(v) authenticating the prover if either comparing step g)(ii) or step g)(iv) is true.

Claim 12

Method according to claim 9, wherein k(M(S)) is a vector and is calculated as a function of S by the prover.

Claim 13

Method according to claim 9, wherein k(M(S)) is a vector and is stored in a memory of the prover which is inaccessible to the verifier.

Claim 14

Method according to claim 2, wherein the step of generating plural commitments comprises calculating commitments h1, h2 and h3 based on a hash function H according to: h1=H(p, q, MU+P*V) h2=H(U.p, V.q) h3=H((U+S).p, (V-T).q) where P*V designates a term-by-term product, modulo d, of vectors P and V, and wherein T=k(M(S)); wherein the step f) of exchanging plural messages comprises the sub-steps of: f)(i) choosing a random number b by the verifier such that 0<b<4; f)(ii) sending the random number b to the prover; f)(iii) returning a reply such that: if b=1, then reply r consists of values p, q, U and V, if b=2, then reply r consists of p, q, and vectors U'=(U+S) and V'=(V-T), and if b=3, then reply r consists of the vectors U.p, V.q, U"=(U+S).p and V"=(V-T).q; and f)(iv) receiving the reply r at the verifier from the prover; and wherein the step g) of authenticating the prover by the verifier comprises the sub-steps of: g)(i) calculating, if b=1, values MU+P*V, U.p, and V.q; g)(ii) comparing, if b=1, if h1=H(p, q, MU+P*V) and if h2=H(U.p, V.q); g)(iii) calculating, if b=2, values MU'+P*V', U'.p, and V'.q; g)(iv) comparing, if b=2, if h1=H(p, q, MU'+P*V') and if h3=H(U'.p, V'.q); g)(v) calculating, if b=3, two vectors U"-U.p and V"-V.q; g)(vi) comparing, if b=3, if h2=H(U.p, V.q), if h3=H(U", V") and if vectors U"-U.p and V"-V.q are composed only of elements of X; and g)(vii) authenticating the prover if any of the comparing steps g)(ii), g)(iv) and g)(vi) is true.

Claim 15

Method according to claim 12, wherein k(M(S)) is a vector and is calculated as a function of S by the prover.

Claim 16

Method according to claim 12, wherein k(M(S)) is a vector and is stored in a memory of the prover which is inaccessible to the verifier.