Papers co-authored by CIS Lab and NTT R&D scientists win Best Paper Awards on quantum equivalence and elliptic curves; NTT-affiliated cryptographers contribute ten total papers
SUNNYVALE, Calif.–(BUSINESS WIRE)–#TechforGood—NTT Research, Inc., a division of NTT (TYO:9432), today announced that scientists from its Cryptography & Information Security (CIS) Lab and NTT R&D’s Social Informatics Laboratories (SIL) co-authored ten papers being delivered at Asiacrypt 2022, one of the leading international conferences on cryptologic research. Two of these papers won the conference’s Best Paper Awards: one paper on quantum equivalence co-authored by CIS Lab Senior Scientist Mark Zhandry, and another on elliptic curves co-authored by NTT SIL Distinguished Researcher Mehdi Tibouchi. Other members of the CIS Lab and SIL contributed three and four papers, respectively. One additional paper had both CIS Lab and SIL co-authors. Organized by the International Association for Cryptologic Research (IACR), this year’s hybrid event will take place in Taipei, December 5-9.
The Asiacrypt 2022 program committee, comprised of more than 80 experts, accepted nearly 100 submissions this year. According to the conference program, the two award-winning papers will be presented on Monday, December 6, at 7:40 pm EDT, during a special opening session. A third “best early career researcher” paper will also be recognized. The eight other NTT-affiliated papers will be presented in sessions on authenticated encryption, blockchains, functional encryption, random sources in private computation and symmetric cryptography.
Dr. Zhandry co-authored his paper with Dr. Hart Montgomery, chief technology officer of the Hyperledger Foundation, part of the Linux Foundation. Their paper, titled “Full Quantum Equivalence of Group Action DLog and CDH, and More,” demonstrates that two computationally hard problems – discrete logarithms (DLog) and computational Diffie-Hellman (CDH) – when structured as group actions are equally resistant to quantum attacks. Dr. Tibouchi’s co-authors, Drs. Jorge Chávez-Saab and Francisco Rodríguez-Henríquez, are members of the Computer Science Department, Cinvestav IPN (The Center for Research and Advanced Studies of the National Polytechnic Institute), in Mexico City, and the Cryptography Research Centre, Technology Innovation Institute, in Abu Dhabi. Their paper, titled “SwiftEC: Shallue-van de Woestijne Indifferentiable Function to Elliptic Curves,” shows how hashing to elliptic curves can be made faster and indifferentiable from a random oracle.
“Congratulations to Mark Zhandry, Mehdi Tibouchi and their co-authors for these two Best Paper Awards, and to all the authors of papers being presented at this year’s Asiacrypt,” NTT Research President and CEO Kazuhiro Gomi said. “It is once again exciting to see members of our CIS Lab and our colleagues at the NTT Social Informatics Labs making strong, original contributions across a wide range of topics.”
The Montgomery-Zhandry paper addresses a mismatch in confidence regarding quantum-secure assumptions. Quantum computing, via the Shor algorithm, can break both DLog and Diffie-Hellman (DH) when in groups, but these two problems are plausibly immune from quantum attack in group actions. In mathematical theory, group actions, such as those built from isogenies (aka, maps) on elliptic curves, can be endowed with hardness properties. While the cryptographic community has focused on attacking DLog – the failure of which attacks has boosted the status of DLog’s security – cryptosystems more often depend on DH. In other words, that focus has led to a lack of confidence in the cryptographic problem that matters most. This paper remedies that deficit for a set of group actions (namely, abelian ones, or those exhibiting commutative properties) in the quantum setting. “By showing that the group action versions of DLog and DH are equivalent from the perspective of quantum computers, we show that DH is just as likely to be secure as DLog,” Zhandry said. “This allows us to automatically lift our confidence in DLog to confidence in DH, and therefore all cryptosystems relying on DH.”
The paper by Tibouchi et al. focuses on a technique – the Shallue-van de Woestijne (SW) map – that enables hashing arbitrary values to points on an elliptic curve, a required step in many cryptographic constructions. The authors note that while SW applies to nearly all elliptic curves over finite fields, it lacks “the desirable property of being indifferentiable from a random oracle when composed with a random oracle to the base field.” Because behaving “like a random oracle” is required for many cryptographic schemes, instantiating an indifferentiable function in practice has become a priority. To improve upon attempts to date, the authors associate SW with a one-parameter family of encodings that enables more cost-efficient (i.e., faster) computation while achieving indifferentiable hashing to most curves. As a result, implementers should no longer have to choose between two existing approaches: “one which is secure in all cases but slower, and one which is faster but requires a careful analysis to ascertain that it does not fully compromise the security of the scheme.”
Both papers are timely. Interest in post-quantum cryptography (PQC) has grown alongside the related National Institute of Standards and Technology (NIST) competition. While NIST has announced that it favors lattice-based candidates, it has also encouraged further research into isogeny-based cryptography. Two Asiacrypt 2022-affiliated workshops focus on quantum cryptography and PQC standardization and migration. As for hashing to elliptic curves, that was the subject of a recent draft document of the Crypto Forum Research Group (CFRG) within the Internet Research Task Force (IRTF). Responding to the call for “original research papers on all aspects of cryptology,” CIS Lab and NTT CIL scientists also co-authored the following papers on several other topics:
- “A modular approach to the Incompressibility of Block-Cipher-Based AEADs” (CIL)
- “Classically Verifiable NIZK for QMA with Preprocessing” (CIL)
- “Compact FE for Unbounded Attribute-Weighted Sums for Logspace from SXDH” (CIS Lab/CIL)
- “Efficient Adaptively-Secure Byzantine Agreement for Long Messages” (CIS Lab)
- “Functional Encryption with Secure Key Leasing” (CIL)
- “Key-Reduced Variants of 3kf9 with Beyond-Birthday-Bound Security” (CIL)
- “Practical Provably Secure Flooding for Blockchains” (CIS Lab)
- “Witness Encryption and Null IO from Evasive LWE” (CIS Lab)
As part of a research organization founded in 2019, the CIS Lab has quickly become a hub of cryptographic excellence. At Crypto 2022, its members authored or co-authored 17 papers, one of which, co-authored by CIS Lab Director Brent Waters, won the event’s Best Paper Award. In related news, Dr. Zhandry and NTT SIL Distinguished Researcher Takashi Yamakawa devised a “breakthrough” approach to verifying quantum advantage in a paper that was discussed at a Simons Institute for the Theory of Computing workshop this summer. For more on Dr. Zhandry, who also won a Best Paper Award at Eurocrypt 2019 and a Best Early Career Award at Crypto 2016, see this profile and Q&A from March 2022.
The proceedings of the IACR’s flagship conferences, including Asiacrypt, are published by Springer in its Lecture Notes in Computer Science series. To attend the event, please visit the AsiaCrypt 2022 registration page.
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.
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
Contacts
NTT Research:
Chris Shaw
Chief Marketing Officer
NTT Research
+1-312-888-5412
Media:
Stephen Russell
Wireside Communications®
For NTT Research
+1-804-362-7484
