search

cloudflare / circl

CIRCL: Cloudflare Interoperable Reusable Cryptographic Library
http://blog.cloudflare.com/introducing-circl
Other
1.23k stars 136 forks source link

tkn20: change seed size for MAC key from 128->448 bits in accordance … #394

Closed tanyav2 closed 1 year ago

tanyav2 commented 1 year ago

…with BK paper

Section 4 Encapsulation Schemes in the Boneh-Katz transform requires the seed size that is used to generate MAC key to be equal to 448 bits. Currently we were using 128 bits. This is not directly related to security parameter size, instead it is due to statistical arguments used in the construction of the proof. Thanks to @mtcvenema for flagging.

As a consequence, the size of the ciphertext increases by the same length (40 bytes), making this an API breaking change.

cc @wbl

tanyav2 commented 1 year ago

EDIT: I have now changed the seed size to now be 576 bits (as opposed to 448 described earlier). This is because while the paper uses 448 bit seed to get a commitment that is a 128 bit string, we were generating a 256 bit commitment. In order to maintain the statistical security difference mentioned in the proof (2^(-63)), we have to increase the seed size to 576 bits. @mtcvenema confirms this.

mtcvenema commented 1 year ago

EDIT: I have now changed the seed size to now be 576 bits (as opposed to 448 described earlier). This is because while the paper uses 448 bit seed to get a commitment that is a 128 bit string, we were generating a 256 bit commitment. In order to maintain the statistical security difference mentioned in the proof (2^(-63)), we have to increase the seed size to 576 bits. @mtcvenema confirms this.

I confirm. To give some rational: in the Boneh-Katz paper (https://eprint.iacr.org/2004/261.pdf - page 12, Theorem 2), they prove that using hash functions with an input domain of 448 bits and output of 128 bits provides the statistical hiding property by distinguishing between 'bad' inputs and 'good' inputs. Basically, the idea is that the number of bad inputs should be very small (i.e., 1 in 2^{65}), and for the good inputs, statistical hiding follows with the leftover-hash lemma. The argument for good inputs remains the same for our case, where we have a larger output space, but the argument for bad inputs changes. To ensure that the probability that we pick a bad input is also 1 in 2^{65}, we fix the size of our input space to 576 bits.