18

This table—of Ed25519 vs. the lattice-based post-quantum candidate Dilithium vs. SPHINCS+ variants at a comparable post-quantum security level, with a tradeoff between signature size and signing time—may help explain: \begin{equation*} \begin{array}{r|rr|rr|rr} \text{sig scheme} && \text{sig bytes} && \text{cycles to sign} \\ \hline \text{...


8

I see two problems with this idea. The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs). In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the ...


8

Yes, a stateless hashbased signature method called Sphincs was recently proposed. It works by having a moderately large Merkle tree (similar to what D.W. suggested), but instead of using Lamport or Winternitz one time signatures at the bottom, it uses a hash based few-time signature method; this allows an occasional collision at the very bottom of the tree. ...


8

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say). Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message. As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a ...


8

If the message is random each additional signature halves the security level. If the message is chosen by the attacker, two signatures (of messages where each bit differs) are enough for a complete break. A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer. So if ...


8

The major issue will be size difference. The size of ECDSA in bitcoin is much less than the Lamport Signature. For ECDSA in bitcoin The public key is only 33 Bytes (1 byte for prefix, and 32 bytes for 256-bit integer x) Signature is at maximum 73 bytes Whereas in Lamport Signature The public key is 512 numbers of 256-bit (total of 16KB) The Signature ...


8

As for the "foot-gun" issues with stateful hash-based signatures, it comes down to repeating state. Stateful hash-based signatures (XMSS, LMS) are moderately interesting (can be implemented with competitive signature generation time, and have a sum of public key and signature size which compares fairly well with other postquantum signature algorithms, based ...


7

Yes, there does happen to be such a scheme: the Lamport one-time digital signature. The basic idea of a Lamport signature is that the private key consists of a large number (say, 256) of pairs of secret random numbers, while the public key consists of the cryptographic hashes of those numbers. To sign a message, you first hash it down to 256 bits, and then,...


7

$w$ is a parameter that can be freely chosen, to maximize performance. Each element of the signature encodes $w$ bits of the message to be signed, so the larger $w$ is, the fewer elements you need to include in the signature. If you make $w$ large, then signatures can be shorter; however, the tradeoff is that key generation, signing, and verification run ...


6

Yes, they can be used for that purpose. The challenge in practice is exactly what you mentioned: if we're willing to trust number-theoretic assumptions, we usually don't need Lamport signatures. Nonetheless, they can be used in this way.


6

Use hash based cryptography. First, define a one way function F. It takes as input a small (10-16 byte) string and uses a secure hash function (EG:SHA2) to produce another string of the same size. We number each day from (Jan 1 2000) to (Jan 1 2100) with a number n (n=0 ... 36500) Each day is assigned a code. If the user has the code for a particular day, ...


6

No, use SHA256. If you look at https://bench.cr.yp.to/results-hash.html it seems that SHA256 would probably be the better choice concerning speed as well. Therefore I don't see a good reason to go with SHA-1.


6

W-OTS+ is stronger, as it makes weaker assumptions on the hash function. Let us take a rather extreme example, let us consider W-OTS and W-OTS+ based on the MD5 hash function. Now, the proof for W-OTS is quite invalid; it assumes that the hash function is collision resistant, and we know how to generate collisions with MD5. On the other hand, W-OTS+ based ...


6

Gravity-SPHINCS and SPHINCS+ are two different improvements of the original SPHINCS algorithm. Both change the few-time signature scheme HORST (used in SPHINCS) in slightly different ways. However, both are variations of HORST. This leads to variable length signatures for Gravity-SPHINCS and fixed length signatures for SPHINCS+ which are as long as the ...


6

Most of this was already explained in the comments but let me summarize this. a) SPHINCS+ as SPHINCS are stateless signature schemes like RSA or (EC)DSA. You can use the secret key to sign a virtually unlimited number of messages. In practice, you can sign up to $2^{64}$ messages with SPHINCS+ ($2^{50}$ for SPHINCS) without allowing any kind of forgery. ...


5

There are few papers like XMSS that try to lower the requirement from collision resistant hash function to second-preimage hash function by introducing bit mask. Actually, that's not why XMSS has the bit masks; as you point out, second preimage resistance is essentially all you need for hash based signatures to be secure; the attacker needs to find a ...


5

So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme. Actually, Sphincs as originally proposed is deterministic; however there is nothing preventing a signer from selecting a path randomly (rather than making it a secret function of the message). But yes, if we assume ...


4

Though this question is fairly old, there is still no accepted answer. Hence, let me try to clarify this. The W-OTS scheme that your talking about was proposed by Ralph Merkle in his 1979 paper as an improved version of the Lamport-Diffie OTS to reduce the size of signatures. Instead of a "per-bit-signature", Merkle proposed to sign multiple Bits at once. ...


4

Yes, it makes sense to truncate the hash to 128 bits. The security proof actually says that if finding a preimage for F requires effort $2^{n}$, then breaking the Lamport signature scheme with $G$ having k-bit digests requires effort $2^{n}/2k$. So strictly speaking, with $F$ truncated to 128 bits and $G$ having 256 bits $(2k=512=2^{9})$, you will have $128-...


4

As I already outlined in this answer, hash trees in combination with any one-time signature scheme gives the so called Merkle signature scheme. I assume there is some misunderstanding and therefore I sketch merkle signatures subsequently: The idea is to produce $n$ key pairs $(X_i,Y_i)$ of a one-time signature scheme and then to take the hash values $g(Y_i)$...


4

There is one such signature scheme designed specifically for cryptocurrencies: https://bitcointalk.org/index.php?topic=1129388.0 It is based on ECDSA and works by committing to $k$ (a number used to create the signature, see https://en.wikipedia.org/wiki/ECDSA) in advance by making $k$ x $G$ part of public key. If this key is used for a second time, $k$ ...


4

You might want to check the literature on (offline) schemes for electronic cash, where they have devised schemes where spending the same coin twice results in de-anonymizing the double-spender. I'm not immediately sure whether it will apply directly to your problem, but I think it might be possible to apply their techniques to your setting.


4

As D.W. notes, this works for the purpose in question. Actually, relying on number theoretic assumptions for the accumulators will give you no benefit as you have observed. However, here is a construction of accumulators from Nyberg in FSE'96, which does not rely on number theoretic or any computational assumptions. This is the paper of Nyberg and you may ...


4

There are actually quite a few of these. Interest has been raised on this topic mainly due to the "post-quantum" security of such schemes. Also, Lamport is only a one-time signature, and we want a full-blown signature schemes. For just one example see, SPHINCS: https://sphincs.cr.yp.to/sphincs-20150202.pdf.


3

HORS (Hash to Obtain Random Subset) is a simple few-time signature scheme with smaller signatures than BiBa. Let $f$ be a one-way function and $H$ be a hash function that outputs a random size $k$ subset of $\{1,2,...,t\}$, where $k$ and $t$ are parameters that affect security with $k < t$. The signing key is a random tuple $(s_1,...,s_t)$, and the ...


3

You could, indeed, form a Merkle tree where each internal node is formed from the hash of 3 (or more) lower level nodes. However, because it hurts signature size (which is the main expense of Merkle trees), we never do it. In a Merkle signature, we reveal the preimage to the leaf node (which may involve a Winternitz signature), and also the authentication ...


3

(Q1) Assuming that you talk about the size of the secret key elements which equals the input size of the OWF when you talk about the "input", this should be at least as much as the output size. Consider a function $f: \{0,1\}^m \rightarrow \{0,1\}^n$.The thing to worry about when you choose $m < n$ is a brute force search for a preimage, which in this ...


3

Ed25519 or more general the EdDSA (Edwards-curve Digital Signature Algorithm) approach can be considered as a variant of ElGamal signatures (such as Schnorr or DSA). They all are signatures following the hash-then-sign approach. This simply means that you can sign arbitrary length messages by hashing them to a constant size string using a secure ...


3

It seems they can be used for that purpose. I found this paper: "Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees" Niko Baric and Birgit Pfitzmann Eurocrypt '97, LNCS, Springer-Verlag, Berlin 1997.


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