# Tag Info

## Hot answers tagged schnorr-signature

27

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 ...

25

How to confirm my implementation is constant time? I'm in scala using bouncy castle from Java. This code is not constant time, for no platform is specified. Computing platforms that run in constant time or cycles are the exception. I don't know any device with internet and video currently for sale that does. That's actually contributing to make attacks ...

14

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 ...

14

Your post was a bit confusing to me, I think you're thinking of this from the wrong perspective. Is there a scheme with security arguably equivalent to DSA (or better, the DLP or related), but with the compactness of the original Schnorr signature scheme? Yes, Schnorr signatures. They are really what you should be doing. It is theoretically and ...

13

Here is a simple-minded Ed25519-based multisignature or collective signature scheme, in which Alice and Bob each having their own private key, kept secret from one another, must work together to create a joint signature that a verifier knowing both of their public keys, or only a joint public key, can verify. This is a simplification of a recent IETF ...

11

Strangely, if $e=0$ then no knowledge of $x$ is proven, as all steps can be carried out by someone who knows only $M$. So, why is $e=0$ not disallowed? Because $e = 0$ is not unique in this regard. Every single $e$ is equally "insecure", i.e. you may as well ban $e = 23$ with the same reasoning. To exemplify, assume $e = 23$ arbitrarily (holds for any ...

9

Adding to other answers, I note that both schemes are related to (but clearly different from) those standardized in ISO/IEC 14888-3:2016 (non-functional preview): The BSI's EC-Schnorr original specification was similar to ISO/IEC 14888-3's EC-SDSA-opt, standing for Elliptic Curve Schnorr Digital Signature Algorithm optimized version, except that ...

8

Sigma protocols as-is are secure only for honest verifiers. However, they can be easily compiled into full-blown zero knowledge protocols. If you don't want interaction, then the Fiat-Shamir transform suffices, with security in the random oracle model. With interaction, you can do the transform at little cost using commitments based on DDH. For more ...

8

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 ...

8

Shor's algorithm can compute discrete logs in elliptic curves and thereby recover the secret scalar from a public Ed25519 key, which you can use to forge signatures of your choice. So, yes, it affects Ed25519—it completely breaks Ed25519, or it would if you could engineer a quantum computer capable of executing it. It can also compute discrete logs in ...

8

This would work, but note that your weakening verification (slightly). Instead of only $(C_1,k_2)$ being a valid signature, now also $(-C_1,k_2)$ is valid. If you want to do signatures by only using $x$-coordinates you can use the qDSA signature scheme, which indeed saves a few bits in the signature size and public key. There is actually a more serious ...

8

What (and where) is the actual definition of a Schnorr group? Where have Schnorr groups first been introduced and who called them Schnorr groups? I don't know who first used the term—the earliest use I can dig up quickly is actually the Wikipedia article, initially drafted in November 2004 by Paul Crowley[1], who also used it a year earlier on sci....

8

In short, TPMFail attack is black-box timing analysis of TPM 2.0 devices deployed on computers. The TPMfail team is able to extract the private authentication key of TPMS's 256-bit private keys for ECDSA and ECSchnorr signatures, even over networks. This attack successful since there was secret dependent execution in TPMs that causes the timing attacks. To ...

7

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)$

6

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, ...

6

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 ...

6

The $(r,s)$ version in theory is more secure than $(h,s)$. Bellare, Namprempre, Neven 2004 paper "Security Proofs for IBI and Signature Schemes" showed that Schnorr signature in the form of $(r,s)$ (which they named as BNN signature) can achieve semi-strong unforgeability (ss-euf); while the signature in the form of $(h,s)$ can only achieve normal ...

6

Pointcheval and Stern [PS00] proved that the Schnorr signature is existentially unforgeable under chosen-message attacks (EU-CMA) in the random oracle model assuming that the discrete-logarithm problem$^1$ (DLP) is hard. On a high level, the reduction (from DLP to the EU-CMA-security of Schnorr signature) works as follows. The reduction algorithm $\... 5 I suppose that you address the question to a signature scheme, in which the signature is still the pair$(r,s)$with$r=g^k \bmod p$as the exponentiated nonce and $$s = H(m)\cdot x + k \mod q,$$ where$h = H(m)$depends solely on the message$m$being signed. Here$x$denotes the secret signing key and$q$the order of the generator$g$of a prime ... 5 I guess you are talking about Figure 5.3? It is said that the Schnorr proof (sigma protocol for discrete log relation) is insecure against cheating verifiers - it is only honest-verifier zero knowledge. Sigma protocols are always only defined in the honest-verifier zero-knowledge setting. To see why a cheating verifier is a problem in Figure 5.3 think ... 5 Ed25519 is well-defined and requires you to use SHA-512 as internal hash function along with the twisted Edwards version of Curve25519, hence there's no need for a KAC when it comes to questions about the parameters. As for the integrity of the public key, there's not yet a standard for Ed25519 based certificates so there would be a custom solution needed ... 5 Well yes,$P$can generate$A^cT$and send it over, but why would it help? The point of this protocol is that$P$proofs to$V$that it knows$x$, without revealing anything about$x$. The way that$P$does this is that given some randomly chosen$t$and a challenge$c$, it can compute an$s$such that$g^s=A^cT$. The fact that$P$can compute this$s$... 5 Schnorr signature is a pair challenge-response$(e, s)$with challenge computed as a hash of message$m$and initial commitment$r$; signature is verified by re-creating that commitment with challenge and response only. For blind Schnorr signature, one keeps verification equation while randomizing both challenge and response with$\beta, \alpha$... 5 TPM-Fail is a new demonstration of the well-known lattice-based attack of Howgrave-Graham and Smart on DLOG-based signature schemes such as Elgamal, Schnorr, and DSA that exploits partial information about per-signature secrets. TPM-Fail specifically applies the attack with timing side channels from the cryptogrpahy decelerators in TPMs. The attack had ... 5 Yes, and in fact, Schnorr's signature scheme was originally described as a non-interactive protocol. I think the confusion around interactivity comes from the fact that the same paper first described a interactive identification scheme, which can be viewed as a specialization of the signature scheme for empty messages. In both schemes, challenges can be ... 4 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 ... 4 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 ... 4 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 ...

4

Note that the signature is $(s,e)$ where $s=k-xe$. If you can learn $k$ since it is predictable, then you can learn the secret signing key by computing $x = (s-k)/e$. Note that even without a concrete attack, the proof of security completely breaks down if the value $k$ is not chosen randomly. Having said this, it is possible to change the scheme to be ...

4

response $s=c(x+r)$, verify $g^s=(yt)^c$ This one doesn't work; a lying prover can chose $t = y^{-1}g^n$, for an arbitrary $n$. Then, when the challenger responds with a $c$, the lying prover can respond with $s = nc$, satisfying the relationship. The other two are good; the second is the standard Schnorr, and the first is standard Schnorr proof of the ...

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