Schnorr identification

The Schnorr identification is a 1989/91 by the German Mathematics Professor Claus-Peter Schnorr designed cryptographic identification scheme. The security relies on the complexity of the discrete logarithm in finite groups. The Schnorr signature is derived from the Schnorr identification in that, as with the Fiat Shamir identification, the interaction is replaced by the use of a cryptographic hash function . The process was patented by Schnorr. It was licensed exclusively to RSA (Siemens has a non-exclusive license). The patent expired on February 23, 2010.

parameter

System-wide parameters

All users can share these parameters:

• A group of prime order . This is cyclical , be a generator. ${\displaystyle G}$ ${\displaystyle q=|G|}$ ${\displaystyle g}$

Schnorr suggests choosing a subgroup of for a prime number . He argues that key and signature lengths refer to, while the security level is oriented towards the larger . ${\displaystyle G}$ ${\displaystyle Z_{p}^{*}}$ ${\displaystyle p}$ ${\displaystyle |G|}$ ${\displaystyle |Z_{p}^{*}|}$

Private key

The private key consists of a randomly chosen number:

• ${\displaystyle x}$ With ${\displaystyle 0<x<q}$

Public key

The public key is the corresponding group element : ${\displaystyle x}$ ${\displaystyle y}$

• ${\displaystyle y=g^{x}}$

Three step protocol

The Prover P identifies itself to the Verifier V using a protocol consisting of 3 steps:

1. Commitment: P chooses at random and sends to V. ${\displaystyle k}$ ${\displaystyle 0<k<q}$ ${\displaystyle r:=g^{k}}$
2. Question (Challenge): V chooses randomly and sends to P. ${\displaystyle e}$ ${\displaystyle 0<e<q}$ ${\displaystyle e}$
3. Response: P sends to V. ${\displaystyle s:=(k+xe)\mod q}$

V accepts the answer if and only if ${\displaystyle g^{s}=ry^{e}}$

Security discussion (informal)

The safety of the Schnorr identification is on the complexity of the discrete logarithm proved to reduce, d. H. whoever breaks the scheme can also efficiently compute the discrete logarithm. However, after decades of intensive research, it is assumed that this problem cannot be solved efficiently. This demonstrable reduction to known problems classified as difficult is typical for public key procedures.

Assuming that there were a successful fraudster - a fraudster who can efficiently determine the secret key from the public key - this fraudster would have to be able to efficiently calculate the discrete logarithm of - contrary to the assumption that discrete logarithm is difficult. ${\displaystyle y=g^{x}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$

1. Simulate the algorithm for identification, save the state before sending the question to the fraudster. ${\displaystyle e_{1}}$
2. Repeat the simulation on the saved state, choose a random one as the question (it is very likely that this is not the same ). ${\displaystyle e_{2}}$ ${\displaystyle 1/q}$ ${\displaystyle e_{1}}$

1. Be and the two (different) answers to the same random value or ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$ ${\displaystyle k}$ ${\displaystyle r}$
2. It is so . The division by is possible because the difference modulo q is not equal to 0 because it is prime, there is also an inverse modulo q. ${\displaystyle s_{1}-s_{2}=(k+xe_{1})-(k+xe_{2})=x(e_{1}-e_{2})\mod q}$ ${\displaystyle x=(s_{1}-s_{2})/(e_{1}-e_{2})\mod q}$ ${\displaystyle e_{1}-e_{2}}$ ${\displaystyle q}$

Individual evidence

1. ↑ Patent EP0384475 : Applied on February 22, 1990 . ‌
2. ↑ Patent US4995082 : Applied February 23, 1990 . ‌