The 2nd Workshop on Mathematical Aspects of Computer Science
January 6-8, 2016.
Aims and Scope:
Click the image to download the poster in PDF format
Wednesday, January 6, 2016
|9:00-9:45||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.
|9:45-10:30|| 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||11:00-12:15|| Cryptography and
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
|14:15-15:00|| 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.
|15:30-16:15||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.
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
|9:00-10:15|| Cryptography and
Limits of provable security
|10:45-11:30|| 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.
|11:30-12:15||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).
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^+.
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.
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.
Friday, January 8, 2016
|9:00-9:45||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.)
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.
|11:00-12:15||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.
Ziba Eslami (chair)Shahid Beheshti University
|Omran Ahmadi||Elliptic curve and finite field DLP|
|Andrea Bogdanov||Cryptography and NP-Hardnes|
|Andrea Bogdanov||Cryptography Hardnes -Other Functionalities|
|Mohammad Sadeq Dousti||FORSAKES A Forward-Secure AKE Based on Symmetric KES|
|Pooya Farshim||Bootstrapping iO from NC^1 to P/Poly and Functional Encryption|
|Pooya Farshim||The Provable Security Methodology|
|Pooya Farshim||Multilinear Maps from Obfuscation|
|Pooya Farshim||Random oracle and obfuscation|
|Shahram Khazaei||Recovery Detectable Verifiable Secret Sharing|
|Mohammad Mamoody||Introduction to code Obfuscation|
|Mohammad Mamoody||Constructing an IO Scheme|
|Mohammad Mamoody||Lower Bounds on Assumptions behind Indistinguishability Obfuscation|
|Mohammad Mamoody||Random Oracle-An Ideal Primitive and a Tool for Separations|
|Maryam Rajabzadeh Asar||Forking Lemmas for Different Signature|
|Registration Deadline:||January 1, 2016|
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:|
There are few suites which you can call to reserve.
archive: MACS workshop: Models of Computation with Order and Topology, 5-17 April 2015. (Link)