Logic seminar

Some consequences of cryptographical conjectures for S^1_2 and EF

We present a paper by J. Krajicek and P. Pudlak from 1995. We show that if the RSA cryptosystem is secure, then \Delta^b_1 interpolation does not hold for S^1_2. Furthermore, we show that if factoring and discrete logarithm are in P/poly, then a certain \Pi^b_1 extension of S^1_2 does not admit \Delta^b_1 interpolation. At last, as a corollary we obtain that the feasible interpolation theorem fails for Extended Frege proof systems, if RSA is secure.