量子情報時代の新暗号基礎:量子状態識別問題の暗号論的性質解明とその応用

量子信息时代密码学新基础：量子态识别问题的密码学性质阐明及其应用

• 批准号: 17700007
• 负责人: 河内 亮周
• 金额: $ 2.18万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17700007/
• 关键词: 量子コンピュータ; 暗号・認証等; 計算量理論; 量子状態識別問題; 量子公開鍵暗号系; 平均時・最悪時計算量の等価性; グラフ自己同型性判定問題

今年度では量子状態識別問題に関す基礎的研究から応用プロトコルまでの研究を行くった。特に基礎研究では隠れ部分群問題と呼ばれる量子アルゴリズム分野において非常に重要な問題を量子状態式別問題に帰着し,その計算量を量子情報理論的手法により特徴付けることに成功した.この成果により,本プロジェクトで以前提案していた量子状態を利用した公開鍵暗号プロトコルの情報理論的観点からの安全性証明を与えることができた.また新しい量子状態を利用した公開鍵暗号系も構成でき,ある条件下での最適性を証明することができた.このプロトコルもあるモデルの下で情報理論的な安全性を保証することができる.別の応用プロトコルでは量子アルゴリズムに対しても現在のところ耐性を持っている整数格子問題と呼ばれる計算困難問題に基づいた公開鍵暗号系の改良に成功した.この問題は直接的には量子状態識別問題を利用はしていないが,その古典版である確率分布識別問題を利用しており,量子状態識別問題の研究で得られた知見を応用することができた.

今年，我们一直在从基础研究中进行量子状态识别问题到应用方案的研究。特别是，基础研究，我们在称为“隐藏的亚组问题”的量子算法领域中实现了一个非常重要的问题，用于量子状态特异性问题，并成功地使用了量子信息理论方法来表征计算的复杂性。通过提供了使用该项目中先前提出的量子状态的公共密钥密码学协议的信息理论观点的安全证明，从而实现了这一结果。我们还可以构建一个使用量子状态的新的公共密钥加密系统，并在某些条件下证明了最佳性。该协议可以在某些模型下保证信息理论安全性。另一个应用协议已基于难以计算的问题（称为整数晶格问题）成功改善了公共密钥加密系统，该问题目前对量子算法具有抵抗力。此问题并未直接利用量子状态识别问题，而是使用概率分布识别问题的经典版本，并且可以应用从量子状态识别问题的研究中获得的发现。

项目成果

Universal Test for Quantum One-Way Permutations

量子单向排列的通用测试

• 发表时间: 2005
• 期刊: Theoretical Computer Science 345・22
• 作者: Akinori Kawachi;Hirotada Kobayashi;Takeshi Koshiba;Raymond H. Putra
• 通讯作者: Raymond H. Putra

NP困難問題における最悪時困難性からの平均時困雌性証明への試み

尝试从 NP 困难问题的最坏情况难度证明平均时间难度

• 发表时间: 2007
• 作者: 河内 亮周;渡辺 治
• 通讯作者: 渡辺 治

Multi-bit Cryptosystems Based on Lattice Problems

• DOI: 10.1007/978-3-540-71677-8_21
• 发表时间: 2006-05
• 作者: Akinori Kawachi;Keisuke Tanaka;Keita Xagawa

Quantum Computational Cryptography

量子计算密码学

• 发表时间: 2006
• 期刊: Topics in Applied Physics 102
• 作者: Akinori Kawachi;Takeshi Koshiba
• 通讯作者: Takeshi Koshiba

Progress in Quantum Computational Cryptography

量子计算密码学的进展

• 发表时间: 2006
• 期刊: Journal of Universal Computer Science Vol.12, No.6
• 作者: Akinori Kawachi;Takeshi Koshiba
• 通讯作者: Takeshi Koshiba