The 2nd Workshop on Mathematical Aspects of Computer Science

Foundations of
January 6-8, 2016.


Aims and Scope:
Mathematical Aspects of Computer Science (MACS) is a series of workshops focusing on the central and deep interconnections between mathematics and computer science.The workshops are designed to be both informative for a wide range of graduate students as well as to present the state of the art and recent results on the subjects they target.
Foundations of Cryptography (FoC) is the second MACS workshop. The aim of FoC is to provide an opportunity for researchers to focus on the scienti?c foundations of cryptography and spot the emerging new areas. Applications may also be covered but the emphasis is on the conceptual and theoretical framework that allows the use of appropriate models, amenable to mathematical reasoning. The workshop consists of crash courses as well as technical presentations by keynote speakers and experts.

Foundations of Cryptography
Click the image to download the poster in PDF format


Wednesday, January 6, 2016

Pooya Farshim
Introduction to the Provable Security Methodology

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
Random Oracles as a Double-Edged 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 black-box separations in which the goal is to understand the limitations of cryptographic assumptions.

10:30-11:00 Break
Andrej Bogdanov
Cryptography and NP-Hardness (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 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.

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

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 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
15:00-15:30 Break
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 "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
Technical Talk:
Elliptic curve and finite field DLP

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.

Thursday, January 7, 2016

Andrej Bogdanov
Cryptography and NP-Hardness(II):
Limits of provable security
  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)
10:15-10:45 Break
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 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
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).

  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

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 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
15:00-15:30 Break
Mohammad Sadeq Dousti
Technical Talk:
FORSAKES: A Forward-Secure Authenticated Key Exchange Protocol Based on Symmetric Key-Evolving Schemes

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
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, (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.

Friday, January 8, 2016

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.)

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:30-11:00 Break
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.

  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

12:15-14:00 Closing-Lunch

Workshop Materials:

Omran AhmadiElliptic curve and finite field DLP
Andrea BogdanovCryptography and NP-Hardnes
Andrea BogdanovCryptography Hardnes -Other Functionalities
Mohammad Sadeq DoustiFORSAKES A Forward-Secure AKE Based on Symmetric KES
Pooya FarshimBootstrapping iO from NC^1 to P/Poly and Functional Encryption
Pooya FarshimThe Provable Security Methodology
Pooya FarshimMultilinear Maps from Obfuscation
Pooya FarshimRandom oracle and obfuscation
Shahram Khazaei Recovery Detectable Verifiable Secret Sharing
Mohammad MamoodyIntroduction to code Obfuscation
Mohammad MamoodyConstructing an IO Scheme
Mohammad MamoodyLower Bounds on Assumptions behind Indistinguishability Obfuscation
Mohammad MamoodyRandom Oracle-An Ideal Primitive and a Tool for Separations
Maryam Rajabzadeh AsarForking Lemmas for Different Signature


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:


Shahid Beheshti University Guest House: 021-22432220 or 021-29903030

There are few suites which you can call to reserve.


Intel Conferences Center, Allame hall

MACS-Foundations of Cryprography- SBU Map Please click here to see a larger image

archive: MACS workshop: Models of Computation with Order and Topology, 5-17 April 2015. (Link)