SUNNYVALE, Calif.--(BUSINESS WIRE)--NTT Research, Inc., a division of NTT (TYO:9432), today announced that the International Association for Cryptologic Research (IACR) has honored a paper written by Cryptography & Information Security (CIS) Lab Director Brent Waters with a Test-of-Time Award. The paper, delivered at Crypto 2009, presented a new way of proving adaptive security for Identity-based Encryption (IBE), which was later expanded to cover more complex cryptographic systems. This is Waters’ third Test-of-Time Award from the IACR, and sixth total. It was presented on August 20, at Crypto 2024, one of the three flagship conferences of the IACR. Dr. Waters and six other cryptographers affiliated with the CIS Lab are also presenting 12 papers at this year’s event. Scientists from NTT Social Informatics Laboratories (SIL), a division of NTT R&D, are responsible for another eight papers at this top-tier conference. Crypto 2024 will be held August 18-22, in Santa Barbara, Calif.
The IACR gives Test-of-Time Awards annually to papers that were delivered 15 years prior at each of the three IACR general conferences (Eurocrypt, Crypto and Asiacrypt). A five-member IACR committee selects the winners based on a consensus view of a paper’s impact on the field. In the 2009 paper, titled “Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions,” Waters – the paper’s sole author – presented a methodology different from the then-prevalent method for proving adaptive security in IBE. (Adaptive security involves adversaries who can interact with a system and adapt their strategies accordingly.) Conceived in 1984 and enhanced in 2001 with a scheme using bilinear maps (i.e. functions that map a pair of elements from two groups to a third), IBE enables a user to encrypt to another party by simply knowing that party’s identity, as well as a set of global parameters. In the related system known as Attribute-based Encryption (ABE), introduced by Waters and Amir Sahai in a Eurocrypt 2005 paper that also won a Test-of-Time Award, a ciphertext is associated with a string of attributes x and a user key with a function f. A user can decrypt a ciphertext if and only if f(x) = true. In general terms, arguing that these cryptosystems are secure requires defining a game in which an attacker (or collusion of attackers) requests several private keys and then tries to decrypt what is called a challenge ciphertext. Because the security proof also includes a reduction algorithm, which relates the security of a cryptographic scheme to a known hard problem, attackers who prevail must also be able to solve some basic theoretical problem believed to be intractable. Thus, security is proved by contradiction.
More precisely, prior to the Crypto 2009 paper, adaptive security was proved according to what Waters called a “partitioning strategy” involving a reduction algorithm that would guess a set of attribute strings S. It would succeed if 1) the attribute string of the challenge ciphertext x* was in the set S and 2) if any private key for a function that had the property that for all x in the set S, f(x) = false. If these conditions did not hold, the reduction would abort. This strategy worked with what Waters said was “less than ideal practical efficiency” for simple functionalities, like IBE, but would fail with more complex functionalities, like ABE. “The difficulty was coming up with a partition where the chance of not aborting was not too low,” Waters said. Overcoming that challenge led to the entirely new approach of dual-system encryption.
“Instead of the proof guessing at the challenge set ahead of time, the dual-system proof changes the structure of private keys given to the attacker in an undetectable way that makes them incompatible with the challenge ciphertext in the security game,” Waters said. “In this paradigm there is never any guess, and the aborting-too-much problem does not happen.”
How does the dual system change the key structure and prove security, especially against collusion attacks? “At a high level, in a dual-system scheme, there are two types of ciphertexts and keys: normal ones used in the scheme, and semi-functional ones used in the security proof,” CIS Lab Senior Scientist Hoeteck Wee said. “Via a clever hybrid argument, we only need to consider the setting with a single semi-functional ciphertext and a single semi-functional key.” Wee added that handling a single ciphertext and key is much simpler and particularly helpful for the setting of adaptive security.
While the Crypto 2009 paper applied dual-system encryption to IBE, the methodology soon expanded beyond that scope. One paper that did so was co-authored by Waters, Sahai, Tatsuaki Okamoto (who later became the founding director of the CIS Lab), et al., and presented at Eurocrypt 2010. The methodology subsequently has been used “in virtually every pairing-based ABE,” Wee said. “More broadly, the methodology has been used to reduce the problem of building advanced public-key primitives to the simpler private-key setting, e.g. signatures to MACs (message authentication codes), and NIZK (non-interactive zero-knowledge proof) to designated-verifier NIZK,” he said. “This enabled further applications to structure-preserving signatures, tight security, NIZK, inner product predicate and functional encryption, and many more.”
In addition to the Test-of-Time Awards for the Crypto 2009 paper and the Eurocrypt 2005 paper that introduced ABE, Waters received another from the IACR for a Crypto 2008 paper. He has also received two from the Association for Computing Machinery (ACM) and another from the Institute of Electrical and Electronics Engineers (IEEE). At Crypto 2024, Waters and Wee, along with CIS Lab Senior Scientists Elette Boyle, Vipul Goyal, Abhishek Jain, Daniel Wichs and Mark Zhandry as well as CIS Lab Post-Doctoral Fellows Valerio Cini, Aarushi Goel and Luowen Qian are contributing 12 papers. Three address ABE; three, multi-party computation (MPC); and three, succinct non-interactive arguments (SNARGs). The other three concern mathematical assumptions, private information retrieval and quantum cryptography. This year’s “Best Paper Authored by Early Career Researchers” was co-authored by Aayush Jain, a former CIS Lab post-doctoral fellow. The eight Crypto 2024 papers from NTT R&D were authored by SIL Fellow Masayuki Abe, SIL Associate Distinguished Researcher Fuyuki Kitagawa, SIL Researcher Susumu Kiyoshima, SIL Researcher Kohei Nakagawa, SIL Distinguished Researcher Ryo Nishimaki, SIL Distinguished Researcher Mehdi Tibouchi, and SIL Distinguished Researcher Takashi Yamakawa. Three of these papers concern quantum cryptography; two, zero-knowledge proofs; and the other three, theoretical foundations, ABE, and isogenies/elliptic curves. Yamakama (who co-authored four papers), Kitigawa, and Nishimaki are also affiliated with the NTT Research Center for Theoretical Quantum Information.
Crypto 2024 is the 44th Annual International Cryptography Conference organized by the IACR. This year’s program committee accepted 143 papers. Five affiliated events took place August 17-18 in the same location. Founded in 2019 as part of NTT Research Inc., the CIS Lab has assembled a team of world-class cryptographers, whose work has made landmark contributions through participation in leading international conferences and collaboration with academic and industry counterparts.
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. © 2024 NIPPON TELEGRAPH AND TELEPHONE CORPORATION
