Many cryptographic protocols are parameterized by a uniformly random reference string (e.g. the commitment key for Pedersen commitments). Our goal is to publicly generate the random values of this string (in a finite field), and to do so using the simplest and fastest seed-expansion process (measured I supposed in `bytes per cycle').

In this scenario, we may have a set of public and random seeds, and we'd like to apply the same expander to each one in parallel, each expansion generating a series of $\mathcal{O}(\lambda)$ finite field elements. Selection of seeds is a one-time and trusted process.

Two questions:

  1. What are the formal properties required?

I've read here. In contrast to XOFs and collision resistant hash functions, it seems there's no need for collision resistance since the seeds are only selected once. In contrast to XOFs, we may assume the output size of each seed expansion is fixed in $\lambda$ (as $\mathcal{O}(\lambda)$) rather than variable-length. In contrast to stream ciphers, the input (a seed) is public rather than private. In contrast to KDFs, the input is uniform rather than non-uniform.

  1. What schemes satisfy those properties?

Given the formal properties required, what are some leading schemes satisfying those properties? What are the fastest such schemes? I am implementing this on a GPU, so I cannot rely on common hardware acceleration (e.g. for AES). (The GPU is also why I mention multiple seeds to be expanded in parallel.)

An example:

In the Dilithium signature scheme (selected by NIST) they use SHAKE-128, an XOF, for seed generation, saying "this is a standard technique." They also use SHAKE, however, for other purposes requiring stronger properties, such as Fiat-Shamir and collision resistance. For the randomness generation alone, they also have an AES variant in contrast to SHAKE-128 (a block-cipher in contrast to an XOF), to "showcase the improved efficiency [...] once hardware-support for SHAKE becomes widely available (as it is for AES)." They say the seed expansion using SHAKE is one of the two most time-intensive operations of the protocol, implying they'd use something faster (e.g. AES) if it met their needs. So this begs the question, if a block-cipher (AES) if faster than an XOF (SHAKE), why use SHAKE as your main choice and AES only as a temporary variant? (I imagine the AES variant is secure and more than toy example.)

  • $\begingroup$ Excellent question. Work required me to follow the final rounds of NIST's contest, including the adoption of "90s versions" using AES, but I've never given proper thought to this. I guess I just assumed they were working under the hypothesis that SHAKE would be faster once hardware acceleration is in place, or perhaps that SHAKE was cheaper in hardware. If I may throw a possibility: I understand that efficient, side-channel resistant implementation of AES is very difficult without hardware acceleration, due to the S-boxes -- apparently this wasn't a consideration during the AES contest. $\endgroup$
    – swineone
    Feb 23 at 22:10
  • $\begingroup$ @swineone Interesting. I'd assume block ciphers are cheaper than XOF's just since they're weaker. As for side-channel attacks, I see no concern for it here as the randomness to be generated is public. $\endgroup$ Feb 23 at 22:25
  • $\begingroup$ Are you sure they're always public? For Dilithium in particular, the result of ExpandA may be public, but ExpandS is essentially the secret key, and also relies on the same expansion scheme using SHAKE. $\endgroup$
    – swineone
    Feb 23 at 22:39
  • $\begingroup$ @swineone Sorry, yes, the expansion for Dilithium is both private and public. For the question above though I'm only considering public randomness, as is the case for many if not most ZKP schemes used in practice. Also worth noting the (public) matrix is much bigger than the two (private) s vectors. $\endgroup$ Feb 23 at 22:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.