Tag Info

Hot answers tagged

10

On a general basis, you want to keep encryption and signature keys disjoint, because they tend to have distinct life cycles. In broad terms, an encryption key should be escrowed, because loss of the private key implies loss of the data which is encrypted relatively to the public key. However, a signature key must not be escrowed, since the proof value of a ...


9

Apparently, Schnorr was quite adamant, at that time, about the applicability of his patent to DSS. See this message and that one. These are from 1998, but the controversy had begun earlier; see for instance this bulletin from NIST, from late 1994, where references to it can be found in the "Patent Issues" section. Interestingly, NIST not only tried to avoid ...


6

Despite their theoretical security advantages, Schnorr signatures aren't very popular. Probably because they were patented. Since the patents expired in 2008 they might rise a bit in popularity. But probably only in the elliptic curve form, and not in finite fields. I don't know of any application actually using Schnorr signatures, but I know several that ...


5

This scheme is insecure, as anyone with the public key can generate a forgery of an arbitrary message. To do this, the forger would take the message $M$, the public key $y$, pick an arbitrary $z$, and compute $r = y^{-H(M)} g^{z} \bmod p$ and output $(r,z)$


5

If Alice guesses $e$ then she chooses a random value $x$ and computes $h = g^x v^{-e}$, a value which she sends to Bob at step 1. At step 3, Alice sends $x$. When Bob does step 4, he recomputes $g^x v^{-e}$ and finds $h$, and he is happy. However, Alice does not know $s$. The "commitment" at step 1 is a way for Alice to say: "I know a $r$ corresponding to ...


5

Suppose that we have Eve, that knows what $e$ is going to be, and does not need to know the prover's private key $a$, just the public one $v$. She then sends $g^k \cdot v^{-e}$ as her first "move", where she can choose her own $k$ (you can modify the $k$ in different plays to make it all look nice and random...). The verifier sends $e$ as expected, of ...


5

The paper "On the Joint Security of Encryption and Signature in EMV" shows that ECIES and EC-Schnorr signatures can be used together without compromising security: In the random oracle model ECIES-KEM and EC-Schnorr are jointly secure if the gap-DLP problem and gap-DH problem are both hard Ed25519 is extremely similar to EC-Schnorr, and both ECIES ...


5

In the other answers, you'll find how to simulate a proof if you know $e$. This answer is meant to provide some "color commentary" on the other answers. It is a companion piece. Notation In step 1, Alice sends $g^r$. Call this value $a=g^r$. In step 3, Alice sends $r+se$. Call this value $b=r+se$. In step 1-3, one value is sent in each step: {$a,e,b$}. ...


4

Well, if fake-Alice guesses the challenge exponent $e$ in step 1, then she can guess the value of $v^{-e}$. That means she can pick an arbitrary value to stand in for $r+se$, compute $g^{r+se}v^{-e}$, and send that as her commitment in step 1. Then, assuming Bob sends the guessed exponent in step 1, fake-Alice sends the value $r+se$ that she picked above. ...


3

First of all, while Schnorr Signatures are usually described that way, the two primes are not necessary for it to work. In principle, Schnorr works in any cyclic group. However, to achieve security we need that the discrete logarithm problem in that group is hard. So the reason for the choice of $q$ (which is the group order) is that DL is believed to be ...


3

As noted by Perseids in a comment to this answer, the formula $s = r + c + x$ would allow an adversary (who has completed the protocol once in the role as verifier with $P$ and already got one valid triplet $t_1,c_1,s_1$) to compute responses to any arbitrary challenge, simply using the formulas $t_2 = t_1$, $s_2 = s1 + c_2 - c_1$. Your other alternative $s ...


3

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$). Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it ...


3

Yes, there are some examples of Schnorr signature in real world applications, although I can not provide you the names of the products. (Edit: OpenSSH contains a reference implementation in schnorr.c). The good feature of Schnorr signature is that by design it does not require lot of computations on the signer side. Therefore, you can use it even on a ...


3

Here and in many other signature schemes, $f$ is modeled as a "random oracle." This means that on each distinct input, $f$ outputs a uniformly random value in $\mathbb{Z}_q$ that is independent of all other outputs. (When queried on the same input multiple times, it always returns the same answer.) The trick here is that the simulator has the power to ...


2

A small message space is no problem and I do not really know what you mean by "signature length is very small". However, it is not only a good idea to choose independent and fresh randomness for every signature, it is (as Alex mentioned in his comment) necessary. Otherwise anyone who gets two signatures of you computed with same randomness for different ...


2

Given the definition of a zero-knowledge proof, it must satisfy three properties: Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover. Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, ...


1

Well, the goal of their reductionists proof is to show that if there is an adversary against the signature scheme one is can use this adversary to extract the unknown secret key. Now, if the reduction would already know the secret key from the start this would make no sense. But how should the reduction then answer the signing queries of the adversary ...


1

You have to look at the response from the perspective of the verifier. This specific construction allows him/her to verify the $P$'s knowledge of $x$: If $P$ could answer two different request $c_1,c_2$ in step 2) then we would have $g^{s_1}=ty^{c_1}$ and $g^{s_2}=ty^{c_2}$. Dividing one equation by the other we get $g^{s_1-s_2}=y^{c_1-c_2}$. Let ...



Only top voted, non community-wiki answers of a minimum length are eligible