Andrej BogdanovChinese University of Hong Kong 

Pooya FarshimQueen's University Belfast, UK. 

Mohammad MahmoodyUniversity of Virginia, USA 
Wednesday, January 6, 2016  

8:309:00  opening  
9:009:45  Pooya Farshim  Introduction to the Provable Security Methodology
In this talk we'll present a highlevel 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.

9:4510:30  Mohammad Mahmoody  Random Oracles as a DoubleEdged Sword: An Ideal Primitive and a Tool for Separations
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 blackbox separations in which the goal is to understand the limitations of cryptographic assumptions. 
10:3011:00  Break  
11:0012:15  Andrej Bogdanov  Cryptography and
NPHardness (I): 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 NPhard problems. We will begin by reviewing some simple, "wellknown" 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 oneway permutations, certain types of oneway functions, and possibly more stringent cryptographic functionalities such as collision resistant hash functions, homomorphic encryption schemes, and private information retrieval schemes. Reductions, proofs, and proof systems

12:1514:15  Lunch  
14:1515:00  Mohammad Mahmoody  Introduction to Obfuscation
In this tutorial we will go over the notion of "code obfuscation" and two ways to formalize it. The first definition leads to "Virtual BlackBox Obfuscation" for which we will talk about a known impossibility result (for the generalpurpose 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.

15:0015:30  Break  
15:3016:15  Pooya Farshim  Random Oracles and Obfuscation
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 "generalpurpose" 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 RObased transforms (such as those for deterministic encryption or CCA security) are.

16:1517:00  Omran Ahmadi  Technical Talk: Elliptic curve and finite field DLP The security of many publickey 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. 
Thursday, January 7, 2016  

9:0010:15  Andrej Bogdanov  Cryptography and
NPHardness(II): Limits of provable security

10:1510:45  Break  
10:4511:30  Pooya Farshim  iO Construction I
This talk will focus on the bootstrapping phase of the iO construction of Garg et al. (GGHRSW; FOCS 13), whereby an obfuscator for logdepth circuits in NC1 is converted to one supporting all polynomialsize 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 noninteractive witnessindistinguishable proof system with verification in NC1. As an application, we'll briefly discuss how functional encryption, an emerging and powerful notion of encryption allowing finegrained access to encrypted data, can be based on iO.

11:3012:15  Mohammad Mahmoody  iO Construction II
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).

12:1514:15  Lunch  
14:1515:00  Pooya Farshim 
Multilinear Maps from Obfuscation 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 primeorder 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 primeorder 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, dualmode NIZK proof systems (with perfect soundness, witness indistinguishability and zero knowledge), and additively homomorphic encryption for Z_N^+.

15:0015:30  Break  
15:3016:15  Mohammad Sadeq Dousti  Technical Talk: FORSAKES: A ForwardSecure Authenticated Key Exchange Protocol Based on Symmetric KeyEvolving Schemes This talk suggests an algorithmic approach to a model and a definition for forwardsecure authenticated key exchange (AKE) protocols, which can be satisfied without depending on the DiffieHellman assumption. The basic idea is to use keyevolving schemes (KES), where the longterm keys of the system get updated regularly and irreversibly. Protocols conforming to our model can be highly efficient, since they do not require the resourceintensive modular exponentiations of the DiffieHellman protocol. We also introduce a protocol, called FORSAKES, which is a forwardsecure AKE protocol in our model. FORSAKES is a very efficient protocol, and can be implemented by merely using hash functions. 
16:1517:00  Maryam RajabzadeAsar  Technical Talk: Forking Lemmas for Different Signatures’ Scenarios
Digital signatures are algorithms used to guarantee authenticity of digital messages or documents. Various signature schemes with different
functionalities such as ring signatures, (identitybased)proxy ring signatures and (identitybased) multiproxy multisignatures 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.

Friday, January 8, 2016  

9:009:45  Mohammad Mahmoody  Recent impossibility results for VBB and iO
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.) 
9:4510:30  Shahram Khazaei  Technical Talk: Recovery Detectable Verifiable Secret Sharing 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. 
10:3011:00  Break  
11:0012:15  Andrej Bogdanov  Complexity Aspects of Secret Sharing Schemes
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.

12:1514:00  ClosingLunch 
Ziba Eslami (chair)Shahid Beheshti University 
Mojgan MahmoudiShahid Beheshti University 
Farokhlagha MoazamiShahid Beheshti University 
Hadi SoleimanyShahid Beheshti University 
Amir DaneshgarSharif University of Technology 

Ziba EslamiShahid Beheshti University 

Omid EtesamiIPM 

Hossein HajiabolhassanShahid Beheshti University 
Registration Deadline:  January 1, 2016 
Registration fee: (including meals) 
Please just after receiving the registration confirmation letter, send the money and not before it.
Academic members: 1,000,000 Rials Graduate Students: 500,000 Rials 
Registration form: 
Registration form is online and can be found on the following link:
http://conf.sbu.ac.ir/index.php/MACS/2ndMACS/schedConf/registration 
There are few suites which you can call to reserve.
Workshop place: Shahid Beheshti University,
Evin 19839, Tehran, Iran. 
archive: MACS workshop: Models of Computation with Order and Topology, 517 April 2015. (Link)