Andrej Bogdanov

Pooya Farshim

Mohammad Mahmoody

Pooya Farshim

In this talk we'll present a high-level overview of the Provable Security Methodology. The roles of definitions, assumptions and reductions in security analyses will be discussed and examples of different types of them will be given.

1. A philosophical intro to definitions, assumption and proofs
2. Basic Concepts: one-way functions, collision resistance, IND-CPA

Mohammad Mahmoody

In this tutorial we will define random oracles and go over two of the main roles they have played in foundations of cryptography. The first role is about *constricting* schemes that are efficient and secure, but only in this model, and would lead to huristic security proofs when a hash function is used instead. The second role is in the area of black-box separations in which the goal is to understand the limitations of cryptographic assumptions.

Andrej Bogdanov

The purpose of this tutorial is to give a sense why it might be difficult to build a cryptosystem whose security is based on the existence of NP-hard problems. We will begin by reviewing some simple, "well-known" cryptographic reductions and explain their relation to proofs and interactive proof systems. We will then turn to the study of such proof systems and illustrate their power through a few examples. Using this connection, we will explore the limits of provable security for one-way permutations, certain types of one-way functions, and possibly more stringent cryptographic functionalities such as collision resistant hash functions, homomorphic encryption schemes, and private information retrieval schemes.

1. Examples of cryptographic reductions
2. Emulating reductions by proofs
3. Randomized reductions and interactive proofs
4. Some important interactive proofs

Mohammad Mahmoody

In this tutorial we will go over the notion of "code obfuscation" and two ways to formalize it. The first definition leads to "Virtual Black-Box Obfuscation" for which we will talk about a known impossibility result (for the general-purpose VBB). We then define the weaker notion of Indistinguishability Obfuscation (iO) that escapes the known impossibility result and we will see that (perhaps more importantly) iO can be used to obtain other crypto applications quite easily.

1. Virtual Black-Box Obfuscation; Impossibility of general-purpose VBB
2. Indistinguishability Obfuscation (iO)
3. Applications of iO such as Sahai-Waters PKE

Pooya Farshim

Motivated by the power of random oracles (ROs) in security proofs, we ask if a feasible model of security for hash functions capturing this power can be formalized and applied across a broad range of cryptographic goals. Our starting point is a classical uninstantiability result of Canetti, Goldreich and Halevi (CGH; STOC 98) that rules out the existence of a "general-purpose" definition. We will then study a new abstraction by Bellare, Hoang and Keelveedhi (CRYPTO 13), called Universal Computational Extractors (UCEs), that overcomes CGH's attack and can be used to instantiate ROs in a wide range of protocols. We conclude the first part by showing, somewhat surprisingly, that indistinguishability obfuscators enable new types of attacks to be launched on UCEs. A weaker UCE notion remains outside the reach of our attacks and still retains its applicability. If there is time, we'll also investigate what the implications of the attack for a number of prominent RO-based transforms (such as those for deterministic encryption or CCA security) are.

1. RO Uninstantiability (CGH98)
2. Instantiating ROs via UCEs
3. iO-based uninstantiability

Omran Ahmadi

The security of many public-key cryptosystems depends on the in- tractability of the Discrete Logarithm Problem (DLP). The DLP is: given elements g and h from a cyclic group G of order n find an integer a such that h = g a . One of the very powerful algorithms to solve the DLP in some groups including the multiplicative groups of finite fields is the Index Calculus Algorithm. In this talk I will survey some of the main results and explain the main ideas behind the recent advances towards solving the DLP over elliptic curves defined over finite fields and the multiplicative groups of finite fields.

Andrej Bogdanov

1. One-way permutations and special one-way functions
2. General one-way functions under restricted proofs of security
3. Some other functionalities (collision-resistant hash functions, homomorphic encryption, private information retrieval)

Pooya Farshim

This talk will focus on the bootstrapping phase of the iO construction of Garg et al. (GGHRSW; FOCS 13), whereby an obfuscator for log-depth circuits in NC1 is converted to one supporting all polynomial-size circuits in P/poly. In addition to iO for NC1, we will rely on two other ingredients in the construction: 1) a fully homomorphic encryption scheme with decryption in NC1, and 2) a non-interactive witness-indistinguishable proof system with verification in NC1. As an application, we'll briefly discuss how functional encryption, an emerging and powerful notion of encryption allowing fine-grained access to encrypted data, can be based on iO.

1. Building blocks: FHE, NIZK
2. Bootstrapping from NC1 to all poly-size circuits

Mohammad Mahmoody

In this talk we continue the discussion on how iO schemes can be constructed. For that we will define a new crypto object called "Multilinear maps and Graded Encodings". Then we show how to use such objects together with the Barrington’s theorem to get the iO for small depth circuits (which is already shown in the previous talk to be sufficient for arbitrary circuits, assuming FHE).

1. Multilinear maps and Graded Encodings
2. Barrington’s theorem and related discussions
3. How to get the iO for small depth circuits

Pooya Farshim

We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related, constructions and show that multilinear analogues of the DDH assumption hold for them. Our first construction is symmetric and comes with a κ-linear map e : G^κ −> G_T for prime-order groups G and G_T. To establish the hardness of the κ-linear DDH problem, we rely on the existence of a base group for which the (κ - 1)-strong DDH assumption holds. Our second construction is for the asymmetric setting, where e : G_1 × ··· × G_κ −> G_T for a collection of κ + 1 prime-order groups G_i and G_T, and relies only on the standard DDH assumption in its base group. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness indistinguishability and zero knowledge), and additively homomorphic encryption for Z_N^+.

1. Probabilistic Obfuscation
2. Symmetric multilinear maps
3. Asymmetric multilinear maps

Mohammad Sadeq Dousti

This talk suggests an algorithmic approach to a model and a definition for forward-secure authenticated key exchange (AKE) protocols, which can be satisfied without depending on the Diffie-Hellman assumption. The basic idea is to use key-evolving schemes (KES), where the long-term keys of the system get updated regularly and irreversibly. Protocols conforming to our model can be highly efficient, since they do not require the resource-intensive modular exponentiations of the Diffie-Hellman protocol. We also introduce a protocol, called FORSAKES, which is a forward-secure AKE protocol in our model. FORSAKES is a very efficient protocol, and can be implemented by merely using hash functions.

Maryam RajabzadeAsar

Digital signatures are algorithms used to guarantee authenticity of digital messages or documents. Various signature schemes with different functionalities such as ring signatures, (identity-based)-proxy ring signatures and (identity-based) multi-proxy multi-signatures have been proposed and used in electronic environments. In real implementations, hash functions are among essential ingredients of such secure schemes, where in the corresponding security proofs, they are usually modeled as random oracles.
A "Forking Lemma" which is essentially what one needs in security proofs of digital signatures in a reduction process was first proposed by Pointcheval and Stern. Then, variants of this technique have been proposed in the literature to prove existential unforgeability of signature schemes with additional properties under adaptively chosen message attacks. Our main objective in this talk is to introduce the technique and present a survey of how this "Forking Lemma" is modified to be used in such security proofs.

Mohammad Mahmoody

In this talk we will discuss the recent results on the impossibility of achieving VBB in various "algebraic models" as well as related impossibility results about the assumption complexity of iO. (Based on joint works with Ameer Mohammed, Soheil Nematihaji, Rafael Pass, and Abhi Shelat.)

Shahram Khazaei

Secret sharing is an important tool in cryptography that allows a dealer to share a secret among n recipients in such a way that it is easily reconstructable from any t + 1 shares, but complete knowledge of any t shares reveals no infor- mation about it. In a digital setting, each share is a digital value such as a number or a bit string. As a result, the dealer is oblivious to the secret reconstruction and the secret is irrevocable. That is, it is impossible for the dealer to know if the secret has ever been reconstructed and the dealer cannot stop the secret from being shared if he changes his mind after having shared his secret. This paper introduces the concept of recovery detectable verifiable secret sharing (RDVSS). Two general constructions of RDVSS are given and specific RDVSS schemes for sharing valid ElGamal or RSA secret keys are provided. It includes physical ac- tions such as sealing a message into an envelope and handing it to a recipient. When at least n − t recipients would return their shares, recovery detectability and revocability are achieved. As a result, assuming that a majority of the re- cipients are honest, secret reconstructability as well as recovery detectability and revocability are achieved when t = b(n − 1)/2c. Interestingly, RDVSS can be integrated in multiparty computation protocols to achieve a very strong notion of security against mixed adversaries: honest parties remain computationally secure provided that at most a minority of the parties are actively corrupted no matter, in addition, how many are passively corrupted.

Andrej Bogdanov

A secret sharing scheme is a mechanism for dividing up a secret piece of information among several parties so that small subsets of the parties do not learn any information about the secret, while large subsets of the parties can recover the secret. This talk will concern two aspects of such schemes: Their computational complexity and the size of the shares. Regarding computational complexity, I will show that secret sharing schemes are highly parallelizable: For every part of constants 0 <= s < r <= 1 and sufficiently large n there exists a secret sharing scheme in the class AC0 that is secure against any coalition of sn parties but allows recovery by any rn parties. (If there is time I will also show that the threshold gap r - s cannot shrink too fast in terms of n.) Regarding share size, I will show some new lower bounds for secret sharing schemes with a sharp threshold.

1. Duality between bounded indistinguishability and polynomial approximation
2. Construction of weak secret sharing schemes in AC0
3. Secrecy/recovery gap amplification
4. Lower bounds for parallelism
5. Lower bounds for share size