Are my calculations about WOTS parameters correct?

MaiaVictor

11/8/22, 9:26 PM

I'm reading the WOTS+ paper, but I'm having some trouble with its notation and specially the involved units. For example, under my interpretation, the parameters n=11, w=16 and m=256 result in a quantum security level of about 81 bits, with a 992 bytes signature length, but that looks incorrect.

To the best of my knowledge, I've made the following script to output public key and signature lengths, and security level, for both WOTS+ and WOTS.

WOTS+

import math

n = 16  # security parameter, in bytes
w = 16  # w parameter
m = 256 # message length, in bits

l1 = math.ceil(m / math.log2(w))
l2 = math.floor(math.log2(l1*(w-1))/math.log2(w))+1
l  = l1 + l2

# formulas from the paper
pub_len = (l + w - 1) * n + 8        # public key length in bytes
sig_len = l * n                      # signature length in bytes
sec_lvl = n*8 - math.log2(w*w*l + w) # quantum security level in bits

print("wots+")
print("pub_len: " + str(pub_len))
print("sig_len: " + str(sig_len))
print("sec_lvl: " + str(sec_lvl))

WOTS

import math

n = 256 # security parameter, in bits
w = 16  # bits per signing unit
m = 256 # message length, in bits

l1 = n / w
l2 = math.ceil((math.floor(math.log2(l1))+1+w)/w)
l  = l1 + l2

# probably wrong
pub_len = m * l1 / 8 # public key length in bytes
sig_len = m * l / 8  # signature length in bytes
sec_lvl = m / 3      # quantum security level in bits

print("wots")
print("pub_len: " + str(pub_len))
print("sig_len: " + str(sig_len))
print("sec_lvl: " + str(sec_lvl))

Are my calculations correct?

1 + 2

hash

post-quantum-cryptography

hash-signature

poncho

11/8/22, 11:30 PM

What do you mean by "80 bits of postquantum security"? Do you mean taking $2^{80}$ operations on a quantum computer? If so, you need to take into account Grover's, which is somewhat difficult to quantify - a naïve application would assume a 160 bit hash; however Grover's would require $2^{80}$ successive hash computations to find a 160 bit preimage with $2^{80}$ computation, which is unrealistic...

MaiaVictor

11/8/22, 11:44 PM

@poncho yes, I mean taking 2^80 operations on a quantum computer. To be honest I'd just like to make sure I understand the formulas in the paper. I've updated the question to ask that more directly.

Score:0

Crypto

mephisto

11/16/22, 4:17 PM

The WOTS+ calculations are largely correct. Only the security level is "just" the security against conventional adversaries. The right equation for quantum adversaries should be

sec_lvl = n*8/2 - math.log2(w*w*l + w) # quantum security level in bits

As quantum computers can find preimages and second preimages with $2^{8n/2}$ queries.

In the WOTS calculations

pub_len = m * l1 / 8 # public key length in bytes 
sig_len = m * l / 8 # signature length in bytes

should be

pub_len = n * l # public key length in bytes 
sig_len = n * l # signature length in bytes

(signatures, secret and public keys consist of l chain values which have n bits).

Otherwise, things seem to be correct.