AF: Medium: Collaborative Research: Quantum-Secure Cryptography and Fine-Grained Quantum Query Complexity

AF：中：协作研究：量子安全密码学和细粒度量子查询复杂性

• 批准号: 1763736
• 负责人: Gorjan Alagic
• 金额: $ 27.5万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-08-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1763736&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Quantum

Secure Internet communication faces a real threat in the form of a new breed of computer that harnesses the laws of quantum mechanics. The technical community is currently hard at work attempting to construct such "quantum" computers. While many mysteries about these devices remain, it is certain that a large-scale quantum computer would easily break all current public-key cryptography that underpins the current Internet. In certain attack models, important examples of private-key cryptography would also be rendered insecure. This 3-institution collaborative project studies the basic theoretical issues underlying these urgent threats to the security infrastructure. It seeks to understand the cryptography-breaking power of quantum computers, concentrating on two interweaving themes: quantum security for 1) authenticating, and 2) constructing quantum-secure cryptography from new primitives. The project activities also include course development and mentorship at the graduate and undergraduate level. The project also involves specific outreach activities intended to broaden participation in Computer Science, including establishment and development of "women in computer science" chapters, outreach to local high schools, workshops for high-school STEM teachers, and development of computer science courses for a general audience at the three partner institutions.Authentication-proofs, for example, that an e-mail really did originate from you--is a basic and well-studied cryptographic challenge. In the setting of quantum adversaries, it is not clear how to appropriately formulate this essential notion, let alone produce specific cryptographic tools that achieve it. This project is addressing both of the challenges noted above, focusing on development of strong formulations of authentication and new cryptographic constructions that offer secure authentication. Finding "hidden" algebraic structures--like the fact that two lists of numbers are merely cyclic shifts of each other--is an emblematic theme in the study of the computing power of quantum computers. Certain variants of this problem have resisted decades of concerted effort by the quantum algorithms community, and appear to be quite difficult. This project studies applications of these problems to constructing new private-key cryptographic tools with quantum security guarantees.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

安全的互联网通信面临着一个真正的威胁，那就是利用量子力学定律的新型计算机。技术界目前正在努力尝试构建这样的“量子”计算机。虽然这些设备仍有许多未解之谜，但可以肯定的是，一台大规模量子计算机将很容易地破解当前支撑互联网的所有公钥加密技术。在某些攻击模型中，私钥加密的重要示例也会变得不安全。这个三家机构合作的项目研究了这些安全基础设施面临的紧迫威胁背后的基本理论问题。它试图理解量子计算机的密码破解能力，集中在两个相互交织的主题上：1)身份验证的量子安全，以及2)从新的原语构建量子安全加密。项目活动还包括研究生和本科生的课程开发和指导。该项目还涉及旨在扩大计算机科学参与的具体外展活动，包括建立和发展“计算机科学中的女性”分会，向当地高中外展，为高中STEM教师举办讲习班，以及在三所合作院校为普通受众开发计算机科学课程。身份验证（例如，证明电子邮件确实来自您）是一项基本的、经过充分研究的密码学挑战。在量子对手的设置中，尚不清楚如何适当地表述这一基本概念，更不用说产生实现它的特定加密工具了。该项目正在解决上述两个挑战，重点是开发强大的身份验证公式和提供安全身份验证的新加密结构。寻找“隐藏的”代数结构——比如两个数字列表只是彼此的循环移位——是研究量子计算机计算能力的一个标志性主题。这个问题的某些变体已经抵制了量子算法社区几十年的共同努力，并且看起来相当困难。本课题研究了这些问题在构造具有量子安全保证的新型私钥加密工具中的应用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Unforgeable Quantum Encryption

• DOI: 10.1007/978-3-319-78372-7_16
• 发表时间: 2017-09
• 期刊: ArXiv
• 作者: G. Alagic;Tommaso Gagliardoni;Christian Majenz

On Quantum Chosen-Ciphertext Attacks and Learning with Errors

关于量子选择密文攻击和错误学习

• 发表时间: 2019
• 期刊: and Cryptography 2019
• 作者: Alagic, Gorjan;Jeffery, Stacey;Ozols, Maris;Poremba, Alexander
• 通讯作者: Poremba, Alexander