3
$\begingroup$

Let's say there is a public key $v$. Peggy has to prove to Victor that she has the corresponding private key $a$. Of course she doesn't want to disclose $a$ to Victor, but just to prove that she has the key.

Question: What is the benefit of "Solution 2" described below (a.k.a. Fiat-Shamir), which seems more complex and using zero knowledge proofs, when there is an easy solution (see Solution 1)?

Solution 1 (easy):

  • Victor generates a random number $r$, encrypts it with the public key $v$, and sends the encrypted message $r_E$ to Peggy
  • If Peggy has the private key $a$, she can decrypt $r_E$ into $r$, and send $r$ back to Victor and claim: "Hey Victor, here is $r$, this is the proof I can decrypt your message $r_E$, so this proves I have $a$"
  • If Peggy doesn't have the private key $a$, she cannot decrypt $r_E$, so she cannot prove anything.

I don't know the name of this simple scheme, but I think this can be done with nearly any public/private key encryption algorithm, and it seems safe.

Solution 2 (Fiat-Shamir, interactive zero knowledge proof):

  1. $a$ is the private key, $v = a^2 \pmod n$ is the public key
  2. Peggy generates a random number $r$ and sends $x=r^2 \pmod n$ to Victor
  3. Victor sends 0 or 1 (randomly) to Peggy
  4. If Peggy receives 0, she has to send $r$ to Victor (he can then check if $r^2$ is $x$ modulo $n$)

    If Peggy receives 1, she has to send $y = r \times a \pmod n$ to Victor (he can then check if $y^2 \times v^{-1}$ is $x$ modulo $n$)

  5. Repeat from step 2 at least $k$ times: the higher $k$ the smaller the probability ($2^{-k}$) of passing the test succesfully without actually knowing $a$

What is the benefit of complex Solution 2 when you can just do Solution 1?

$\endgroup$
1
$\begingroup$

Digital signatures and authentication/identification schemes are very closed concepts. A major difference is that a digital signature is a proof that can be verified by every one that get it. The proofs in authentication/identification schemes are generally addressed to a target verifier.

One point is that in many applications when Peggy wants prove herself, or do a proof of identity, she can require that an adversary Eve can't be able to copy their interaction and so get some advantage on it. In the challenge-response in solution 1, a malicious Eve can impersonate Victor, i.e., how can Peggy be sure of Victor identity? If Eve captures an answer cheating this way, she can pose as Peggy hereafter.

Solution 2 brought some advances: $2^{k}$ is number of ways Victor can challenge Peggy. So, if Eve copied a previous protocol transcript, $2^{-k}$ is the probability Victor repeat the same challenge set, making the chance of Eve impersonate Peggy harder.

$\endgroup$
  • $\begingroup$ Thank you @McFly. To be sure to understand: do you mean the weakness of Solution 1 is that Eve can ask Victor for the challenge number $r_E$ (encrypted), then pass this number to Peggy (impersonating Victor), get Peggy's decrypted $r$, and then send $r$ to Victor, then Eve will be authentified as Peggy! Is that what you mean? Couldn't Eve do the same with Solution 2? $\endgroup$ – Basj Feb 11 '18 at 21:32
  • 1
    $\begingroup$ she can require that an adversary Eve can't be able to copy their interaction and so get some advantage on it: since Victor sends a new random number each time he's doing a new challenge-response, having a log of previous interaction doesn't help Eve, isn't it right? $\endgroup$ – Basj Feb 11 '18 at 22:17
  • $\begingroup$ About your comment I: imagine if Eve maliciously use Peggy doing oracle access to her decryption functionality: by submit a manageable number of encryption to Peggy and keep all answers in memory. In a future Eve can take advantage of this knowledge, i.e., if Victor challenge question matches some of already answered by Peggy. In solution II Eve isn't able to keep these answers in advance, because the 0/1 interactive challenge mechanism from Victor. $\endgroup$ – McFly Feb 13 '18 at 18:56
  • $\begingroup$ About your comment II: Victor must be aware of what was submitted to Peggy (by anyone, not just by Victor), you see? $\endgroup$ – McFly Feb 13 '18 at 18:57
  • 1
    $\begingroup$ Still not sure to understand ;) In solution 1, if challenge number r is chosen randomly in 1...2^1024, then I don't see how Eve can reuse it later: Victor won't probably reask the same challenge again ever. $\endgroup$ – Basj Feb 13 '18 at 19:05
1
$\begingroup$

Solution 1 has some weakness when the verifier is malicious. If the prover's private key $a$ is used for decryption, Solution 1 provides the verifier with a decryption oracle, i.e., a malicious verifier can decrypt any ciphertext encrypted with the public key $v$. On the other hand, Solution 2 reveals nothing about the private key $a$ because the random number $r$ (which masks the private key $a$ when the verifier sends a bit 1) is chosen by the prover rather than the verifier.

$\endgroup$
0
$\begingroup$

So yes, your solution 1 would work providing use of a one-way encryption scheme. However, this is also a zero-knowledge proof since it obeys completeness, soundness and honest verifier zero knowledge (transcript can be simulated by anyone).

What solution 2 has going for it is that it can be make in to a non-interactive proof and it also obeys special soundness. So yeah, it is more complicated but it gives better guarantees.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your answer. I'm not sure to understand. Solution 2 (Fiat Shamir) is not non-interactive, in fact it's even more interactive than solution 1. Also why does it give better guarantee? $\endgroup$ – Basj Feb 11 '18 at 1:03
  • $\begingroup$ It gives not only "soundness" but "special soundness" guarantee. Yeah, you are right, but it can be easily transformed in to a non-interactive protocol using hashes like in the Fiat–Shamir heuristic. $\endgroup$ – Jackoson Feb 11 '18 at 19:29
  • $\begingroup$ What is difference between soundness and special soundness @N.jackoson? Also, could you add detail about how to transform this Solution 2 into non-interactive? I don't see exactly how it works. $\endgroup$ – Basj Feb 11 '18 at 21:19
  • $\begingroup$ Soundness is that for false statements (lying Peggy) the probability of the verifier (Victor) accepting is very small. Whereas, special soundness is that for a particular value of the first message (x) exists only one response that will be accepted out of all of the possible ones. $\endgroup$ – Jackoson Feb 12 '18 at 11:23
  • $\begingroup$ Turning an interactive protocol into a non interactive one is done by calculating victor's challenge by taking the hash of the statement and initial x value. The prover can do this without the verifiers interaction and then send the whole transcript to the verifier who can verify the whole thing in one go (including checking that the hash was done correctly) $\endgroup$ – Jackoson Feb 12 '18 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.