There Are No Post-Quantum Weakly Pseudo-Free Families in Any Nontrivial Variety of Expanded Groups
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913431567728640 |
|---|---|
| author | Anokhin, Mikhail |
| author_facet | Anokhin, Mikhail |
| contents | Let $Ω$ be a finite set of finitary operation symbols and let $\mathfrak V$ be a nontrivial variety of $Ω$-algebras. Assume that for some set $Γ\subseteqΩ$ of group operation symbols, all $Ω$-algebras in $\mathfrak V$ are groups under the operations associated with the symbols in $Γ$. In other words, $\mathfrak V$ is assumed to be a nontrivial variety of expanded groups. In particular, $\mathfrak 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 $\mathfrak V$, even in the worst-case setting and/or the black-box model. In this paper, we restrict ourselves to families $(H_d\mathbin|d\in D)$ of computational and black-box $Ω$-algebras (where $D\subseteq\{0,1\}^*$) such that for every $d\in 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 weak pseudo-freeness for families of computational and black-box $Ω$-algebras. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_10847 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | There Are No Post-Quantum Weakly Pseudo-Free Families in Any Nontrivial Variety of Expanded Groups Anokhin, Mikhail Cryptography and Security Computational Complexity 94A60 (primary), 68Q12, 68Q09, 08A70 (secondary) Let $Ω$ be a finite set of finitary operation symbols and let $\mathfrak V$ be a nontrivial variety of $Ω$-algebras. Assume that for some set $Γ\subseteqΩ$ of group operation symbols, all $Ω$-algebras in $\mathfrak V$ are groups under the operations associated with the symbols in $Γ$. In other words, $\mathfrak V$ is assumed to be a nontrivial variety of expanded groups. In particular, $\mathfrak 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 $\mathfrak V$, even in the worst-case setting and/or the black-box model. In this paper, we restrict ourselves to families $(H_d\mathbin|d\in D)$ of computational and black-box $Ω$-algebras (where $D\subseteq\{0,1\}^*$) such that for every $d\in 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 weak pseudo-freeness for families of computational and black-box $Ω$-algebras. |
| title | There Are No Post-Quantum Weakly Pseudo-Free Families in Any Nontrivial Variety of Expanded Groups |
| topic | Cryptography and Security Computational Complexity 94A60 (primary), 68Q12, 68Q09, 08A70 (secondary) |
| url | https://arxiv.org/abs/2302.10847 |