Adversarial randomness. Another line of work, e.g. [ACD19, HKP`21, BFG`22a, AJM22] assumes
that the adversary gets to fully control the randomness.
As argued by Balli et al. [BRV20], the additional power of each corruption model does reflect to certain
real-world attacks. For instance, there are certain real-world attacks that randomness leakage does not
capture, but that is captured by adversarially chosen randomness. While thus appealing, we argue that the
third model is problematic when considering post-quantum security: For realistic choices of parameters, most
lattice-based KEMs are not perfectly correct, implying that an adversary choosing the randomness can induce
arbitrary decryption failures. For “ratcheting” protocols that continuously exchange fresh key material, such
correctness issues moreover can translate into security issues, if it allows the adversary to tamper with the
decryption of a freshly exchanged public key.
Several countermeasures are conceivable:
• One may choose parameters in a regime where perfect correctness is guaranteed for lattice-based scheme.
While this approach was taken in the initial (theoretical) post-quantum instantiation of the Double
Ratchet in [ACD19], this ultimately is highly undesirable for practical applications where the size of
post-quantum keys is one of the main obstacles towards adoption.
• One may harden the randomness as part of the cryptographic protocol. For instance in [HKP`21] the
authors generate the randomness via an output of a hash function. In the ROM, one can then prove,
using a union bound argument, that the probability of the adversary finding bad randomness triggering
a decryption failure is negligible (cf. [HKP`21, Section 1.3]).
In this work we eschew the issue of adversarially chosen randomness and choose the model of honest-butleaked randomness instead for several reasons. First, the model already captures many of the attacks from
bad randomness. In particular, this captures the exposure of all intermediate values of a computation during
a corruption. (In contrast, if an attacker only gets to see the state between operations and the operations
can use fresh randomness, intermediate values may remain hidden.) Second, while a real-world attacker
may realistically have some control over the randomness source, arbitrarily setting the randomness (but not
allowing to tamper with other protocol state) seems to be an extremely strong assumption not met by the
real-world attacks pointed out by [BRV20]. Finally, randomness hardening should preferably be performed at
the operating system level and not the at the level of an individual cryptographic protoco
![Adversarial randomness. Another line of work, e.g. [ACD19, HKP`21, BFG`22a, AJM22] assumes
that the adversary gets to fully control the randomness.
As argued by Balli et al. [BRV20], the additional power of each corruption model does reflect to certain
real-world attacks. For instance, there are certain real-world attacks that randomness leakage does not
capture, but that is captured by adversarially chosen randomness. While thus appealing, we argue that the
third model is problematic when considering post-quantum security: For realistic choices of parameters, most
lattice-based KEMs are not perfectly correct, implying that an adversary choosing the randomness can induce
arbitrary decryption failures. For “ratcheting” protocols that continuously exchange fresh key material, such
correctness issues moreover can translate into security issues, if it allows the adversary to tamper with the
decryption of a freshly exchanged public key.
Several countermeasures are conceivable:
• One may choose parameters in a regime where perfect correctness is guaranteed for lattice-based scheme.
While this approach was taken in the initial (theoretical) post-quantum instantiation of the Double
Ratchet in [ACD19], this ultimately is highly undesirable for practical applications where the size of
post-quantum keys is one of the main obstacles towards adoption.
• One may harden the randomness as part of the cryptographic protocol. For instance in [HKP`21] the
authors generate the randomness via an output of a hash function. In the ROM, one can then prove,
using a union bound argument, that the probability of the adversary finding bad randomness triggering
a decryption failure is negligible (cf. [HKP`21, Section 1.3]).
In this work we eschew the issue of adversarially chosen randomness and choose the model of honest-butleaked randomness instead for several reasons. First, the model already captures many of the attacks from
bad randomness. In particular, this captures the exposure of all intermediate values of a computation during
a corruption. (In contrast, if an attacker only gets to see the state between operations and the operations
can use fresh randomness, intermediate values may remain hidden.) Second, while a real-world attacker
may realistically have some control over the randomness source, arbitrarily setting the randomness (but not
allowing to tamper with other protocol state) seems to be an extremely strong assumption not met by the
real-world attacks pointed out by [BRV20]. Finally, randomness hardening should preferably be performed at
the operating system level and not the at the level of an individual cryptographic protoco](https://asset.circumstances.run/media_attachments/files/117/173/612/331/601/291/original/a29a5aebb7eb2cef.png)
