Talk:Schnorr signature

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

Computing: Software / Security Low‑importance

This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles

Low

This article has been rated as Low-importance on the project's importance scale.

This article is supported by WikiProject Software (assessed as Low-importance).

This article is supported by WikiProject Computer Security (assessed as Mid-importance).

Things you can help WikiProject Computer Security with:

Article alerts will be generated shortly by AAlertBot. Please allow some days for processing. More information...

Review importance and quality of existing articles
Identify categories related to Computer Security
Tag related articles
Identify articles for creation (see also: Article requests)
Identify articles for improvement
Create the Project Navigation Box including lists of adopted articles, requested articles, reviewed articles, etc.
Find editors who have shown interest in this subject and ask them to take a look here.

Some significance to 40 bytes?

The article mentions if q < 2^160, then the signature is less than 40 bytes. This is obviously true, but is there any special significance to 40 bytes?

I believe that it means that even when the group order is large, the signature is small. For instance, using a 1024-bit prime field (128 bytes), the signature would still be 40 bytes, with a security level of 80 bits. For the same security level, DSA signatures would have 40 bytes, too.

202.246.252.97 (talk) 01:57, 3 March 2008 (UTC)[reply]

Patent expired?

The article says: "It is covered by U.S. Patent 4,995,082 , which expires in February 2008." February 2008 is now. However, the priority date of the patent is February 24th 1989 (according to the link); why is it that the patent does not expire in 2009? —Preceding unsigned comment added by 202.246.252.97 (talk) 05:18, 29 February 2008 (UTC)[reply]

What is the || operator

Could please somebody who knows what is meant with "||" in the formulas add a note about what that means? Cacadril (talk) 22:24, 21 April 2010 (UTC)[reply]

That would most likely be the Logical Disjunction operator, better known as OR.

I've tested out the algorithm and I believe the operator would probably be non-bitwise, meaning that you will likely end up with a hash of either 1 or 0. I've also seen that after using bitwise OR, the value for e, and

e_{v}

was non-congruent.

It could depend on the language I decided to use for my tests though. But I'll probably take a look into any papers for the algorithm, and eventually figure this out.

As for a note on what the operator does, I would suggest reading the article on Logical disjunction

Dante Feistel (talk) 18:36, 11 July 2010 (UTC)[reply]

No. It denotes concatenation. 85.3.36.240 (talk) 21:49, 11 July 2010 (UTC)[reply]

Thanks for the clarification. I was thinking a bit about that earlier, and have seen it in a different scheme I looked at. Must have been the operator that got me confused. Dante Feistel (talk) 00:57, 12 July 2010 (UTC)[reply]

The || operator is frequently used for concatenation in crypto literature, but is not much used otherwise. I'll add a short comment to the article. 85.3.0.61 (talk) 07:49, 12 July 2010 (UTC)[reply]

Hash

Article mentions that e < q. But it is nowhere assumes, or stated that hash function should depends this way. If I would use hash function with 1024bit output it will obviously make signature very big. Please clarify.

Also some small proof that indeed valid signature will validate correct would be usefull. —Preceding unsigned comment added by 91.213.255.7 (talk) 01:06, 12 January 2011 (UTC)[reply]

I have added the proof, would appreciate someone checking it. 129.27.152.197 (talk) 09:48, 7 June 2011 (UTC)[reply]

I have changed the article to clarify how e < q is derived, as requested under first point above. Modulo reduction on e limits the size without affecting the verification outcome, and more properly reflects the security level. Naturally, if H produces a smaller output than the number of bits in q, only the width of this output need be transmitted as e. Quondum (talk) 19:16, 4 August 2011 (UTC)[reply]

Proposal to replace "n∈ℕ with 0 ≤ n < q" in terms of ℤ_q (and similarly ℤ_q^* when non-zero)

I note that the reference Handbook of Applied Cryptography gives H : {0,1}^* → ℤ_q, which is a set if equivalence groups, not a set of integers. The reference is notationally inconsistent inasmuch as it then flips back to using integers within a range. This article seems a bit clumsy due to the repeated "∈" qualifications in each line, but it is evident that they facilitate understanding. I would like to revise the article in two respects, namely: (a) moving the "∈ℕ" and "∈G" into a list of qualifications for each variable with associated ranges to a line at the end of each section, and (b) replacing the "∈ℕ" in a range with ℤ_q and ℤ_q^* as appropriate for compactness. Should anyone have objections or alternate suggestion, please say, else I'll make the modifications as I have suggested. 41.174.54.111 (talk) 11:12, 7 August 2011 (UTC)[reply]

I have made the changes as I suggested, plus a bit. Any comments will be appreciated. I am not happy with unclarified "The other direction ..." line, but have left that unchanged for now. Quondum (talk) 09:06, 4 September 2011 (UTC)[reply]

Hash and collision resistance

> Its security can also be argued in the generic group model, under the assumption that is "random-prefix preimage resistant" and "random-prefix second-preimage resistant". In particular, H does not need to be collision resistant.

The algorithm as described in this article uses $H(M||R)$. In this variant the hash must be collision resistant. (At least resistant to state collisions, but for MD hash constructions, such as MD5, SHA-1 and SHA-2 that's the same thing.)

The cited paper uses $H(R||M)$ where $R$ serves as random prefix, leading to the weaker requirements. Its security proof does not apply to $H(M||R)$.

--- CiC — Preceding unsigned comment added by 84.151.205.34 (talk) 18:01, 6 March 2013 (UTC)[reply]

Indeed, I've changed the order. Dchestnykh (talk) 10:54, 25 March 2017 (UTC)[reply]

Characteristics of this scheme

The characteristics of this signature scheme(able to be aggreated) is not well explained. Jackzhp (talk) 14:55, 17 November 2017 (UTC)[reply]

Short schnorr signatures

I've added a bit of text about this topic in a separate section (as it's technically a different algorithm). There is some interesting literature review here: https://crypto.stackexchange.com/a/50088/64874 --Nanite (talk) 04:36, 12 January 2019 (UTC)[reply]

s = k - ex vs. s = k + ex

This article uses s = k - ex for computing the signature, while the original source uses s = k + ex. This changes the verification algorithm in a minor way. All other publications use that '+' version as well. Unless somebody objects, I'll re-edit the article in a few weeks to match other implementations. — Preceding unsigned comment added by Clefru (talk • contribs) 10:30, 2 February 2019 (UTC)[reply]

This is due to the definition of the public-private key generation. Since this article (and is usually the case) defines the public key as y=g^x. With this definition, the computation of the signature must use the inverse of x (thus -x mod q). In the original paper by Schnorr, he defined y=g^-x and therefore could rely on +x to have it work out mathematically. Markovisch (talk) 12:33, 6 May 2019 (UTC)[reply]

The international Standard ISO/IEC defines SDSA and FSDSA (Schnorr and Full Schnorr DSA) as well as their EC pendants with s=k+ex. An approach that follows Schnorr itself in his lectures (cf. chap. 1.7, p. 18 in http://www.math.uni-frankfurt.de/~dmst/teaching/ss05/Kryptographie.pdf). Annie Yousar (talk) 10:58, 28 August 2022 (UTC)[reply]

Does ROMDL stand for "Random Oracle Model, Discrete Log"?

Does ROMDL stand for "Random Oracle Model, Discrete Log"? Because that would be worth mentioning in the article. That's very impressive, as I don't think that other Discrete Log type algorithms have been reduced to this assumption. --Svennik (talk) 09:19, 18 September 2019 (UTC)[reply]