2
$\begingroup$

Suppose we had a decentralized log of messages, i.e., an ever-growing array of information on which anyone could append arbitrary data to. Given such primitive, could a party broadcast authenticated messages using just hash functions? Here is what I have in mind:

1. Register

To start submitting authenticated messages, one must first introduce himself by logging an unsigned message:

pvtKey = uint256.random() // random 256-bit string
pubKey = hash256(pvtKey)  // 256-bit hash function
LOG("REG" + pubKey)

In other words, just logg the hash of the private key. User then waits the LOG above to be globally confirmed (i.e., permanently and irreversibly stored on the decentralized log; that'd be 6 block confs if using Bitcoin, for example).

2. Prepare a message

Before submitting a message, the user must prepare it as follows:

newPvtKey = uint256.random()
newPubKey = hash256(newPvtKey)
msg = "some arbitrary string"
pre = hash256(pvtKey + newPubKey + msg)
LOG("PRE" + pre)

User then waits the log above to be globally confirmed.

3. Submit the message

LOG("SUB" + pvtKey + newPubKey + msg)

Now, every user takes hash256(pvtKey + newPubKey + msg). This is found to be equal to pre, as submitted on the 2nd log. Every user then takes hash256(pvtKey), which is equal to pubKey, as submitted on the 1st log. Every user then concludes the owner of the first pubKey signed msg. To sign a new message, the user repeats steps 2 and 3 using his new pub/pvt key pairs.

Does this scheme work?

|improve this question
$\endgroup$
  • $\begingroup$ Since the hash-function you specified seems to output 128 bit, a collision would occur after $2^{64}$ public key, which would automaticly reveal a possible secret key if the old hash has already been used to sign something. $\endgroup$ – VincBreaker Apr 24 '18 at 19:45
  • $\begingroup$ @VincBreaker that's right. Will it work with 256 bits? I've edited the post. $\endgroup$ – MaiaVictor Apr 24 '18 at 20:35
  • $\begingroup$ Given that you use a cryptographic secure hash function, you will be able to create $2^{128}$ (or $2^{n/2}$ in for an $n$ bit-hash-function) which seems reasonable to me. But at this point, the SUB-step alone uses 512 bit for the signature which is similar to EdDSA or similiar algorithms, which won't require the commitment step making them faster while using less space. $\endgroup$ – VincBreaker Apr 24 '18 at 21:03
  • $\begingroup$ However, your scheme seems to be quantum-computer-resistant (AFAIK), which (most of) ECC is not. $\endgroup$ – VincBreaker Apr 24 '18 at 21:05
  • $\begingroup$ @VincBreaker ok, thank you! Having a size similar to ECDSA, lower processing time and quantum-resistance at the cost of longer waits seems like a good tradeoff for my use case. Specially considering the alternative (Lamport sigs) would has huge sizes. $\endgroup$ – MaiaVictor Apr 24 '18 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.