Score:0

Can we use symmetric/hashing functions to sign messsages as a quantum-proof replacement of public-private key signing?

in flag

Public-private key signing generally works like this:

  1. I announce my pubic key.
  2. I encrypt something with my private key.
  3. If people managed to decrypt (2) with (1) then (2) is from the owner of (1).
  4. People then can encrypt things to me using the public key in (1).

Signing can also be done using hashing or symmetric cipher algorithms, but the verification happens when the person publishes his old random secret.

Hashing function signing:

  1. I encrypt some standard message, e.g. 0, using a randomly generated key $k_r$. E.g. $c_1 = enc(\text{`0`}, k_1)$.
  2. I send $c_1$ to people alongside my normal messages.
  3. Receivers won't know if (2) is me, until I send a another message and alongside it I give them $k_1$ that can decrypt $c_1$ to bring 0 back. Alongside this, I will send a new $c_2$.

Not sure if there is a chicken and egg problem. E.g. in a signing party where people exchange their public-private keys, they can, instead, exchange their encrypted 0 messages (i.e. $c_1$ in this example).

But what's not clear to me is how can such a thing work for other cases, such as a method for signing payments or transactions. E.g. imagine if Bitcoin addresses were hashing/symmetric-cipher signatures like $c_1$, $c_2$, etc, instead of public keys.

I see that hashing/symmetric signing needs extra housekeeping (e.g. have a copy of latest $c_i$). But if such house keeping is resolved, is there any reason why it cannot replace public-private keys for all tasks?

Score:3
my flag

Public-private key signing generally works like this

No, it doesn't. RSA can be viewed this way (if you stay at the 10,000 foot level); however a) using the same key to both sign and decrypt is not encouraged, and b) RSA is essentially the only signature algorithm that can be described this way.

However, that doesn't address your real question:

Hashing function signing

Well, you didn't describe it properly - for one, there's nothing to tie the message to the revealed key value. That is, someone could modify the message in flight, and the key value would still check out.

What Lamport is generally understood as:

  • We pick $k$ hash preimages $c_1, c_2, ..., c_k$, and hash each of them, and publish the result of each hash $H(c_1), H(c_2), ..., H(c_k)$ as the public key

  • When we get the message to sign, we convert the message into a series of values $b_1, b_2, ..., b_n$ (each value between $1$ and $k$) - this conversion is done in such a way that it is hard to find a second message that converts into a series of bits that consist solely of the values within $b_1, b_2, ..., b_n$).

  • The signature consists of the revealed preimages $c_{b_1}, c_{b_2}, ..., c_{b_n}$

  • The verifier can take the message and convert it into a series of values $b_1, b_2, ..., b_n$, and verify that each of the preimages in the signature hashes to the value within the public key.

It should be easy to see that forging a signature would require either a) finding a message that converts into values that are all revealed in the good signature (which we assumed was hard), or b) finding a preimage for a value that was not revealed (which we also assume is hard).

That said, your question really was:

I see that hashing/symmetric signing needs extra housekeeping

Well, Lamport is useful only if you need to sign a single message with a public key. When you look at blockchain (where we assume that the verifier an see all the signatures, and we can include the next public key in with the signature (and have the message being signed include the next public key, of course), this can work - it does, as you point out, require us to remember the next public key (which will change for every signature), but it's doable.

In many other contexts, this doesn't work. However, there are a number of modifications to hash based signatures that don't have these limitations:

  • Stateful hash based signatures (such as LMS and XMSS); these work like Lamport, except that a public key can sign a large number of different messages (and we can make this 'large number' larger than the number of messages we'll ever see). They do have the requirement that the signer keep track of state (which changes with every signature)

  • Stateless hash based signatures (such as Sphincs+); this eliminates the need to track any state while signing, and so acts just like any other signature algorithm

And, if you assume that RSA and hash based signatures are the only options on the table, well, they're not. There are also various lattice based schemes, multivariate schemes, zero-knowledge proof based schemes (Picnic) - there are a number of various options out there.

caveman avatar
in flag
Thanks a lot. Not sure if related, but, any idea why we don't have such crypto currencies that completely get rid of public-private/asymmetric signing in favour of such hash-based alternatives?
poncho avatar
my flag
@caveman: I have not specifically heard of any; however, you would be astonished about how much I do not know about cryptocurrencies...
my flag
Jon
@caveman Capitalisk https://capitalisk.com/ uses Lamport OTS signatures with Merkle Signature Trees to allow multiple signatures.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.