5
$\begingroup$

Let $n$ be an integer (the motivating context had $n\approx2^{27}$). All other lowercase variables are non-negative integers less than $n$ (elements of $\mathbb Z_n$). All uppercase variables are vectors of $n$ distinct such elements, or equivalently permutations of $n$ elements.

We want to efficiently distinguish among oracles, with as few queries as possible, in an experiment where an oracle initializes, then at query $j$ outputs a permutation $V_j$, with the additional property that: $\forall i,\forall j,\forall k,\;j\ne k\implies V_j[i]\ne V_k[i]$.

  1. Oracle 1 initializes with an empty memory of earlier outputs, then at each query outputs a random permutation uniformly distributed among those still allowed by the additional property.
  2. Oracle 2 initializes by choosing 3 independent random uniformly distributed permutations $P$, $Q$, $R$; then computes $V_j[i]$ as $R[(P[i]+Q[j])\bmod n]$.

Both oracles meet their duty and can answer $n$ queries. Each of their output, taken in isolation, is indistinguishable from a random permutation. The scheme of oracle 2 and standard Format-Preserving Encryption techniques allow to build a PRP generator meeting the additional property, with $O(\ln n)$ memory, and direct access to any output value.

By a counting argument, for $n>4$, a distinguisher is possible with 3 queries if we disregard efficiency. But how can we build an efficient distinguisher?

Any proposal for an efficiently implementable oracle 3, harder to distinguish from oracle 1?


Additions:

  • As pointed by David Cary, what's constructed is known as a latin square. Terry Ritter has a literature survey, and discussions on their uses in cryptography. See also Smile Markovski Design of crypto primitives based on quasigroups in Quasigroups and Related Systems, 2015.
  • Possible application: decide how to lend to participant $i$ out of $n$, on week $j$, sample number $V_j[i]$ out of $n$, in a randomized manner additionally such that no participant gets the same sample twice. In that practice, permutations can be implemented as ciphers using Format Preserving Encryption.
  • Proof that Oracle 2 has the additional property: If $j\ne k$, then (since $Q$ is a permutation, thus injective) it holds that $Q[j]\ne Q[k]$, thus $((P[i]+Q[j])\bmod n)\ne((P[i]+Q[k])\bmod n)$, thus $R[(P[i]+Q[j])\bmod n]\ne R[(P[i]+Q[k])\bmod n]$, thus $V_j[i]\ne V_k[i]$.
$\endgroup$
  • $\begingroup$ To clarify: the $j$th time you query the oracle, it returns an entire permutation of $n$ items? $\endgroup$ – Mikero Oct 18 '16 at 3:21
  • 1
    $\begingroup$ @Mikero: Yes. The oracle reveals a line of a latin square at each query. $\endgroup$ – fgrieu Oct 18 '16 at 5:27
  • 1
    $\begingroup$ Thank you for mentioning my modest contribution. You might also add a link to "Latin Squares in Cryptography" next to the link you already have to "Latin Squares: A Literature Survey". $\endgroup$ – David Cary Oct 20 '16 at 3:15
2
$\begingroup$

a distinguisher is possible with 3 queries if we disregard efficiency. But how can we build an efficient distinguisher?

I'm not sure exactly what you mean by efficient (since $n \approx 2^{27}$ is a small number), but here is a sketch of a possible constructive attack. I'll let you tell me whether this satisfies your idea of efficiency. I figure that if you have enough time to accept a long ($n$ items) output from the oracle, you have time to do the attack I have in mind. To keep notation cleaner, I won't explicitly write the modular reductions in $R[ \alpha \bmod n ]$.

Query twice, to obtain (assuming oracle #2): $V_1[i] = R[ P[1] + Q[j] ]$ and $V_2[i] = R[ P[2] + Q[j] ]$. Let $\Delta = P[2] - P[1] \bmod n$, which is unknown to the attacker. Still, if $V_1[i] = R[\alpha]$ then $V_2[i] = R[\alpha + \Delta]$. So the function $F$ that maps all $V_1[i]$ to $V_2[i]$ (which the attacker can compute) is a function that maps all $R[\alpha]$ to $R[\alpha + \Delta]$.

I think the cycle structure of $F$ already leads to an attack! For example, if $n$ is prime then $F$ must be a simple cycle. This is because the sequence $\alpha, \alpha+\Delta, \alpha+2\Delta, \ldots$ generates all numbers mod $n$ before repeating (so $F$ visits all positions in $R$ before repeating). But I would guess that under oracle #1, the attacker would get $F$ to be a random involution. So this already gives an attack with reasonable bias, with just 2 queries.

In general, all cycles in $F$ must have cycle length that divides $n$ (in the presence of oracle #2). Again, this seems much less likely to happen in the presence of oracle #1.

OK, but suppose that reasoning doesn't work out for some reason. In that case, make another query. The attacker can compute a new $F$ again now using $\{V_2,V_3\}$ this time instead of $\{V_1, V_2\}$. If we got lucky, and $P[3]-P[2] = \Delta$ (which happens with probability $1/n$), then the attacker will obtain the same $F$ as before! Again I have not worked out the probabilities, but in the presence of oracle #1 this event seems much less likely than probability $1/n$.

$\endgroup$

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.