Invited Talk 1

Kristin Lauter,
Microsoft Research,
"Practical Applications of Homomorphic Encryption"

Abstract.  The possibility of outsourcing computation to the cloud offers businesses and individuals substantial cost-savings, flexibility, and availability of compute resources, but potentially sacrifices privacy. Homomorphic encryption can help address this problem by allowing the user to upload encrypted data to the cloud, which the cloud can then operate on without having the secret key. The cloud can return encrypted outputs of computations to the user without ever decrypting the data, thus providing hosting of data and services without compromising privacy. Important applications include electronic medical data and financial applications, as well as private targeted advertising. The catch is the degradation of performance and issues of scalability and flexibility. This talk will survey the trade-offs when using homomorphic encryption, and highlight scenarios and functionality where homomorphic encryption seems to be the most appropriate solution. In recent work, we showed that homomorphic encryption can even be used to enable private versions of some basic machine learning algorithms. This talk will cover several pieces of joint work with Michael Naehrig, Vinod Vaikuntanathan, and Thore Graepel.


Invited Talk 2

David Naccache,
Ecole normale superieure,
"Another Look at Affine-Padding RSA Signatures"

Abstract. Affine-padding rsa signatures consist in signing ¥ø¡¤m+ ¥á instead of the message m for some fixed constants ¥ø, ¥á. A thread of publications progressively reduced the size of m for which affine signatures can be forged in polynomial time. The current bound is log m ~ N/3 where N is the RSA modulus¡¯ bit-size. Improving this bound to N/4 has been an elusive open problem for the past decade.
In this invited talk we consider a slightly different problem: instead of minimizing m¡¯s size we try to minimize its entropy. We show that affinepadding signatures on N/4 entropy-bit messages can be forged in polynomial time. This problem has no direct cryptographic impact but allows to better understand how malleable the RSA function is. In addition, the techniques presented in this talk might constitute some progress towards a solution to the longstanding N/4 forgery open problem. We also exhibit a sub-exponential time technique (faster than factoring) for creating affine modular relations between strings containing three messages of size N/4 and a fourth message of size 3N/8 . Finally, we show than N/4 -relations can be obtained in specific scenarios, e.g. when one can pad messages with two independent patterns or when the modulus¡¯ most significant bits can be chosen by the opponent.


Invited Talk 3

Christian Rechberger,
Technical University of Denmark,
"New meet-in-the-middle attacks in symmetric cryptanalysis"