Score:0

Pseudorandom permutations

hu flag

So I am trying to solve some exercises about pseudorandom permutations.

Assume that keyed-permuation $E_k(x)$ is a pseudorandom permutation, where $|x|=|k|=n$. Using $E_k(x)$, we construct an encryption sheme as follows.
$$ c=m\oplus E_k(0^n)\\ m=c\oplus E_k(0^n) $$ where $k$ is a random key.

The task is to show if this sheme either provides OT-IND-CPA or IND-CPA.

So if I understand pseudorandom permutations correctly this sheme should not provide any of those two. My argument would be that no mather what key $k$ one uses the output of $E_k(0^n)$ will always be $0^n$ since every permutation of $0^n$ is $0^n$ and therefore every message $m$ gets encrypted as its plaintext: $c=m$ which obiously does not provide IND-CPA or OT-IND-CPA.

Am I missing something or is it really that easy?

r3mainer avatar
us flag
No, the permutation $E$ is a mapping from all values in $\{01\}^n$ to a different ordering of the same set of values. So the probability that $E_k(0^n)=0^n$ is negligible if $n$ is large.
fgrieu avatar
ng flag
Hint: when $k$ is fixed and $m$ varies, what part(s) of the expression defining $c$ varies? What about (various variants of) the IND-CPA property under that condition?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.