There Are No Post-Quantum Weakly Pseudo-Free Families in Any Nontrivial Variety of Expanded Groups
Let Ξ© be a finite set of finitary operation symbols and let π be a nontrivial variety of Ξ©-algebras. Assume that for some set ΞβΞ© of group operation symbols, all Ξ©-algebras in π are groups under the operations associated with the symbols in Ξ. In other words, π is assumed to be a nontrivial variety of expanded groups. In particular, π can be a nontrivial variety of groups or rings. Our main result is that there are no post-quantum weakly pseudo-free families in π, even in the worst-case setting and/or the black-box model. In this paper, we restrict ourselves to families (H_d|dβ D) of computational and black-box Ξ©-algebras (where Dβ{0,1}^*) such that for every dβ D, each element of H_d is represented by a unique bit string of length polynomial in the length of d. We use straight-line programs to represent nontrivial relations between elements of Ξ©-algebras in our main result. Note that under certain conditions, this result depends on the classification of finite simple groups. Also, we define and study some types of weak pseudo-freeness for families of computational and black-box Ξ©-algebras.
READ FULL TEXT