Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [schnorr-signature]

A digital signature algorithm based on the discrete logarithm problem, provably secure in the random oracle model.

1
vote
1answer
24 views

Monero Ring CT sj calculation

For a university project, I am currently implementing the RingCT Ring signatures as used in Monero (before the introduction of Bulletproofs) as laid out in this paper. To close the ring we calculate ...
0
votes
0answers
17 views

Why can multiparty schnorr signatures not be solved for linearly?

If you only need the notation skim down to the bold line. Quoting from en.bitcoin.it Schnorr signatures are a proposed future extension that give a new way to generate signatures r, s on a hash h....
1
vote
0answers
59 views

Prove that two commitments are commitments to the same value

Let $x$ be the secret value, $(n,a,b,c)$ a public key, $(n_C, g, h)$ the commitment public key. Furthermore let $r, r_C$ be two random numbers. Define $C = g^x h^{r_C} \bmod n_C$, $C_x = a^x b^r \...
0
votes
1answer
51 views

Malleable version of Schnorr signature

Given an elliptic curve defined in $\mathbb{F}_{q}$ with a generator $G$ and a hash function $H_{q}(x)$ which maps $x$ to $\mathbb{F}_{q}$. A Schnorr signature variation for a data block $B$ such as: ...
1
vote
0answers
64 views

Schnorr-signature calculating a coefficient

I need to create program that makes signature for selected file. I simplified algorithm a little, because I draw max 64 bit prime numbers instead of ...
11
votes
1answer
143 views

Why is $e=0$ allowed in Schnorr signatures?

In a Schnorr signature (Wikipedia style), we have: $R = kG$, where $0<k<n$ is a nonce and $G$ is the generator point. $e = H(R \| M) \bmod n$, where $H()$ is a hashing function and $M$ is the ...
2
votes
1answer
88 views

Is Wikipidia wrong about Schnorr Signatures?

Wikipidia says Schnorr signature generation is defined like this: ...
1
vote
0answers
49 views

HW wallet and multisignaters in ECC

I need to design a system where there is a secure device (a.k.a. HW wallet), with the following functionality: Deterministic key generation for key parameters (speaking simply: key ID). Never expose/...
1
vote
0answers
86 views

Drawbacks of Schnorr Authentication that require Fiat-Shamir and Random Oracles?

I've been going through G. Maxwell's paper on the Borromean Ring Signature, and I don't fully understand this part on Schnorr Signature. If some could explain it more intuitively thank you. "...
1
vote
2answers
127 views

Using the same private key to generate Schnorr and BLS signatures

I am wondering if it is possible or if there are any limitations to using the same private key to generate Schnorr and BLS signatures. Specifically, assuming I have a private key $x$, I want to use it ...
1
vote
0answers
46 views

Threshold Bitcoin signature scheme

Any advice would be appreciated: It seems to me that using an uncomplicated combination of a shamir scheme and schnorr it's fairly trivial to have a threshold signature scheme. I think it's also ...
1
vote
1answer
222 views

Schnorr Pubkey Recovery

As per How does recovering the public key from an ECDSA signature work? , it's possible to recover public keys from ECDSA signatures. Is this possible for EC-Schnorr signatures as well? I'm looking ...
0
votes
1answer
357 views

Schnorr signature using discrete logarithm / problem with python implementation [closed]

For educational purposes (by purpose with small values for the prime order q), I tried to write a small Python implementation of the Schnorr signature described in the Wikipedia article https://en....
4
votes
2answers
257 views

Compact Schnorr signature?

The commonly-used ECDSA signature consists of 2 scalars $(r,s)$. There's also a Schnorr signature. Given private key $k$, public key $C = [k]G$ and the message $M$: Generate random scalar $k_1$ ...
1
vote
1answer
285 views

Shor algorithm and schnorr signature in ed25519

Does the application of Shor's algorithm in any way relate/affect the schnorr signature in ed25519?
1
vote
0answers
181 views

BLS aggregate signatures for relay node non-interactive incentive accounting

This is a practical application of cryptography question and I hope this is the right place to ask it. Any advice would be very much appreciated. I'm looking for a low-bandwidth, non-interactive ...
1
vote
0answers
93 views

Missing step in Schnorr's proof that an attack on blind signatures requires solving ROS?

In Security of Blind Discrete Log Signatures Against Interactive Attacks C.P. Schnorr defines the ROS Problem and claims that a $(l+1)$ attack against his blind signature scheme is equivalent to ...
14
votes
2answers
2k views

Schnorr signatures: multisignature support

Schnorr signature is mentioned as a promising upgrade to bitcoin to improve scalability. It support multisignature, several signatures can be aggregated into a single, new signature. But I fail to ...
0
votes
1answer
430 views

Schnorr Digital Signature

I tried to rewrite the Schnorr signature algorithm for elliptic curves but I wanted to be sure to have not done any errors. So I would be very happy if someone could look over this algorithm and tell ...
5
votes
1answer
989 views

Prove the Security of Schnorr's Signature Scheme

I know that Schnorr's signature is important since it is one of the most compact signature schemes whose security has been proved in the random oracle model. Now, I want to know if such proof is ...
17
votes
2answers
1k views

Security of Schnorr signature versus DSA and DLP

The Schnorr signature scheme is a randomized signature scheme with appendix. The signature is $3t$-bit for conjectured $t$-bit security in a chosen-messages setup, with at most $2^{t/2}$ queries to a ...
3
votes
0answers
112 views

Small generator for classical Schnorr signatures?

I'm implementing classical Schnorr signatures for real-world use. By "classical" I mean that the operations take place in a finite group, no elliptic curves. I'm following https://en.wikipedia.org/...
2
votes
1answer
208 views

Plausible Deniability in Schnorr

How does a dishonest verifier affect plausible deniability of the interactive Schnorr protocol?
4
votes
1answer
171 views

Security proof of partially blind signature (schnorr signature based)

I read a representative paper about partially blind signature. Abe and Okamoto - "provably secure partially blind signature". They suggested a partially blind signature scheme based on Schnorr ...
1
vote
1answer
93 views

Unforgeability proof of partially blind signature (schnorr signature based)

I read a representative paper about partially blind signature. Abe and Okamoto - "provably secure partially blind signature". They suggested a partially blind signature scheme based on Schnorr ...
8
votes
4answers
716 views

Schnorr protocol: how does malicious verifier win?

My question is about the challenge space size in Schnorr protocol. To be precise, I feel I've read all the Internet (twice) and I still don't understand why is it bad to allow challenge space to be ...
4
votes
1answer
525 views

Intuition for Schnorr Blind Signatures

I was studying the Blind schnorr signatures in this paper (PDF) which says that the signer sends a commitment $$r=g^{k}\bmod p$$ which the user blinds with 2 random elements $a,b$ to get $$r'=r\...
2
votes
1answer
99 views

Tricking the Schnorr's protocol

From the lecture notes I have learned the following: $P \rightarrow V$: $T=g^t$ ($t$, randomly chosen from $Z_q$) $P \leftarrow V$: $c$ (randomly chosen from $Z_q$) $P \rightarrow V$: $s=xc+t \mod q$ ...
0
votes
1answer
83 views

Schnorr's signature scheme with addition of modulus secure?

In Schnorr signature scheme,$s=(k-xe)$$ s_1=(k-xe_1)$ If the same key $k$ is used, then it is possible to reveal $k$ and $x$ value by using $\frac{s-s_1}{e_1-e}$. However, if we add $s=(k-xe) \bmod q$...
2
votes
1answer
229 views

Additive proof of discrete log?

Let's say someone has $K$, and I want to prove to them that I know $k$ such $K = k*g$ (where $g$ is some sort of group element). I can use a Schnorr signature. Is there some protocol for mergable ...
7
votes
1answer
136 views

How to forge signatures in the Schnorr scheme if $r=g^k$ is eliminated?

I need some help to demonstrate how to forge signatures in the Schnorr scheme if I eliminate the random string $r=g^k$ used in the hash – using $H(M)$ instead of $H(M||r)$. How would one be able to ...
1
vote
1answer
154 views

Single-scalar multiplication with sign bit

I want to know if there's an "easy" timing-free way to compute the sign of $y$-coordinate of $r G$, for a secret scalar $r$ and $G$ the generator of an elliptic curve. We have several choices for ...
14
votes
4answers
2k views

EC Schnorr signature: multiple standard?

I'm working on some EC-Schnorr signature code. Reading various papers on that, it seems EC-Schnorr is not standardized as well as ECDSA. For example, I found two main differences in two main actors ...
4
votes
1answer
213 views

Schnorr signature security level as compared to AES/RSA

As per the Schnorr's original paper (1991), The Security Complexity $2^t$: We wish to choose the parameters $p$, $q$ so that forging a signature or an authentication requires about $2^t$ steps by ...
8
votes
2answers
811 views

What is an example of a secure sigma proof?

I want to implement Threshold Elgamal as described in section 6.3.1 and in the decryption phase each party must broadcast a sigma proof to show that it actually has a valid secret share of the secret ...
2
votes
1answer
336 views

Schnorr Ring Signatures - wrong hash results

I don't know if I've placed the question right, It is half maths, half programming. I'm writing Schnorr Ring Signatures on Elliptic Curves in Java and I have a problem. I've found scheme on integers ...
1
vote
1answer
110 views

How are all necessary parameters shared between signer and verifier in ED25519 signature scheme?

I want to use ED25519 signature scheme in my application which requires frequent sharing of secret data between two entities in public domain. I know that Schnorr signature scheme has a key ...
0
votes
1answer
389 views

How to prove knowledge of discrete logarithm in a product?

Definitions Suppose I have two large safe primes $p$ and $q$, and a composite number $N=pq$. I have $G$, a large cyclic subgroup of $\mathbb{Z}^{*}_{N}$; $g$ and $h$ are generators of $G$. I commit ...
1
vote
2answers
323 views

On the fly signatures and zero-knowledge

I am reading some articles which explain on the fly signatures (also called online/offine signatures). The principle is that a few operations do not depend of the message we want to sign, so these ...
1
vote
0answers
606 views

Zero Knowledge Non Interactive Proof with random oracle

I am trying to write an assay about Non Interactive Zero-Knowledge proofs and would like to take the simple discrete logarithm problem example fallowing the Feige-Fiat-Shamir heuristics. I understand ...
2
votes
1answer
588 views

How does Schnorr signature actually work?

I'm trying to get a grip on how Schnorr signature works. Suppose Alice sends Trent a tuple $(P, M)$, which contains a payload and a message to be signed by him. She then passes the certificate to Bob ...
8
votes
1answer
1k views

Does Ed25519 support cryptographic threshold signatures?

This is a loaded question so I'll list the concerns, not all of which need to be satisfied. Does there exist a threshold-signature scheme for Ed25519 that... Does not require a trusted dealer to set ...
4
votes
1answer
352 views

Is this modified Schnorr signature scheme secure?

Signing Let $y = g^x$, which is your public/private keypair. Let $r = g^v$, for random $v$ Let $c = H(M)$ Let $z = (v + cx) \bmod q$ The signature is the pair $(r,z)$ Verifying $g^z = ry^c \bmod p$ ...
4
votes
2answers
250 views

Is ”generating transcripts that are indistinguishable from actual messages in a signature scheme” not universal forgery?

In the Pointcheval paper “Security arguments for digital signatures and blind signatures”, they have proved the security of Schnorr signature for existential forgery under adaptively chosen-message ...
1
vote
0answers
72 views

How to specify last $t$ bits are only sent when a signature is sent?

I have read that in cases where there is a limit on the amount of data sent over the network, one idea is to sent only $t$ bits of data rather than sending all the bits. For example, in the Schnorr ...
4
votes
1answer
494 views

Does changing the random number selected for each message increase security in Schnorr's scheme?

I was reading about Schnorr's scheme and in that for signing the signer generates a random number and continues with his operation. I am trying to implement this in a scenario where the signature ...
1
vote
0answers
117 views

Factorization or discrete logarithm is difficult for an attacker?

I have read that difficulty in breaking many algorithms are based either on Factorization or discrete logarithm. I am reading about schemes that are similar to RSA which make use of integer ...
12
votes
1answer
5k views

DSA vs. ElGamal vs. Schnorr

It has been well known for a long time that NSA played a primary role in the development of the Digital Signature Algorithm (DSA). DSA is a sort of hybrid of the ElGamal and Schnorr signature schemes....
12
votes
3answers
5k views

Perfect zero knowledge for the Schnorr protocol?

Can somebody explain (or point to a reference) why the Schnorr protocol cannot be proved zero knowledge?
3
votes
2answers
321 views

Could this be a valid variation of the Schnorr protocol?

The Schnorr protocol is a 3-steps proof of knowledge of a discrete logarithm, whose interactive version works as follows. Let $p$ and $q$ be two public primes, such that $q \mid (p-1)$, and let $G$ ...