A polynomial-time universal security amplifier in the class of block ciphers (Q1429277)

An \(n\)-bit block cipher means an \(S_M\)-valued random variable in this paper, where \(M\) is the set of all \(n\)-bit binary strings, and \(S_M\) is the symmetric group consisting of all invertible functions on \(M\). For two independent ciphers \(X\) and \(Y\), the cipher \(XY\) is called a product cipher. The cipher \(U\) which is uniformly distributed on \(S_M\) is called the perfect cipher. After defining the optimally chosen plaintext attack work factor \(\theta_l(X)\), a measure of security for \(X\), the main result is proven by construction: There is a cipher \(X\), computable in polynomial-time, such that for each \(0\leq l \leq 2^n\) and any independent cipher \(Y\), \(\theta_l(XY) \geq \theta_l(Y)\); and equality holds if and only if \(\theta_l(Y) \geq \theta_l(U)\).