| 講演名 | 2023-05-11 擬ランダム量子状態に必要な計算量的仮定 白川 雄貴(京大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 擬ランダム量子状態生成器(PRSGs)とはHaarランダムな状態と計算量的に区別出来ない量子状態を効率的に生成するアルゴリズムである．セキュリティパラメータ$lambda$に対して$loglambda$以上のqubit数を持つPRSGsが存在するためには何らかの計算量的仮定が必要であることが知られている．我々は，$n(lambda)=O(log lambda)$かつ$n(lambda)gelog lambda$を満たす$n(lambda)$に対して$n(lambda)$-qubit状態を出力するPRSGsが存在するために$mathbf{BQP}neq mathbf{QCMA}$が必要であることを示した．さらにPRSGsから構成される古典通信量子擬one-time pad(ccQPOTP)と呼ばれる暗号プリミティブに着目し，ccQPOTPの安全性にも$mathbf{BQP}neqmathbf{QCMA}$が必要であることを明らかにした． |
| 抄録(英) | 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. |
| キーワード(和) | 量子計算 / 量子暗号 / computational complexity / pseudorandomness |
| キーワード(英) | quantum computation / quantum cryptography / computational complexity / pseudorandomness |
| 資料番号 | COMP2023-2 |
| 発行日 | 2023-05-03 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2023/5/10(から2日開催) |
| 開催地（和） | 北海道大学 |
| 開催地（英） | Hokkaido University |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 委員長氏名（和） | 宇野 裕之(大阪公立大) |
| 委員長氏名（英） | Hiroyuki Uno(Osaka Metropolitan Univ.) |
| 副委員長氏名（和） | 来嶋 秀治(滋賀大) |
| 副委員長氏名（英） | Shuji Kijima(Shiga Univ.) |
| 幹事氏名（和） | 和佐 州洋(法政大) / 横井 優(NII) |
| 幹事氏名（英） | Kunihiro Wasa(Hosei Univ.) / Yu Yokoi(NII) |
| 幹事補佐氏名（和） | 安藤 映(専修大) |
| 幹事補佐氏名（英） | Ei Ando(Senshu Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 擬ランダム量子状態に必要な計算量的仮定 |
| サブタイトル（和） | |
| タイトル（英） | A computational complexity assumption necessary for pseudorandom quantum states generators |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子計算 / quantum computation |
| キーワード(2)（和/英） | 量子暗号 / quantum cryptography |
| キーワード(3)（和/英） | computational complexity / computational complexity |
| キーワード(4)（和/英） | pseudorandomness / pseudorandomness |
| 第 1 著者 氏名（和/英） | 白川 雄貴 / Yuki Shirakawa |
| 第 1 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 発表年月日 | 2023-05-11 |
| 資料番号 | COMP2023-2 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | COMP-12 |
| ページ範囲 | pp.2-7(COMP), |
| ページ数 | 6 |
| 発行日 | 2023-05-03 (COMP) |