25

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


14

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


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

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


12

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


12

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


10

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


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

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


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


7

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


7

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


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

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

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 is similar to ISO/IEC 14888-3's EC-SDSA-opt, standing for Elliptic Curve Schnorr Digital Signature Algorithm optimized version, except that EC-Schnorr outputs $H(M\...


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


6

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


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

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


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

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

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


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

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

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

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


3

How does value of $p$ comes to $2^{512}$ for security complexity of $2^{72}$? Personally, I couldn't connfirm this number, but rather landed at $2^{66}$. If you don't know how to find this number, just plug the $2^{512}$ into the complexity equation given and take the logarithm to the base two for better readability. Note that Schnorr's complexity ...


3

Threshold (robust) m-of-n variant of Schnorr signature scheme is known: Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates Major hints on intended usage are from Ripple page mentioned. Points 4 and 3 are explicit: produce a signature, in a theshold m-of-n way. This could ...


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