Questions tagged [hash-signature]

Hash-based digital signatures, such as Lamport one-time signatures, are digital signature schemes based on a (non-trapdoor) one-way function such as a cryptographic hash. Such schemes are expected to remain secure even against attacks using quantum computers.

Filter by
Sorted by
Tagged with
11
votes
3answers
3k views

One-time digital signatures

Are there digital signatures for which, given two documents signed by the same key, one could derive the key? With such one-time signatures, one may be able to design a cryptocurrency based on proof-...
10
votes
3answers
4k views

Lamport signature: How many signatures are needed to forge a signature?

Lamport signature: Signing the message Note that now Alice's private key is used and should never be used again. The other 256 random numbers that she did not use for the signature she must never ...
9
votes
2answers
2k views

Advantages and disadvantages of hash-based signatures

We know hash-based signatures (Winternitz signature, HORS(T) signature) that are quantum-safe and efficient. They can be stateful or stateless, one-time or multiple-time. But why are they not widely ...
9
votes
3answers
5k views

Winternitz One-Time Signature

I am reading the page 38 in this "Post Quantum Cryptography" book (Equations 8 and 9). My question is, why to compute the verification key $Y$, $f$ is applied $2^w-1$ times? Are there any security ...
8
votes
3answers
1k views

Stateless hash based public key cryptography?

Merkle-Winternitz signatures based on fractal hash trees are an attractive alternative to other post-quantum cryptographic schemes, in particular since they are conceptually simple, the security ...
8
votes
2answers
2k views

Why don't crypto-currencies use the Lamport signature scheme?

The Lamport signature scheme is faster, less complex and considerably safer than ECDSA. It's only downside - being only usable once - isn't really a downside when signing transactions, since you could ...
7
votes
1answer
380 views

Do other one-time signature schemes exist?

I'm curious to know if there are any one-time signature schemes other than Lamport's or its variants (Merkle trees are one such variant). The first I've discovered is called "Bins and Balls" which ...
6
votes
3answers
808 views

Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree?

One of the problems of one-time Lamport signatures is that public keys are disposed after use, so you must generate many keys and store them in a Merkle tree. The root is the "real" public key and ...
6
votes
3answers
893 views

Why do we need Collision Resistant Hash Function for the Merkle Tree Signature Scheme?

I am studying Merkle Tree Construction for digital signature. I don't quite understand why we need collision resistant hash function for Merkle tree construction. There are few papers like XMSS that ...
6
votes
2answers
147 views

Is there a signature scheme which doesn't rely on the difficulty of factoring/dlp which generates short signatures?

The Lamport signature scheme, for example, doesn't rely on the difficulty of any problem and it only depends on the existence of one-way functions. Is there an alternative scheme which also doesn't ...
6
votes
1answer
561 views

Difference Between Gravity-SPHINCS and SPHINCS+?

What are the differences between Gravity-SPHINCS and SPHINCS+ from security and practicality standpoints? Are they just different implementations of the underlying SPHINCS algorithms or are they ...
6
votes
1answer
247 views

Choice of the one-way function (OWF) for Lamport signatures

I am studying the Lamport signature scheme, and I found that in many sources (eg: Hash-based Digital Signature Schemes) the input and output bitstring of the OWF and the message digest have the same ...
4
votes
2answers
242 views

Small Quantum Signatures - Reality check needed

I've been thinking a bit lately about how to get quantum resistant signatures fast and (relatively) small. One idea I've been keen on exploring is finding a crypto PRNG that allows fast-forwarding, e....
4
votes
1answer
398 views

Does still make sense to use SHA1?

I'm working with Arduino and hash-based signatures which are signature schemes that use only hash functions. Due to the constraints of an Arduino I was thinking about using SHA1 as the underlying ...
3
votes
1answer
379 views

How to use SPHINCS+?

Based on the NIST submission it looks like the SPHINCS+-256s algorithm comes in at public key sizes of 64 bytes, private key sizes of 128 bytes, and signature sizes ...
3
votes
1answer
809 views

Winternitz One time signature security

There are two versions of Winternitz-One time signature scheme, $W-OTS$ and $W-OTS^+$ Security of both is as following $W-OTS$ is strongly unforgeable under chosen message attacks if $F$ is a ...
3
votes
1answer
467 views

How can I generate reasonably short temporary unlock codes?

I need a way to generate temporary unlock codes for an application to use when it can't go online to confirm that its activation subscription is still current. The application needs to able go ...
3
votes
1answer
87 views

SPHINCS and HORST: can we sign the same message twice?

I was reading about SPHINCS which uses layers of WOTS+ trees and a bottom layer of HORST trees. HORST is a few time signature scheme, using a selection function you can sign at least twice without ...
3
votes
2answers
585 views

Winternitz hash based signature signing and verification

In Winternitz hash based signature There are two functions $f: \{0,1\}^n \to \{0,1 \}^n$, a one way function and $g: \{0,1\}^* \to \{0,1 \}^n$, cryptographic hash function Key Generation steps ...
3
votes
1answer
1k views

Quantum resistance of Lamport signatures

The Lamport-Diffie signature scheme is said to be quantum-resistant. Why is that? What would a quantum attempt to attack this signature scheme look like, and how does it fail?
3
votes
1answer
39 views

For a hash over a finite space without size reduction, is a public permutation sufficient?

Suppose the application is a Lamport signature scheme. Is the following a secure hash $\{0,1\}^n \rightarrow \{0,1\}^n$? $$ H(x) = x \oplus P(x) $$ where $P$ is a public permutation that permutes an ...
3
votes
1answer
120 views

Why are the bit lengths of keys and digests equal in Lamport signatures?

In Lamport's one time signature scheme: One way function to convert a pseudo random number private key to a public key takes $\{0,1\}^n$ and returns $\{0,1\}^n$. Cryptographic hash function to ...
3
votes
0answers
36 views

Are there any hash-based multisignature schemes?

Are there any hash-based signature schemes which would let two (or more) people sign the same message without increasing the size of the signature linearly? For my purposes, it is fine if the scheme ...
2
votes
2answers
198 views

Blind Hash Signatures?

Is it possible to implement blind signatures with purely hash-based signature algorithms? Any whitepapers, code samples, etc on the subject would be helpful.
2
votes
1answer
545 views

What is a Trapdoor in Merkle Signature?

Merkle signature (pag. 40) use than public key (verification key) the root of the Merkle Tree and than private key (to sign) the set of pre-images of the $g(Y_i)$ where $Y_i$ is the verification key ...
2
votes
1answer
740 views

Hash collision resistance requirements for Lamport signatures

According to the original paper, Lamport one-time signature scheme uses two one-way functions: $F$ and $G$. The former one, $F$, is used to create a public key by hashing elements of the private key (...
2
votes
1answer
976 views

Is ed25519 a “hash signature”

Writing my last question, I saw the hash-signature tag. I tried to research it best I could, but I'm simply overwhelmed in this field. I don't think it means to simply hash data before signing, but ...
2
votes
1answer
224 views

What is a formal definition of strong one-time-secure signatures?

What is a formal definition of strong one-time-secure signatures? I know the Lamport's scheme is one of them, but what is the global definition of it?
2
votes
1answer
89 views

How secure is a hash based signature scheme after signing assuming quantum computers?

Consider a hash based signature scheme that requires taking the $k$-bit hash of an arbitrary length message to be signed (e.g. Lamport one-time signature scheme). My understanding is, assuming that ...
2
votes
1answer
153 views

How is SPHINCS Hash-based signature “stateless”?

I really hope someone can help me with these questions related to SPHINCS. I am trying to understand the concept of “stateless” vs. “stateful” signature scheme which is the basis of SPHINCS. I went ...
2
votes
1answer
113 views

Why is WOTS-type signature schemes OTS?

I'm sure I've missed something super trivial, but why are WOTS-type schemes one-time? I've been looking into hash-based schemes, and I feel like I understand WOTS quite well (specifically I have ...
2
votes
1answer
118 views

Smallest 256-bit security hash-based OTS?

What is the smallest hash-based OTS in terms of the sum of the public key and signature which provides 256 bits of security?
2
votes
0answers
25 views

HkdfLabel in TLS 1.3 [migrated]

In rfc8446, it says ...
2
votes
0answers
124 views

Can this hash-based, short signature scheme work, given a decentralized log of messages as a primitive?

Suppose we had a decentralized log of messages, i.e., an ever-growing array of information on which anyone could append arbitrary data to. Given such primitive, could a party broadcast authenticated ...
2
votes
1answer
69 views

What's the difference between a hash chain, transaction chain and a blockchain?

Can anyone explain to me what the difference is between a hash chain, transaction chain and a blockchain?
1
vote
1answer
223 views

Merkle Signature Generation

In the section 2 (page 42) of the book "Post Quantum Cryptography", it says: Then he generates the one-time signature $\sigma_{\text{OTS}}$ of the digest using the $s$-th one-time signature key $...
1
vote
2answers
166 views

Lamport-Diffie + attempting to invert OWF

I am studying Lamport-Diffie signature scheme and in my lecture present the follow algorithm for attempting to invert the one way function $f$, where $f$ is used to compute the public key of this ...
1
vote
2answers
786 views

Merkle signature scheme

I was browsing the Wikipedia article on Merkle signature schemes and noted that it says: The number of possible messages must be a power of two[…] Why is that? ...
1
vote
1answer
554 views

Lamport-Diffie + Security Proof

I am studying Lamport-Diffie signature scheme. In the lecture present the algorithm $A'$ for attempting to invert the one way function $f$, where $f$ is used to compute the public key. My question is ...
1
vote
1answer
143 views

Does the One-Time Hash-based Signature Scheme render Ring Signatures useless?

On the Bitcoin community, to maintain privacy, they recommend using one-time spend addresses. CryptoNote, Monero et al. prefer Ring Signatures to maintain that privacy. There are some issues regarding ...
1
vote
1answer
137 views

Bitmasks or seed along with public key in WOTS+ post-quantum signatures

The state of the art hash-based post-quantum signature schemes, like Sphincs and XMSS, are using variations of WOTS (Winternitz OTS), like WOTS+, that require extra random bitmasks along with the ...
1
vote
1answer
463 views

What are the advantages and disadvantages of Merkle signatures over Lamport signatures?

I know they are both hash-based and post-quantum secure, and that Lamport signatures can form the basis for a Merkle scheme, but what do you actually gain over standard Lamport signatures by doing ...
1
vote
1answer
75 views

Signing a message using SPHINCS Hash-based Signature scheme

I have questions on “SPHINCS: practical stateless has-based signature” by Bernstein et al. And I really hope that someone can help me with it. To help me understand it, I read the https://...
1
vote
0answers
40 views

Tuning the signature size of Sphincs+

If I only need a small number of signatures (perhaps $2^{10}$) for the lifetime of my key pair, how would I calculate the consequent signature size? Unfortunately managing state for an LMS or XMSS ...
1
vote
0answers
24 views

How does the KeyGen of Merkle's improvement of Lamport's OTS work?

In his paper [1] on page 17 and 18, Merkle proposes an improvement on Lamport's OTS by only signing the 1's in the message in combination with a checksum of the amount of 0's in the message. I get the ...
1
vote
2answers
136 views

Why does WOTS+ need a checksum during signing operation?

I was reviewing WOTS+ scheme for consideration in our private blockchain, and noticed that it had a small overhead of calculating a checksum as seen in the following pseudocode excerpt from the ...
0
votes
1answer
403 views

eXtended Merkle Signature Scheme (XMSS) vs Leighton-Micali Signature (LMS)

Very briefly, how does eXtended Merkle Signature Scheme (XMSS) stack up against Leighton-Micali Signature (LMS)? I'm asking this in the context of my article here.
0
votes
1answer
45 views

In W-OTS, is it trivial to forge smaller N values?

Just read about W-OTS, since the signature is the private key hashed 256-N times, is it trivial to forge a signature with a smaller vale for N when having access to original signature? I.e. just hash ...
0
votes
1answer
73 views

How many messages before Sphincs(+) becomes insecure?

How many messages would it take until the success probability of a forger becomes $1/2$? $1/4$?
0
votes
1answer
81 views

Sequential delayed release of chained HMAC keys for use as asymmetric signature

Iterative hashing of a private random seed can yield keys for use in HMAC, which if revealed publicly in reverse order and on predetermined schedule, can be used in a manner similar to other ...