BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
This paper is a compressed summary of some principal definitions and concepts in the approach to the black box algebra being developed by the authors. We suggest that black box algebra could be useful in cryptanalysis of homomorphic encryption schemes, and that homomorphic encryption is an area of research where cryptography and black box algebra may benefit from exchange of ideas.
Given a global exponent E for a black box group Y encrypting SL2(F), where F is an unknown finite field of unknown odd characteristic, we construct, in probabilistic time polynomial in logE, the isomorphisms Y⟷SL2(K), where K is a black box field encrypting F. Our algorithm makes no reference to any additional oracles. We also give similar algorithms for black box groups encrypting PGL2(F), PSL2(F).
For the black box groups X encrypting PGL2(q), q odd, we propose an algorithm constructing a subgroup encrypting Sym4 and subfield subgroups of X. We also present the analogous algorithms for black box groups encrypting (P)SL2(q).
The paper proposes a new and systematic approach to the so-called black box group methods in computational group theory. As the starting point of our programme, we construct Frobenius maps on black box groups of untwisted Lie type in odd characteristic and then apply them to black box groups X encrypting groups (P)SL(2,q) in small odd characteristics. We propose an algorithm constructing a black box field K isomorphic to F_q, and an isomorphism from (P)SL(2,K) to X. The algorithm runs in time quadratic in the characteristic of the underlying field and polynomial in log q. Due to the nature of our work we also have to discuss a few methodological issues of the black box group theory.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.