(Draft)
Santi J. Vives Macallini
@jotasapiens
http://jotasapiens.com
Keywords: signatures, hash, postquantum, cryptography.
In this paper we will introduce ic, a family of one-time, hash-based, digital signatures.
The family shows improvements over previous hash-based schemes like wots (Winternitz one-time signatures). Some of the advantages are:
A more efficient size/cost trade-off, allowing for signatures of the same size with less computational cost (fewer hash functions evaluations) or a similar cost with a signature of smaller size.
Verification in constant time and signing in nearly constant time.
Resistance against forgery without the need for checksums.
Tweakable parameters, that make the signature tunable to a large range of uses:
Unlike wots, whose w parameter only leads to signatures of various (but limited) signature lengths, the size of the signatures can by adjusted to an arbitrary number of output hashes L (length).
In addition to compression, the ic family allows for expansion to reduce the cost of signing and verifying.
The signature can be tuned for fast verification, fast signing, and values in between.
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 is encoded as a list fm w-bit numbers. The parameter w determines the compression level of the signature. The one-way function is iterated over the first numbers in the private key v, a number ot times determined by fm.
Once the signature is published, all values at higher levels (those between fm and the public key) become known. To avoid an attacker from forging a signature, a checksum of the signature is needed. The checksum is computed in a similar way as the main part of the signature.
To verify, the iterations remaining to reach the higher level are applied to the main part to the checksum. The result is compared against the public key p.
An ic signature represents each message as an integer composition of an integer N. That is, one of the many ways an integer N can be written as a sum of parts, taking into account the ordering of the parts. For example, the tuples (2, 2, 2, 2), (4, 2, 1, 1), (1, 2, 2, 3) and (3, 2, 1, 2) are distinct compositions of the integer 8.
Similarly to wots, the parts in the composition are used to determine the number of iterations of the one-way functions. But a difference arises: since the composition requires that their parts add up to N (as seen in the graph), a higher level in any of the parts results in a lower level in at least another.
An attacker can no longer forge a signature from the values of a known message without breaking the one-way function. This eliminates the need for a checksum, leading to a smaller, faster signature.
The ic family of signatures uses compositions that are length-restricted (with a fixed number of parts), and alphabet-restricted, with parts taking values from an alphabet 0, 1, 2, ..., zeta.
In the different sections of this paper, we will:
describe a method to transform the hash of a message into a restricted composition, which is equivalent to picking a composition uniformly at random from the set of all possible compositions (2.3, 2.4, 2.5)..
describe the signature scheme based on restricted integer compositions. (2.2, 2.3, 2.4).
describe methods for finding optimal constants, that minimize the number of hash evaluations for diferrent uses (2.1).
compare various types of ic signatures, showing that the family can be tweaked to outperform wots verification, signing or both (4.).
The ic signature takes 3 main parameters: bits, length and type.
An ic signature with parameters (bits, length) is a one-time signature of size=length, capable of signing at least 2bits distinct messages.
(Optimal for fast verification)
Given the parameters bits and length:
(Approximately optimal for verifying, while being faster at keys creation and signing)
Given the parameters bits and length, and a tolerance value:
(Minimal keys creation time, at the expense of greater signing time)
Given the parameters bits and length:
(Optimized for fast keys creation and signing)
Given the parameters bits and length:
(Optimal for fast keys creation and signing. Inverse mode)
Given the parameters bits and length:
Given the parameter length and the constant N:
Given M:
Given a one-way function hashUp with output size bits:
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 zeta iterations of the one-way function hashUp:
pub = pub0, pub1, pub2,..., publength - 1
pubn = hashUp (privn, iterations=zeta)
Publish the list pub as the public key.
Compute the hash value h of the message:
h = hashA (message)
Given a counter n = 0, 1, ...
Compute the list ups, as needed for signing:
ups = ups0, ups1, ..., upslength-1
Where each upsn is given by:
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.
Compute the #m restricted composition of N, using the auxiliary function compR:
c = compR (N, length, i=m)
Check that no part in c is bigger than zeta:
max (c) <= zeta
Compute the list ups (for verification):
ups = ups0, ups1, ..., upslength-1
Where each upsn is given by:
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, 5 and 8) evaluate to true, invalid otherwise.
(Transforms and integer m in the range [0, M) into a length-restricted composition of N)
Given the constants N, length and an integer m:
Given a number and a list of bases b:
R (N, L) is the number of integer comps of N, with length L and alphabet 0, 1, 2, ..., N
Given the parameter L and N:
R (N, L, z) is the number of integer comps of N, with length L and alphabet 0, 1, 2, ..., z
For a given z, the integer R (N, L, z) can be computed iteratively. To do so, we will define the special cases L=1, N=0, and a method to compute R for each L = 2, 3, ... from its previous value L-1:
R (N, 1, z) = 1
for any value of N, z.
R (0, L, z) = 1
for any value of L, z.
R (N, L, z) = sum R (n, L-1, z), for n = s0 ... s1
where:
p0 = max (0, N - z * (L- 1))
p1 = min (z, N)
s0 = N - p1
s1 = N - p0
For a given L, z pair, N can take values in the range [0, z*L+1).
The table shows computed N, zeta values for parameter bits=256, with various lengths and types.
(bits=256)
length | type 'v' | type 'a' | type 's' | type '1/s' |
---|---|---|---|---|
20 | N=90189
zeta=41972 |
N=91541
zeta=18786 |
N=120841
zeta=12105 |
N=109440
zeta=12348 |
24 | N=21126
zeta=7730 |
N=21442
zeta=3707 |
N=28017
zeta=2369 |
N=25613
zeta=2419 |
28 | N=7796
zeta=2316 |
N=7912
zeta=1183 |
N=9903
zeta=755 |
N=9316
zeta=773 |
32 | N=3786
zeta=962 |
N=3842
zeta=507 |
N=4613
zeta=326 |
N=4432
zeta=334 |
40 | N=1437
zeta=318 |
N=1458
zeta=157 |
N=1665
zeta=103 |
N=1621
zeta=106 |
48 | N=778
zeta=112 |
N=789
zeta=72 |
N=868
zeta=49 |
N=857
zeta=50 |
56 | N=510
zeta=67 |
N=517
zeta=42 |
N=557
zeta=29 |
N=549
zeta=30 |
64 | N=375
zeta=45 |
N=380
zeta=28 |
N=409
zeta=19 |
N=401
zeta=20 |
To evaluate the scheme we will take into account the cost of signing and verifying, given by the number of hash evaluations. The cost of verification is given by Wv, and the cost of signing corresponds to the added costs Wc and Ws (the cost of finding a valid composition, and the cost of computing the signature from the private key):
Wv = N
Ws = N * (zeta - 1)
Wc = R (N, length) / R (N, length, zeta)
The following table compares the cost of keys creation for 256-bit ic signatures with length=28 and various types. Costs of wots+ are shown for comparison.
(bits=256)
length (bits) | signing | verifying | |
---|---|---|---|
ic (type='v') | 7424 bits | 57.1 msh | 7.8 msh |
ic (type='a') | 7424 bits | 25.2 msh | 7.9 msh |
ic (type='s') | 7424 bits | 10.5 msh | 9.9 msh |
wots+ | 7424 bits | 14.3 msh | 14.3 msh |
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 ic family of signatures. The code can be found at: