## CryptoDB

### Rishab Goyal

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Multi-Input Quadratic Functional Encryption from Pairings
📺
Abstract

We construct the first multi-input functional encryption (MIFE) scheme for quadratic functions from pairings. Our construction supports polynomial number of users, where user $i$, for $i \in [n]$, encrypts input $\bfx_i \in \mbZ^m$ to obtain ciphertext $\ct_i$, the key generator provides a key $\sk_\bfc$ for vector $\bfc \in \mbZ^{({mn})^2}$ and decryption, given $\ct_1,\ldots,\ct_n$ and $\sk_\bfc$, recovers $\ip{\bfc}{\bfx \otimes \bfx}$ and nothing else. We achieve indistinguishability-based (selective) security against unbounded collusions under the standard bilateral matrix Diffie-Hellman assumption. All previous MIFE schemes either support only inner products (linear functions) or rely on strong cryptographic assumptions such as indistinguishability obfuscation or multi-linear maps.

2021

ASIACRYPT

Bounded Collusion ABE for TMs from IBE
Abstract

We give an attribute-based encryption system for Turing Machines that is provably secure assuming only the existence of identity- based encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search Diffie-Hellman assumption, and the Learning with Errors assumption.
Our core construction provides security against an attacker that makes a single key query for a machine T before declaring a challenge string w∗ that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova and Wichs; however, to prove security we need to introduce a new notion of security called iterated simulation security.
We then show how to transform our core construction into one that is secure for an a-priori bounded number q = q(\lambda) of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of non-committing encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this non-committing encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from single-key adaptive security to q-key adaptive security.

2021

ASIACRYPT

Adaptive Security via Deletion in Attribute-Based Encryption: Solutions from Search Assumptions in Bilinear Groups
Abstract

One of the primary research challenges in Attribute-Based Encryption
(ABE) is constructing and proving cryptosystems that are adaptively
secure. To date the main paradigm for achieving adaptive security in
ABE is dual system encryption. However, almost all such solutions in
bilinear groups rely on (variants of) either the subgroup decision
problem over composite order groups or the decision linear assumption.
Both of these assumptions are decisional rather than search
assumptions and the target of the assumption is a source or bilinear
group element. This is in contrast to earlier selectively secure ABE
systems which can be proven secure from either the decisional or
search Bilinear Diffie-Hellman assumption. In this work we make
progress on closing this gap by giving a new ABE construction for the
subset functionality and prove security under the Search Bilinear
Diffie-Hellman assumption.
We first provide a framework for
proving adaptive security in Attribute-Based Encryption systems. We
introduce a concept of ABE with deletable attributes where any party
can take a ciphertext encrypted under the attribute string x in {0,
1}^n and modify it into a ciphertext encrypted under any string x'
in {0, 1, bot}^n where x' is derived by replacing any bits of
x with bot symbols (i.e. ``deleting" attributes of x). The
semantics of the system are that any private key for a circuit C can
be used to decrypt a ciphertext associated with x' if none of the
input bits read by circuit C are bot symbols and C(x') = 1.
We show a pathway for combining ABE
with deletable attributes with constrained pseudorandom functions to
obtain adaptively secure ABE building upon the recent work of
[Tsabary19]. Our new ABE system will be adaptively
secure and be a ciphertext-policy ABE that supports the same
functionality as the underlying constrained PRF as long as the PRF is
``deletion conforming". Here we also provide a simple constrained PRF
construction that gives subset functionality.
Our approach enables us to access a
broader array of Attribute-Based Encryption schemes support deletion
of attributes. For example, we show that both the [GPSW06] and [Boyen13] ABE schemes can
trivially handle a deletion operation. And, by using a hardcore bit
variant of GPSW scheme we obtain an adaptively secure ABE scheme under
the Search Bilinear Diffie-Hellman assumption in addition to
pseudo random functions in NC1. This gives the first adaptively
secure ABE from a search assumption as all prior work relied on
decision assumptions over source group elements.

2021

ASIACRYPT

Beyond Software Watermarking: Traitor-Tracing for Pseudorandom Functions
Abstract

Software watermarking schemes allow a user to embed an identifier into a piece of code such that the resulting program is nearly functionally-equivalent to the original program, and yet, it is difficult to remove the identifier without destroying the functionality of the program. Such schemes are often considered for proving software ownership or for digital rights management. Existing constructions of watermarking have focused primarily on watermarking pseudorandom functions (PRFs).
In this work, we revisit the definitional foundations of watermarking, and begin by highlighting a major flaw in existing security notions. Existing security notions for watermarking only require that the identifier be successfully extracted from programs that preserve the exact input/output behavior of the original program. In the context of PRFs, this means that an adversary that constructs a program which computes a quarter of the output bits of the PRF or that is able to distinguish the outputs of the PRF from random are considered to be outside the threat model. However, in any application (e.g., watermarking a decryption device or an authentication token) that relies on PRF security, an adversary that manages to predict a quarter of the bits or distinguishes the PRF outputs from random would be considered to have defeated the scheme. Thus, existing watermarking schemes provide very little security guarantee against realistic adversaries. None of the existing constructions of watermarkable PRFs would be able to extract the identifier from a program that only outputs a quarter of the bits of the PRF or one that perfectly distinguishes.
To address the shortcomings in existing watermarkable PRF definitions, we introduce a new primitive called a traceable PRF. Our definitions are inspired by similar definitions from public-key traitor tracing, and aim to capture a very robust set of adversaries: namely, any adversary that produces a useful distinguisher (i.e., a program that can break PRF security), can be traced to a specific identifier. We provide a general framework for constructing traceable PRFs via an intermediate primitive called private linear constrained PRFs. Finally, we show how to construct traceable PRFs from a similar set of assumptions previously used to realize software watermarking. Namely, we obtain a single-key traceable PRF from standard lattice assumptions and a fully collusion-resistant traceable PRF from indistinguishability obfuscation (together with injective one-way functions).

2021

TCC

Multi-Party Functional Encryption
Abstract

We initiate the study of multi-party functional encryption (MPFE) which unifies and abstracts out various notions of functional encryption which support distributed ciphertexts or secret keys, such as multi-input FE, multi-client FE, decentralized multi-client FE, multi-authority FE, dynamic decentralized FE, adhoc multi-input FE and such others. Using our framework, we identify several gaps in the literature and provide some constructions to fill these:
1. Multi-Authority ABE with Inner Product Computation. The recent work of Abdalla et al. (ASIACRYPT’20) constructed a novel “composition” of Attribute Based Encryption (ABE) and Inner Product Functional Encryption (IPFE), namely functional encryption schemes that combine the access control functionality of attribute based encryption with the possibility of performing linear operations on the encrypted data. In this work, we extend the access control component to support the much more challenging multi-authority setting, i.e. “lift” the primitive of ABE in their construction to multi-authority ABE for the same class of access control policies (LSSS structures). This yields the first construction of a nontrivial multi-authority FE beyond ABE from simple assumptions on pairings to the best of our knowledge.
Our techniques can also be used to generalize the decentralized attribute based encryption scheme of Michalevsky and Joye (ESORICS’18) to support inner product computation on the message. While this scheme only supports inner product predicates which is less general than those supported by the Lewko-Waters (EUROCRYPT’11) construction, it supports policy hiding which the latter does not. Our extension inherits these features and is secure based on the k-linear assumption, in the random oracle model.
2. Function Hiding DDFE. The novel primitive of dynamic decentralized functional encryption (DDFE) was recently introduced by Chotard et al. (CRYPTO’20), where they also provided the first construction for inner products. However, the primitive of DDFE does not support function hiding, which is a significant limitation for several applications. In this work, we provide a new construction for inner product DDFE which supports function hiding. To achieve our final result, we define and construct the first function hiding multi-client functional encryption (MCFE) scheme for inner products, which may be of independent interest.
3. Distributed Ciphertext-Policy ABE. We provide a distributed variant of the recent ciphertext- policy attribute based encryption scheme, constructed by Agrawal and Yamada (EUROCRYPT’20). Our construction supports NC1 access policies, and is secure based on “Learning With Errors” and relies on the generic bilinear group model as well as the random oracle model.
Our new MPFE abstraction predicts meaningful new variants of functional encryption as useful targets for future work.

2020

CRYPTO

Verifiable Registration-Based Encryption
📺
Abstract

In recent work, Garg, Hajiabadi, Mahmoody, and Rahimi (TCC 2018) introduced a new encryption framework, which they referred to as Registration-Based Encryption (RBE). The central motivation behind RBE was to provide a novel methodology for solving the well-known key-escrow problem in Identity-Based Encryption (IBE) systems. Informally, in an RBE system, there is no private-key generator unlike IBE systems, but instead, it is replaced with a public key accumulator. Every user in an RBE system samples its own public-secret key pair and sends the public key to the accumulator for registration. The key accumulator has no secret state and is only responsible for compressing all the registered user identity-key pairs into a short public commitment. Here the encryptor only requires the compressed parameters along with the target identity, whereas a decryptor requires supplementary key material along with the secret key associated with the registered public key.
The initial construction by Garg et al. based on standard assumptions only provided weak efficiency properties. In a follow-up work by Garg, Hajiabadi, Mahmoody, Rahimi, and Sekar (PKC 2019), they gave an efficient RBE construction from standard assumptions. However, both these works considered the key accumulator to be honest which might be too strong an assumption in real-world scenarios. In this work, we initiate a formal study of RBE systems with malicious key accumulators. To that end, we introduce a strengthening of the RBE framework which we call Verifiable RBE (VRBE). A VRBE system additionally gives the users an extra capability to obtain short proofs from the key accumulator proving correct (and unique) registration for every registered user as well as proving non-registration for any yet unregistered identity.
We construct VRBE systems that provide succinct proofs of registration and non-registration from standard assumptions (such as CDH, Factoring, LWE). Our proof systems also naturally allow a much more efficient audit process which can be performed by any non-participating third party as well. A by-product of our approach is that we provide a more efficient RBE construction than that provided in the prior work of Garg \etal\cite{GHMRS19}. And, lastly, we initiate a study on the extension of VRBE to a wider range of access and trust structures.

2020

CRYPTO

New Constructions of Hinting PRGs, OWFs with Encryption, and more
📺
Abstract

Over the last few years, there has been a surge of new cryptographic results, including laconic oblivious
transfer, (anonymous/ hierarchical) identity-based encryption, trapdoor functions, chosen-ciphertext security transformations, designated-verifier zero-knowledge proofs, due to a beautiful framework recently introduced in the works of Cho et al. (Crypto 2017), and Dottling and Garg (Crypto 2017). The primitive of one-way function with encryption (OWFE) and its relatives (chameleon encryption, one-time signatures with encryption, hinting PRGs, trapdoor hash encryption, batch encryption) has been a centerpiece in all these results.
While there exist multiple realizations of OWFE (and its relatives) from a variety of assumptions such as CDH, Factoring, and LWE, all such constructions fall under the same general ``missing block" framework. Although this framework has been instrumental in opening up a new pathway towards various cryptographic functionalities via the abstraction of OWFE (and its relatives), it has been accompanied by undesirable inefficiencies that might inhibit a much wider adoption in many practical scenarios. Motivated by the surging importance of the OWFE abstraction (and its relatives),
a natural question to ask is whether the existing approaches can be diversified to not only obtain more constructions from different assumptions, but also in developing newer frameworks. We believe
answering this question will eventually lead to important and previously unexplored performance trade-offs in the overarching applications of this novel cryptographic paradigm.
In this work, we propose a new accumulation-style framework for building a new class of OWFE as well as hinting PRG constructions with a special focus on achieving shorter ciphertext size and shorter
public parameter size (respectively). Such performance improvements parlay into shorter parameters in their corresponding applications. Briefly, we explore the following performance trade-offs --- (1) for OWFE, our constructions outperform in terms of ciphertext size as well as encryption time, but this comes at the cost of larger evaluation and setup times, (2) for hinting PRGs, our constructions provide a rather dramatic trade-off between evaluation time versus parameter size, with our construction leading to significantly shorter public parameter size. The trade-off enabled by our hinting PRG construction also leads to interesting implications in the CPA-to-CCA transformation provided in. We also provide concrete performance measurements for our constructions and compare them with existing approaches. We believe highlighting such trade-offs will lead to wider adoption of these abstractions in a practical sense.

2020

TCC

On Perfect Correctness in (Lockable) Obfuscation
📺
Abstract

In a lockable obfuscation scheme a party takes as input a program P, a lock value alpha, a message msg, and produces an obfuscated program P'. The obfuscated program can be evaluated on an input x to learn the message msg if P(x)= alpha. The security of such schemes states that if alpha is randomly chosen (independent of P and msg), then one cannot distinguish an obfuscation of $P$ from a dummy obfuscation. Existing constructions of lockable obfuscation achieve provable security under the Learning with Errors assumption. One limitation of these constructions is that they achieve only statistical correctness and allow for a possible one-sided error where the obfuscated program could output the msg on some value x where P(x) \neq alpha.
In this work we motivate the problem of studying perfect correctness in lockable
obfuscation for the case where the party performing the obfuscation might wish
to inject a backdoor or hole in the correctness. We begin by studying the existing
constructions and identify two components that are susceptible to imperfect correctness. The first is in the LWE-based pseudo-random generators (PRGs) that are non-injective, while the second is in the last level testing procedure of the core constructions.
We address each in turn. First, we build upon previous work to design injective
PRGs that are provably secure from the LWE assumption. Next, we design an alternative last level testing procedure that has an additional structure to prevent correctness errors. We then provide surgical proof of security (to avoid redundancy) that connects our construction to the construction by Goyal, Koppula, and Waters (GKW). Specifically, we show how for a random value alpha an obfuscation under our new construction is indistinguishable from an obfuscation under the existing GKW construction.

2019

PKC

Collusion Resistant Broadcast and Trace from Positional Witness Encryption
Abstract

An emerging trend is for researchers to identify cryptography primitives for which feasibility was first established under obfuscation and then move the realization to a different setting. In this work we explore a new such avenue—to move obfuscation-based cryptography to the assumption of (positional) witness encryption. Our goal is to develop techniques and tools, which we will dub “witness encryption friendly” primitives and use these to develop a methodology for building advanced cryptography from positional witness encryption.We take a bottom up approach and pursue our general agenda by attacking the specific problem of building collusion-resistant broadcast systems with tracing from positional witness encryption. We achieve a system where the size of ciphertexts, public key and private key are polynomial in the security parameter $$\lambda $$ and independent of the number of users N in the broadcast system. Currently, systems with such parameters are only known from indistinguishability obfuscation.

2019

CRYPTO

Watermarking Public-Key Cryptographic Primitives
📺
Abstract

A software watermarking scheme enables users to embed a message or mark within a program while preserving its functionality. Moreover, it is difficult for an adversary to remove a watermark from a marked program without corrupting its behavior. Existing constructions of software watermarking from standard assumptions have focused exclusively on watermarking pseudorandom functions (PRFs).In this work, we study watermarking public-key primitives such as the signing key of a digital signature scheme or the decryption key of a public-key (predicate) encryption scheme. While watermarking public-key primitives might intuitively seem more challenging than watermarking PRFs, our constructions only rely on simple assumptions. Our watermarkable signature scheme can be built from the minimal assumption of one-way functions while our watermarkable public-key encryption scheme can be built from most standard algebraic assumptions that imply public-key encryption (e.g., factoring, discrete log, or lattice assumptions). Our schemes also satisfy a number of appealing properties: public marking, public mark-extraction, and collusion resistance. Our schemes are the first to simultaneously achieve all of these properties.The key enabler of our new constructions is a relaxed notion of functionality-preserving. While traditionally, we require that a marked program (approximately) preserve the input/output behavior of the original program, in the public-key setting, preserving the “functionality” does not necessarily require preserving the exact input/output behavior. For instance, if we want to mark a signing algorithm, it suffices that the marked algorithm still output valid signatures (even if those signatures might be different from the ones output by the unmarked algorithm). Similarly, if we want to mark a decryption algorithm, it suffices that the marked algorithm correctly decrypt all valid ciphertexts (but may behave differently from the unmarked algorithm on invalid or malformed ciphertexts). Our relaxed notion of functionality-preserving captures the essence of watermarking and still supports the traditional applications, but provides additional flexibility to enable new and simple realizations of this powerful cryptographic notion.

2019

CRYPTO

Broadcast and Trace with
$N^{\varepsilon }$
Ciphertext Size from Standard Assumptions
📺
Abstract

We construct a broadcast and trace scheme (also known as trace and revoke or broadcast, trace and revoke) with N users, where the ciphertext size can be made as low as
$$O(N^\varepsilon )$$
, for any arbitrarily small constant
$$\varepsilon >0$$
. This improves on the prior best construction of broadcast and trace under standard assumptions by Boneh and Waters (CCS ‘06), which had ciphertext size
$$O(N^{1/2})$$
. While that construction relied on bilinear maps, ours uses a combination of the learning with errors (LWE) assumption and bilinear maps.Recall that, in both broadcast encryption and traitor-tracing schemes, there is a collection of N users, each of which gets a different secret key
$${\mathsf {sk}}_i$$
. In broadcast encryption, it is possible to create ciphertexts targeted to a subset
$$S \subseteq [N]$$
of the users such that only those users can decrypt it correctly. In a traitor tracing scheme, if a subset of users gets together and creates a decoder box D that is capable of decrypting ciphertexts, then it is possible to trace at least one of the users responsible for creating D. A broadcast and trace scheme intertwines the two properties, in a way that results in more than just their union. In particular, it ensures that if a decoder D is able to decrypt ciphertexts targeted toward a set S of users, then it should be possible to trace one of the users in the set S responsible for creating D, even if other users outside of S also participated. As of recently, we have essentially optimal broadcast encryption (Boneh, Gentry, Waters CRYPTO ’05) under bilinear maps and traitor tracing (Goyal, Koppula, Waters STOC ’18) under LWE, where the ciphertext size is at most poly-logarithmic in N. The main contribution of our paper is to carefully combine LWE and bilinear-map based components, and get them to interact with each other, to achieve broadcast and trace.

2019

TCC

New Approaches to Traitor Tracing with Embedded Identities
Abstract

In a traitor tracing (TT) system for n users, every user has his/her own secret key. Content providers can encrypt messages using a public key, and each user can decrypt the ciphertext using his/her secret key. Suppose some of the n users collude to construct a pirate decoding box. Then the tracing scheme has a special algorithm, called $$\mathsf {Trace}$$, which can identify at least one of the secret keys used to construct the pirate decoding box.Traditionally, the trace algorithm output only the ‘index’ associated with the traitors. As a result, to use such systems, either a central master authority must map the indices to actual identities, or there should be a public mapping of indices to identities. Both these options are problematic, especially if we need public tracing with anonymity of users. Nishimaki, Wichs, and Zhandry (NWZ) [Eurocrypt 2016] addressed this problem by constructing a traitor tracing scheme where the identities of users are embedded in the secret keys, and the trace algorithm, given a decoding box D, can recover the entire identities of the traitors. We call such schemes ‘Embedded Identity Traitor Tracing’ schemes. NWZ constructed such schemes based on adaptively secure functional encryption (FE). Currently, the only known constructions of FE schemes are based on nonstandard assumptions such as multilinear maps and iO.In this work, we study the problem of embedded identities TT based on standard assumptions. We provide a range of constructions based on different assumptions such as public key encryption (PKE), bilinear maps and the Learning with Errors (LWE) assumption. The different constructions have different efficiency trade offs. In our PKE based construction, the ciphertext size grows linearly with the number of users; the bilinear maps based construction has sub-linear ($$\sqrt{n}$$) sized ciphertexts. Both these schemes have public tracing. The LWE based scheme is a private tracing scheme with optimal ciphertexts (i.e., $$\log (n)$$). Finally, we also present other notions of traitor tracing, and discuss how they can be build in a generic manner from our base embedded identity TT scheme.

2018

CRYPTO

Risky Traitor Tracing and New Differential Privacy Negative Results
Abstract

In this work we seek to construct collusion-resistant traitor tracing systems with small ciphertexts from standard assumptions that also move toward practical efficiency. In our approach we will hold steadfast to the principle of collusion resistance, but relax the requirement on catching a traitor from a successful decoding algorithm. We define a f-risky traitor tracing system as one where the probability of identifying a traitor is $$f(\lambda ,n)$$f(λ,n) times the probability a successful box is produced. We then go on to show how to build such systems from prime order bilinear groups with assumptions close to those used in prior works. Our core system achieves, for any $$k > 0$$k>0, $$f(\lambda ,n) \approx \frac{k}{n + k - 1}$$f(λ,n)≈kn+k-1 where ciphertexts consists of $$(k + 4)$$(k+4) group elements and decryption requires $$(k + 3)$$(k+3) pairing operations.At first glance the utility of such a system might seem questionable since the f we achieve for short ciphertexts is relatively small. Indeed an attacker in such a system can more likely than not get away with producing a decoding box. However, we believe this approach to be viable for four reasons:1.A risky traitor tracing system will provide deterrence against risk averse attackers. In some settings the consequences of being caught might bear a high cost and an attacker will have to weigh his utility of producing a decryption D box against the expected cost of being caught.2.Consider a broadcast system where we want to support low overhead broadcast encrypted communications, but will periodically allow for a more expensive key refresh operation. We refer to an adversary produced algorithm that maintains the ability to decrypt across key refreshes as a persistent decoder. We show how if we employ a risky traitor tracing systems in this setting, even for a small f, we can amplify the chances of catching such a “persistent decoder” to be negligibly close to 1.3.In certain resource constrained settings risky traitor tracing provides a best tracing effort where there are no other collusion-resistant alternatives. For instance, suppose we had to support 100 K users over a radio link that had just 10 KB of additional resources for extra ciphertext overhead. None of the existing $$\sqrt{N}$$N bilinear map systems can fit in these constraints. On the other hand a risky traitor tracing system provides a spectrum of tracing probability versus overhead tradeoffs and can be configured to at least give some deterrence in this setting.4.Finally, we can capture impossibility results for differential privacy from $$\frac{1}{n}$$1n-risky traitor tracing. Since our ciphertexts are short ($$O(\lambda )$$O(λ)), we get the negative result which matches what one would get plugging in the obfuscation based tracing system Boneh-Zhandry [9] solution into the prior impossibility result of Dwork et al. [14].

2017

EUROCRYPT

#### Program Committees

- Eurocrypt 2020

#### Coauthors

- Shweta Agrawal (2)
- Vipul Goyal (1)
- Susan Hohenberger (1)
- Sam Kim (2)
- Venkata Koppula (7)
- Jiahui Liu (1)
- Nathan Manohar (1)
- Willy Quach (1)
- Andrew Russell (1)
- Habeeb Syed (1)
- Junichi Tomida (2)
- Satyanarayana Vusirikala (4)
- Brent Waters (14)
- Daniel Wichs (1)
- David J. Wu (2)