Integer Composition Signatures

(Draft)

Santi J. Vives Macallini
@jotasapiens
http://jotasapiens.com


Abstract: We introduce integer composition signatures (ic): a hash-based family of one-time signatures. The family shows improvements over previous schemes like Winternitz: less costly/shorter signatures, verification in constant time, and tweakable parameters allowing optimization for either signing/verifying.

Keywords: signatures, hash, postquantum, cryptography.

1. Introduction

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:

1.1 Concepts

Winternitz One-Time Signatures (wots)

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.

Integer Composition Signatures (ic)

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:

2. Description of the algorithm

2.1 Parameters and constants

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.

Type 'v' constants

(Optimal for fast verification)

Given the parameters bits and length:

  1. Using the auxiliary function R, find the smallest integer N that satisfies:
    R (N, length) >= 2bits
  2. Find the smallest integer zeta that satisfies:
    R (N, length, zeta) >= 2bits
  3. Return the constants (N, zeta) as the result.

Type 'a' constants

(Approximately optimal for verifying, while being faster at keys creation and signing)

Given the parameters bits and length, and a tolerance value:

  1. Find the smallest integer N' that satisfies:
    R (N', length) >= 2bits
  2. Compute N:
    N = N' * (1 + tolerance / 100)
  3. Find the smallest integer zeta that satisfies:
    R (N, length, zeta) >= 2bits
  4. Return the constants (N, zeta) as the result.

Type 'zmin' constants

(Minimal keys creation time, at the expense of greater signing time)

Given the parameters bits and length:

  1. Define the function n (z) as the smallest integer n satisfying:
    R (n, length, z) >= 2bits
  2. Find the smallest integer zeta that satisfies:
    R (n(zeta), length, zeta) >= 2bits
  3. Define N:
    N = n(zeta)
  4. Return the constants (N, zeta) as the result.

Type 's' constants

(Optimized for fast keys creation and signing)

Given the parameters bits and length:

  1. Define the cost function W (nz, nn, nr):
    wk = nz * length
    ws = nz * length - nn
    wc = R (nn, length) / nr
    W (nz, nn, nr) = wk + ws + wc
  2. Define the function n (z) as the smallest integer n satisfying:
    R (n, length, z) >= 2bits
  3. Define the function r (z) as:
    r (z) = R (n(z), length, z)
  4. Find the smallest integer zeta that satisfies:
    W (zeta, n(zeta), r(zeta)) < W (zeta+1, n(zeta+1), r(zeta+1))
  5. Define N:
    N = n(zeta)
  6. Return the constants (N, zeta) as the result.

Type '1/s' constants

(Optimal for fast keys creation and signing. Inverse mode)

Given the parameters bits and length:

  1. Define the cost function W (nz, nn, nr):
    wk = nz * length
    w1/s = nn
    wc = R (nn, length) / nr
    W (nz, nn, nr) = wk + w1/s + wc
  2. Define the function n (z) as the smallest integer n satisfying:
    R (n, length, z) >= 2bits
  3. Define the function r (z) as:
    r (z) = R (n(z), length, z)
  4. Find the smallest integer zeta that satisfies:
    W (zeta, n(zeta), r(zeta)) < W (zeta+1, n(zeta+1), r(zeta+1))
  5. Define N:
    N = n(zeta)
  6. Return the constants (N, zeta) as the result.

M and mbits constants

Given the parameter length and the constant N:

  1. Set the variable r:
    r = 1
  2. For n = 1, 2, .., length:
  3. Return M = r as the result.

Given M:

  1. Define the output size mbits of two one-way functions hashA, hashB:
    mbits = len (binary (M - 1))

2.2 Keys creation

Given a one-way function hashUp with output size bits:

  1. Generate the private key by picking numbers (with size=bits) uniformly at random:
    priv = priv0, priv1, priv2,..., privlength - 1
    privn = urandom (bits)

  2. For each privn, apply zeta iterations of the one-way function hashUp:
    pub = pub0, pub1, pub2,..., publength - 1
    pubn = hashUp (privn, iterations=zeta)

  3. Publish the list pub as the public key.

2.3 Signing

  1. Compute the hash value h of the message:
    h = hashA (message)

  2. Given a counter n = 0, 1, ...

  3. Compute the list ups, as needed for signing:
    ups = ups0, ups1, ..., upslength-1
    Where each upsn is given by:

  4. Apply upsn iterations of the one-way function hashUp to each privn in priv:
    f = f0, f1, ..., flength - 1
    fn = hashUp (privn, iterations=upsn)

  5. Publish (f, n) as the signature.

2.4 Verification

Given a message, a signature (f, n) and a public key pub:

  1. Compute the hash value h of the message:
    h = hashA (message)

  2. Compute the hash value m of the message
    m = hashB (n || h)

  3. Check that m < M.

  4. Compute the #m restricted composition of N, using the auxiliary function compR:
    c = compR (N, length, i=m)

  5. Check that no part in c is bigger than zeta:
    max (c) <= zeta

  6. Compute the list ups (for verification):
    ups = ups0, ups1, ..., upslength-1
    Where each upsn is given by:

  7. Apply upsn iterations of the one-way function hashUp to each fn:
    t = t0, t1, ..., tlength - 1
    tn = hashUp (fn, iterations=upsn)

  8. Check that t == pub.

  9. The signature is valid if all test
    (steps 3, 5 and 8) evaluate to true, invalid otherwise.

2.5 Auxiliary functions

compR

(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:

  1. Represent the integer m as a mix-radix number with bases b:
    b = N+length-1, N+length-2, ..., N-1
    d = mixradix (m, bases=b)
  2. Create the tuple p:
    p = (p0)
    p0 = N + length (d)
  3. For each dn in d:
  4. Return the tuple p as the result.

mixradix

Given a number and a list of bases b:

  1. Set the variable n:
    n = number
  2. Create the empty tuple r:
    r = ()
  3. For each blast, .., b1, b0:
  4. Return r as the result.

R (N, L)

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:

  1. Set the variable r:
    r = 1
  2. For n = 1, 2, .., L:
  3. Compute:
    r /= factorial (L - 1)
  4. Return r as the result.

R (N, L, z)

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:

3. Table of N, zeta constants

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

4. Evaluation

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.

5. Source code

A python implementation is provided to further illustrate the ic family of signatures. The code can be found at:

[1] http://jotasapiens.com/