Quantum-Secure Cryptography
and Fine-Grained Quantum Query Complexity
About
This was a project funded by the NSF Algorithmic Foundations program, in the Division of Computing and Communication Foundations. The full title of the project was “AF: Medium: Collaborative Research: Quantum-Secure Cryptography and Fine-Grained Quantum Query Complexity.” The start date was August 1, 2018 and the end date was July 31, 2021. It was a collaborative project involving three institutions: University of Maryland, University of Connecticut, and Portland State University (and, for a time, Texas A&M University.)
Project abstract
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.
Project institutions and personnel
| Institution | PI | Students |
| University of Maryland | Gorjan Alagic | Bibhusa Rawal |
| University of Connecticut | Alex Russell | Luke Johnson |
| Portland State University | Fang Song | Ben Hamlin and Chuhan Lu |
Publications
| Author | Title | Year | Journal/Proceedings | Reftype | DOI/URL |
|---|---|---|---|---|---|
| Alagic, G., Brakerski, Z., Dulek, Y. and Schaffner, C. | Impossibility of quantum virtual black-box obfuscation of classical circuits [BibTeX] |
2021 | Annual International Cryptology Conference, pp. 497-525 | inproceedings | |
BibTeX:
@inproceedings{ABDS21,
author = {Alagic, Gorjan and Brakerski, Zvika and Dulek, Yfke and Schaffner, Christian},
title = {Impossibility of quantum virtual black-box obfuscation of classical circuits},
booktitle = {Annual International Cryptology Conference},
year = {2021},
pages = {497--525}
}
|
|||||
| Cojocaru, A., Garay, J., Kiayias, A., Song, F. and Wallden, P. | Post-Quantum Security of the Bitcoin Backbone and Quantum Multi-Solution Bernoulli Search [BibTeX] |
2021 | arXiv preprint arXiv:2012.15254 | misc | |
BibTeX:
@misc{CGKSW21,
author = {Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, Petros Wallden},
title = {Post-Quantum Security of the Bitcoin Backbone and Quantum Multi-Solution Bernoulli Search},
year = {2021},
note = {https://arxiv.org/abs/2012.15254}
}
|
|||||
| Demarest, L., Fuller, B. and Russell, A. | Code Offset in the Exponent [BibTeX] |
2021 | Vol. 1992nd Conference on Information-Theoretic Cryptography, ITC 2021, July 23-26, 2021, Virtual Conference, pp. 15:1-15:23 |
inproceedings | DOI URL |
BibTeX:
@inproceedings{DBLP:conf/citc/Demarest0R21,
author = {Luke Demarest and Benjamin Fuller and Alexander Russell},
title = {Code Offset in the Exponent},
booktitle = {2nd Conference on Information-Theoretic Cryptography, ITC 2021, July 23-26, 2021, Virtual Conference},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
year = {2021},
volume = {199},
pages = {15:1--15:23},
url = {https://doi.org/10.4230/LIPIcs.ITC.2021.15},
doi = {https://doi.org/10.4230/LIPIcs.ITC.2021.15}
}
|
|||||
| Alagic, G., Majenz, C. and Russell, A. | Efficient simulation of random states and random unitaries [BibTeX] |
2020 | Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 759-787 | inproceedings | URL |
BibTeX:
@inproceedings{alagic2020efficient,
author = {Alagic, Gorjan and Majenz, Christian and Russell, Alexander},
title = {Efficient simulation of random states and random unitaries},
booktitle = {Annual International Conference on the Theory and Applications of Cryptographic Techniques},
year = {2020},
pages = {759--787},
url = {https://arxiv.org/abs/1910.05729}
}
|
|||||
| Alagic, G., Childs, A.M., Grilo, A.B. and Hung, S.-H. | Non-interactive classical verification of quantum computation [BibTeX] |
2020 | Theory of Cryptography Conference, pp. 153-180 | inproceedings | |
BibTeX:
@inproceedings{alagic2020non,
author = {Alagic, Gorjan and Childs, Andrew M and Grilo, Alex B and Hung, Shih-Han},
title = {Non-interactive classical verification of quantum computation},
booktitle = {Theory of Cryptography Conference},
year = {2020},
pages = {153--180}
}
|
|||||
| Alagic, G., Majenz, C., Russell, A. and Song, F. | Quantum-access-secure message authentication via blind-unforgeability [BibTeX] |
2020 | Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 788-817 | inproceedings | |
BibTeX:
@inproceedings{alagic2020quantum,
author = {Alagic, Gorjan and Majenz, Christian and Russell, Alexander and Song, Fang},
title = {Quantum-access-secure message authentication via blind-unforgeability},
booktitle = {Annual International Conference on the Theory and Applications of Cryptographic Techniques},
year = {2020},
pages = {788--817}
}
|
|||||
| Alagic, G., Jeffery, S., Ozols, M. and Poremba, A. | On Quantum Chosen-Ciphertext Attacks and Learning with Errors [BibTeX] |
2020 | Cryptography Vol. 4(1), pp. 10 |
article | |
BibTeX:
@article{alagic2020quantum,
author = {Alagic, Gorjan and Jeffery, Stacey and Ozols, Maris and Poremba, Alexander},
title = {On Quantum Chosen-Ciphertext Attacks and Learning with Errors},
journal = {Cryptography},
publisher = {Multidisciplinary Digital Publishing Institute},
year = {2020},
volume = {4},
number = {1},
pages = {10}
}
|
|||||
| Eaton, E. and Song, F. | A Note on the Instantiability of the Quantum Random Oracle [BibTeX] |
2020 | International Conference on Post-Quantum Cryptography, pp. 503-523 | inproceedings | DOI URL |
BibTeX:
@inproceedings{ES20,
author = {Eaton, Edward and Song, Fang},
title = {A Note on the Instantiability of the Quantum Random Oracle},
booktitle = {International Conference on Post-Quantum Cryptography},
year = {2020},
pages = {503--523},
url = {https://doi.org/10.1007/978-3-030-44223-1_27},
doi = {https://doi.org/10.1007/978-3-030-44223-1_27}
}
|
|||||
| Hamlin, B. and Song, F. | Quantum security of hash functions and property-preservation of iterated hashing [BibTeX] |
2019 | 10th International Conference on Post-Quantum Cryptography (PQCrypto 2019) | inproceedings | DOI URL |
BibTeX:
@inproceedings{HS19,
author = {Hamlin, Ben and Song, Fang},
title = {Quantum security of hash functions and property-preservation of iterated hashing},
booktitle = {10th International Conference on Post-Quantum Cryptography (PQCrypto 2019)},
year = {2019},
url = {https://doi.org/10.1007/978-3-030-25510-7_18},
doi = {https://doi.org/10.1007/978-3-030-25510-7_18}
}
|
|||||