# Can Trivium be used as a PRF?

The Trivium encryption algorithm has two inputs, key and IV, both of which are 80 bits long. Let's call it Trivium(key, IV) → keystream. My question is whether doing Trivium(key, input) and taking the first 80 bit of keystream would result in a secure PRF.

I have found another way to create a PRF from a stream cipher, but that seems to be for stream ciphers that do not have an IV input, so such a complex construction might not be needed for one that does. Based on reading the Trivium algorithm description paper and the Trivium design paper I feel like my construction should be secure but I have no idea how to go around proving it.

This question was spurred by wondering whether I could implement authenticated encryption using only Trivium as a primitive. If I could turn it into a PRF, as far as I understand I could construct something similar to CBC-MAC from it. (Of course this doesn't make much sense to because rekeying the cipher, which you'd need to do for every 8 bytes, is quite slow.)

• I'm pretty sure the standard security proof for CPA security of nonce-based stream ciphers does assume the stream cipher to behave like a PRF. – SEJPM Oct 6 '19 at 13:53
• With the limited description above, wouldn't your input data be limited to 80 bits / 10 bytes? – Maarten Bodewes Oct 7 '19 at 9:25
• Yes. My understanding was that a PRF is usually defined to map from a fixed-size input to a fixed-size output. Is that not correct? – nortti Oct 7 '19 at 15:51
• @nortti: PRFs can have either fixed- or variable-size input domains. Block ciphers are the most common example of fixed-size input PRFs. HMAC is the most common example of a variable input size PRF, but see also CMAC. – Luis Casillas Oct 7 '19 at 22:36

To attempt such a proof you need a definition of what security properties an IV-based stream cipher is supposed to provide. For example, like this (very informally):

• A nonce-based cipher is secure if and only if its encryptions are indistinguishable from random bitstrings of the same length to a nonce-respecting adversary that's allowed to carry out a chosen-plaintext attack.

The "nonce-respecting" bit is important, because one of the key assumptions in a PRF is that it's supposed to be secure against adversarially-chosen inputs, and the inclusion of "nonce-respecting" in such a definition is to give the adversary as much control over nonces as we can get away with. (Note not all ciphers meet this standard—e.g., CBC-mode encryption doesn't, because it requires random nonces. Evaluating whether Trivium meets this standard is a whole 'nother topic.)

So if encrypting message $$p$$ with key $$k$$ and nonce $$n$$ is notated as $$Enc^n_k(p)$$, then your proposed PRF construction would be:

$$PRF_k(m) = Enc^m_k(0^{80})$$

...where $$0^{80}$$ is the 80-bit all-zero string. And what you want to prove is that, given a secret, random choice of $$k$$, if an attacker who can choose messages $$m$$ could distinguish your PRF apart from a random function, then they could break the underlying nonce-based cipher.

In this case, that follows by observing that if there was such a chosen-message attack they could mount against the PRF, it would imply the existence a corresponding attack on the cipher by querying for the encryption of the same plaintext $$0^{80}$$ repeatedly but with different, adversarially-controlled nonces.