EuroCrypt 2016 - a post about two talks

This post is about two interesting talks I attended at Eurocrypt 2016 in Vienna.

A well-structured talk has been given by Shota Yamada from the AIST (Japan), who presented two adaptive-secure Identity-Based Encryption schemes, both constructions being based on lattices. Identity-Based Encryption generalizes the public-key encryption paradigm by addressing the problem of simplifying the public-keys; it does this by storing some unique information about owner's identity: for instance, an email addresses or a phone number (referred to as identities).

In his paper, Yamada presents two adaptive-secure IBE constructions from lattices (we omit the details of construction). They follow the usual way of setting-up IBEs based on lattices. The secret-key corresponding to an identity ID of length $k$ is generated as $(A|H(ID)) \vec{e} = \vec{u}$ $mod$ $q$, where H maps the ID to a matrix of size $n \times m'$ and $A$ is $n \times m$. A ciphertext w.r.t. an ID includes $s^T(A|H(ID)) + (x_1^T|x_2^T)$. The novel part of Yamada's work is a technique allowing for improvement in the direction of reducing the size of the (master) public-key, based on which the function $H$ is computed. In a lattice based construction, one way to define it is: $H(ID) = B_0 + \sum_{i\in[1,k]\land ID_i=1} B_i$. The new idea uses the gadget matrix $G^{-1}$ and samples $2l = 2 \sqrt{k}$ matrices instead of $2k$; it also sets up $H(ID) = B_0 + \sum_{(i,j) \in S(ID)} B_{1,i} \cdot G^{-1}(B_{2,j})$, where $S$ is an injective map between IDs and $2^{[l] \times [l]}$. As a slide remark, one can further reduce the number of matrices from $O(k^{1/2})$ to $O(k^{1/d})$. In terms of efficiency, the size of the public parameters are $\tilde{O}(n^2 \cdot k^{1/d})$, therefore reducing the dimension of the master public key and allowing for faster encryption relative to an identity, while the size of the secret-key and ciphertexts have the same order of magnitude as the recent IBEs obtained from lattices.

Another noticeable presentation has been delivered by Igors Stepanovs (UCSD) about his joint work with Brent Waters and Mihir Bellare. The problem they tackled was the existence of differing-inputs obfuscation (diO). This work is related to the one of Garg, Gentry, Halevi and Wichs, who showed (Crypto 2014 paper) that the existence of "special purpose" obfuscation implies a negative result for the existence of diO.

In short, diO is a relaxation of indistinguishability obfuscation: while $iO$ asks that two obfuscated programs to be indistinguishable and produce the same results when evaluated at all inputs, the diO allows for inputs for which the two circuits are not equivalent (differing inputs), but it requires that it is computationally hard to find such inputs. The result of their work states that assuming sub-exponentially secure OWF, then we sub-exponentially secure diO for DTMs does not exist. A similar negative result for diO holds even if we assume that sub-exponentially secure iO exist.

These were just two interesting results, sampled from the set of "public-key" related talks, presented at EuroCrypt 2016.