There are no post-quantum weakly pseudo-free families in any nontrivial variety of expanded groupsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 17 июля 2024 г.
Аннотация:Let Ω be a finite set of finitary operation symbols and let V be a nontrivial variety of Ω-algebras. Assume that for some set Γ ⊆ Ω of group operation symbols, all Ω-algebras in V are groups under the operations associated with the symbols in Γ. In other words, V is assumed to be a nontrivial variety of expanded groups. In particular, V can be a nontrivial variety of groups or rings. Our main result is that there are no post-quantum weakly pseudo-free families in V, 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. In our main result, we use straight-line programs to represent nontrivial relations between elements of Ω-algebras. Note that under certain conditions, this result depends on the classification of finite simple groups. Also, we define and study some types of post-quantum weak pseudo-freeness for families of computational and black-box Ω-algebras.