(Draft)
Santi J. Vives Macallini
@jotasapiens
http://jotasapiens.com
Keywords: signatures, hash, postquantum, cryptography.
In this paper we will introduce uwots, a family of one-time, hash-based, digital signatures. Uwots is an optimized, tweakable generalization of the Winternitz signature scheme.
In a wots scheme, the signer picks n numbers uniformly at random to create the private key v (at the bottom of the graph).
Then, a (keyed) one-way function is iterated over each of the numbers at the bottom to compute the public key p at the top. The one-wayness of the function ensures the values at a lower level cannot be computed from a higher one.
In order to sign, the hash of a message and a checksum are encoded as a list f, composed of n w-bit numbers. The parameter w determines the compression level of the signature. The one-way function is iterated over each part of the private key v, a number ot times determined by f.
To verify, the iterations remaining to reach the higher level are applied to the signature. The result is compared against the public key p.
In the case of uwots, we encode the message and the checksum as mix-radix numbers instead. The different bases result in different (unbalanced) levels for different parts of the signature, as seen in the graph.
In the different sections of this paper, we will:
describe the mix-radix (unbalanced) generalization of the Winternitz one-time signature scheme (2.2, 2.3, 2.4).
describe a method for finding optimal parameters, that minimize the number of hash evaluations (2.1, 3.).
show that the optimal parameters within the generalized form outperform wots, leading to signatures of the same size and reduced cost. (4.)
Uwots takes 2 parameters: Lp and bits.
An uwots signature with parameters (Lp, bits) is a one-time signature of length=Lp (measured in hash outputs), capable of signing at least 2bits distinct messages.
Given the parameter Lp and a bits:
List all the ways sn that an integer Lp can be split in two parts: a main part LAB and a checksum LCD:
s = (1, Lp-1), (2, Lp-2), (3, Lp-3), ..., (Lp-2, 2), (Lp-1, 1)
sn = (LAB, LCD)
For each sn = (LAB, LCD):
Pick the sn value with the minimal cost W.
Return the constants (LA, LB, LC, LD), (bA, bB, bC, bD) and (zA, zB, zC, zD) corresponding to the sn value we picked in step 3.
The constants Ln, bn, bn are expanded into the lists baseAB, baseCD, zetaAB, zetaCD, zeta as following:
Define list (c, length) as a list with length copies of the element c. For example:
list (1, length=4) = 1, 1, 1, 1
Define the lists baseAB, baseCD, zetaAB, zetaCD and zeta as following:
baseAB = list (bA, length=LA) || list (bB, length=LB)
baseCD = list (bC, length=LC) || list (bD, length=LD)
zetaAB = list (zA, length=LA) || list (zB, length=LB)
zetaCD = list (zC, length=LC) || list (zD, length=LD)
zeta = zetaAB || zetaCD
Given (LA, LB) and (bA, bB):
Compute M:
M = bA ^ LA * bB ^ LB
Define the output size mbits of the one-way functions hashA and hashB:
mbits = len (binary (M - 1))
Generate the private key by picking numbers (with size=bits) uniformly at random:
priv = priv0, priv1, priv2,..., privlength-1
privn = urandom (bits)
For each privn, apply zetan iterations of a one-way function hashUp with output size bits:
pub = pub0, pub1, pub2,..., publength-1
pubn = hashUp (privn, iterations=zetan)
Publish the list pub as the public key.
Given a message and a private key priv:
Compute the hash value h of the message.
h = hashA (message)
Given a counter n = 0, 1, ...
Represent m as a mix-radix number with bases baseAB:
uAB = mixradix (m, baseAB)
Compute the downs values dABn from each uABn value:
dAB = dAB0, dAB1, ..., dABLA+LB-1
dABn = zetaABn - uABn
Compute the checksum, given by:
check = sum (dAB)
Represent check as a mix-radix number with bases baseCD:
uCD = mixradix (check, baseCD)
Compute the downs values dCDn from each uCDn value:
dCD = dCD0, dCD1, ..., dCDLC+LD-1
dCDn = zetaCDn - uCDn
Define the ups list (needed for signing) as the concatenation of the two lists dAB and dCD:
ups = dAB || dCD
Apply upsn iterations of the one-way function hashUp to each privn in priv:
f = f0, f1, ..., flength-1
fn = hashUp (privn, iterations=upsn)
Publish (f, n) as the signature.
Given a message, a signature (f, n) and a public key pub:
Compute the hash value h of the message.
h = hashA (message)
Compute the hash value m of the message.
m = hashB (n || h)
Check that m < M.
Represent m as a mix-radix number with bases baseAB:
uAB = mixradix (m, baseAB)
Compute the downs values dABn from each uABn value:
dAB = dAB0, dAB1, ..., dABLA + LB - 1
dABn = zetaABn - uABn
Compute the checksum, given by:
check = sum (dAB)
Represent check as a mix-radix number with bases baseCD:
uCD = mixradix (check, baseCD)
Define the ups list (needed for verification) as the concatenation of the two lists uAB and uCD:
ups = uAB || uCD
Apply upsn iterations of the one-way function hashUp to each fn:
t = t0, t1, ..., tlength-1
tn = hashUp (fn, iterations=upsn)
Check that t == pub.
The signature is valid if all test (steps 3 and 10) evaluate to true, invalid otherwise.
Given a number and a list of bases b:
The table shows computed L, z values for parameters bits=256 and various lengths Lp.
L = LA, LB, LC, LD
z = zA, zB, zC, zD
Other constants can be derived easily from them:
bn = zn + 1
M = bA ^ LA * bB ^ LB
(bits=256)
length | L | z |
---|---|---|
16 | (15, 0, 1, 0) | (137270, 137269, 2059049, 2059048) |
20 | (8, 10, 2, 0) | (19112, 19111, 586, 585) |
24 | (10, 12, 2, 0) | (3183, 3182, 264, 263) |
28 | (12, 14, 2, 0) | (920, 919, 154, 153) |
32 | (16, 14, 1, 1) | (370, 369, 105, 104) |
40 | (26, 12, 1, 1) | (106, 105, 63, 62) |
48 | (17, 29, 1, 1) | (47, 46, 46, 45) |
56 | (40, 14, 1, 1) | (26, 25, 37, 36) |
64 | (21, 40, 1, 2) | (18, 17, 10, 9) |
80 | (2, 75, 3, 0) | (10, 9, 8, 7) |
96 | (82, 10, 4, 0) | (6, 5, 4, 3) |
112 | (20, 88, 3, 1) | (5, 4, 4, 3) |
128 | (25, 99, 2, 2) | (4, 3, 4, 3) |
160 | (25, 130, 2, 3) | (3, 2, 3, 2) |
192 | (120, 66, 4, 2) | (2, 1, 2, 1) |
224 | (67, 150, 2, 5) | (2, 1, 2, 1) |
256 | (12, 237, 2, 5) | (2, 1, 2, 1) |
To evaluate the scheme we will take into account the cost of keys creation W, given by the hash evaluation needed to go from the private key to the public key. The cost W equals the costs of signing and verifying combined, and can be computed from the equation:
W = La * zA + LB * zB + LC * zC + LD * zD
The following table compares the cost of keys creation for 256-bit uwots and wots+ signatures of the same size. Notice that the performance improvement tends to increase as the signatures get smaller (more compressed).
(bits=256)
L | length (bits) | uwots | wots+ | relation |
---|---|---|---|---|
20 | 5376 bits | 345.18 msh | 655.34 msh | 52.7% |
22 | 5888 bits | 143.37 msh | 180.20 msh | 79.6% |
28 | 7424 bits | 24.21 msh | 28.64 msh | 84.5% |
39 | 10240 bits | 4.57 msh | 4.95 msh | 92.3% |
55 | 14336 bits | 0.15 msh | 0.17 msh | 89.7% |
For reference, a msh equals 1 ms, assuming a computer performing 1 million hash iterations per second. The length in bits includes the size of a salt (or seed), used to randomize the hash functions.
A python implementation is provided to further illustrate the uwots family of signatures. The code can be found at: