I feel I am misunderstanding the idea of nCPA security and its relation to uniform permutations. In particular I've been reading the paper "Hoang, Morris Rogaway; An Enciphering Scheme Based on a Card Shuffle".

My understanding of the definition of nCPA security is the following. Suppose that $E : \mathcal M \to \mathcal M$ is a permutation, ie $E(m) \neq E(m')$ for all $m \neq m'$. Suppose also that $\pi$ is a permutation chosen uniformly at random.

The adversary $A$ is then given an oracle, which is either $E$ or $\pi$ -- but she does not know which; her aim is to find out which one it is. She is allowed to ask $q$ queries of her oracle, and then must make her decision as to which she thinks it is. (This is non-adaptive, in the sense that she must decide in advance which questions to ask.)

The nCPA advantage of $A$ is then defined as $$ \bigl| P(A \text{ says } E \mid E) - P(A \text{ says } E \mid \pi) \bigr|.$$ (Note that this is the same as replacing "$\text{says } E$" by "$\text{says } \pi$", the probabilities sum to 1.) This part I may not be understanding correctly.

For two distributions $\mu$ and $\nu$ on a space $\Omega$, the total variation distance is defined as $$ \| \mu - \nu \| = \max_{A \subseteq \Omega} \bigl\| \mu(A) - \nu(A) \bigr\|. $$

In a related paper "Morris, Rogaway, Stegers; How to Encipher Messages on a Small Domain", the authors say

Total variation distance is identical to the advantage with repsect to a (deterministic) nCPA (non-adaptive, chosen-plaintext attack).

I sort of see why this might be the case, but not exactly. (There is no proof given, just the statement.)

My main source of confusion, though, is the following. In both the aforementioned papers, an enciphering scheme is given. Let's consider the first paper, for concreteness. This requires random integers $K_1, ..., K_r$ from $\{1,...,N\}$ and random bits $\{b_{i,j} \mid i = 1,...,r, \, j = 1,...,N/2\}$. Here $r$ is order $\log N$.

One of the advantages, though, is that in order to encrypt some $m \in \mathcal M = \{1,...,N\}$, one only needs to know the keys $K_1, ..., K_r$ and $r$ of the bits. However, if one wishes to generate the whole permutation $E$, the entire key is required.

It seems to me that one could just draw a uniform permutation naively: draw $\pi_1 \sim U(\{1,...,N\})$, then $\pi_2 \sim U(\{1,...,n\}\setminus\{\pi_1\})$, and so on. This takes time order $N$ (by Fisher-Yates); each round of the algorithm draws $N/2$ independent uniform bits, which I presume takes time order $N$. So if one wants the whole permutation, just draw it uniformly, rather than using an approximate method.

Alternatively, one wishes to just encrypt one, or a small number, of messages. Then just draw this part of the cipher. After all, one could just use the random integers $K_1, ..., K_r$. (Since $r \asymp \log n \ll \sqrt n$, with high probability all the $K_i$ will be different.)

Can someone explain to me what the purpose of a cipher, such as those described in the two linked papers, is?


Your Answer

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

Browse other questions tagged or ask your own question.