1
$\begingroup$

Suppose an encrypion scheme uses a random string to encrypt and decrypt, which is publicly available, such as an IV or nonce. In all the cases I am aware of, the existence of say an IV is not "assumed": it is taken as fact that generating a 128 bit IV for example is easy and the existence of such a random IV is not the same as an unproven assumption.

But now suppose an encryption scheme operates with large amounts of publicly accessable random data, say on the order of $2^{256}$ bits. Then would a proof of security for this cipher have to "assume" the existence of such a database? In other words, if the security proof of a cipher relied on the existence of a public database storing $2^{256}$ bits, would this be deemed an "assumption", and treated similarly as an "unproven assumption" (like the difficulty of the discrete log problem)?

$\endgroup$

1 Answer 1

2
$\begingroup$

In all the cases I am aware of, the existence of say an IV is not "assumed": it is taken as fact that generating a 128 bit IV for example is easy and the existence of such a random IV is not the same as an unproven assumption.

Generally, if (pseudo-)randomness is required, then it is assumed for the block cipher mode (such as CBC) that it actually is randomized of course. That's a pre-condition which should be indicated in the definition.

But now suppose an encryption scheme operates with large amounts of publicly accessable random data, say on the order of $2^{256}$ bits.

That's generally not how it works. Even though the IV can be made public after encryption, modes such as CBC mode assume that the IV is unpredictable to an adversary before such encryption happens.

Then would a proof of security for this cipher have to "assume" the existence of such a database?

Not for the cipher algorithm. Ciphers are not related to databases. A the protocol or application specific scheme should definitely take this into account for the system to be secure.

In other words, if the security proof of a cipher relied on the existence of a public database storing $2^{256}$ bits, would this be deemed an "assumption", and treated similarly as an "unproven assumption" (like the difficulty of the discrete log problem)?

No, not even that.

First of all, such a database is known as a table in cryptography, even if it is very large.

In the case a cipher uses such a table then it should prove or show the equivalence of the algorithmic use of the table to a known hardness assumption. You cannot just assume that any problem is hard, after all.

What you can assume / make it a precondition that the database consist of random bits. We can certainly create (pseudo-)random bits after all. If that would be useful or not strongly depends.

Of course, storing $2^{256}$ bits in a table is nonsense anyway (that's $1.447 \cdot 10^{49}$ hellabytes!).


Note that many modes do not require a randomized IV. Many - such as CTR, GCM and ChaCha20 simply require a nonce. For those you just need to keep a synchronized (message) counter. If you want to pluck an IV out of a shared table then you'd need to synchronize offsets anyway.

For CBC mode you can similarly encrypt a counter to create an unpredictable IV, preferably using a separate key.

So you can probably do without the table in the first place.

$\endgroup$
2
  • $\begingroup$ Can you expand on "In the case a cipher uses such a table then it should prove or show the equivalence of the use of the table to a known hardness assumption", and in particular what showing equivalence of use of the table to a known hardness assumption would look like? $\endgroup$
    – user918212
    Jun 5, 2022 at 18:47
  • 1
    $\begingroup$ I cannot because I don't know how the table would be used. Just specifying a table is not the same as specifying an algorithm after all. And really, that's up to the designer of the algorithm, you cannot start with a table as a solution without a problem. $\endgroup$
    – Maarten Bodewes
    Jun 5, 2022 at 18:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.