The ACM announced several award winners today. Two of particular interest to the theory community.
Craig Gentry, recipient of the Grace Murray Hopper Award for his breakthrough construction of a fully homomorphic encryption scheme, which enables computations to be performed on encrypted data without unscrambling it. This long-unsolved mathematical puzzle requires immense computational effort, but Gentry’s innovative approach broke the theoretical barrier to this puzzle by double encrypting the data in such a way that unavoidable errors could be removed without detection. This insight has the potential to result in adaptable cryptography methods that can prevent security breaches and protect sensitive personal data. Gentry is a researcher at IBM. In 2009, he won the ACM Doctoral Dissertation Award. The Hopper Award recognizes the outstanding young computer professional of the year.
Kurt Mehlhorn, recipient of the Paris Kanellakis Theory and Practice Award for contributions to algorithm engineering that led to creation of the Library of Efficient Data Types and Algorithms (LEDA). This software collection of data structures and algorithms, which Mehlhorn developed with Stefan Näher, provides practical solutions for problems that had previously impeded progress in computer graphics, computer-aided geometric design, scientific computation, and computational biology. LEDA’s software has been incorporated in the applied research programs of thousands of companies worldwide in telecommunications, bioinformatics, Computer-Aided Design (CAD) and Geographic Information System (GIS), banking, optical products, and transportation. Since 2001, LEDA has been developed and distributed by Algorithmic Solutions Software GmbH, founded by Mehlhorn with Näher and Christian Uhrig, who introduced a novel distribution model that is free to researchers and licensed to companies. Mehlhorn is the founding director of the Max Planck Institute for Informatics and a professor at Saarland University in Saarbrucken, Germany. A Fellow of ACM, he received the Gottfried Wilhelm Leibniz Prize in 1986, and the European Association for Theoretical Computer Science (EATCS) Award in 2010. The Kanellakis Award honors specific theoretical accomplishments that significantly affect the practice of computing.
Does anyone have a sense of how far we are from an implementation of a homomorphic encryption scheme?
ReplyDeleteThere are already several implementations, with the most recent described in a paper appearing at Eurocrypt 2011.
ReplyDeleteIt's not a question of implementation, it's a question of efficiency.
It's not a question of implementation, it's a question of efficiency.
ReplyDeleteAnd correctness: nobody's anywhere near being able to do it based on standard assumptions. We've got no idea how much of a margin of safety (if any) there is in these new assumptions.
More news: Mohammad Hajiaghayi won ONR Young Investigator Award 2011 (http://www.onr.navy.mil/en/Science-Technology/Directorates/office-research-discovery-invention/Sponsored-Research/YIP/2011-young-investigator-recipients.aspx). I think he is the only computer scientist who won the award this year.
ReplyDelete
ReplyDeleteDoes anyone have a sense of how far we are from an implementation of a homomorphic encryption scheme?
Here is a long answer:
---------------
DARPA Will Spend $20 Million to Search for Crypto's Holy Grail
Forbes (04/06/11) Andy Greenberg
The U.S. Defense Advanced Research Projects Agency (DARPA) plans to spend $20 million over five years to find a way to both encrypt data and let it be used and manipulated. The Programming Computation on Encrypted Data (PROCEED) project would build upon the work of IBM researcher Craig Gentry, who has solved the theoretical problem of performing complex computations on encrypted data without decrypting it. Such full homomorphic encryption would enable someone to query a database without it ever knowing the content of the request. Gentry's method takes immense computational power, so DARPA wants the participating contractors and academic research teams to reduce the computing time for full homomorphic encryption by a factor of 10 million compared to its current state, or alternatively reduce it to 100,000 times the computation required for unencrypted computing.
http://blogs.forbes.com/andygreenberg/2011/04/06/darpa-will-spend-20-million-to-search-for-cryptos-holy-grail/
Correction: Mehlhorn and Naher did not write LEDA. Their msc and phd students did. The cheapest labour in the high-tech market.
ReplyDelete@Anon 6: [Citation needed.]
ReplyDelete