2
$\begingroup$

Ideal cipher is a random permutation for every key in its key space.

And, ideal encryption scheme is the one which has perfect secrecy/indistinguishability. For an encryption scheme, random permutation from plain text space to cipher text space seems to be a stronger property and is not always needed

I do not understand the rationale :

  1. Why would having just perfect secrecy/indistinguishability (and not randomness) be enough for encryption schemes but not for block ciphers?
  2. On the other side, why can't perfect secrecy/indistinguishability property be enough for a block cipher? Why does it need to be random permutation?
$\endgroup$

2 Answers 2

3
$\begingroup$

1. Why would having just perfect secrecy/indistinguishability (and not randomness) be enough for encryption schemes but not for block ciphers? 2. On the other side, why can't perfect secrecy/indistinguishability property be enough for a block cipher? Why does it need to be random permutation?

Indistinguishability is for multiple messages, which means multiple blocks. A block cipher by itself is not indistinguishable: if you encrypt the same message block twice you'll get the same ciphertext. And obviously that's a property you would want to maintain for a block cipher, as it would not be a permutation if it wouldn't.

$\endgroup$
1
  • $\begingroup$ Okay this is what I understand. We actually want the property of perfect secrecy/indistinguishability for both ideal cipher and ideal encryption scheme (this makes sense for practical needs). Perfect indistinguishability to me is : Given cipher text C and two plain text messages M1 and M2, P(plain text = M1 | cipher text = C) = P(plain text = M2 | cipher text = C) where M1 != M2. Since block cipher is bijection, a block cipher with perfect indistinguishability should be a random permutation i.e. for ideal block cipher, perfect indistinguishability <=> random permutation $\endgroup$
    – driewguy
    Feb 12, 2022 at 16:18
1
$\begingroup$

Why would having just perfect secrecy/indistinguishability (and not randomness) be enough for encryption schemes but not for block ciphers?

Block ciphers are primitives. We want them to be a Pseudo-Random Permutation (PRP) and secure against attacks like brute-force, linear, and differential attacks.

When we want to encrypt/decrypt we need Encryption Schemes that consist of key generation, encryption, and decryption algorithms ( informally; it defines how to use the block cipher for encryption). To form a scheme we need a mode of operation for a block cipher in which how the multiple block messages, randomization (IV, nonce, tweak), etc. are defined. Then we can talk about indistinguishability on encryption schemes under the adversary model like Ind-CPA.

Even ECB mode is an encryption scheme that we must forget.

Why does it need to be random permutation?

The better formalization is Why does it need to be pseudo random permutation.

The security proofs (Ind-X) have relied on the PRP * of the block cipher (see the proofs are started with let $F$ be a PRP), otherwise, the proof is not easy to show. Actually, the security theorems don't require the existence of PRP. So, the bounds are set with an (ideal) PRP, and if you start to initialize this encryption scheme (realization) and if the block cipher is not a PRP then the bounds are not working.

If the block cipher is proven to be not a PRP then one has a distinguisher for it that can be used to exploit the encryption scheme that this block cipher is used.

If the block cipher is broken, then the mode of encryption is not secure under this block cipher.

On the other side, why can't perfect secrecy/indistinguishability property be enough for a block cipher?

One can talk about the perfect secrecy of restricted block cipher (it is an encryption scheme) though not feasible to prove since it implies it is broken. As you can see, it requires restrictions that we don't have.

Ideal cipher vs Ideal encryption scheme

Remember that a block cipher is a family of permutations where each one is selected/represented by a key; $$F:\{0,1\}^k\times \{0,1\}^b \to \{0,1\}^b$$

An ideal cipher is a model that we assume the block cipher is a random permutation for every key and those permutations are independent of each other. This is too much for an idealization since there is no construction for this under a small construction like block cipher. We need a gnome as in the Random Oracle model. This is again used in proving the constructions. Then when you need to implement that construction you must turn to a real model and in the face of using a block cipher to realize it.


* One must say that the mode of operations are not restricted to PRPs, there are mode of operations (CTR, CFB)that can use PRF then the bounds are different, see the PRF-PRF swithing-lemma

$\endgroup$
1
  • $\begingroup$ ideal encryption scheme??? $\endgroup$
    – kelalaka
    Feb 12, 2022 at 17:44

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.