NTT Research, Inc., a subsidiary of NTT (TYO: 9432), today announced that two scientists from the NTT Research Cryptography & Information Security (CIS) Lab and NTT Social Informatics Laboratories have written papers selected to be presented at the annual IEEE Symposium on Foundations of Computer Science (FOCS). The FOCS Symposium (FOCS 2021) is taking place virtually, Feb. 7-10, 2022. Event organizers have scheduled 118 presentations over the four-day program. The two papers associated with NTT scientists address aspects of challenges that quantum computing poses to cryptographic systems. One paper, titled “Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier,” is co-authored by NTT Research CIS Lab Senior Scientist and Princeton University Assistant Professor Mark Zhandry; the other, “On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds,” is co-authored by Takashi Yamakawa, Researcher, NTT Social Informatics Laboratories. These papers are being presented back-to-back on Feb 7, 2022, Day 1 of the event, at 9:00 am and 9:25 am ET, respectively.
Sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), FOCS is a leading conference in the field of theoretical computer science. The call for papers for this event listed quantum computing as one of sixteen areas of interest. Fully realized, quantum computers hold great promise but also pose threats to existing public-key cryptosystems. These NTT-affiliated papers point to areas that are – and are not – likely to be feasible going forward. The “Post-Quantum Succinct Arguments” paper co-authored by Dr. Zhandry introduces a powerful technique to facilitate “rewinding” in the quantum state. The “Post-Quantum Black-Box Zero-Knowledge (ZK)” paper co-authored by Dr. Yamakawa, on the other hand, demonstrates that very efficient (“constant round”) ZK proofs may not be possible in the quantum state.
“We were excited to learn that FOCS had selected these two papers, which break new ground in our understanding of post-quantum cryptography and deserve widespread attention,” said NTT Research CIS Lab Director Tatsuaki Okamoto. “I also hope that their positions as ‘leadoff batters’ on Day 1 augur well for the success of this prestigious conference.”
In the paper by Zhandry (and Alessandro Chiesa, Fermi Ma and Nicholas Spooner), rewinding is an important tool for security reductions. In cryptography, security is proved by means of a reduction, which transforms an adversary into an efficient algorithm for the hard problem – such as factoring integers or lattice structures – around which a given cryptosystem is designed. In rewinding, the reduction runs the adversary to a certain point in time, backtracks to a previous step, changes the adversary’s view in some way, and then runs the adversary again. The program state of a quantum algorithm, however, is very delicate and generally is destroyed when running the adversary. The paper develops a powerful new rewinding technique for quantum adversaries. By combining this technique with Learning With Errors (LWE)-based collapsible hashes, the paper proves the post-quantum security of a thirty-year-old succinct argument system (Kilian’s protocol) for which no reduction compatible with quantum attackers was previously known.
The second paper by Yamakawa (and Nai-Hui Chia, Kai-Min Chung and Qipeng Liu) focuses on ZK interactive proofs, fundamental cryptographic primitives that allow one party (the prover) to prove to another party (a malicious verifier) without revealing additional information, except that the statement is true. These protocols have been expressed in a range of languages, including those classified as non-deterministic polynomial (NP) hard. Apart from their wide expression, ZK proofs also exhibit efficiency, even in NP. They achieve constant rounds of communication vs. super-constant rounds, which add significant latency. How they do so is through rewinding (see above) and providing black-box access to the malicious verifier. A post-quantum ZK protocol has been introduced using a technique other than the quantum-averse rewinding, but it requires a super-constant number of rounds and, hence, suffers from latency issues. Non-black-box techniques are also available, yet they can be computationally inefficient as well, incurring slow-downs by factors of 1 million or more. Thus, this paper’s negative, though intriguing conclusion: very efficient ZK proofs may not be quantumly possible.
“What I find very interesting about Takashi’s work is that it highlights a really subtle issue with quantum algorithms: the nature of time,” said Dr. Zhandry, who has sponsored Dr. Yamakawa as a visitor to Princeton. “Algorithms will often have different running times on different inputs, or even variable running times on the same inputs. Classically, this isn’t much of an issue; however, quantumly, Takashi’s work shows that these variable run times can be quite problematic.” About his paper on the rewinding barrier, Dr. Zhandry pointed to the quantum threat of overriding Kilian’s protocol, convincing someone of a false statement because prior techniques could not rewind enough: “Our result shows that there is nothing to worry about, provided you use a collapsing hash function inside the protocol.”
This upcoming event is the 62nd FOCS Symposium. It has traditionally been held in the autumn and is paired with its sister conference, the annual Symposium on Theory of Computing (STOC), held in an opposite season and sponsored by the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory (ACM SIGACT), whose purpose is support of research in theoretical computer science. To register and learn more about this event, please visit the FOCS 2021 website.
About NTT Research
NTT Research opened its offices in July 2019 as a new Silicon Valley startup to conduct basic research and advance technologies that promote positive change for humankind. Currently, three labs are housed at NTT Research facilities in Sunnyvale: the Physics and Informatics (PHI) Lab, the Cryptography and Information Security (CIS) Lab, and the Medical and Health Informatics (MEI) Lab. The organization aims to upgrade reality in three areas: 1) quantum information, neuroscience and photonics; 2) cryptographic and information security; and 3) medical and health informatics. NTT Research is part of NTT, a global technology and business solutions provider with an annual R&D budget of $3.6 billion.
About NTT Social Informatics Laboratories
NTT Social Informatics Laboratories, a division of NTT R&D, is engaged in research and development of technologies to contribute to the transformation and development of advanced social systems and human societies through ICT. Research objectives include: wellbeing research for human happiness; innovation technology for social systems through the fusion of ICT technology and social science; establishment of new technologies to eliminate threats such as cyberattacks; establishment of technologies to realize innovations to create safe social systems through the analysis and prediction of social information; creation of high-value-added social systems through data distribution and utilization that balances usability and security; new data protection technology that utilizes cryptography as well as physical properties; and creation of fundamental next-generation cryptography theories that will lead global expansion.
NTT and the NTT logo are registered trademarks or trademarks of NIPPON TELEGRAPH AND TELEPHONE CORPORATION and/or its affiliates. All other referenced product names are trademarks of their respective owners. © 2022 NIPPON TELEGRAPH AND TELEPHONE CORPORATION
View source version on businesswire.com: https://www.businesswire.com/news/home/20220207005164/en/