NTT Research and NTT Corporation Engage in Breakthrough Research at Crypto 2022

CIS Lab Director Brent Waters wins Best Paper Award; NTT-affiliated cryptographers contribute 23 papers

Sunnyvale, Calif. – August 9, 2022 – NTT Research, Inc., a division of NTT (TYO:9432), today announced that members of its Cryptography & Information Security (CIS) Lab authored or co-authored 17 papers that are being delivered at Crypto 2022, one of the leading international conferences on cryptologic research. A paper co-authored by CIS Lab Director Brent Waters won the event’s Best Paper Award, his second such award in the past three years. In addition, NTT Corporation and NTT Social Informatics Laboratories contributed another six papers. Organized by the International Association for Cryptologic Research (IACR), this year’s hybrid event will take place in Santa Barbara, August 13-18. NTT Research is one of the conference’s eight gold-level sponsors.

The Crypto 2022 program committee, comprised of more than 70 experts, accepted nearly 100 submissions this year. According to the posted conference program, the 23 papers associated with CIS Lab and other NTT cryptographers will be presented in sessions with the following topics: coding theory, distributed algorithms, idealized models, lattice-based signatures, lattice-based zero knowledge, lower bounds, post-quantum cryptography, quantum cryptography, secret sharing, secure hash functions, secure messaging and secure multiparty computation. Dr. Waters will present his paper, titled “Batch Arguments for NP and More from Standard Bilinear Group Assumptions” on Tuesday, August 16, at 11:20 (PST) during a session that acknowledges it with the conference’s only Best Paper award this year. Two “best early career researcher papers” will also be recognized. Dr. Waters, who is also a professor of computer science at the University of Texas (UT) at Austin, was named CIS Lab Director in June, succeeding Dr. Tatsuaki Okamoto. At Crypto 2020, a paper co-authored by Dr. Waters won one of three Best Paper Awards given that year. (One of the other winners was co-authored by a senior researcher at NTT Secure Platforms Labs.) Dr. Waters’ collaborator in this year’s paper is Dr. David Wu, an assistant professor at UT Austin. Their breakthrough is to show how to batch the proofs of nondeterministic polynomial (NP)-class and other problems using standard assumptions and relatively non-complex techniques.

“It is exciting to see our CIS Lab and other parts of NTT engaged in so much cutting-edge research,” NTT Research President and CEO Kazuhiro Gomi said. “Congratulations to Brent Waters and David Wu for their Best Paper Award, and the research itself, which appears to have such timely applications. Best wishes to all for a very productive conference.”

The Waters-Wu paper introduces a new kind of proof system, which in cryptography consists of a proving party and a verifying party, where the prover is trying to convince the verifier of a “statement.” Typically, the verifier relies on the prover to provide a witness. An example might be a digital signature, acting as a witness to the statement that a software update is not malware, but in fact produced by the vendor. In this paper, the authors develop techniques that allow for efficiently batching the transmission and verification of several statements. In so doing, they improve upon what Dr. Waters said are two main lines of prior work in this direction, namely: one that uses less standard and thus more risky computational assumptions for security; and the other, which uses certain types of lattice assumptions and probabilistic checkable proofs.

“In this work we show that batchable proof systems can be achieved from standard and well-studied assumptions on bilinear groups,” Dr. Waters said. “Moreover, our techniques are very direct and show that complex probabilistic checkable proofs are not needed.”

Two potential use cases involve the aggregation of signatures and the delegation of computation to cloud services. The first case relates to applications such as blockchains, in which each update consists of several signatures representing various transactions that users want to have processed. Instead of simply including all signatures from the transaction as part of an update (the default solution, which can incur a significant overhead), batchable verification enables aggregating these into one shorter object, the size of which is independent of the number of signatures included. The second case involves the increasingly large amounts of information storage and processing being done via cloud services.

“The problem of delegation asks, how can I verify that a computation was performed correctly in a more efficient manner than simply performing it myself,” Waters said. “Our work on batch argument systems can be immediately applied to tackle that problem.”

The proceedings of the IACR’s flagship conferences, which draw the world’s leading cryptographers, are published by Springer in its Lecture Notes in Computer Science series. Dr. Yehuda Lindell, CEO and co-founder of Unbound Security, is scheduled to deliver this year’s invited talk. To attend, see this 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

NTT Research Contact:
Chris Shaw
Chief Marketing Officer
NTT Research
Media Contact:
Stephen Russell
Wireside Communications®
For NTT Research