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
130
votes
6answers
92k views

Should we sign-then-encrypt, or encrypt-then-sign?

Frequently, we want to send messages that are (a) encrypted, so passive attackers can't discover the plaintext of the message, and (b) signed with a private-key digital signature, so active attackers ...
12
votes
3answers
5k 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 ...
11
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 ...
11
votes
3answers
4k 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

Why is SHA3 more secure than SHA2?

Why are SHA3 algorithms considered more secure than their SHA2 counterparts? Surely in part, it is due to their resistance to length extension attacks. But specifically, when considering collision ...
9
votes
3answers
6k 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
2k 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
3answers
959 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 ...
7
votes
1answer
658 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 ...
7
votes
1answer
534 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
1k 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
162 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
306 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
258 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
260 views

Is $H(k || m) \oplus k$ secure?

It is known that $H(k || m)$ (when using SHA1) is an insecure MAC function since it is vulnerable to hash length extension. But what about $H(k || m) \oplus k$? A normal hash length extension seems to ...
4
votes
1answer
205 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 ...
4
votes
1answer
432 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 ...
4
votes
1answer
198 views

Why are LMS and XMSS not candidates in the Post-Quantum Cryptography Standardization process?

Why are Leighton-Micali Signature Scheme (LMS) and eXtended Merkle Signature Scheme (XMSS) not candidates in the NIST Post-Quantum Cryptography Standardization process? Both are mentioned in the final ...
3
votes
1answer
128 views

Is NOTS a valid one time signature scheme?

I've just learn about NOTS, a quantum-resistant signature scheme based on hash functions that claims to have much shorter signature and key sizes. Is this signature scheme known to be secure? From ...
3
votes
1answer
758 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
945 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
550 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
4k views

Understanding example of ECDSA P256

I am new to cryptography, I found the below Example on a nice website, but I am not able to understand the most of the terms used (H:Hash, K:Random number,E=?, Kinv=?,Rx=?=RY?,R=Private key?,D?,S? ...
3
votes
2answers
852 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
74 views

What hash based digital signature algorithms exist that have reasonably small signature sizes?

What hash based digital signature algorithms exist that have reasonably small signature sizes? By reasonably small, I mean not much bigger than what you would get with a 256-bit ECDSA (which I ...
3
votes
1answer
215 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 ...
3
votes
1answer
447 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 ...
3
votes
1answer
61 views

How can a collision attack using MD5 be used to break WOTS

It is stated in Winternitz One time signature security that MD5 is not safe for Winternitz due to collision attack. Given that WOTS generates multiple, say 32 private keys then hashing them a number ...
3
votes
1answer
233 views

How does second pre-image attack on Merkle Signature Scheme work?

I understand that a second pre-image attack on the Merkle tree works by creating another Merkle tree using the intermediate nodes as the leaf nodes, and this will lead to the same root hash (public ...
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
67 views

Making WOTS+ public keys shorter

In WOTS+ — as described in section 3 of RFC 8391 — public keys, private keys and signatures all consist of $len$ strings with $n$ bytes each, where $len, n \in \mathbb{N}$. Is it safe to use the hash ...
3
votes
1answer
44 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
170 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
657 views

Are there any hash functions that are commutative yet secure for ordered lists?

I'm looking for a hashing function that can combine random numbers together in any order yet still find the same value. But it needs to be secure against hackers. The idea is if I'm hashing together: ...
3
votes
0answers
52 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
1answer
162 views

Mapping the hash of message to a point of elliptic curve for signature

Let the subgroup $G$ of elliptic curve constructed with point $P$ with prime order $q$ by $G=\langle P\rangle $. The $h(x)$ is a hash function. We want to map the hash of arbitrary message $m$ to a ...
2
votes
2answers
245 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
57 views

W-OTS+ one-wayness property

I am reading the "W-OTS⁺ – Shorter Signatures for Hash-Based Signature Schemes," by Andreas Hülsing, and I am stuck in understanding the success probability of an adversary, $\mathcal A$, against the ...
2
votes
1answer
605 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
864 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
1k 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
305 views

Is it possible to retrieve the original hash of a digital signature using a public key?

I am running a server that is receiving packets. Each packet is signed with an RSA 512 SHA-256 digital signature. I have a public key and exponent that I use to verify the digital signatures. I'm ...
2
votes
1answer
317 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
51 views

How do I construct the Fn family of functions of WOTS+ using SHA3?

From the WOTS+ paper: Furthermore, W-OTS+ uses a family of functions Fn : {f_k : {0, 1}^n → {0, 1}^n | k ∈ Kn} with key space Kn. The reader might think of it as a cryptographic hash function family ...
2
votes
1answer
43 views

Using XMSS with Blake2

Since XMSS only requires a 2nd preimage resistant hash function, is using Blake2 in XMSS possible? It is not in standard, but Blake2 seems to be faster than SHA256
2
votes
1answer
246 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
162 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
80 views

Is it more, or less, secure to use a different $F$ and $G$ for a Lamport signature?

A Lamport signature is made as follows: Alice stores $k_1, \cdots, k_{n'} \leftarrow K $ as her "private key", with one-way function $F: K\to V$, $n'>n$, and (easily enough) all $F(k_i)\...
2
votes
0answers
42 views

How can one-way hash functions in the signatures help by using same algorithm for encryption and signature verification?

I read some documents about digital signatures and one way hash functions, etc., but everything was too complicated and I don't have much experience in cryptography. Can anyone explain to me in a ...