Unpredictable permutation
 | This article may be too technical for most readers to understand. (November 2011) |
In combinatorial mathematics, an unpredictable permutation (UP) Fk is a permutation where a probablistic polynomial-time (PPT) adversary cannot predict the outcome of the challenge query Fk, that was queried on a new input m during the challenge round. This happens after the adversary queries Fk on many inputs before finally accepting the challenge. Here, the adversary has access to an oracle for both forward and inverse permutation operations and has to predict an unqueried input/output pair. This is the challenge [1] [3].
It can be shown that a function Fk is not a secure Message Authentication Code (MAC) if it satisfies only the unpredictability requirement [1]. It can also be shown that one cannot build an efficient variable input length MAC from a block cipher which is modelled as an UP of n bits. It has been shown that the output of a k = n/ω(log λ) round Feistel construction with unpredictable round functions may leak all the intermediate round values. Even for realistic Unpredictable Functions (UF), some partial information about the intermediate round values may be leaked through the output. It was later shown that if a super-logarithmic number of rounds in the Feistel construction is used, then the resulting UP construction is secure even if the adversary gets all the intermediate round values along with the permutation output [4].
There is also a theorem that has been proven in this regard which states that if there exists an efficient UP adversary Aπ that has non-negligible advantage επ in the unpredictability game against UP construction ψU,k and which makes a polynomial number of queries to the challenger, then there also exists a UF adversary Af that has non-negligible advantage in the unpredictability game against a UF sampled from the UF family F . From this, it can be shown that the maximum advantage of the UP adversary Aπ is επ = O (εf. (qk)6). Here εf denotes the maximum advantage of a UF adversary running in time O(t + (qk)5) against a UF sampled from F, where t is the running time of the PRP adversary Aψ and q is the number of queries made by it [2] [4].
In addition, a signature scheme that satisfies the property of unpredictability and not necessarily pseudo- randomness is essentially a Verifiable Unpredictable Function (VUF). A verifiable unpredictable function is defined analogously to a Verifiable Pseudorandom Function (VRF) but for pseudo- randomness being substituted with weaker unpredictability. Verifiable unpredictable permutations are the permutation analogs of VUFs or unpredictable analogs of VRPs. A VRP is also a VUP and a VUP can actually be built by building a VRP via the Feistel construction applied to a VRF. But this is not viewed useful since VUFs appear to be much easier to construct than VRFs [5].