TCC Test-of-Time Award

The TCC Test of Time Award recognizes outstanding papers, published in TCC at least eight years ago, making a significant contribution to the theory of cryptography, preferably with influence also in other areas of cryptography, theory, and beyond. The inaugural TCC Test of Time Award was given in TCC 2015 for papers published no later than TCC 2007.

Award Recipients

• Multi-authority Attribute Based Encryption, by Melissa Chase. For the first attribute-based encryption scheme in which no small subset of authorities can compromise user privacy, inspiring further work in decentralized functional encryption.

• Perfectly secure oblivious RAM without random oracles, by Ivan Damgård, Sigurd Meldgaard, and Jesper Buus Nielsen, published in TCC 2011, for the first perfectly secure unconditional Oblivious RAM scheme and for setting the stage for future Oblivious RAM and PRAM schemes. See the YouTube Video.

• Keyword Search and Oblivious Pseudorandom Functions by Michael J. Freedman, Yuval Ishai, Benny Pinkas, Omer Reingold, published in TCC 2005, for introducing and formalizing the notion of Oblivious Pseudorandom Functions, and identifying connections to other primitives such as keyword search, inspiring a vast amount of theoretical and practical work

• Perfectly-Secure MPC with Linear Communication Complexity by Zuzana Trubini and Martin Hirt, published in TCC 2008, for introducing hyper-invertible matrices to perfectly secure multiparty computation, thus enabling significant efficiency improvements and, eventually, constructions with minimal communication complexity. See the YouTube Video.

• Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency by Paul Valiant, published in TCC 2008, for demonstrating the power of recursive composition of proofs of knowledge and enabling the development of efficiently verifiable proofs of correctness for complex computations.

• Evaluating 2-DNF Formulas on Ciphertexts by Dan Boneh, Eu-Jin Goh, and Kobbi Nissim, published in TCC 2005, for introducing compact two-operation homomorphic encryption and developing new bilinear map techniques that led to major improvements in the design of cryptographic schemes.

• Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices by Chris Peikert (U. Michigan) and Alon Rosen (IDC Herzlia), published in TCC 2006, for advancing the use of hard algebraic lattice problems in cryptography, paving the way for major theoretical and practical advances.
  
  
  

• Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology by Ueli Maurer (ETH), Renato Renner (ETH) and Clemens Holenstein, published in TCC 2004, for introducing the security notion of "indifferentiability", that had a significant impact on both the theory of cryptography and the design of practical cryptosystems.
  
  
  
  
  
• Calibrating Noise to Sensitivity in Private Data Analysis by Cynthia Dwork (Microsoft Research), Frank McSherry, Kobbi Nissim (Ben-Gurion University), and Adam Smith (Penn State), which was published in TCC 2006, for introducing the definition of differential privacy, and providing a solid mathematical foundation for a vast body of subsequent work on private data analysis.
  
  

• Physically Observable Cryptography by Silvio Micali (MIT) and Leonid Reyzin (Boston University), which was published in TCC 2004, for pioneering a mathematical foundation of cryptography in the presence of information leakage in physical systems.

Award Rules

• Ran Canetti, Boston University (2022-2024)
• Alon Rosen, IDC Herzliah (2021-2023)
• Hugo Krawczyk, Algorand Foundation (2020-2022)

Anyone can nominate a paper for the test-of-time award by sending email to the award committee at [email protected]. A nomination should include the title, authors, and year that the paper was published, and a statement describing the contributions of the work and the reason why it is worthy of the award. The award committee can also self-nominate papers, i.e. consider papers that were nominated by members of the committee itself. Papers authored or co-authored by current members of the award committee are not eligible to receive the award that year.

Past members of the award committee

• Ivan Damgård, Aarhus University (2019-2021)
• Leonid Reyzin, Boston University (2018-2020)
• Shafi Goldwasser, MIT & Weizmann Inst. (2017-2019)
• Jesper Buus Nielsen, Aarhus University (2016-2018)
• Yuval Ishai, Technion, Israel (2015-2017)
• Ronald Cramer, CWI Amsterdam (2014-2016)
• Daniele Micciancio, UCSD (2014-2016)
• Tal Rabin, IBM Research (2014-2016)