| Presentation | 2023-05-11 A computational complexity assumption necessary for pseudorandom quantum states generators Yuki Shirakawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Pseudorandom quantum states generators (PRSGs) are efficient quantum algorithms that output quantum states which are computationally indistinguishable from Haar random states. It is known that some computational assumptions are necessary for the existence of PRSGs which output more than $loglambda$-qubit states for the security parameter $lambda$. We show that $mathbf{BQP}neqmathbf{QCMA}$ is necessary for PRSGs with output length $n(lambda)$ satisfying $n(lambda)=O(log lambda)$ and $n(lambda)gelog lambda$. Moreover, we focus on classical-communication quantum pseudo one-time pad (ccQPOTP) schemes which are cryptographic primitives constructed from PRSGs and we also show that $mathbf{BQP}neqmathbf{QCMA}$ is necessary for the security of ccQPOTP schemes. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | quantum computation / quantum cryptography / computational complexity / pseudorandomness |
| Paper # | COMP2023-2 |
| Date of Issue | 2023-05-03 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2023/5/10(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Hokkaido University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Theoretical Computer Science, etc |
| Chair | Hiroyuki Uno(Osaka Metropolitan Univ.) |
| Vice Chair | Shuji Kijima(Shiga Univ.) |
| Secretary | Shuji Kijima(Hosei Univ.) / (NII) |
| Assistant | Ei Ando(Senshu Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A computational complexity assumption necessary for pseudorandom quantum states generators |
| Sub Title (in English) | |
| Keyword(1) | quantum computation |
| Keyword(2) | quantum cryptography |
| Keyword(3) | computational complexity |
| Keyword(4) | pseudorandomness |
| 1st Author's Name | Yuki Shirakawa |
| 1st Author's Affiliation | Kyoto University(Kyoto Univ.) |
| Date | 2023-05-11 |
| Paper # | COMP2023-2 |
| Volume (vol) | vol.123 |
| Number (no) | COMP-12 |
| Page | pp.pp.2-7(COMP), |
| #Pages | 6 |
| Date of Issue | 2023-05-03 (COMP) |