Project Summary
Protecting the electronic information world is paramount to the success and stability of modern society. This includes, protecting the integrity and privacy of stored and communicated data, guaranteeing security of complex electronic transactions, and maintaining availability of the existing infrastructure. At the core of any trustworthy and resilient solution to the above problems lies a set of `cryptographic protocols'. These are protocols that are guaranteed to preserve explicitly stated `security requirements' under some `cryptographic hardness assumptions', in face of malicious attacks.
The design of cryptographic protocols is a complex endeavor, which must
be accompanied by a security analysis which rests on sound theoretical
foundations. The research undertaken will address challenges which
arise in the the design of cryptograhic protocols at multiple levels,
from the mathematical underpinnings of computational difficulty,
through modeling and analysis of protocols, to deployment and run-time
issues. The following objectives will be pursued:
-Diversifing cryptographic hardness assumptions.
-Adequate modeling and analysis of cryptographic protocols in complex
environments.
-Analyzing the security of current practices.
-Designing new cryptographic protocols which achieve stronger levels
of security.
The diversity of the challenges addressed will have a significant impact on the design and practice of cryptographic protocols in the future.
Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On Basing One-Way Functions on NP-Hardness. 38th ACM Symposium on Theory of Computing (STOC06), Seattle, Washington, May 2006.
Boaz Barak, Ran Canetti, Jesper Buus Nielsen and Rafael Pass. Universally Composable Protocols with Relaxed Set-Up Assumptions. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), Rome Italy, October 2004.
Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, and Tal Rabin. Secure Computation Without Authentication. In Advances in Cryptology: 25th Annual International Cryptology Conference (Crypto 2005), Santa Barbara, California, August 14-18, 2005. Volume 3621 of Lecture Notes in Computer Science, Springer, 2005.
Michael Ben-Or, Elan Pavlov and Vinod Vaikuntanathan. Byzantine Agreement in the Full-Information Model in O(log n) Rounds. 38th ACM Symposium on Theory of Computing (STOC 2006), Seattle, Washington, May 2006.
Dan Boneh, Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-Ciphertext Security from Identity-Based Encryption. SIAM Journal of Computing, volume 36, pages 915-942, 2006. Full version. Early version appeared at Eurocrypt, 2004, with a long version at eprint.iacr.org/2003/182.
Ran Canetti, Yevgeniy Dodis, Rafael Pass and Shabsi Walfish. Universally Composable Security with Pre-Existing Setup. To appear in the The Fourth Theory of Cryptology Conference (TCC 2007), Trippenhuis, Amsterdam, The Netherlands, February 2007. Long version at eprint.iacr.org/2006/432.
Ran Canetti, Shai Halevi, M. Steiner. Mitigating Dictionary Attacks on Password-Based Local Storage. The 26th Annual International Cryptology Conference (Crypto 2006), Santa Barbara, CA, August 2006. Long version at eprint.iacr.org/2006/276.
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Time-Bounded Task-PIOAs: A Framework for Analyzing Security Protocols. In 20th symposium on distributed computing (DISC 2006), Stockholm, Sweden, September 18-20, 2006. Invited paper. Long version at MIT CSAIL TR 2006-047.
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic I/O Automata. Proceedings the 8th International Workshop on Discrete Event Systems (WODES'06), Ann Arbor, Michigan, July, 2006. Long version at MIT CSAIL TR 2006-060.
Ran Canetti and Jon Herzog. Universally Composable Symbolic Analysis of Mutual Authentication and Key-Exchange Protocols. The Third Theory of Cryptography Conference (TCC 2006), New York, NY, pages 380-403, March 2006. Long version at eprint.iacr.org/2004/334.
Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell, and Phil D. Mackenzie. Universally Composable Password-Based Key Exchange. In Ronald Cramer, editor, Advances in Cryptology - Eurocrypt 2005: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, volume 3494 of Lecture Notes in Computer Science, pages 404-421, Springer, 2005.Long version at eprint.iacr.org/2005/196.
Ran Canetti, Shai Halevi, M. Steiner. Hardness Amplification for Computational Riddles. The Second Theory of Cryptography Conference (TCC 2005), Cambridge, MA, February 2005. Long version at eprint.iacr.org/2004/329.
Ran Canetti, Shai Halevi and Jonathan Katz. Adaptively Secure Non-Interactive Public-Key Encryption. The Second Theory of Cryptography Conference (TCC 2005), Cambridge, MA, February 2005. Long version at eprint.iacr.org/2004/314.
Ran Canetti. Universally Composable Notions of Signature, Certification, and Authentication. 17th IEEE Computer Security Foundations Workshop (CSFW 2004), Pacific Grove, CA, June 2004. Long version at eprint.iacr.org/2003/239.
Ran Canetti, Oded Goldreich, and Shai Halevi. On the random-oracle methodology as applied to length-restricted signature schemes. The First Theory of Cryptography Conference (TCC 2004), Cambridge, MA, February 2004. Long version at eprint.iacr.org/2003/150.
Shafi Goldwasser and Guy Rothblum. On Best-Possible Obfuscation. To appear in The Fourth Theory of Cryptography Conference (TCC 2007), Trippenhuis, Amsterdam, The Netherlands, February 21-24 2007.
Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman and Guy Rothblum. Designing Efficient Program Checkers by Delegating Their Work Submitted for publication.
Shafi Goldwasser and Yael Tauman Kalai. On the Impossibility of Obfuscation with Auxiliary Input. In FOCS 2005: 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, October 2005.
Shafi Goldwasser, Elan Pavlov and Vinod Vaikuntanathan. Fault-tolerant Distributed Computing in Full-Information Networks. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, CA, October 2006.
Shafi Goldwasser, Madhu Sudan and Vinod Vaikuntanathan. Distributed Computing With Imperfect Randomness. 19th International Symposium on Distributed Computing (DISC 2005), Cracow, Poland, September 2005.
Susan Hohenberger, Guy N. Rothblum, abhi shelat and Vinod Vaikuntanathan. Securely Obfuscating Re-Encryption. To appear in The Fourth Theory of Cryptography Conference (TCC 2007), Trippenhuis, Amsterdam, The Netherlands, February 21-24 2007.
Rafael Pass, Abhi Shelat and Vinod Vaikuntanathan. Bounded CCA2-Secure Non-Malleable Encryption. MIT CSAIL Technical Report TR-2006-081, 2006.
Rafael Pass, Abhi Shelat and Vinod Vaikuntanathan. Construction of a Non-Malleable Encryption Scheme From Any Semantically Secure One. Crypto 2006.
Yael Tauman Kalai, Yehuda Lindell and Manoj Prabhakaran. Concurrent general composition of secure protocols in the timing model. In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 644-653, Baltimore, MD, May 2005.
Yael Tauman Kalai. Smooth Projective Hashing and Two-Message Oblivious Transfer. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT05, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, volume 3494 of Lecture Notes in Computer Science, Springer, 2005.
Yael Tauman Kalai and Ran Raz. Succinct Non-Interactive Zero Knowledge proofs for LOGSNP with Preprocessing. In FOCS 2006: 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, California, October 2006.
Yael Tauman Kalai and Ran Raz. Interactive PCP. Submitted for publication.
Vinod Vaikuntanathan. Broadcast in Radio Networks in the Presence of Byzantine Faults. (Brief Announcement). Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, Nevada, July 2005.
Project Summary
Fourier Analysis, and, in particular, the Fast Fourier Transform (FFT), has been among the most widely used tools in Electrical Engineering and Computer Science for many years. In recent years, the great value of Fourier Analysis to Theoretical Computer Science is also becoming more and more evident, with usages of Fourier Analysis in many different area such as Cryptography, Complexity, Computational Learning and Property Testing.
An algorithm for computing Fourier Transform in sub-linear time is clearly of major significance: improving time-complexity of a vast number of applications utilizing the FFT algorithms, as well as making it feasible to use Fourier analysis for applications where FFT is currently infeasible.
In a recent work [AGS], we present a probabilistic algorithm that learns the {\em heavy Fourier coefficients} of a given function $\ff$. Namely, a probabilistic algorithm that, given a chosen-input query access (Namely, the learning algorithm is provided with access to a black box, that on query $x$, returns $\ff(x)$, in unit time.) to a signal $\ff$ of length $n$ and a threshold $\tau$, returns all $\a$ such that the weight of the $\a$-Fourier coefficient is at least $\tau$-fraction of the signals $l_2$-norm (\ie, $\card{\widehat{\ff}(\a)}^2\ge \tau\norm{\ff}_2^2$); and the running time of the algorithm is \polyWordsII{$\log n$} {$\f {\max\set{1,\norm{\ff}_\infty}} \tau$}.
In our research we intend to improve the current algorithms for learning heavy Fourier coefficients (HFC-learning algorithms), and to explore their applications.
Research Goals: Alternative Query Models: The existing HFC-Learning algorithms work in the chosen-input query model. It is our goal to devise new HFC-learning algorithms that work under query models which are more realistic then the chosen-input query model. We intend to explore the feasibility of HFC-Learning algorithm under the random query model, namely, a model where the algorithm is given access to values $\ff(r)$ for randomly chosen $r$'s. We intend to explore lower bounds as well as algorithms which trade off sample size and accuracy. We also intend to explore HFC-Learning algorithms that work under the correlated query model, namely, a model where --though the algorithm does not have access to chosen input queries-- the algorithm has access to queries of correlated inputs. It is our intension to explore different types of correlations. In particular, we hope to explore algorithms which operate under geometric progression correlated queries, namely, for randomly chosen $r$, the algorithm can query the function $\ff$ on inputs $r^k$ for chosen values $k$'s.
Research Goals: Applications of HFC-Learning Algorithms: There are many applications in which the FFT algorithm is used, while it actually suffices to deal only with the {\em few heavy Fourier coefficients}. We intend to to explore such applications and improve their complexity by the use of an HFC-learning algorithm instead the full FFT algorithm. We consider theoretical applications that would emerge from improved HFC-learning algorithms that are compatible to alternative query models, such as proving the first hard-core predicate for the Diffie-Hellman function. We will consider the use of the current and improved HFC-learning algorithms to construct new list decodable binary error correcting codes of polynomial rate. We also consider practical applications for the current and the improved algorithms, such as compression and data retrieval applications.
Research Goals: Improved Complexity: A natural goal, in view of the above, is accelerating the time-complexity of the current HFC-learning algorithm.
Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On Basing One-Way Functions on NP-Hardness. 38th ACM Symposium on Theory of Computing (STOC06), Seattle, Washington, May 2006.
Project Summary
Program obfuscation is the process of taking a program as an input and modifying it so that the resulting program has the same I/O behavior as the input program but otherwise looks `garbled' to the entity that runs it, even if this entity is adversarial and has full access to the program. Intuitively, by looking garbled to an adversarial entity, we mean that it should be impossible to understand the internal working of the program.
Program obfuscation has been studied in the past, both from practice-oriented, ad-hoc point of view, and from a more rigorous and theoretical point of view. Taking both points of view, most of the existing results are negative, suggesting that program obfuscation is impractical or even impossible altogether.
In contrast, we propose to investigate the possibility of program obfuscation by changing the existing models, definitions, and even goals of the current study of obfuscation. In particular, we plan to pursue the following avenues of investigation.
1. Explore new models in which program obfuscators can be developed. In particular, we propose to study interactive models in which a user engages in a certain `small' amount of interaction with a server; models in which a `minimal' secure hardware component is available; and obfuscation in the quantum model of computing.
2. Explore the idea of one time programs: programs which can be executed on a restricted number of inputs, and how to achieve one time programs in the new models considered.
3. Explore the application of obfuscation to achieving fault tolerance to bad-input attacks on software, and construction of watermarking schemes. This involves new approaches such as as constructing `obfuscated data structures' and their applications
4. Explore relaxations of the definition of successful obfuscation in a meaningful and yet attainable manner. In particular, we will consider the best possible obfuscation definition.
5. Explore the use of program obfuscators for special functions (e.g., the point function) to ``realizing random oracles'', namely to find sound ways to instantiate the Random Oracle abstraction by concrete constructions while retaining security.
The proposed investigation is a 3 year single investigator proposal involving an academic lead institution (MIT) and participation by personnel from a technology company (IBM). The intellectual merit of the proposed research is that it will broaden our foundational understanding of what can be done with code in contrast with black box access to code. The broader impact of the proposed research will be through the PI and senior personnel disseminating the knowledge and understanding gained in journal publications, public conference and workshop presentations, and teaching graduate level and undergraduate level courses in theory of computation, cryptography, and network security. Finally, two members of the research team, including the PI, are women.
Shafi Goldwasser and Guy Rothblum. On Best-Possible Obfuscation. To appear in The Fourth Theory of Cryptography Conference (TCC 2007), Trippenhuis, Amsterdam, The Netherlands, February 21-24 2007.
Shafi Goldwasser, Dan Gutfreund, Alex Healy, Tali Kaufman, and Guy Rothblum. Designing Efficient Program Checkers by Delegating Their Work. Submitted for publication.
Shafi Goldwasser and Yael Tauman Kalai. On the Impossibility of Obfuscation with Auxiliary Input. In FOCS 2005: 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, October 2005.
Susan Hohenberger, Guy N. Rothblum, abhi shelat and Vinod Vaikuntanathan. Securely Obfuscating Re-Encryption. To appear in The Fourth Theory of Cryptography Conference (TCC 2007), Trippenhuis, Amsterdam, The Netherlands, February 21-24 2007.
Yael Tauman Kalai, Yehuda Lindell and Manoj Prabhakaran. Concurrent general composition of secure protocols in the timing model. In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 644-653, Baltimore, MD, May 2005.
Yael Tauman Kalai. Smooth Projective Hashing and Two-Message Oblivious Transfer. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT05, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, volume 3494 of Lecture Notes in Computer Science, Springer, 2005.
Yael Tauman Kalai and Ran Raz. Succinct Non-Interactive Zero Knowledge proofs for LOGSNP with Preprocessing. In FOCS 2006: 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, California, October 2006.
Yael Tauman Kalai and Ran Raz. Interactive PCP. Submitted for publication.