Let $\mathcal S=\{0,1\}^n$ be the set of bitstrinsg of $n$ bits (for security parameter $n$). Let $P$ be a public Pseudo-Random Permutation of $\mathcal S$, efficiently computable in both directions.

Construct a block cipher $E$ with message and key domains $\mathcal S$ as $$\begin{align} E:\mathcal S\times\mathcal S\to\;&\mathcal S\\ (k,m)\mapsto\;&E(k,m)\underset{\text{def}}=P(k\oplus m)\oplus k\\ \end{align}$$ What can we prove about the security (under Chosen Ciphertext Attack, or orther) of that block cipher?

Update: that's known as the single-key variant of the Even-Mansour scheme. The original scheme has two independent input and output keys. The reference article is Shimon Even and Yishay Mansour's A construction of a cipher from a single pseudorandom permutation, in Journal of Cryptology, 1997, originally in proceedings of Asiacrypt 1991.

Note: I still welcome a reference, or better a proof, for the single key variant.

Can one break (find a practical distinguisher of) $E$ for the following candidate instantiation of $P$?

Restrict to $n$ with $p=2^n+3$ prime (see A057732 for values, some multiple of $8$ and even $16$). Let $e$ be $3$ (resp. $5$) for odd (resp. even) $n$, which insures $\gcd(e,p-1)=1$. Assimilate elements of $\mathcal S$ to integers. Define $$\begin{align} Q:S\to\;&\mathcal S\\ m\mapsto\;&Q(m)\underset{\text{def}}=((m+2)^e\bmod p)-2 \end{align}$$ That's a permutation of $\mathcal S$, but not a good enough PRP for the application (that makes an interesting exercise. Hint: What's $Q(m)+Q(2^n-1-m)$ ?)

Let $a$ and $b$ be two $n$-bit nothing-up-my-sleeves constants, e.g. $a=\left\lfloor\pi\,2^{n-2}\right\rfloor$ and $b=\left\lfloor2^{n-1/2}\right\rfloor$. Define $$\begin{align} P:\mathcal S\to\;&\mathcal S\\ m\mapsto\;&P(m)\underset{\text{def}}=Q((Q(m)+a\bmod 2^n)\oplus b)\\ \end{align}$$

Vague rationale: insert the non-linear $x\mapsto (x+a\bmod 2^n)\oplus b$ between two instances of $Q$ providing the diffusion. $a\ne0$ is necessary for security, but so far I have no break for $(a,b)=(1,0)$.

Note: I only created a security system so clever that I can't imagine a way of breaking it. The most clueless amateur can, as observed by Bruce Schneier. That second part of the question if thus off-topic, and I'd understand downvotes!

  • 1
    $\begingroup$ The first is called Even-Mansour construction and is known to look like a random permutation, if P itself is a random permutation. Not sure what “public random Pseudo-Random Permutation” and “CCA security of a block cipher” meant. $\endgroup$ – Gee Law Sep 25 '20 at 12:23
  • $\begingroup$ @Gee Law: Even-Mansour is worth an answer. Thanks for pointing the two issues, they should be fixed now. $\endgroup$ – fgrieu Sep 25 '20 at 12:37
  • 1
    $\begingroup$ More precisely, this is the Single-Key Even-Mansour construction (the more classical one has different inner and outer keys). $\endgroup$ – SEJPM Sep 25 '20 at 12:40
  • 1
    $\begingroup$ Also note that such schemes are usually analysed as Strong Pseudo-Random-Permutations (sPRPs) rather than with a CCA model. $\endgroup$ – SEJPM Sep 25 '20 at 13:41

What can we prove about the security (under Chosen Ciphertext Attack, or orther) of that block cipher?

This is the single-key Even-Mansour construction as was already noted in the comments of the question. The latest analysis I could find of this construction is by Orr Dunkelman, Nathan Keller, and Adi Shamir: "Minimalism in Cryptography: The Even-Mansour Scheme Revisited" where they argue that any successful attack satisfies $DT=\Omega(2^n)$ with $D$ being the number of queries to the encryption oracle and $T$ being the number of queries to the permutation itself. This means that the product of these two numbers of queries scales exponentially in the width of the permutation for any attack with constant success probability. This result was also proven in the original work by Even and Mansour for the two-key case.

As for the candidate construction for a public random permutation, one should first note that this model is very close to the random oracle model (but with a permutation instead of a function). This means that any candidate construction can only offer (indirect) heuristic security. I don't have an attack on the permutation at hand though. However this is a model that is sometimes used in cryptography, e.g. in MPC applications, where one would use AES with a fixed key for such needs.

  • $\begingroup$ That paper you cite (or a slightly abridged later version in proceedings of Eurocrypt 2012, free too) fully answers the first half of the question. For the second part, as you note, it's not expected that we get a security proof; that's why I ask for a break! $\endgroup$ – fgrieu Sep 26 '20 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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