## CryptoDB

### Mohammad Hajiabadi

#### Affiliation: University of Victoria

#### Publications

**Year**

**Venue**

**Title**

2019

PKC

Registration-Based Encryption from Standard Assumptions
Abstract

The notion of Registration-Based Encryption (RBE) was recently introduced by Garg, Hajiabadi, Mahmoody, and Rahimi [TCC’18] with the goal of removing the private-key generator (PKG) from IBE. Specifically, RBE allows encrypting to identities using a (compact) master public key, like how IBE is used, with the benefit that the PKG is substituted with a weaker entity called “key curator” who has no knowledge of any secret keys. Here individuals generate their secret keys on their own and then publicly register their identities and their corresponding public keys to the key curator. Finally, individuals obtain “rare” decryption-key updates from the key curator as the population grows. In their work, they gave a construction of RBE schemes based on the combination of indistinguishability obfuscation and somewhere statistically binding hash functions. However, they left open the problem of constructing RBE schemes based on standard assumptions.In this work, we resolve the above problem and construct RBE schemes based on standard assumptions (e.g., CDH or LWE). Furthermore, we show a new application of RBE in a novel context. In particular, we show that anonymous variants of RBE (which we also construct under standard assumptions) can be used for realizing abstracts forms of anonymous messaging tasks in simple scenarios in which the parties communicate by writing messages on a shared board in a synchronized way.

2019

EUROCRYPT

New Techniques for Efficient Trapdoor Functions and Applications
📺
Abstract

We develop techniques for constructing trapdoor functions (TDFs) with short image size and advanced security properties. Our approach builds on the recent framework of Garg and Hajiabadi [CRYPTO 2018]. As applications of our techniques, we obtainThe first construction of deterministic-encryption schemes for block-source inputs (both for the CPA and CCA cases) based on the Computational Diffie-Hellman (CDH) assumption. Moreover, by applying our efficiency-enhancing techniques, we obtain CDH-based schemes with ciphertext size linear in plaintext size.The first construction of lossy TDFs based on the Decisional Diffie-Hellman (DDH) assumption with image size linear in input size, while retaining the lossiness rate of [Peikert-Waters STOC 2008].
Prior to our work, all constructions of deterministic encryption based even on the stronger DDH assumption incurred a quadratic gap between the ciphertext and plaintext sizes. Moreover, all DDH-based constructions of lossy TDFs had image size quadratic in the input size.At a high level, we break the previous quadratic barriers by introducing a novel technique for encoding input bits via hardcore output bits with the use of erasure-resilient codes. All previous schemes used group elements for encoding input bits, resulting in quadratic expansions.

2018

CRYPTO

Limits on the Power of Garbling Techniques for Public-Key Encryption
📺
Abstract

Understanding whether public-key encryption can be based on one-way functions is a fundamental open problem in cryptography. The seminal work of Impagliazzo and Rudich [STOC’89] shows that black-box constructions of public-key encryption from one-way functions are impossible. However, this impossibility result leaves open the possibility of using non-black-box techniques for achieving this goal.One of the most powerful classes of non-black-box techniques, which can be based on one-way functions (OWFs) alone, is Yao’s garbled circuit technique [FOCS’86]. As for the non-black-box power of this technique, the recent work of Döttling and Garg [CRYPTO’17] shows that the use of garbling allows us to circumvent known black-box barriers in the context of identity-based encryption.We prove that garbling of circuits that have OWF (or even random oracle) gates in them are insufficient for obtaining public-key encryption. Additionally, we show that this model also captures (non-interactive) zero-knowledge proofs for relations with OWF gates. This indicates that currently known OWF-based non-black-box techniques are perhaps insufficient for realizing public-key encryption.

2018

CRYPTO

Trapdoor Functions from the Computational Diffie-Hellman Assumption
📺
Abstract

Trapdoor functions (TDFs) are a fundamental primitive in cryptography. Yet, the current set of assumptions known to imply TDFs is surprisingly limited, when compared to public-key encryption. We present a new general approach for constructing TDFs. Specifically, we give a generic construction of TDFs from any Chameleon Encryption (Döttling and Garg [CRYPTO’17]) satisfying a novel property which we call recyclability. By showing how to adapt current Computational Diffie-Hellman (CDH) based constructions of chameleon encryption to yield recyclability, we obtain the first construction of TDFs with security proved under the CDH assumption. While TDFs from the Decisional Diffie-Hellman (DDH) assumption were previously known, the possibility of basing them on CDH had remained open for more than 30 years.

2018

PKC

New Constructions of Identity-Based and Key-Dependent Message Secure Encryption Schemes
Abstract

Recently, Döttling and Garg (CRYPTO 2017) showed how to build identity-based encryption (IBE) from a novel primitive termed Chameleon Encryption, which can in turn be realized from simple number theoretic hardness assumptions such as the computational Diffie-Hellman assumption (in groups without pairings) or the factoring assumption. In a follow-up work (TCC 2017), the same authors showed that IBE can also be constructed from a slightly weaker primitive called One-Time Signatures with Encryption (OTSE).In this work, we show that OTSE can be instantiated from hard learning problems such as the Learning With Errors (LWE) and the Learning Parity with Noise (LPN) problems. This immediately yields the first IBE construction from the LPN problem and a construction based on a weaker LWE assumption compared to previous works.Finally, we show that the notion of one-time signatures with encryption is also useful for the construction of key-dependent-message (KDM) secure public-key encryption. In particular, our results imply that a KDM-secure public key encryption can be constructed from any KDM-secure secret-key encryption scheme and any public-key encryption scheme.

2018

TCC

Enhancements are Blackbox Non-trivial: Impossibility of Enhanced Trapdoor Permutations from Standard Trapdoor Permutations
Abstract

Trapdoor permutations (TDP) are a fundamental primitive in cryptography. Several variants of this notion have emerged as a result of different applications. However, it is not clear whether these variants can be based on the standard notion of TDPs.We study the question of whether enhanced trapdoor permutations can be based on classical trapdoor permutations. The main motivation of our work is in the context of existing TDP-based constructions of oblivious transfer and non-interactive zero knowledge protocols, which require enhancements to the classical TDP notion. We prove that these enhancements are non-trivial, in the sense that there does not exist fully blackbox constructions of enhanced TDPs from classical TDPs.On the technical side, we show that the enhanced TDP security of any construction in the random TDP oracle world can be broken via a polynomial number of queries to the TDP oracle as well as a weakening oracle, which provides inversion with respect to randomness. We also show that the standard one-wayness of the random TDP oracle stays intact in the presence of this weakening oracle.

2018

TCC

Registration-Based Encryption: Removing Private-Key Generator from IBE
Abstract

In this work, we introduce the notion of registration-based encryption (RBE for short) with the goal of removing the trust parties need to place in the private-key generator in an IBE scheme. In an RBE scheme, users sample their own public and secret keys. There will also be a “key curator” whose job is only to aggregate the public keys of all the registered users and update the “short” public parameter whenever a new user joins the system. Encryption can still be performed to a particular recipient using the recipient’s identity and any public parameters released subsequent to the recipient’s registration. Decryption requires some auxiliary information connecting users’ public (and secret) keys to the public parameters. Because of this, as the public parameters get updated, a decryptor may need to obtain “a few” additional auxiliary information for decryption. More formally, if n is the total number of identities and $$\mathrm {\kappa }$$κ is the security parameter, we require the following.Efficiency requirements: (1) A decryptor only needs to obtain updated auxiliary information for decryption at most $$O(\log n)$$O(logn) times in its lifetime, (2) each of these updates are computed by the key curator in time $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn), and (3) the key curator updates the public parameter upon the registration of a new party in time $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn). Properties (2) and (3) require the key curator to have random access to its data.Compactness requirements: (1) Public parameters are always at most $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn) bit, and (2) the total size of updates a user ever needs for decryption is also at most $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn) bits.We present feasibility results for constructions of RBE based on indistinguishably obfuscation. We further provide constructions of weakly efficient RBE, in which the registration step is done in $${\text {poly}}(\mathrm {\kappa },n)$$poly(κ,n), based on CDH, Factoring or LWE assumptions. Note that registration is done only once per identity, and the more frequent operation of generating updates for a user, which can happen more times, still runs in time $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn). We leave open the problem of obtaining standard RBE (with $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn) registration time) from standard assumptions.

2017

EUROCRYPT

2016

PKC

2015

EPRINT

#### Coauthors

- Jonathan Bootle (1)
- Andrea Cerulli (1)
- Nico Döttling (1)
- Sanjam Garg (6)
- Romain Gay (1)
- Essam Ghadafi (1)
- Jens Groth (1)
- Sune K. Jakobsen (1)
- Bruce M. Kapron (8)
- Mohammad Mahmoody (3)
- Daniel Masny (1)
- Ameer Mohammed (1)
- Ahmadreza Rahimi (2)
- Sruthi Sekar (1)
- Venkatesh Srinivasan (2)