89

Assuming you are asking about public-key signatures + public-key encryption: Short answer: I recommend sign-then-encrypt, but prepend the recipient's name to the message first. Long answer: When Alice wants to send an authenticated message to Bob, she should sign and encrypt the message. In particular, she prepends Bob's name to the message, signs this ...


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{...


13

It depends on your requirement, If you Sign-then-encrypt then only receiver can decrypt and then verify . If encrypt-then-sign then anybody can verify the authenticity and only receiver can decrypt it . But in practice, both are not enough , ideally We have to sign-encrypt-sign , am not able to recollect the paper which discusses this There is one ...


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

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

$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 ...


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,...


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

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

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

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

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

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.


4

That's insecure. In BLS signatures: for private key $x$ and public key $X = xP$, the signature is computed as $T = xS$, and the verification checks if $e(T, P) = e(S, X)$, which works because: $e(T, P) = e(xS, P) = e(xS, P) = e(S, P)^x$ $e(S,X) = e(S, xP) = e(S, P)^x$ If you know that $S = kP$, then you can forge a signature for a message with hash $k'$ ...


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

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 ...


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