## CryptoDB

### Enrique Larraia

#### Publications

Year
Venue
Title
2020
JOFC
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 ${\text {DDH}}$ DDH assumption hold for them. Our first construction is symmetric and comes with a $\kappa$ κ -linear map $\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$ e : G κ ⟶ G T for prime-order groups ${\mathbb {G}}$ G and ${\mathbb {G}}_T$ G T . To establish the hardness of the $\kappa$ κ -linear ${\text {DDH}}$ DDH problem, we rely on the existence of a base group for which the $\kappa$ κ -strong ${\text {DDH}}$ DDH assumption holds. Our second construction is for the asymmetric setting, where $\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$ e : G 1 × ⋯ × G κ ⟶ G T for a collection of $\kappa +1$ κ + 1 prime-order groups ${\mathbb {G}}_i$ G i and ${\mathbb {G}}_T$ G T , and relies only on the 1-strong ${\text {DDH}}$ DDH assumption in its base group. In both constructions, the linearity $\kappa$ κ can be set to any arbitrary but a priori fixed polynomial value in the security parameter. 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 the group $\mathbb {Z}_N^{+}$ Z N + . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.
2018
PKC
We construct a graded encoding scheme (GES), an approximate form of graded multilinear maps. Our construction relies on indistinguishability obfuscation, and a pairing-friendly group in which (a suitable variant of) the strong Diffie–Hellman assumption holds. As a result of this abstract approach, our GES has a number of advantages over previous constructions. Most importantly: We can prove that the multilinear decisional Diffie–Hellman (MDDH) assumption holds in our setting, assuming the used ingredients are secure (in a well-defined and standard sense). Hence, our GES does not succumb to so-called “zeroizing” attacks if the underlying ingredients are secure.Encodings in our GES do not carry any noise. Thus, unlike previous GES constructions, there is no upper bound on the number of operations one can perform with our encodings. Hence, our GES essentially realizes what Garg et al. (EUROCRYPT 2013) call the “dream version” of a GES. Technically, our scheme extends a previous, non-graded approximate multilinear map scheme due to Albrecht et al. (TCC 2016-A). To introduce a graded structure, we develop a new view of encodings at different levels as polynomials of different degrees.
2016
TCC
2015
EPRINT
2015
EPRINT
2014
CRYPTO
2014
EPRINT