Incremental data signing for Dilithium

[likakisp]

Are there any plans to offer "incremental data signing" with liboqs?

Currently, function "crypto_sign_signature" requires the entire message (data) along with the message length to compute a signature (i.e. dilithium).

What if I wanted to sign a 1GB or 2GB data file and my application is limited in memory size (RAM) that is less than the data size? My application would not be able to dynamically allocate a big enough buffer to hold this data.

Do you have any plans to offer "incremental data signing" or "multi part signing"? In this case, chucks of data (message) would be fed to liboqs which it would hash (using shake 256, like it does today) and continue hashing until the final data (message) is received.

[dstebila]

Interesting suggestion. There are already incremental hashing APIs, do you think that people would be satisfied with using the incremental hashing API to hash the long message, then signing that hash using the signature algorithm (which itself will do an extra hash)? Or do you think there will be a desire to directly sign the long message using the signature algorithm without an intermediate step?

[likakisp]

Based on my understanding of liboqs signature implementation, the library is hashing the message using shake256 before the message is signed. Therefore, it should be fine with people to break the signing process in multiple parts (or offer it as an additional option, "crypto_sign_inc_signature"). For example, something like this:

1. Sign Init calls:
   shake256_inc_init(&state);
   shake256_inc_absorb(&state, tr, SEEDBYTES);

2. Sign Update - this would be called multiple times given chunks of the long message:
   shake256_inc_absorb(&state, mChunk, mChunkLen);

3. Sign Final:
   shake256_inc_finalize(&state);
   shake256_inc_squeeze(mu, CRHBYTES, &state);
   Generate PQC Signature

Given the fact that we are limited with memory space, I don't see how liboqs can sign a large message (i.e. 1GB, 2GB) without an intermediate hashing step. For sure, liboqs could accumulate the data, but I would think it would run out of memory space. So, we would be having the same problem.

Please keep in mind that we are statically linking liboqs library to our application.

Thank you.

[baentsch]

Based on my understanding of liboqs signature implementation, the library is hashing the message using shake256 before the message is signed.

Can you please point to the code that lets you come to this understanding?

There are already incremental hashing APIs, do you think that people would be satisfied with using the incremental hashing API to hash the long message, then signing that hash using the signature algorithm (which itself will do an extra hash)?

Can you please state why this proposal by @dstebila would not work for you?

[likakisp]

In reference to "Can you please state why this proposal by @dstebila would not work for you?":

I don't believe I stated somewhere that the proposal would NOT work. I said "It should be fine..." and would love to have such implementation within liboqs.

In response to "Can you please point to the code that lets you come to this understanding?":

Please see function "crypto_sign_signature" below. It calls shake_256 to hash the entire message. Our application calls "OQS_SIG_sign" using Dilithium and that function calls crypto_sign_signature.

int crypto_sign_signature(uint8_t *sig,
size_t *siglen,
const uint8_t m,
size_t mlen,
const uint8_t sk)
{
unsigned int n;
uint8_t seedbuf[3SEEDBYTES + 2CRHBYTES];
uint8_t *rho, *tr, *key, *mu, *rhoprime;
uint16_t nonce = 0;
polyvecl mat[K], s1, y, z;
polyveck t0, s2, w1, w0, h;
poly cp;
shake256incctx state;

rho = seedbuf;
tr = rho + SEEDBYTES;
key = tr + SEEDBYTES;
mu = key + SEEDBYTES;
rhoprime = mu + CRHBYTES;
unpack_sk(rho, tr, key, &t0, &s1, &s2, sk);

/ Compute CRH(tr, msg) /
shake256_inc_init(&state);
shake256_inc_absorb(&state, tr, SEEDBYTES);
shake256_inc_absorb(&state, m, mlen);
shake256_inc_finalize(&state);
shake256_inc_squeeze(mu, CRHBYTES, &state);

#ifdef DILITHIUM_RANDOMIZED_SIGNING
randombytes(rhoprime, CRHBYTES);
#else
shake256(rhoprime, CRHBYTES, key, SEEDBYTES + CRHBYTES);
#endif

/* Expand matrix and transform vectors */
polyvec_matrix_expand(mat, rho);
polyvecl_ntt(&s1);
polyveck_ntt(&s2);
polyveck_ntt(&t0);

rej:
/* Sample intermediate vector y */
polyvecl_uniform_gamma1(&y, rhoprime, nonce++);

/* Matrix-vector multiplication */
z = y;
polyvecl_ntt(&z);
polyvec_matrix_pointwise_montgomery(&w1, mat, &z);
polyveck_reduce(&w1);
polyveck_invntt_tomont(&w1);

/* Decompose w and call the random oracle */
polyveck_caddq(&w1);
polyveck_decompose(&w1, &w0, &w1);
polyveck_pack_w1(sig, &w1);

shake256_inc_ctx_reset(&state);
shake256_inc_absorb(&state, mu, CRHBYTES);
shake256_inc_absorb(&state, sig, K*POLYW1_PACKEDBYTES);
shake256_inc_finalize(&state);
shake256_inc_squeeze(sig, SEEDBYTES, &state);
poly_challenge(&cp, sig);
poly_ntt(&cp);

/* Compute z, reject if it reveals secret */
polyvecl_pointwise_poly_montgomery(&z, &cp, &s1);
polyvecl_invntt_tomont(&z);
polyvecl_add(&z, &z, &y);
polyvecl_reduce(&z);
if(polyvecl_chknorm(&z, GAMMA1 - BETA))
goto rej;

/* Check that subtracting cs2 does not change high bits of w and low bits

• do not reveal secret information */
  polyveck_pointwise_poly_montgomery(&h, &cp, &s2);
  polyveck_invntt_tomont(&h);
  polyveck_sub(&w0, &w0, &h);
  polyveck_reduce(&w0);
  if(polyveck_chknorm(&w0, GAMMA2 - BETA))
  goto rej;

/* Compute hints for w1 */
polyveck_pointwise_poly_montgomery(&h, &cp, &t0);
polyveck_invntt_tomont(&h);
polyveck_reduce(&h);
if(polyveck_chknorm(&h, GAMMA2))
goto rej;

polyveck_add(&w0, &w0, &h);
n = polyveck_make_hint(&h, &w0, &w1);
if(n > OMEGA)
goto rej;

shake256_inc_ctx_release(&state);

/* Write signature */
pack_sig(sig, sig, &z, &h);
*siglen = CRYPTO_BYTES;
return 0;
}

[likakisp]

Good afternoon.

Do you have an update on this?

Are you planning on implementing this enhancement?

If so, do you have an estimate on its implementation?

Thanks!

[dstebila]

@cryptojedi @tlepoint Do you have any opinions on an incremental API for Dilithium signature generation?

[cryptojedi]

If this is only about signing, I don't have a strong opinion, no.

[baentsch]

Do you have any opinions on an incremental API for Dilithium signature generation?

@likakisp : Are you looking for a solution only valid for Dilithium or would you possibly want to use other algorithms, too? Should the implementation be efficient in terms of SHA(KE) rounds done? Or asked another way: Is incremental hashing followed by finishing hash-and-sign "good enough"? The latter would arguably be easy to "wrap around" all algorithms.

[likakisp]

@baentsch: No, all PQC algorithms should offer incremental signing or encryption.
Yes, incremental hashing followed by finishing hash-and-sign would be great.
Ideally, this would look similar to the OpenSSL model where the functions would have an Init to setup the key, an Update to process incremental message fragments, and then a Final to perform final calculations once all message data has been delivered.

Thank you.

[cryptojedi]

This won't work for all PQC algorithms. See, for example, the SPHINCS+ specification [1], Section 6.4 (page 33). The signing procedure first takes M as an input to PRF_msg to generate R and then takes R and the message as input to H_msg. So, the message would need to be streamed through the incremental API twice.

[1] http://sphincs.org/data/sphincs+-r3.1-specification.pdf

[likakisp]

@cryptojedi: I understand. No need to worry about the incremental concept with SPHINCS.

[baentsch]

Yes, incremental hashing followed by finishing hash-and-sign would be great.
Ideally, this would look similar to the OpenSSL model where the functions would have an Init to setup the key, an Update to process incremental message fragments, and then a Final to perform final calculations once all message data has been delivered.

OK. This then begs the question of which hashing alg to use: In OpenSSL you can pick-and-choose. Should the same choice be provided by liboqs? Or should it be only "shake(256)"? Or something else, e.g., depending on claimed NIST strength of the signature alg? And just to be sure: Even though OpenSSL already provides this functionality, what's the reason you would like to see this in liboqs/do not want to use OpenSSL? Don't you want that dependency? So offering different, configurable hash algs via OpenSSL then wouldn't cut it for you then?

[dstebila]

OK. This then begs the question of which hashing alg to use: In OpenSSL you can pick-and-choose. Should the same choice be provided by liboqs? Or should it be only "shake(256)"? Or something else, e.g., depending on claimed NIST strength of the signature alg? And just to be sure: Even though OpenSSL already provides this functionality, what's the reason you would like to see this in liboqs/do not want to use OpenSSL? Don't you want that dependency? So offering different, configurable hash algs via OpenSSL then wouldn't cut it for you then?

No, you wouldn't be doing an extra hash with a possibly different algorithm, you'd be using the existing hash inside Dilithium but making it available incrementally.

[baentsch]

No, you wouldn't be doing an extra hash with a possibly different algorithm, you'd be using the existing hash inside Dilithium but making it available incrementally.

That's OK for Dilithium. But wasn't the request for a mechanism working for all algorithms?

[likakisp]

@baentsch: OpenSSL was mentioned as an example for the API. We don't need choices like OpenSSL. We don't want to bring OpenSSL in our solution. We are just bringing in liboqs. Our requirements are to sign large files with Diilithium or encrypt large files with Kyber. That's where the need arises for incremental sign or encrypt.

dstebila is correct. No need for extra hash. You would use the existing hash inside Dilithium and make it incremental.