## CryptoDB

### Shweta Agrawal

#### Affiliation: IIT Madras, India

#### Publications

**Year**

**Venue**

**Title**

2020

EUROCRYPT

Optimal Broadcast Encryption from Pairings and LWE
★
Abstract

Boneh, Waters and Zhandry (CRYPTO 2014) used multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption (BE) where all parameters in the system are small. In this work, we improve their result by providing a solution that uses only {\it bilinear} maps and Learning With Errors (LWE). Our scheme is fully collusion-resistant against any number of colluders, and can be generalized to an identity-based broadcast system with short parameters. Thus, we reclaim the problem of optimal broadcast encryption from the land of ``Obfustopia''.
Our main technical contribution is a ciphertext policy attribute based encryption (CP-ABE) scheme which achieves special efficiency properties -- its ciphertext size, secret key size, and public key size are all independent of the size of the circuits supported by the scheme. We show that this special CP-ABE scheme implies BE with optimal parameters; but it may also be of independent interest. Our constructions rely on a novel interplay of bilinear maps and LWE, and are proven secure in the generic group model.

2020

EUROCRYPT

Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE
📺
Abstract

Candidates of Indistinguishability Obfuscation (iO) can be categorized as ``direct'' or ``bootstrapping based''. Direct constructions rely on high degree multilinear maps [GGH13,GGHRSW13] and provide heuristic guarantees, while bootstrapping based constructions [LV16,Lin17,LT17,AJLMS19,Agr19,JLMS19] rely, in the best case, on bilinear maps as well as new variants of the Learning With Errors (LWE) assumption and pseudorandom generators. Recent times have seen exciting progress in the construction of indistinguishability obfuscation (iO) from bilinear maps (along with other assumptions) [LT17,AJLMS19,JLMS19,Agr19].
As a notable exception, a recent work by Agrawal [Agr19] provided a construction for iO without using any maps. This work identified a new primitive, called Noisy Linear Functional Encryption (NLinFE) that provably suffices for iO and gave a direct construction of NLinFE from new assumptions on lattices. While a preliminary cryptanalysis for the new assumptions was provided in the original work, the author admitted the necessity of performing significantly more cryptanalysis before faith could be placed in the security of the scheme. Moreover, the author did not suggest concrete parameters for the construction.
In this work, we fill this gap by undertaking the task of thorough cryptanalytic study of NLinFE. We design two attacks that let the adversary completely break the security of the scheme. Our attacks are completely new and unrelated to attacks that were hitherto used to break other candidates of iO. To achieve this, we develop new cryptanalytic techniques which (we hope) will inform future designs of the primitive of NLinFE.
From the knowledge gained by our cryptanalytic study, we suggest modifications to the scheme. We provide a new scheme which overcomes the vulnerabilities identified before. We also provide a thorough analysis of all the security aspects of this scheme and argue why plausible attacks do not work. We additionally provide concrete parameters with which the scheme may be instantiated. We believe the security of NLinFE stands on significantly firmer footing as a result of this work.

2020

PKC

Adaptive Simulation Security for Inner Product Functional Encryption
📺
Abstract

Inner product functional encryption ( $${mathsf {IPFE}}$$ ) [ 1 ] is a popular primitive which enables inner product computations on encrypted data. In $${mathsf {IPFE}}$$ , the ciphertext is associated with a vector $$varvec{x}$$ , the secret key is associated with a vector $$varvec{y}$$ and decryption reveals the inner product $$langle varvec{x},varvec{y}
angle $$ . Previously, it was known how to achieve adaptive indistinguishability ( $$mathsf {IND}$$ ) based security for $${mathsf {IPFE}}$$ from the $$mathsf {DDH}$$ , $$mathsf {DCR}$$ and $$mathsf {LWE}$$ assumptions [ 8 ]. However, in the stronger simulation ( $$mathsf {SIM}$$ ) based security game, it was only known how to support a restricted adversary that makes all its key requests either before or after seeing the challenge ciphertext, but not both. In more detail, Wee [ 46 ] showed that the $$mathsf {DDH}$$ -based scheme of Agrawal et al. (Crypto 2016) achieves semi-adaptive simulation-based security, where the adversary must make all its key requests after seeing the challenge ciphertext. On the other hand, O’Neill showed that all $$mathsf {IND}$$ -secure $${mathsf {IPFE}}$$ schemes (which may be based on $$mathsf {DDH}$$ , $$mathsf {DCR}$$ and $$mathsf {LWE}$$ ) satisfy $$mathsf {SIM}$$ based security in the restricted model where the adversary makes all its key requests before seeing the challenge ciphertext. In this work, we resolve the question of $$mathsf {SIM}$$ -based security for $${mathsf {IPFE}}$$ by showing that variants of the $${mathsf {IPFE}}$$ constructions by Agrawal et al. , based on $$mathsf {DDH}$$ , Paillier and $$mathsf {LWE}$$ , satisfy the strongest possible adaptive $$mathsf {SIM}$$ -based security where the adversary can make an unbounded number of key requests both before and after seeing the (single) challenge ciphertext. This establishes optimal security of the $${mathsf {IPFE}}$$ schemes, under all hardness assumptions on which it can (presently) be based.

2020

TCC

CP-ABE for Circuits (and more) in the Symmetric Key Setting
📺
Abstract

The celebrated work of Gorbunov, Vaikuntanathan and Wee [GVW13] provided the first key policy attribute based encryption scheme (ABE) for circuits from the Learning With Errors (LWE) assumption. However, the arguably more natural ciphertext policy variant has remained elusive, and is a central primitive not yet known from LWE.
In this work, we construct the first symmetric key ciphertext policy attribute based encryption scheme (CP-ABE) for all polynomial sized circuits from the learning with errors (LWE) assumption. In more detail, the ciphertext for a message m is labelled with an access control policy f, secret keys are labelled with public attributes x from the domain of f and decryption succeeds to yield the hidden message m if and only if f(x) = 1. The size of our public and secret key do not depend on the size of the circuits supported by the scheme – this enables our construction to support circuits of unbounded size (but bounded depth). Our construction is secure against collusions of unbounded size. We note that current best CP-ABE schemes [BSW07, Wat11, LOS+10, OT10, LW12, RW13, Att14, Wee14, AHY15, CGW15, AC17, KW19] rely on pairings and only support circuits in the class NC1 (albeit in the public key setting).
We adapt our construction to the public key setting for the case of bounded size circuits. The size of the ciphertext and secret key as well as running time of encryption, key generation and decryption satisfy the efficiency properties desired from CP-ABE, assuming that all algorithms have RAM access to the public key. However, the running time of the setup algorithm and size of the public key depends on the circuit size bound, restricting the construction to support circuits of a-priori bounded size. We remark that the inefficiency of setup is somewhat mitigated by the fact that setup must only be run once.
We generalize our construction to consider attribute and function hiding. The compiler of lockable obfuscation upgrades any attribute based encryption scheme to predicate encryption, i.e. with attribute hiding [GKW17, WZ17]. Since lockable obfuscation can be constructed from LWE, we achieve ciphertext policy predicate encryption immediately. For function privacy, we show that the most natural notion of function hiding ABE for circuits, even in the symmetric key setting, is sufficient to imply indistinguishability obfuscation. We define a suitable weakening of function hiding to sidestep the implication and provide a construction to achieve this notion for both the key policy and ciphertext policy case. Previously, the largest function class for which function private predicate encryption (supporting unbounded keys) could be achieved was inner product zero testing, by Shen, Shi and Waters [SSW09].

2020

TCC

Optimal Broadcast Encryption from LWE and Pairings in the Standard Model
📺
Abstract

Broadcast Encryption with optimal parameters was a long-standing problem, whose first solution was provided in an elegant work by Boneh, Waters and Zhandry \cite{BWZ14}. However, this work relied on multilinear maps of logarithmic degree, which is not considered a standard assumption. Recently, Agrawal and Yamada \cite{AY20} improved this state of affairs by providing the first construction of optimal broadcast encryption from Bilinear Maps and Learning With Errors (LWE). However, their proof of security was in the generic bilinear group model. In this work, we improve upon their result by providing a new construction and proof in the standard model. In more detail, we rely on the Learning With Errors (LWE) assumption and the Knowledge of OrthogonALity Assumption (KOALA) \cite{BW19} on bilinear groups.
Our construction combines three building blocks: a (computational) nearly linear secret sharing scheme with compact shares which we construct from LWE, an inner-product functional encryption scheme with special properties which is constructed from the bilinear Matrix Decision Diffie Hellman (MDDH) assumption, and a certain form of hyperplane obfuscation, which is constructed using the KOALA assumption. While similar to that of Agrawal and Yamada, our construction provides a new understanding of how to decompose the construction into simpler, modular building blocks with concrete and easy-to-understand security requirements for each one. We believe this sheds new light on the requirements for optimal broadcast encryption, which may lead to new constructions in the future.

2020

ASIACRYPT

Cryptography from One-Way Communication: On Completeness of Finite Channels
📺
Abstract

Garg et al. (Crypto 2015) initiated the study of cryptographic protocols over noisy channels in the non-interactive setting, namely when only one party speaks. A major question left open by this work is the completeness of {\em finite} channels, whose input and output alphabets do not grow with the desired level of security. In this work, we address this question by obtaining the following results:
Completeness of Bit-ROT with Inverse Polynomial Error: We show that bit-ROT (i.e., Randomized Oblivious Transfer channel, where each of the two messages is a single bit) can be used to realize general randomized functionalities with inverse polynomial error. Towards this, we provide a construction of string-ROT from bit-ROT with inverse polynomial error.
No Finite Channel is Complete with Negligible Error: To complement the above, we show that {\it no} finite channel can be used to realize string-ROT with negligible error, implying that the inverse polynomial error in the completeness of bit-ROT is inherent. This holds even with semi-honest parties and for computational security, and is contrasted with the (negligible-error) completeness of string-ROT shown by Garg et al.
Characterization of Finite Channels Enabling Zero-Knowledge Proofs: An important instance of secure computation is zero-knowledge proofs.
Noisy channels can potentially be used to realize truly non-interactive zero-knowledge proofs, without trusted common randomness, and with non-transferability and deniability features that cannot be realized in the plain model. Garg et al. obtain such zero-knowledge proofs from the binary erasure channel (BEC) and the binary symmetric channel (BSC). We complete the picture by showing that in fact any non-trivial channel suffices.

2019

CRYPTO

Attribute Based Encryption (and more) for Nondeterministic Finite Automata from LWE
📺
Abstract

Constructing Attribute Based Encryption (ABE) [56] for uniform models of computation from standard assumptions, is an important problem, about which very little is known. The only known ABE schemes in this setting that (i) avoid reliance on multilinear maps or indistinguishability obfuscation, (ii) support unbounded length inputs and (iii) permit unbounded key requests to the adversary in the security game, are by Waters from Crypto, 2012 [57] and its variants. Waters provided the first ABE for Deterministic Finite Automata (DFA) satisfying the above properties, from a parametrized or “q-type” assumption over bilinear maps. Generalizing this construction to Nondeterministic Finite Automata (NFA) was left as an explicit open problem in the same work, and has seen no progress to date. Constructions from other assumptions such as more standard pairing based assumptions, or lattice based assumptions has also proved elusive.In this work, we construct the first symmetric key attribute based encryption scheme for nondeterministic finite automata (NFA) from the learning with errors (LWE) assumption. Our scheme supports unbounded length inputs as well as unbounded length machines. In more detail, secret keys in our construction are associated with an NFA M of unbounded length, ciphertexts are associated with a tuple $$(\mathbf {x}, m)$$ where $$\mathbf {x}$$ is a public attribute of unbounded length and m is a secret message bit, and decryption recovers m if and only if $$M(\mathbf {x})=1$$.Further, we leverage our ABE to achieve (restricted notions of) attribute hiding analogous to the circuit setting, obtaining the first predicate encryption and bounded key functional encryption schemes for NFA from LWE. We achieve machine hiding in the single/bounded key setting to obtain the first reusable garbled NFA from standard assumptions. In terms of lower bounds, we show that secret key functional encryption even for DFAs, with security against unbounded key requests implies indistinguishability obfuscation ($$\mathsf {iO}$$) for circuits; this suggests a barrier in achieving full fledged functional encryption for NFA.

2019

EUROCRYPT

Indistinguishability Obfuscation Without Multilinear Maps: New Methods for Bootstrapping and Instantiation
Abstract

Constructing indistinguishability obfuscation ($$\mathsf{iO}$$iO) [17] is a central open question in cryptography. We provide new methods to make progress towards this goal. Our contributions may be summarized as follows:1.Bootstrapping. In a recent work, Lin and Tessaro [71] (LT) show that $$\mathsf{iO}$$iO may be constructed using (i) Functional Encryption ($$\mathsf {FE}$$FE) for polynomials of degree L, (ii) Pseudorandom Generators ($$\mathsf{PRG}$$PRG) with blockwise localityL and polynomial expansion, and (iii) Learning With Errors ($$\mathsf{LWE}$$LWE). Since there exist constructions of $$\mathsf {FE}$$FE for quadratic polynomials from standard assumptions on bilinear maps [16, 68], the ideal scenario would be to set $$L=2$$L=2, yielding $$\mathsf{iO}$$iO from widely believed assumptionsUnfortunately, it was shown soon after [18, 73] that $$\mathsf{PRG}$$PRG with block locality 2 and the expansion factor required by the LT construction, concretely $$\varOmega (n \cdot 2^{b(3+\epsilon )})$$Ω(n·2b(3+ϵ)), where n is the input length and b is the block length, do not exist. In the worst case, these lower bounds rule out 2-block local $$\mathsf{PRG}$$PRG with stretch $$\varOmega (n \cdot 2^{b(2+\epsilon )})$$Ω(n·2b(2+ϵ)). While [18, 73] provided strong negative evidence for constructing $$\mathsf{iO}$$iO based on bilinear maps, they could not rule out the possibility completely; a tantalizing gap has remained. Given the current state of lower bounds, the existence of 2 block local $$\mathsf{PRG}$$PRG with expansion factor $$\varOmega (n \cdot 2^{b(1+\epsilon )})$$Ω(n·2b(1+ϵ)) remains open, although this stretch does not suffice for the LT bootstrapping, and is hence unclear to be relevant for $$\mathsf{iO}$$iO.In this work, we improve the state of affairs as follows.(a)Weakening requirements on Boolean PRGs: In this work, we show that the narrow window of expansion factors left open by lower bounds do suffice for $$\mathsf{iO}$$iO. We show a new method to construct $$\mathsf {FE}$$FE for $$\mathsf {NC}_1$$NC1 from (i) $$\mathsf {FE}$$FE for degree L polynomials, (ii) $$\mathsf{PRG}$$PRGs of block locality L and expansion factor $$\tilde{\varOmega }(n \cdot 2^{b(1+\epsilon )})$$Ω~(n·2b(1+ϵ)), and (iii) $$\mathsf{LWE}$$LWE (or $$\mathsf{RLWE}$$RLWE).(b)Broadening class of sufficient randomness generators: Our bootstrapping theorem may be instantiated with a broader class of pseudorandom generators than hitherto considered for $$\mathsf{iO}$$iO, and may circumvent lower bounds known for the arithmetic degree of $$\mathsf{iO}$$iO-sufficient $$\mathsf{PRG}$$PRGs [18, 73]; in particular, these may admit instantiations with arithmetic degree 2, yielding $$\mathsf{iO}$$iO with the additional assumptions of $$\mathsf{SXDH}$$SXDH on Bilinear maps and $$\mathsf{LWE}$$LWE. In more detail, we may use the following two classes of $$\mathsf{PRG}$$PRG:i.Non-Boolean PRGs: We may use pseudorandom generators whose inputs and outputs need not be Boolean but may be integers restricted to a small (polynomial) range. Additionally, the outputs are not required to be pseudorandom but must only satisfy a milder indistinguishability property (We note that our notion of non Boolean PRGs is qualitatively similar to the notion of $$\varDelta $$Δ RGs defined in the concurrent work of Ananth, Jain and Sahai [9]. We emphasize that the methods of [9] and the present work are very different, but both works independently discover the same notion of weak PRG as sufficient for building $$\mathsf{iO}$$iO.).ii.Correlated Noise Generators: We introduce an even weaker class of pseudorandom generators, which we call correlated noise generators ($$\mathsf{CNG}$$CNG) which may not only be non-Boolean but are required to satisfy an even milder (seeming) indistinguishability property than $$\varDelta $$Δ RG.(c)Assumptions and Efficiency. Our bootstrapping theorems can be based on the hardness of the Learning With Errors problem or its ring variant ($$\mathsf{LWE}/ \mathsf{RLWE}$$LWE/RLWE) and can compile $$\mathsf {FE}$$FE for degree L polynomials directly to $$\mathsf {FE}$$FE for $$\mathsf {NC}_1$$NC1. Previous work compiles $$\mathsf {FE}$$FE for degree L polynomials to $$\mathsf {FE}$$FE for $$\mathsf {NC}_0$$NC0 to $$\mathsf {FE}$$FE for $$\mathsf {NC}_1$$NC1 to $$\mathsf{iO}$$iO [12, 45, 68, 72].Our method for bootstrapping to $$\mathsf {NC}_1$$NC1 does not go via randomized encodings as in previous works, which makes it simpler and more efficient than in previous works.2.Instantiating Primitives. In this work, we provide the first direct candidate of $$\mathsf {FE}$$FE for constant degree polynomials from new assumptions on lattices. Our construction is new and does not go via multilinear maps or graded encoding schemes as all previous constructions. Together with the bootstrapping step above, this yields a completely new candidate for$$\mathsf{iO}$$iO (as well as $$\mathsf {FE}$$FE for $$\mathsf {NC}_1$$NC1), which makes no use of multilinear or even bilinear maps. Our construction is based on the ring learning with errors assumption ($$\mathsf{RLWE}$$RLWE) as well as new untested assumptions on NTRU rings.We provide a detailed security analysis and discuss why previously known attacks in the context of multilinear maps, especially zeroizing and annihilation attacks, do not appear to apply to our setting. We caution that our construction must yet be subject to rigorous cryptanalysis by the community before confidence can be gained in its security. However, we believe that the significant departure from known multilinear map based constructions opens up a new and potentially fruitful direction to explore in the quest for $$\mathsf{iO}$$iO.Our construction is based entirely on lattices, due to which one may hope for post quantum security. Note that this feature is not enjoyed by instantiations that make any use of bilinear maps even if secure instances of weak PRGs, as identified by the present work, the follow-up by Lin and Matt [69] and the independent work by Ananth, Jain and Sahai [9] are found.

2019

TCC

Attribute Based Encryption for Deterministic Finite Automata from $\mathsf{DLIN}$
Abstract

Waters [Crypto, 2012] provided the first attribute based encryption scheme ABE for Deterministic Finite Automata (DFA) from a parametrized or “q-type” assumption over bilinear maps. Obtaining a construction from static assumptions has been elusive, despite much progress in the area of ABE.In this work, we construct the first attribute based encryption scheme for DFA from static assumptions on pairings, namely, the $$\mathsf{DLIN}$$ assumption. Our scheme supports unbounded length inputs, unbounded length machines and unbounded key requests. In more detail, secret keys in our construction are associated with a DFA M of unbounded length, ciphertexts are associated with a tuple $$(\mathbf {x}, \mathsf {\mu })$$ where $$\mathbf {x}$$ is a public attribute of unbounded length and $$\mathsf {\mu }$$ is a secret message bit, and decryption recovers $$\mathsf {\mu }$$ if and only if $$M(\mathbf {x})=1$$.Our techniques are at least as interesting as our final result. We present a simple compiler that combines constructions of unbounded ABE schemes for monotone span programs (MSP) in a black box way to construct ABE for DFA. In more detail, we find a way to embed DFA computation into monotone span programs, which lets us compose existing constructions (modified suitably) of unbounded key-policy ABE ($${\mathsf {kpABE}}$$) and unbounded ciphertext-policy ABE ($${\mathsf {cpABE}}$$) for MSP in a simple and modular way to obtain key-policy ABE for DFA. Our construction uses its building blocks in a symmetric way – by swapping the use of the underlying $${\mathsf {kpABE}}$$ and $${\mathsf {cpABE}}$$, we also obtain a construction of ciphertext-policy ABE for DFA.Our work extends techniques developed recently by Agrawal, Maitra and Yamada [Crypto 2019], which show how to construct ABE that support unbounded machines and unbounded inputs by combining ABE schemes that are bounded in one co-ordinate. At the heart of our work is the observation that unbounded, multi-use ABE for MSP already achieve most of what we need to build ABE for DFA.

2018

TCC

FE and iO for Turing Machines from Minimal Assumptions
Abstract

We construct Indistinguishability Obfuscation ($$\mathsf {iO}$$) and Functional Encryption ($$\mathsf {FE}$$) schemes in the Turing machine model from the minimal assumption of compact $$\mathsf {FE}$$ for circuits ($$\mathsf {CktFE}$$). Our constructions overcome the barrier of sub-exponential loss incurred by all prior work. Our contributions are:1.We construct $$\mathsf {iO}$$ in the Turing machine model from the same assumptions as required in the circuit model, namely, sub-exponentially secure $$\mathsf {FE}$$ for circuits. The previous best constructions [6, 41] require sub-exponentially secure $$\mathsf {iO}$$ for circuits, which in turn requires sub-exponentially secure $$\mathsf {FE}$$ for circuits [5, 15].2.We provide a new construction of single input $$\mathsf {FE}$$ for Turing machines with unbounded length inputs and optimal parameters from polynomially secure, compact $$\mathsf {FE}$$ for circuits. The previously best known construction by Ananth and Sahai [7] relies on $$\mathsf {iO}$$ for circuits, or equivalently, sub-exponentially secure $$\mathsf {FE}$$ for circuits.3.We provide a new construction of multi-input $$\mathsf {FE}$$ for Turing machines. Our construction supports a fixed number of encryptors (say k), who may each encrypt a string $$\mathbf {x}_i$$ of unbounded length. We rely on sub-exponentially secure $$\mathsf {FE}$$ for circuits, while the only previous construction [10] relies on a strong knowledge type assumption, namely, public coin differing inputs obfuscation.
Our techniques are new and from first principles, and avoid usage of sophisticated $$\mathsf {iO}$$ specific machinery such as positional accumulators and splittable signatures that were used by all relevant prior work [6, 7, 41].

2012

CRYPTO

2010

EPRINT

Preventing Pollution Attacks in Multi-Source Network Coding
Abstract

Network coding is a method for achieving channel capacity in networks.
The key idea is to allow network routers to linearly mix packets as
they traverse the network so that recipients receive linear
combinations of packets. Network coded systems are vulnerable to
pollution attacks where a single malicious node floods the network
with bad packets and prevents the receiver from decoding correctly.
Cryptographic defenses to these problems are based on homomorphic
signatures and MACs. These proposals, however, cannot handle mixing of
packets from multiple sources, which is needed to achieve the full
benefits of network coding. In this paper we address integrity of
multi-source mixing. We propose a security model for this setting
and provide a generic construction.

#### Program Committees

- Asiacrypt 2020
- Asiacrypt 2019
- TCC 2018
- PKC 2018
- Crypto 2018
- Asiacrypt 2017
- Crypto 2017
- Eurocrypt 2016
- PKC 2015

#### Coauthors

- Shashank Agrawal (3)
- Saikrishna Badrinarayanan (1)
- Dan Boneh (4)
- Xavier Boyen (5)
- Yevgeniy Dodis (1)
- David Freeman (3)
- Craig Gentry (1)
- Sergey Gorbunov (1)
- Vipul Goyal (1)
- Shai Halevi (1)
- Yuval Ishai (1)
- Abhishek Jain (1)
- Abishek Kumarasubramanian (1)
- Eyal Kushilevitz (1)
- Benoît Libert (2)
- Monosij Maitra (4)
- Varun Narayanan (1)
- Alice Pellet-Mary (1)
- Vinod Prabhakaran (1)
- Manoj Prabhakaran (5)
- Alon Rosen (2)
- Amit Sahai (3)
- Damien Stehlé (1)
- Radu Titiu (1)
- Vinod Vaikuntanathan (4)
- Panagiotis Voulgaris (1)
- Hoeteck Wee (2)
- Daniel Wichs (2)
- Shota Yamada (5)