Invited Speakers / Tutorials
Please click on each speakers photo/name for more information.
Invited Speakers
Itai Dinur
Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel
Personal Homepage
Title: "The Power of Linear Algebra: Breaking Block Ciphers Using Linearization"
Abstract
Linearization transforms a system of non-linear equations into a linear system using various operations such as replacing complex expressions with new variables. Despite its simplicity, linearization is a versatile and very power tool in cryptanalysis. In this talk, I will review attacks on recent block cipher proposals and emphasize the various roles that linearization plays in these attacks. The talk will consist of three parts, each part analyzing a different block cipher construction and demonstrating how to use lineararization to enhance a different crypt-analytic attack.
In the first part of the talk, I will analyze the security of the block cipher Zorro (presented by G ?rard et al. at CHES 2013) using a tool that expl oits linearization in order to enhance differential and linear cryptanalysis. The tool gives rise to devastating and practical attacks on Zorro, but also allows to repair it and prove the immunity of the fixed block cipher to these attacks.
The second part of the talk will focus on the LowMC family of block ciphers that was presented at EUROCRYPT 2015 by Albrecht et al. I will analyze the resistance of LowMC against the classical interpolation attack (due to Jakobsen and Knudsen) which uses linearization in order to recover the secret key in a meet-in-the-middle approach. While the LowMC instances proposed at EUROCRYPT 2015 seem to resist the original interpolation attack, I will show how to optimize it using new ideas in order to break their claimed security.
Finally, I will discuss the ASASA block cipher construction that was proposed by Biryukov et al. at ASIACRYPT 2014. A very recent attack on ASASA (presented by Minaud et al. at ASIACRYPT 2015) uses li nearization in a novel way in order to recover the key by exploiting a high order differential distinguisher. Although the original attack applies to a subset of ASASA instances, I will show that it can be extended to all instances of this construction.
Sanjam Garg
University of California, Berkeley, USA
Personal Homepage
Title: "New Advances in Program Obfuscation"
Abstract:
Recent proposals for plausible candidate constructions of obfuscation have radically transformed what we imagined to be possible in cryptography. For over a decade cryptographers had been very skeptical about the existence of such objects. In this talk, I will first provide a very brief introduction to these results and some of their interesting consequences. Next I will present our recent progress towards basing obfuscation on weaker computational assumptions, and the challenges that remain.
Seny Kamara
Microsoft Research, Redmond Lab, USA
Personal Homepage
Title: Encrypted Search: Theory, Practice and Cryptanalysis
Abstract
Encrypted search is one of the most potentially impactful topics in cryptography research. Secure and practical encrypted search could fundamentally change how we store and process data, allowing us to design cloud services, databases and storage systems that are both end-to-end encrypted and usable. Research in encrypted search is now 15 years old and is more active and relevant than ever due to the emergence of cloud computing and to consumer, enterprise and government concerns over data privacy.
In this talk I will go over the evolution of encrypted search from its inception until now. I will describe the theoretical and practical advances that pushed the field forward and will discuss where res earch is headed. I will also survey the latest and most exciting directions including the design of inference attacks and the expansion of encrypted search techniques to handle graph and relational databases. Finally, I will highlight some of the most important theoretical and practical open problems in the area.
Alon Rosen
School of Computer Science IDC Herzliya, Israel
Personal Homepage
Title: "On the Cryptographic Hardness of Finding a Nash Equilibrium"
Abstract
The notion of Nash equilibrium (NE) is fundamental to game theory. While a mixed Nash equilibrium is guaranteed to exist in any game, there is no known polynomial-time algorithm for finding one. The tractability of the problem has received much attention in the past decade, in large part due to its theoretical and philosophical significance.
Prominent evidence for the hardness of finding a NE emerges from a line of works, originating in Papadimitriou and ultimately showing that the problem is complete for the complexity class PPAD. The class PPAD contains several other search problems that are not known to be tractable, such as finding a fixed point of the kind guaranteed by Brouwer’s Theorem. Akin to the phenomenon of NP-completeness, this could be interpreted as evidence t o computational difficulty. However, unlike in the case of NP, currently known problems in PPAD appear to be of fairly restricted nature, and carry similar flavor to one another.
In this talk I will show that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in PPAD. Previous proposals for basing PPAD-hardness on program obfuscation considered a strong “virtual black-box” notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested.
Our result provides further evidence of the intractability of finding a Nash e quilibrium, one that is extrinsic to the evidence presented so far.
The talk is based on joint work with Nir Bitansky (MIT) and Omer Paneth (BU). It was presented in FOCS’15.
Palash Sarkar
Applied Statistics Unit, Indian Statistical Institute, 203, B.T.Road, Kolkata, India - 700108
Personal Homepage
Title: "On the Appropriateness of (Normal) Approximations in Statistical Analysis of Attacks on Symmetric Ciphers"
Abstract
Statistical analysis of attacks on symmetric ciphers often require assuming that a test statistic follows the normal distribution. Typically such an assumption holds in an asymptotic sense. In contrast, we consider concrete versions of some important normal approximations that have been made in the literature. To do this, we use the Berry-Esse ?en theorem to derive explicit bounds on the approximation errors. Analysing these error bounds in several cryptanalytic contexts throws up several surprising results. One important implication is that this puts in doubt the applicability of the order statistics based approach for analysing key recovery attacks on block ciphers. This approach has been earlier used to obtain several results on the data complexities of (multiple) linear and differential cryptanalysis. The non-applicability of the order statistics based approach puts a question mark on the validity of data complexities obtained using this approach. Fortunately, it is possible to recover all of these results by utilising the hypothesis testing framework.
For analysing multiple linear and differential attacks, previous works had used the χ2 and the log-likelihood ratio (LLR) based test statistics and had approximated their distributions using the normal distribution. The hypothesis testing framework that we consider also uses these statistics and their normal approximations. Detailed consideration of the error in such normal approximations, however, shows that there are serious implications for the applicability of these results.
A general message that we would like to convey is that all cryptanalytic attacks should properly derive and in terpret the error bound for any normal (or other) approximation that is made. This will show that an attack is meaningful in a concrete setting rather than in an asymptotic sense.
The talk will be based on joint work with Subhabrata Samajder.
Tutorial Speakers
Yevgeniy Dodis
Department of Computer Science, New York University, USA
Personal Homepage
Title: "On Randomness, Codes and Extractors in Cryptography"
Abstract
We survey several recent advances in information-theoretic cryptography, such as cryptography with imperfect randomness, randomness extractors, leftover hash lemma and non-malleable extractors/codes.
Manoj M. Prabhakaran
University of Illinois at Urbana-Champaign, USA
Personal Homepage
Title: Secure Multi-Party Computation: A Tutorial
Abstract
Secure Multi-Party Computation (MPC) is a central problem in modern cryptography, that allows mutually distrusting parties to collaborate with each other on computational tasks, without compromising their private data (beyond what the output of the computation reveals). In this tutorial we shall cover some of the basic concepts behin d MPC, informed by recent developments in the field.
The first half of the tutorial will introduce the concept of MPC and briefly present some of the classic constructions, including Yao's Garbled Circuits, the GMW protocol and the BGW protocol. We shall then see some blackbox transformations that can be applied to simpler protocols, to achieve higher security or efficiency goals.
The second half of the tutorial will deal with fundamental issues in the theory of MPC. These include definitions of security, classification of MPC tasks according to their cryptographic complexity (including characterization of tasks as possible or impossible to carry out), and questions regarding the communication complexity of MPC.
