A Note on Output Length of One-Way State Generators and EFIs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914579650445312 |
|---|---|
| author | Hhan, Minki Morimae, Tomoyuki Yamakawa, Takashi |
| author_facet | Hhan, Minki Morimae, Tomoyuki Yamakawa, Takashi |
| contents | We study the output length of one-way state generators (OWSGs), their weaker variants, and EFIs.
- Standard OWSGs. Recently, Cavalar et al. (arXiv:2312.08363) give OWSGs with $m$-qubit outputs for any $m=ω(\log λ)$, where $λ$ is the security parameter, and conjecture that there do not exist OWSGs with $O(\log \log λ)$-qubit outputs. We prove their conjecture in a stronger manner by showing that there do not exist OWSGs with $O(\log λ)$-qubit outputs. This means that their construction is optimal in terms of output length.
- Inverse-polynomial-advantage OWSGs. Let $ε$-OWSGs be a parameterized variant of OWSGs where a quantum polynomial-time adversary's advantage is at most $ε$. For any constant $c\in \mathbb{N}$, we construct $λ^{-c}$-OWSGs with $((c+1)\log λ+O(1))$-qubit outputs assuming the existence of OWFs. We show that this is almost tight by proving that there do not exist $λ^{-c}$-OWSGs with at most $(c\log λ-2)$-qubit outputs.
- Constant-advantage OWSGs. For any constant $ε>0$, we construct $ε$-OWSGs with $O(\log \log λ)$-qubit outputs assuming the existence of subexponentially secure OWFs. We show that this is almost tight by proving that there do not exist $O(1)$-OWSGs with $((\log \log λ)/2+O(1))$-qubit outputs.
- Weak OWSGs. We refer to $(1-1/\mathsf{poly}(λ))$-OWSGs as weak OWSGs. We construct weak OWSGs with $m$-qubit outputs for any $m=ω(1)$ assuming the existence of exponentially secure OWFs with linear expansion. We show that this is tight by proving that there do not exist weak OWSGs with $O(1)$-qubit outputs.
- EFIs. We show that there do not exist $O(\log λ)$-qubit EFIs. We show that this is tight by proving that there exist $ω(\log λ)$-qubit EFIs assuming the existence of exponentially secure PRGs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_16025 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Note on Output Length of One-Way State Generators and EFIs Hhan, Minki Morimae, Tomoyuki Yamakawa, Takashi Quantum Physics Computational Complexity Cryptography and Security We study the output length of one-way state generators (OWSGs), their weaker variants, and EFIs. - Standard OWSGs. Recently, Cavalar et al. (arXiv:2312.08363) give OWSGs with $m$-qubit outputs for any $m=ω(\log λ)$, where $λ$ is the security parameter, and conjecture that there do not exist OWSGs with $O(\log \log λ)$-qubit outputs. We prove their conjecture in a stronger manner by showing that there do not exist OWSGs with $O(\log λ)$-qubit outputs. This means that their construction is optimal in terms of output length. - Inverse-polynomial-advantage OWSGs. Let $ε$-OWSGs be a parameterized variant of OWSGs where a quantum polynomial-time adversary's advantage is at most $ε$. For any constant $c\in \mathbb{N}$, we construct $λ^{-c}$-OWSGs with $((c+1)\log λ+O(1))$-qubit outputs assuming the existence of OWFs. We show that this is almost tight by proving that there do not exist $λ^{-c}$-OWSGs with at most $(c\log λ-2)$-qubit outputs. - Constant-advantage OWSGs. For any constant $ε>0$, we construct $ε$-OWSGs with $O(\log \log λ)$-qubit outputs assuming the existence of subexponentially secure OWFs. We show that this is almost tight by proving that there do not exist $O(1)$-OWSGs with $((\log \log λ)/2+O(1))$-qubit outputs. - Weak OWSGs. We refer to $(1-1/\mathsf{poly}(λ))$-OWSGs as weak OWSGs. We construct weak OWSGs with $m$-qubit outputs for any $m=ω(1)$ assuming the existence of exponentially secure OWFs with linear expansion. We show that this is tight by proving that there do not exist weak OWSGs with $O(1)$-qubit outputs. - EFIs. We show that there do not exist $O(\log λ)$-qubit EFIs. We show that this is tight by proving that there exist $ω(\log λ)$-qubit EFIs assuming the existence of exponentially secure PRGs. |
| title | A Note on Output Length of One-Way State Generators and EFIs |
| topic | Quantum Physics Computational Complexity Cryptography and Security |
| url | https://arxiv.org/abs/2312.16025 |