# Tag Info

29

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

17

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

15

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

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

13

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

11

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

9

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

9

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

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

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

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

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

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 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 ... 6 This answer is assuming you are not removing the private key$a$from the computation of$S$, and instead actually meant what is said in the title of the question:$S = r + a H(A, M)$Removing$a$from the computation would be terrible. The first issue that comes to mind is malleability, on top of collision resistance. The signature process for EdDSA ... 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 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 Probably the most widely deployed Schnorr-type signature scheme over elliptic curve groups today is EdDSA, in its instantiation Ed25519 over Curve25519 with SHA-512. A public key is the encoding of a point$A$in the$\mathbb F_q$-rational points of an elliptic curve$E/\mathbb F_q$of order$h \ell$for large prime$\ell$, over a finite field of odd prime ... 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 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 Fix a group$E(k)$on an elliptic curve over a field$k$. Suppose$P \in E(k)$is a public key. If a signature on a message$m$under$P$is the encoding of a pair$(R, s)$of a point$R \in E(k)$and an integer$s$satisfying (various criteria and) the equation $$[s]G = R + [H(R \mathbin\| m)]P,$$ where$G$is the standard base point, then you can recover ... 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 As pointed out by @SEJPM, you can read more about security proofs for DSA/ECDSA family on this thread. As for whether there exists an interactive protocol corresponding to DSA/ECDSA à la Schnorr identification/Schnorr signature, not that I am aware of. I would add that this is unlikely for two reasons: The (unfortunate) reason for coming up with DSA/ECDSA ... 5 would using S = r + H(A, M) be a secure variant? Actually, it would become trivial to generate a signature for an abitrary message with just the public key. The verification check would be: $$2^h s G = 2^h R + 2^h H(A, M) A$$ where$h$is the curve cofactor,$G$is the curve generator,$A$is the public key,$M$is the message and$(R, s)$is the signature. ... 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 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 Partial answer to my own question, after some weeks of research based on the question's expanded bibliography. History The Schnorr signature scheme was initially proposed with a$t$-bit hash ($3t$-bit signature), at a time when security proof where the exception. [PS96] proved security for a$2t\$-bit ideal hash assuming the underlying discrete logarithm is ...

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