Schnorr protocol

Identification protocol

Identification protocol is different than signature scheme as identification protocol is used to identify that prover holds the private while signature scheme is used to verify that the holder indeed used the private key to sign the message and generate the signature.

Steps followed in schnorr identification protocol:

sequenceDiagram
participant a as Prover
participant b as Verifier
note left of a: (I,st)<-P1(sk)
a->>b:I
note right of b: r<-Random
b->>a:r
note left of a: s=P2(sk,st,r)
a->>b:s
note over b:V(pk,r,s)=I

Properties

• Correctness: Honest Prover should be able to convince a Honest verifier that it knows the secret.
• Soundness: Malicious Prover (doesn’t know secret) shouldn’t be able to convince a Honest verifier with non-negligible probability.
• Non-Degeneracy: there should be enough initial values $I$ or in other words, for a fixed $sk$ and $I$, $\mathrm{Pr}[{\mathcal{P}}_1(sk)\to I]\le \text{negl}(n)$.

Identification Experiment ${\text{Ident}}_{\mathcal{A},\Pi }(n)$:

• $\text{Gen}(1^n)\to (pk,sk)$.
• $\mathcal{A}$ is given $pk$ and given access to a $\text{Trans}(\cdot )$ oracle that can give transcript $(I,r,s)$ of an honest execution of the protocol.
• $\mathcal{A}$ outputs $I$, and is given a uniform $r\leftarrow {\Omega }_{pk}$ to which $\mathcal{A}$ responds with $s$.
• experiment succeeds if $\mathcal{V}(pk,r,s)=I$.

$\mathrm{Pr}[{\text{Ident}}_{\mathcal{A},\Pi }(n)=1]\le \text{negl}(n)$

Not feasible, requires interaction from verifier. Also not publicly verifiable as both parties have to be involved.

FS86 introduced Fiat-Shamir which transforms identification protocols to signatures. Later, it was recognised by PS96 that this can be generalised to any interactive protocol with negligible soundness to turn it into non-interactive protocol.

Prove any signature scheme instantiated from an identification scheme and Fiat-Shamir transcript is secure if underlying identification scheme is secure.

Schnorr Digital Signature

Schnorr’s Identification Scheme $\Pi =(\text{Gen},{\mathcal{P}}_1,{\mathcal{P}}_2,\mathcal{V})$. Let there be two parties $A$ (Prover) and $B$ (Verifier):

1. A runs $\text{Gen}(1^n)\to (pk,sk)$. Let private key be $x$ and public key = $Gx(modN)$
2. Generates random value using ${\mathcal{P}}_1$, $Y=Gy(modN)$
3. $Y$ is sent to B
4. B generates random challenge $c$, and send to A
5. A sends back: $z=y+xc$
6. B verifies: $z.G=y.G+c.x.G=Y+c.PK$

Security of Schnorr’s identification scheme depends on Discrete Logarithm Problem. So, if an adversary is able to forge a signature, it can also break DLP.

Passive adversarial approach doesn't work, i.e. access to honest transcript is of no use. Why?

Used to implement ==Proof of Knowledge==. Used in cryptography to prove to verifier that prover knows some value $x$. Verifier gets convinced that they are communicating with the prover without verifier’s knowledge of private key and prover is in fact, right about his private key.

Features:

1. faster than ECDSA as doesn’t have to calculate $1/s$
2. linear

But this also proposes other disadvantages that this signature scheme can’t be used for aggregation and multi-sigs due to its linearity.

Non-interactive Schnorr identification protocol also exists using Fiat-Shamir transformation where challenge $c$ is not generated by verifier but $c=H(g,q,h,u)$ where g: generator, q: prime number, h: public key, u: public key of random nonce

Proving Schnorr Signatures Are Zero-knowledge

Proving completeness is the easiest part in protocol, i.e. if the prover performs protocol honestly, verifier is able to verify it by just substituting g in schnorr signatures.

Soundness is done through another algorithm called extractor which is able to extract secret of the prover by tricking it. Note: it doesn’t actually reveal the secret but only proving that extractor can extract the secret by duping prover. Done through replay attack on schnorr protocol.

Construct an algorithm ${\mathcal{A}}^{\prime }$ running $\mathcal{A}$ attacking Identification scheme $\Pi$ as subroutine.

• Answers $\text{Trans}$ queries of $\mathcal{A}$ uniformly.
• $\mathcal{A}$ outputs $I$. ${\mathcal{A}}^{\prime }$ chooses $r_1$ uniformly, sends to $\mathcal{A}$ which outputs $s_1$.
• Rewinds $\mathcal{A}$ to challenge generation point with same randomness. Returns $r_2$ and gets $s_2$ as response from $\mathcal{A}$.
• if $r_1\ne r_2$ and $g^{s_1}\cdot h^{-r_1}=I=g^{s_2}\cdot h^{-r_2}$, then calculates secret key as $[(s_1-s_2)\cdot (r_1-r_2{)}^{-1}\mathrm{mod}q]$. Reason why Probability is negligible.

Zero-Knowledgness is proven through a simulator which has no knowledge of the the secret and yet it is able to convince every verifier into believing that the statement is true. This has an assumption that verifier is honest, i.e. HVZK. Done through rewinding a verifier so that prover knows challenge $c$ and forging false signature on the basis of it.

references

• Schnorr’s identification protocol
• Introduction to Schnorr Signatures
• CS355: Lecture 5