Efficient Secure Two-Party Computation and Delegatable Computation
In the first part of my talk I will focus on the fundamental problem of pattern matching where one party holds a text, whereas the other party holds a pattern with the aim to learn all the locations of the pattern that match the text. This problem has been widely looked at by researchers due to its potential applications for computational biology, text editing, Meteorology and more. I will describe an efficient secure construction for this problem in the standard setting, focusing on new techniques and tools that enable relatively practical security.
In the second part of my talk I will focus on the delegatable setting that received much attention lately due to the growing interests in cloud computing. I will present the first feasibility result that enables secure computation with a single round complexity and small communication overhead. In the last part of the talk I will discuss the difficulties in adapting the solutions from the standard setting into this new setting, and show potential tools for securely solving the problem of delegatable pattern matching.
The fundamental question of secure two-party computation considers a number of distrusting parties that wish to jointly compute a function of their respective inputs while ensuring secrecy and correctness. This setting encompasses a large variety of tasks and essentially captures any two-party cryptographic problem. The standard modeling assumes two parties, with the same computational resources allocated to each party. In delegatable computation, a computationally weak device (or client) wish to outsource its computation to an untrusted server. The ultimate goal in this setting is to design protocols that minimize the computation overhead of the client and instead rely on the extended resources of the server.