Program:
9:00 - 9:30 Gathering and refreshments
9:30 - 10:15 Nathan Keller, New Attacks on Feistel Structures with Improved Memory Complexities
10:15 - 10:45 coffee
10:45 - 11:30 Jean-Philippe Aumasson, NORX: sponge-based parallel authenticated encryption
11:30 - 12:00 Ran Cohen, Lower Bounds for Secure Multiparty Computation Without Broadcast
12:00 - 13:00 Lunch
13:00 - 14:00 Iftach Haitner, Tutorial:The Many Entropies in One-Way Functions
14:00 - 14:20 coffee break
14:20 - 15:25 Gilad Asahrov, Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
Abstracts:
Nathan Keller, New Attacks on Feistel Structures with Improved Memory Complexities
Abstract:
Feistel structures are an extremely important and extensively researched type of cryptographic schemes. In this paper we describe improved attacks on Feistel structures with more than 4 rounds. We achieve this by a new attack that combines the main benefits of meet-in-the-middle attacks (which can reduce the time complexity by comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on n-bit inputs with seven independent round keys of n/2 bits each), a MITM attack can use (2^1.5n ,2^1.5n) time and memory, while dissection requires (2^2n, 2^n) time and memory. Our new attack requires only (2^1.5n, 2^n) time and memory, using a few known plaintext/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multicollisions and differential properties deep in the structure in order to further reduce the memory complexity.
Our new attacks are not just theoretical generic constructions - in fact, we can use them to improve the best known attacks on several concrete cryptosystems such as CAST-128 (where we reduce the memory complexity from 2^111 to 2^64) and DEAL-256 (where we reduce the memory complexity from 2^200 to 2^144), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures - for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of 2^16.
Joint work with Itai Dinur, Orr Dunkelman and Adi Shamir
Jean-Philippe Aumasson, NORX: sponge-based parallel authenticated encryption
Abstract:
The talk will present NORX, one of the 57 submissions to CAESAR, the competition for authenticated ciphers started in 2014. From the provable security results on the mode and the core algorithm to implementations for a variety of platforms, this talk will review all the work published on NORX. Documentation and code are available on https://norx.io and https://github.com/norx.
Ran Cohen, Lower Bounds for Secure Multiparty Computation Without Broadcast
Abstract:
A major challenge in the study of cryptography is characterizing the necessary and sufficient assumptions required to conduct a given cryptographic task. The focus of this work is the necessity of a \emph{broadcast channel} for secure multiparty computation, involving three or more parties. We show that if one third of the parties might be corrupted, broadcast is necessary for securely computing any symmetric $n$-party functionality that is not an \emph{$n/3$-junta}; a functionality is a $k$-junta, if any $k$-size subset of its input variables can be set to determine its output. The above immediately yields that securely computing (in the presence of one-third corruptions) non-junta symmetric functionalities, like Boolean XOR, requires broadcast. It also shows the necessity of broadcast for securely computing symmetric \emph{random} functionalities like coin-flipping protocols (in which all honest parties must output a common value). The above characterization is tight for three-party symmetric functionalities that can be securely computed \emph{with} broadcast (e.g., Boolean OR), since Cohen and Lindell [Asiacrypt '14] showed that such three-party $1$-junta symmetric functionalities, can be securely computed \emph{without} broadcast.
Our proof employs a novel extension of the well-known \emph{hexagon} argument of Fischer et al. [PODC '85], for the case of non-junta randomized functionalities.
Joint work with Iftach Haitner and Eran Omri
Iftach Haitner, Tutorial: The Many Entropies in One-Way Functions
Abstract:
One-way functions are the most basic, unstructured form of cryptographic hardness. Yet in a sequence of celebrated results (mostly in the eighties and early nineties), one-way functions were shown to imply a rich collection of cryptographic schemes and protocols (such as digital signatures and secret-key encryption). At the basis of this beautiful mathematical structure, are a few constructions of basic primitives: pseudorandom generators [Håstad-Impagliazzo-Levin-Luby ‘91], universal one-way hash functions [Naor-Yung ‘89, Rompel ‘90], and more recently statistically hiding commitments and statistical zero-knowledge arguments [Haitner-Nguyen-Ong-Reingold-Vadhan ’06 & ‘07]. In all three cases, turning raw hardness into a much more exploitable cryptographic object requires some very elaborate constructions and proofs.
In this talk we will try to hint on how one-way functions naturally contain a basic form of each of these objects. The talk will be influenced by a recent line of results, simplifying and improving all of these contractions. The crux of each new construction is defining the “right” notion of computational entropy and recovering this form of entropy from one-way functions.
Based on several works with (subsets of) Thomas Holenstein, Omer Reingold, Salil Vadhan and Hoeteck Wee.
Gilad Asharov, Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
Abstract:
Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a ``central hub'' for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. In this paper we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows:
-- There is no fully black-box construction with a polynomial security loss of a collision-resistant function family from a general-purpose indistinguishability obfuscator.
-- There is no fully black-box construction with a polynomial security loss of a key-agreement protocol with perfect completeness from a general-purpose private-key functional encryption scheme.
-- There is no fully black-box construction with a polynomial security loss of an indistinguishability obfuscator for oracle-aided circuits from a private-key functional encryption scheme for oracle-aided circuits.
Specifically, we prove that any such potential construction must suffer from at least a sub-exponential security loss. Our results are obtained within a subtle framework capturing constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme themselves are used in a black-box manner.