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]$.
- 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.
- 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]$.