An investigation into WOTS+C counter size and its effects on signing failure probability

wots+c.py

from math import factorial, log2, inf

# n-choose-k, AKA the binomial coefficient.
def binomial(n, k):
  return factorial(n) // (factorial(k) * factorial(n - k))

# Multiply two vectors of polynomial coefficients in O(n^2) time.
# Coefficients are ordered from lowest to highest degree.
def multiply_polynomials(p1, p2):
  deg1 = (len(p1) - 1)
  deg2 = (len(p2) - 1)
  out = [0 for _ in range(deg1 + deg2 + 1)]
  for i in range(len(p1)):
    for j in range(len(p2)):
      out[i + j] += p1[i] * p2[j]
  return out

# Parameters
n = 32                  # Number of WOTS chains
s = 16                  # WOTS chain length
p = int((s+1) / 2 * n)  # Target WOTS+C constant sum, modified because we're computing with non-zero dice rolls.

print('n = ', n, '(# of dice)')
print('s = ', s, '(# of sides on the dice)')
print('p = ', p, '(target sum)')

# The total number of possible combinations rolling n dice with s sides each is:
d = s**n
print('d = ', d, '(# of combinations total)')


# This finds the number of possible rolls of n dice with s sides whose faces sum to p.
#
# Uses the formula from https://mathworld.wolfram.com/Dice.html
#   https://mathworld.wolfram.com/images/equations/Dice/NumberedEquation7.svg
c = sum(((-1)**k * binomial(n, k) * binomial(p - s*k - 1, n - 1) for k in range((p-n)//s + 1)))
print('c = ', c, '(# of combinations summing to p)')


# Brute force alternative method of computing the number of possible rolls which sum to p.
#
# Expands the polynomial (x + x^2 + ... + x^s)^n and then finds the biggest coefficient
# (of the x^p term). This should be mathematically identical to the above formula from Wolfram's article,
# but much slower.
def compute_coefficient(n, s, p):
  coefficients = [0] + [1 for _ in range(s)]
  acc = [1]
  for i in range(n):
    acc = multiply_polynomials(acc, coefficients)
  return max(acc)

# The brute-force method and formulaic computation should agree.
assert compute_coefficient(n, s, p) == c, "incorrect coefficient"

# The failure probability for a single roll is:
#
#   invalid_combinations / total_combinations
q = d - c
print('q = ', q, '(# of combinations not summing to p)')
print('q/d =', q/d, '(failure probability after 1 try)')

# Computes the probability of 2^b consecutive dice rolls which do not sum to p,
# i.e. the WOTS+C counter has overflowed b bits.
for b in range(1, 17):
  try:
    chances = pow(d/q, 2**b) # Same as 1 / ((q/d) ** (2**b))
  except OverflowError:
    chances = inf
  print('after 2^%d tries: 1 chance in 2^%f' % (b, log2(chances)))

# The below code can be used to evaluate the effects of grinding counter size
# on the expected number of invalid WOTS+C keys in a SPHINCS+C hypertree.
# Not relevant for stateful XMSS since randomizers can be rotated, and messages
# can be modified and retried in that context.
def evaluate_sphincs():
  xmss_height = 9
  ht_layers = 7
  wots_keys = 2**xmss_height

  for _ in range(ht_layers - 1):
    wots_keys += wots_keys * (2**xmss_height)

  print('WOTS keys: 2^%f' % log2(wots_keys))

  for counter_bits in range(8, 17):
    unusable_prob = pow(q/d, 2**counter_bits)
    print('%d-bit counter:' % counter_bits)
    print('  probability WOTS key is unusable: 1 / 2^%.4f' % log2(1/unusable_prob))
    print('  # of expected unusable WOTS keys: 2^%f' % (log2(wots_keys) - log2(1/unusable_prob)))

wots-compression-failure-prob.md

WOTS+C

WOTS+C (Winternitz One-Time Signature with Compression) is a one-time hash-based signature scheme with very compact signatures. Each keypair can sign at most one message.

In vanilla WOTS, each keypair signs a message by revealing certain preimages in a set of hash chains. The exact locations of those preimages are determined by the message, which is mapped to a set of indexes among those hash chains. At least one checksum hash chain is needed to prevent forgery. This checksum increases the signature size and must be verified for the scheme to be secure.

The WOTS+C scheme improves over stock WOTS by appending a small grinding counter to the signature, such that when the message and grinding counter are hashed, the resulting hash chain indexes sum to a constant value, fixed as part of the scheme. This prevents forgeries and removes the need for a checksum, resulting in faster verification and smaller signatures.

WOTS+C Failures

WOTS+C signing can fail depending on the parameters used. Most WOTS+C instances use a fixed-size counter so the signature size is constant. This means given a message to sign, the signer has a finite number of attempts to find a counter which which maps the message to a constant-sum set of hash chain indexes. For some messages, no such valid fixed-size counter may exist. In this case, signing fails, and the message cannot be signed.

This attached Python script computes the exact probabilities involved with WOTS+C grinding counter failures, using dice theory. It computes the failure probability for different bit-sizes of counters, and as a bonus, computes the expected number of invalid WOTS+C keys across a SPHINCS+C hypertree (which uses WOTS+C as a crucial component).

Namely, we can compute the exact probability of a WOTS+C key failing to sign a given message by reframing it into the following question:

If we repeatedly roll $n$ dice with $s$ sides each, what is the probability that the faces of those dice do not sum to a fixed target $p$ over $v$ consecutive rolls?

The parameters are equivalent as follows:

Parameter	Dice theory	WOTS+C equivalent
$n$	Number of dice	Number of WOTS chains
$s$	Sides per die	Length of each WOTS chain
$p$	Target sum	hash chain index constant-sum target
$v$	Number of consecutive rolls	Number of possible counters, typically a power of two if counters are encoded as bits.