# Tag Info

4

No. Cryptography alone cannot solve this problem. Solving this problem requires a combination of technical (e.g., cryptography, systems security) and non-technical (e.g., legal, regulatory, contractual) solutions. Even the technical part is not solely a cryptography question; it as much about systems security.

4

I think you don't quite understand how RSA signatures work (and why they are the size they are). When generating an RSA signature, we follow a two-step process: We take that hash of the message we're signing, and convert (and pad) it into an integer $M$ which is between 0 and $N$ (where $N$ is a large integer that specified by the RSA key) We use the RSA ...

3

There's an easy attack against public keys with $e=3$. Here's how it works; the attacker selects an arbitrary message $M$ that hashes to an odd value $H$ (or, more generally, a $H$ of the form $k8^n$ for odd $k$). Since half of the potential messages hash this way, this is not a severe limitation to the attacker. Then, the attacker looks for a perfect ...

3

I am not quite sure if I exactly get what you are looking for, but I'll give it a try. This answer refers to the original question before the edit I'm looking for some kind of crypto-based data structure that will allow me to produce a signature over a set of hashes such that I can verify that any of the hashes is in the set at a later point in time ...

3

The standard definition of existential forgery allows the adversary to ask and obtain the signature of any message she wants, and claim success if she can exhibit (with sizable odds) any acceptable (message, signature) pair, for any message for which she did not ask signature. Update: There is also strong existential unforgeability, where the adversary ...

2

By a counting or entropy argument, a technique as in the question can only provide moderate space savings compared to sending the list of hashes, unless we allow that a value appears to be in the set of hashes, when it really is not, much as if we truncated the hashes. Borrowing the notation in that other answer, assume there are $n\ge1$ distinct hashes in ...

2

I happened to see some similar question like this. The question mentioned about sending fake signature message. The method is like this: Find some random string R. Use the public key to encrypt the random string R, let the result be X. (R,X) is your signature pair.(Think backwards) When someone verifies the signature, he'll compare {R} with X which are ...

1

What you describe is a digital signature, which works using methods very similar to the one you suggest. Examples include elgamal-signature and RSA signature schemes (the second of which I would recommend you read). Digital signatures allow you to provide a public signature that 'proves' you provided the message. As the author, you would produce database ...

1

Ed25519 in the default implementation is malleable. It includes the public key $A$ in the hashed message, so it cannot be modified It includes $R$ in the hashed message, so it cannot be modified $S$ is encoded as a 256 bit. But since it's a scalar, $S^\prime = S + k \cdot l$ is equivalent to $S$ for any integral $k$ (where $l$ is the order of the subgroup, ...

1

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

1

Ok, lets look at the operations. Sign: $s = g * r^{f(t,m)} \pmod n$ This is an assignment. You compute $(g * r^{f(t,m)}) \mod n$ and assign the resulting value to $s$. If you have a multiplication $(a \cdot b) \mod n$, this is equal to $((a \mod n)\cdot (b \mod n)) \mod n$. See for instance here. Verification: $s^e = i * t^{f(t, m)} \pmod n$ This is no ...

1

A theoretical concept for that is covered by so called contract signing protocols. There are quite some research papers into this direction, such as the seminal paper and follow up works in the field of (optimistic) contract signing. For instance, this one or this one. Such protocols always involve a trusted third party, although this party might not be ...

1

I think destroying the private key and using a notary could be some kind of solution to that problem. Both Parties create a private and public key. The public keys are signed by a CA. Both parties sign the document with their private key. After signing the document both parties destroy their private key. After step 4 nobody can claim that he lost the ...

1

As already discussed by @fgrieu in his answer and myself in the comments of your question and his answer, the standard notion of security of digital signature schemes, namely (strong) existential unforgeability under adaptively chosen message attacks (UF-CMA), does not cover the case you are concerned about. At least for hash-then-sign signatures built ...

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