2
$\begingroup$

The paper Breaking Symmetric Cryptosystems using Quantum Period Finding shows how to break the Even-Mansour Cipher using Simon's algorithm. The Even-Mansour uses two keys $k_1, k_2$ and a random public permutation $P$ to encrypt a message $x$:

$$E_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2$$

In a quantum known plaintext scenario we can use quantum period finding (Simon's algorithm), to find the period $k_1$ in the following function: $$f(x) = P(x \oplus k_1) \oplus k_2 \oplus P(x)$$ Clearly, $f(x) = f(x \oplus k_1)$ So far I can follow. The paper then argues that if there would be another period $t \notin \{0,k_1\}$ such that $$Pr[f(x) = f(x \oplus t)] \geq \frac{1}{2}$$ Then there would be a higher higher order differential for P, because then it would hold that: $$Pr[P(x) \oplus P(x \oplus k_1) \oplus P(x \oplus t) \oplus P(x \oplus t \oplus k_1)] \geq \frac{1}{2}$$ It is unclear to me why. Would the existence of another period not merely imply that: $$P(x \oplus k_1) \oplus P(x) = P(x \oplus k_1 \oplus k_1) \oplus P(x \oplus k_1) = P(x \oplus t \oplus k_1) \oplus P(x \oplus t) = P(x \oplus t \oplus k_1 \oplus k_1) \oplus P(x \oplus t \oplus k_1)$$ How can the higher-order differential be followed from that?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Firstly, you have a typo [missing $=0$] what you need to show is that $$Pr[P(x) \oplus P(x \oplus k_1) \oplus P(x \oplus t) \oplus P(x \oplus t \oplus k_1)=0] \geq \frac{1}{2}$$

If you then plugin the definition of $f(x)$ into the relation $$ Pr[f(x)=f(x\oplus t)]\geq \frac{1}{2}, $$ you get $$ Pr\left[P(x \oplus k_1) \oplus k_2 \oplus P(x) = P(x \oplus k_1 \oplus t) \oplus k_2 \oplus P(x \oplus t)\right]\geq \frac{1}{2} $$ which reduces to the desired expression after some cancellation.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks much! Could you also explain to me the derivation of the same argument for the LRW construction construction (page 13)? There, the function is $f(x) = E_K[x \oplus h(t_0)] \oplus h(t_0) \oplus E_k[x \oplus h(t_1)] \oplus h(t_1)$ and we want to show $Pr[E_k[x] \oplus E_k[x \oplus s] \oplus E[x \oplus t] \oplus E_K[x \oplus s \oplus t]] \geq 1/2$ if the probability of an unwanted collision is greater than $1/2$, where the period is $s = h(t_0) \oplus h(t_1)$ $\endgroup$
    – cryptobeginner
    Mar 28, 2022 at 22:05
0
$\begingroup$

Thanks for the question and the answer which I could not understand. My doubt is how to build f(x)=P(x⊕k1)⊕k2⊕P(x) when K is not known and our job is to find K. If K comes from superposition, then how the cipher text is used to get the key. Is it possible to get a quantum circuit for implementation of Simon's algorithm for a toy cipher or step by step procedure like how qubits are initialised, which set of qubits are taken to super position, how plain text and cipher texts are utilised after encoding in qubits, how many qubits will be required for a given size of teh problem?

Improve this answer
$\endgroup$
1

Your Answer

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

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