| Application RC | One-time signatures |
Partial one-time-signature chains
There are two libsodium primitives that are relevant at this level, key derivation and generic hashing. The key derivation function takes a master key and a 64 bit index, and produces a sub-key. In a later post we will look at index-space allocation in detail, for now just know the key derivation function is used to produce two secret keys for signing a small number of bits in a one-time signature construct. It is also used to produce a level-key-wide salt that is to be used as key with all generic hashing function invocations.
Now for our example, shown in the image above, we have taken the number 3 as our otsbits parameter. This means we will be signing three bits at a time. Three bits that need to be signed together can have any value from zero up to seven, and these numbers are depicted in the image above. Not that if we were to sign 10 bits at a time, the chains would be 1024 operations high. Each additional bit doubles the height of the OTS chains. But in our example to make things visualizable, we sign only 3 bits at a time. In this case we sign the bits 011, that as a number depicts the value 3.
So how is the signature made?
- The secret-up value is hashed (salted) 3+1, 4 times, this is the up part of the signature
- The secret-down value is hashed (salted) 2^otsbits - 3, 5 times, this is the down part of the signature.
Now, when the other side needs to validate the signature, (s)he completes the chain in order to create the pub-up and pub-down values.
- The up part of the signature is hashed an additional 2^otsbits-(3+1), 4 times to create the pub-up value.
- The down part of the signature is hashed an additional 3 times to create the pub-down value.
So why are we using an up and a down chain, when it seems that a single chain would suffice?
Well, imagine we only had the up chain, and imagine there is a man in the middle trying to do some nasty stuff. Imagine Mallet has a collection of hundreds of thousands of transactions ready that she would want Alice to sign. Most of the time Mallet as Man In The Middle, won't be able to do much, but every once in a while, the digest of the transaction Alice does might have a lot of 3 bit groups in the lower end of the spectrum.
Say the digest in groups of 3 bits looks something like:
- 1-7-4-2-0-3-0-1-1-5-3-0-0-1
Now imagine, using the salt provided, Mallet has a transaction that has a digest that looks like this:
- 4-7-5-5-2-3-6-4-2-7-5-5-2-4
Mallet will have all the information needed from the signature of the first, to create a valid Alice signature for the second.
The down-chain prevent such man in the middle attacks. It does this in a more conservative way than XMSS, the hash-based-signatures used by QRL, does. That means coinZdense signatures will be bigger and slower than XMSS signatures for the reason that the author really doesn't want to use CRC for security. Maybe I'm being too paranoid as XMSS has been widely reviewed by experts, it is better t be safe than sorry.
For the receiver to be able to do anything with the calculated value, the signing party will have to have created and shared some public key. The pub-up and pub-down public key chunks aren't meant for imediate sharing, but, as we will see in later posts, will get used to create a multi-signature level-key level signing key. For now just know that the sender will need to derive pub-up and pub-down values for each OTS chunk level private keys.
- Hash secret-up 2^orsbits times to get pub-up
- Hash secret-down 2^otsbits times to get pub-down
So far the partial one-time-signature chains. In the next post we are going to be looking at how a set of these combine into a one-time signature big enough to sign exactly one transaction.
| Application RC | One-time signatures |
|
|
|