## CryptoDB

#### Publications

Year
Venue
Title
2022
TCC
Trapdoor Claw-free Functions (TCFs) are two-to-one trapdoor functions where it is computationally hard to find a claw, i.e., a colliding pair of inputs. TCFs have recently seen a surge of renewed interest due to new applications to quantum cryptography: as an example, TCFs enable a classical machine to verify that some quantum computation has been performed correctly. In this work, we propose a new family of (almost two-to-one) TCFs based on conjectured hard problems on isogeny-based group actions. This is the first candidate construction that is not based on lattice-related problems and the first scheme (from any plausible post-quantum assumption) with a deterministic evaluation algorithm. To demonstrate the usefulness of our construction, we show that our TCF family can be used to devise a computational test of qubit, which is the basic building block used in general verification of quantum computations.
2022
TCC
2019
PKC
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.
2018
TCC
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.

#### Coauthors

Navid Alamati (1)
Sanjam Garg (2)