NATURAL REPRESENTATIONS OF BLACK BOX GROUPS ENCRYPTING SL2(Fq)

Abstract

Given a global exponentEfor a black box groupYencrypting SL2(F), whereFis an unknown finite field of unknown odd characteristic, we construct, in probabilistic time polynomial in logE, the isomorphismsY←→SL2(K),whereKis a black box field encryptingF. Our algorithm makes no reference to any additional oracles. We also give similar algorithms for black box groups encrypting PGL2(F), PSL2(F).