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:
- 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.
- 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.)
