## CryptoDB

### Hoeteck Wee

#### Publications

**Year**

**Venue**

**Title**

2024

EUROCRYPT

Succinct Functional Commitments for Circuits from k-Lin
Abstract

A functional commitment allows a user to commit to an input x and later, open the commitment to an arbitrary function y = f(x). The size of the commitment and the opening should be sublinear in |x| and |f|.
In this work, we give the first pairing-based functional commitment for arbitrary circuits where the size of the commitment and the size of the opening consist of a constant number of group elements. Security relies on the standard bilateral k-Lin assumption. This is the first scheme with this level of succinctness from falsifiable bilinear map assumptions (previous approaches required SNARKs for NP). This is also the first functional commitment scheme for general circuits with poly(lambda)-size commitments and openings from any assumption that makes fully black-box use of cryptographic primitives and algorithms. Our construction relies on a new notion of projective chainable commitments which may be of independent interest.

2024

CRYPTO

Circuit ABE with poly(depth, λ)-sized Ciphertexts and Keys from Lattices
Abstract

We present new lattice-based attribute-based encryption (ABE) and
laconic function evaluation (LFE) schemes for circuits with *sublinear*
ciphertext overhead. For depth $d$ circuits over $\ell$-bit inputs, we obtain
* an ABE with ciphertext and secret key size $O(1)$;
* a LFE with ciphertext size $\ell + O(1)$ and digest size $O(1)$;
* an ABE with public key and ciphertext size $O(\ell^{2/3})$ and
secret key size $O(1)$,
where $O(\cdot)$ hides $\poly(d,\lambda)$ factors. The first two
results achieve almost optimal ciphertext and secret key / digest
sizes, up to the $\poly(d)$ dependencies. The security of our schemes
relies on $\ell$-succinct LWE, a falsifiable assumption which is
implied by evasive LWE. At the core of our results is a new technique
for compressing LWE samples $s(A-x \otimes G)$ as well
as the matrix $A$.

2024

CRYPTO

Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup
Abstract

Polynomial commitment scheme allows a prover to commit to a polynomial $f \in \ring[X]$ of degree $L$, and later prove that the committed function was correctly evaluated at a specified point $x$; in other words $f(x)=u$ for public $x,u \in \ring$. Most applications of polynomial commitments, e.g. succinct non-interactive arguments of knowledge (SNARKs), require that (i) both the commitment and evaluation proof are succinct (i.e., polylogarithmic in the degree $L$) - with the latter being efficiently verifiable, and (ii) no pre-processing step is allowed.
Surprisingly, as far as plausibly quantum-safe polynomial commitments are concerned, the currently most efficient constructions only rely on weak cryptographic assumptions, such as security of hash functions. Indeed, despite making use of the underlying algebraic structure, prior lattice-based polynomial commitments still seem to be much behind the hash-based ones. Moreover, security of the aforementioned lattice constructions against quantum adversaries was never formally discussed.
In this work, we bridge the gap and propose the first (asymptotically and concretely) efficient lattice-based polynomial commitment with transparent setup and post-quantum security. Our interactive variant relies on the standard (Module-)SIS problem, and can be made non-interactive in the random oracle model using Fiat-Shamir transformation. In addition, we equip the scheme with a knowledge soundness proof against quantum adversaries which can be of independent interest. In terms of concrete efficiency, for $L=2^{20}$ our scheme yields proofs of size $2$X smaller than the hash-based \textsf{FRI} commitment (Block et al., Asiacrypt 2023), and $60$X smaller than the very recent lattice-based construction by Albrecht et al. (Eprint 2023/1469).

2024

CRYPTO

Laconic Function Evaluation and ABE for RAMs from (Ring-)LWE
Abstract

Laconic function evaluation (LFE) allows us to compress a circuit $f$ into a short digest. Anybody can use this digest as a public-key to efficiently encrypt some input $x$. Decrypting the resulting ciphertext reveals the output $f(x)$, while hiding everything else about $x$. In this work we consider LFE for \emph{Random-Access Machines} (RAM-LFE) where, instead of a circuit $f$, we have a RAM program $f_{\DB}$ that potentially contains some large hard-coded data $\DB$. The decryption run-time to recover $f_{\DB}(x)$ from the ciphertext should be roughly the same as a plain evaluation of $f_{\DB}(x)$ in the RAM model, which can be sublinear in the size of $\DB$. Prior works constructed LFE for circuits under LWE, and RAM-LFE under indisitinguishability obfuscation (iO) and Ring-LWE. In this work, we construct RAM-LFE with essentially optimal encryption and decryption run-times from just Ring-LWE and a standard circular security assumption, without iO.
RAM-LFE directly yields 1-key succinct functional encryption and reusable garbling for RAMs with similar parameters.
If we only want an \emph{attribute-based} LFE for RAMs (RAM-AB-LFE), then we can replace Ring-LWE with plain LWE in the above. Orthogonally, if we only want \emph{leveled} schemes, where the encryption/decryption efficiency can scale with the depth of the RAM computation, then we can remove the need for a circular-security. Lastly, we also get a leveled many-key \emph{attribute-based encryption for RAMs (RAM-ABE)}, from LWE.

2023

EUROCRYPT

Traitor Tracing with N^(1/3)-size Ciphertext and O(1)-size Keys from k-Lin
Abstract

We present a pairing-based traitor tracing scheme for N users with
|pk| = |ct| = O(N^(1/3)), |sk| = O(1).
This is the first pairing-based scheme to achieve |pk| * |sk| * |ct| = o(N). Our construction relies on the (bilateral) k-Lin assumption, and achieves private tracing and full collusion resistance. Our result simultaneously improves upon the sizes of pk, ct in Boneh--Sahai--Waters [Eurocrypt '06] and the size of sk in Zhandry [Crypto '20], while further eliminating the reliance on the generic group model in the latter work.

2023

EUROCRYPT

Succinct Vector, Polynomial, and Functional Commitments from Lattices
Abstract

Vector commitment schemes allow a user to commit to a vector of values $\mathbf{x} \in \{0,1\}^\ell$ and later, open up the commitment to a specific set of positions. Both the size of the commitment and the size of the opening should be succinct (i.e., polylogarithmic in the length $\ell$ of the vector). Vector commitments and their generalizations to polynomial commitments and functional commitments are key building blocks for many cryptographic protocols.
We introduce a new framework for constructing non-interactive lattice-based vector commitments and their generalizations. A simple instantiation of our framework yields a new vector commitment scheme from the standard short integer solution (SIS) assumption that supports private openings and large messages. We then show how to use our framework to obtain the first succinct functional commitment scheme that supports openings with respect to arbitrary bounded-depth Boolean circuits. In this scheme, a user commits to a vector $\mathbf{x} \in \{0,1\}^\ell$, and later on, open the commitment to any function $f(\xv)$. Both the commitment and the opening are non-interactive and succinct: namely, they have size $\textsf{poly}(\lambda, d, log \ell)$, where \lambda is the security parameter and $d$ is the depth of the Boolean circuit computing $f$. Previous constructions of functional commitments could only support constant-degree polynomials, or require a trusted online authority, or rely on non-falsifiable assumptions. The security of our functional commitment scheme is based on a new falsifiable family of "basis-augmented" SIS assumptions (BASIS) we introduce in this work.
We also show how to use our vector commitment framework to obtain (1) a polynomial commitment scheme where the user can commit to a polynomial $f \in \mathbb{Z}_q[x]$ and subsequently open the commitment to an evaluation $f(x) \in \mathbb{Z}_q$; and (2) an aggregatable vector (resp., functional) commitment where a user can take a set of openings to multiple indices (resp., function evaluations) and aggregate them into a single short opening. Both of these extensions rely on the same BASIS assumption we use to obtain our succinct functional commitment scheme.

2023

ASIACRYPT

Lattice-Based Functional Commitments: Fast Verification and Cryptanalysis
Abstract

A functional commitment allows a user to commit to an input x \in {0, 1}^\ell and later open up the commitment to a value y = f(x) with respect to some function f. In this work, we focus on schemes that support fast verification. Specifically, after a preprocessing step that depends only on $f$, the verification time as well as the size of the commitment and opening should be sublinear in the input length \ell, We also consider the dual setting where the user commits to the function f and later, opens up the commitment at an input x.
In this work, we develop two (non-interactive) functional commitments that support fast verification. The first construction supports openings to constant-degree polynomials and has a shorter CRS for a broad range of settings compared to previous constructions. Our second construction is a dual functional commitment for arbitrary bounded-depth Boolean circuits that supports fast verification with security from falsifiable assumptions. Both schemes are lattice-based and avoid non-black-box use of cryptographic primitives or lattice sampling algorithms. Security of both constructions rely on the \ell-succinct short integer solutions (SIS) assumption, a falsifiable q-type generalization of the SIS assumption (Preprint 2023).
In addition, we study the challenges of extending lattice-based functional commitments to extractable functional commitments, a notion that is equivalent to succinct non-interactive arguments (when considering openings to quadratic relations). We describe a general methodology that heuristically breaks the extractability of our construction and provides evidence for the implausibility of the knowledge k-R-ISIS assumption of Albrecht et al. (CRYPTO 2022) that was used in several constructions of lattice-based succinct arguments. If we additionally assume hardness of the standard inhomogeneous SIS assumption, we obtain a direct attack on a variant of the extractable linear functional commitment of Albrecht et al.

2023

ASIACRYPT

Distributed Broadcast Encryption from Bilinear Groups
Abstract

Distributed broadcast encryption (DBE) improves on the
traditional notion of broadcast encryption by eliminating the key-escrow
problem: In a DBE system, users generate their own secret keys non-
interactively without the help of a trusted party. Then anyone can broad-
cast a message for a subset S of the users, in such a way that the resulting
ciphertext size is sublinear in (and, ideally, independent of) |S|. Unfor-
tunately, the only known constructions of DBE requires heavy crypto-
graphic machinery, such as general-purpose indistinguishability obfusca-
tion, or come without a security proof.
In this work, we formally show that obfuscation is not necessary for DBE,
and we present two practical DBE schemes from standard assumptions in
prime-order bilinear groups. Our constructions are conceptually simple,
satisfy the strong notion of adaptive security, and are concretely efficient.
In fact, their performance, in terms of number of group elements and
efficiency of the algorithms, is comparable with that of traditional (non
distributed) broadcast encryption schemes from bilinear groups.

2022

EUROCRYPT

Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions
📺
Abstract

We present a new, simple candidate broadcast encryption scheme for N users with parameter size poly(logN). We prove security of our scheme under a non-standard variant of the LWE assumption where the distinguisher additionally receives short Gaussian pre-images while avoiding zeroizing attacks. This yields the first candidate optimal broadcast encryption that is plausibly post-quantum secure, and enjoys a security reduction to a simple assumption. As a secondary contribution, we present a candidate ciphertext-policy attribute-based encryption (CP-ABE) scheme for circuits of a-priori bounded polynomial depth where the parameter size is independent of the circuit size, and prove security under an additional non-standard assumption.

2022

ASIACRYPT

Witness Encryption and Null-IO from Evasive LWE
Abstract

Witness encryption (WE) allows us to use an arbitrary NP statement $x$ as a public key to encrypt a message, and the witness $w$ serves as a decryption key. Security ensures that, when the statement $x$ is false, the encrypted message remains computationally hidden. WE appears to be significantly weaker than indistinguishability obfuscation (iO). Indeed, WE is closely related to a highly restricted form of iO that only guarantees security for null circuits (null iO). However, all current approaches towards constructing WE under nice assumptions go through iO. Such constructions are quite complex and are unlikely to lead to practically instantiable schemes.
In this work, we revisit a very simple WE and null iO candidate of Chen, Vaikuntanathan and Wee (CRYPTO 2018). We show how to prove its security under a nice and easy-to-state assumption that we refer to as {\em evasive LWE} following Wee (EUROCRYPT 2022). Roughly speaking, the evasive LWE assumption says the following: assume we have some joint distributions over matrices $\mathbf{P}$, $\mathbf{S}$ and auxiliary information $\aux$ such that
$$({\bS\bB + \bE},{\bS \bP + \bE'}, \aux) \approx_c ({\bU},{\bU'}, \aux),$$
for a uniformly random (and secret) matrix $\mathbf{B}$, where $\mathbf{U}, \mathbf{U}'$ are uniformly random matrices, and $\mathbf{E},\mathbf{E}'$ are chosen from the LWE error distribution with appropriate parameters. Then it must also be the case that:
$$({\bS\bB + \bE}, \bB^{-1}(\bP),\aux) \approx_c (\bU, \bB^{-1}(\bP),\aux).$$
Essentially the above says that given ${\bS\bB + \bE}$, getting the additional component $\bB^{-1}(\bP)$ is no more useful than just getting the product $({\bS\bB + \bE})\cdot \bB^{-1}(\bP) \approx \bS \bP + \bE'$.

2022

TCC

Multi-Authority ABE from Lattices without Random Oracles
Abstract

Attribute-based encryption (ABE) extends public-key encryption to enable fine-grained control to encrypted data. However, this comes at the cost of needing a central trusted authority to issue decryption keys. A multi-authority ABE (MA-ABE) scheme decentralizes ABE and allows anyone to serve as an authority. Existing constructions of MA-ABE only achieve security in the random oracle model.
In this work, we develop new techniques for constructing MA-ABE for the class of subset policies (which captures policies such as conjunctions and DNF formulas) whose security can be based in the plain model without random oracles. We achieve this by relying on the recently-proposed "evasive" learning with errors (LWE) assumption by Wee (EUROCRYPT 2022) and Tsabury (CRYPTO 2022).
Along the way, we also provide a modular view of the MA-ABE scheme for DNF formulas by Datta et al. (EUROCRYPT 2021) in the random oracle model. We formalize this via a general version of a related-trapdoor LWE assumption by Brakerski and Vaikuntanathan (ITCS 2022), which can in turn be reduced to the plain LWE assumption. As a corollary, we also obtain an MA-ABE scheme for subset policies from plain LWE with a polynomial modulus-to-noise ratio in the random oracle model. This improves upon the Datta et al. construction which relied on LWE with a sub-exponential modulus-to-noise ratio. Moreover, we are optimistic that the generalized related-trapdoor LWE assumption will also be useful for analyzing the security of other lattice-based constructions.

2021

CRYPTO

Broadcast Encryption with Size N^{1/3} and More from k-Lin
Abstract

We present the first pairing-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for the class of degree 3 polynomials with compact parameters: the public key, ciphertext and secret keys comprise O(n) group elements, where n is input length for the function. As an immediate corollary, we obtain a pairing-based broadcast encryption scheme for N users with O(N^1/3)- sized parameters, giving the first significant parameter improvements in pairing- based broadcast encryption in over a decade. All of our constructions achieve adaptive security against unbounded collusions, and rely on the (bilateral) k-Lin assumption in prime-order bilinear groups.

2021

TCC

Succinct LWE Sampling, Random Polynomials, and Obfuscation
📺
Abstract

We present a construction of indistinguishability obfuscation (iO) that relies on the learning with errors (LWE) assumption together with a new notion of succinctly sampling pseudo-random LWE samples. We then present a candidate LWE sampler whose security is related to the hardness of solving systems of polynomial equations. Our construction improves on the recent iO candidate of Wee and Wichs (Eurocrypt 2021) in two ways: first, we show that a much weaker and simpler notion of LWE sampling suffices for iO; and secondly, our candidate LWE sampler is secure based on a compactly specified and falsifiable assumption about random polynomials, with a simple error distribution that facilitates cryptanalysis.

2021

TCC

ABE for DFA from LWE against Bounded Collusions, Revisited
Abstract

We present a new public-key ABE for DFA based on the LWE assumption,
achieving security against collusions of a-priori bounded size. Our
scheme achieves ciphertext size O~(L + B) for attributes
of length L and collusion size B. Prior LWE-based schemes has
either larger ciphertext size O~(L B), or are
limited to the secret-key setting. Along the way, we introduce a new
technique for lattice trapdoor sampling, which we believe would be
of independent interest. Finally, we present a simple candidate public-key ABE for DFA for the unbounded collusion setting.

2021

EUROCRYPT

Candidate Obfuscation via Oblivious LWE Sampling
📺
Abstract

We present a new, simple candidate construction of indistinguishability obfuscation (iO). Our scheme is inspired by lattices and learning-with-errors (LWE) techniques, but we are unable to prove security under a standard assumption. Instead, we formulate a new falsifiable assumption under which the scheme is secure. Furthermore, the scheme plausibly achieves post-quantum security.
Our construction is based on the recent ``split FHE'' framework of Brakerski, D\"ottling, Garg, and Malavolta (EUROCRYPT '20), and we provide a new instantiation of this framework. As a first step, we construct an iO scheme that is provably secure assuming that LWE holds and that it is possible to obliviously generate LWE samples without knowing the corresponding secrets. We define a precise notion of oblivious LWE sampling that suffices for the construction. It is known how to obliviously sample from any distribution (in a very strong sense) using iO, and our result provides a converse, showing that the ability to obliviously sample from the specific LWE distribution (in a much weaker sense) already also implies iO. As a second step, we give a heuristic contraction of oblivious LWE sampling. On a very high level, we do this by homomorphically generating pseudorandom LWE samples using an encrypted pseudorandom function.

2020

JOFC

Compact Adaptively Secure ABE for ${\textsf {NC}}^{1}$ from k-Lin
Abstract

We present compact attribute-based encryption (ABE) schemes for $${\textsf {NC}}^{1}$$ NC 1 that are adaptively secure under the k -Lin assumption with polynomial security loss. Our KP-ABE scheme achieves ciphertext size that is linear in the attribute length and independent of the policy size even in the many-use setting, and we achieve an analogous efficiency guarantee for CP-ABE. This resolves the central open problem posed by Lewko and Waters (CRYPTO 2011). Previous adaptively secure constructions either impose an attribute “one-use restriction” (or the ciphertext size grows with the policy size) or require q -type assumptions.

2020

EUROCRYPT

New Constructions of Statistical NIZKs: Dual-Mode DV-NIZKs and More
📺
Abstract

Non-interactive zero-knowledge proofs (NIZKs) are important primitives in cryptography. A major challenge since the early works on NIZKs has been to construct NIZKs with a statistical zero-knowledge guarantee against unbounded verifiers. In the common reference string (CRS) model, such "statistical NIZK arguments" are currently known from k-Lin in a pairing-group and from LWE. In the (reusable) designated-verifier model (DV-NIZK), where a trusted setup algorithm generates a reusable verification key for checking proofs, we also have a construction from DCR. If we relax our requirements to computational zero-knowledge, we additionally have NIZKs from factoring and CDH in a pairing group in the CRS model, and from nearly all assumptions that imply public-key encryption (e.g., CDH, LPN, LWE) in the designated-verifier model. Thus, there still remains a gap in our understanding of statistical NIZKs in both the CRS and the designated-verifier models.
In this work, we develop new techniques for constructing statistical NIZK arguments. First, we construct statistical DV-NIZK arguments from the k-Lin assumption in pairing-free groups, the QR assumption, and the DCR assumption. These are the first constructions in pairing-free groups and from QR that satisfy statistical zero-knowledge. All of our constructions are secure even if the verification key is chosen maliciously (i.e., they are "malicious-designated-verifier" NIZKs), and moreover, they satisfy a "dual-mode" property where the CRS can be sampled from two computationally indistinguishable distributions: one distribution yields statistical DV-NIZK arguments while the other yields computational DV-NIZK proofs. We then show how to adapt our k-Lin construction in a pairing group to obtain new publicly-verifiable statistical NIZK arguments from pairings with a qualitatively weaker assumption than existing constructions of pairing-based statistical NIZKs.
Our constructions follow the classic paradigm of Feige, Lapidot, and Shamir (FLS). While the FLS framework has traditionally been used to construct computational (DV)-NIZK proofs, we newly show that the same framework can be leveraged to construct dual-mode (DV)-NIZKs.

2020

EUROCRYPT

Adaptively Secure ABE for DFA from k-Lin and More
📺
Abstract

In this work, we present:
- the first adaptively secure ABE for DFA from the k-Lin assumption in prime-order bilinear groups; this resolves one of open problems posed by Waters [CRYPTO'12];
- the first ABE for NFA from the k-Lin assumption, provided the number of accepting paths is smaller than the order of the underlying group; the scheme achieves selective security;
- the first compact adaptively secure ABE (supporting unbounded multi-use of attributes) for branching programs from the k-Lin assumption, which generalizes and simplifies the recent result of Kowalczyk and Wee for boolean formula (NC1) [EUROCRYPT'19].
Our adaptively secure ABE for DFA relies on a new combinatorial mechanism avoiding the exponential security loss in the number of states when naively combining two recent techniques from CRYPTO'19 and EUROCRYPT'19. This requires us to design a selectively secure ABE for NFA; we give a construction which is sufficient for our purpose and of independent interest. Our ABE for branching programs leverages insights from our ABE for DFA.

2020

CRYPTO

Functional Encryption for Attribute-Weighted Sums from k-Lin
📺
Abstract

We present functional encryption schemes for attribute-weighted sums, where encryption takes as input N attribute-value pairs (x_i,z_i) where x_i is public and z_i is private; secret keys are associated with arithmetic branching programs f, and decryption returns the weighted sum \sum_{i=1}^N f(x_i) z_i while leaking no additional information about the z_i's. Our main construction achieves
(1) compact public parameters and key sizes that are independent of N and the secret key can decrypt a ciphertext for any a-priori unbounded N;
(2) short ciphertexts that grow with N and the size of z_i but not x_i;
(3) simulation-based security against unbounded collusions;
(4) relies on the standard k-linear assumption in prime-order bilinear groups.

2020

CRYPTO

Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions
📺
Abstract

We study collision-finding against Merkle-Damgård hashing in the random-oracle model by adversaries with an arbitrary $S$-bit auxiliary advice input about the random oracle and $T$ queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage $\Omega(ST^2/2^n)$, where $n$ is the output length, beating the birthday bound by a factor of $S$. These attacks were shown to be optimal.
We observe that the collisions produced are very long, on the order $T$ blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find short collisions. We first exhibit a simple attack for finding $B$-block-long collisions achieving advantage $\tilde{\Omega}(STB/2^n)$. We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the $ST^2/2^n$ bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length $1$, length $2$, and unbounded-length collisions. Namely, the optimal attacks achieve (up to logarithmic factors) order of $(S+T)/2^n$, $ST/2^n$ and $ST^2/2^n$ advantage. We also give an upper bound on the advantage of a restricted class of short-collision finding attacks via a new analysis on the growth of trees in random functional graphs that may be of independent interest.

2020

TCC

Functional Encryption for Quadratic Functions from k-Lin, Revisited
Abstract

We present simple and improved constructions of public-key functional
encryption (FE) schemes for quadratic functions. Our main results are:
* an FE scheme for quadratic functions with constant-size keys as well
as shorter ciphertexts than all prior schemes based on static
assumptions;
* a public-key partially-hiding FE that supports
NC1 computation on public attributes and quadratic computation on
the private message, with ciphertext size independent of the length
of the public attribute.
Both constructions achieve selective, simulation-based security
against unbounded collusions, and rely on the (bilateral) k-linear
assumption in prime-order bilinear groups. At the core of these
constructions is a new reduction from FE for quadratic functions
to FE for linear functions.

2020

TCC

Information-Theoretic 2-Round MPC without Round Collapsing: Adaptive Security, and More
📺
Abstract

We present simpler and improved constructions of 2-round protocols for secure multi-party computation (MPC) in the semi-honest setting. Our main results are new information-theoretically secure protocols for arithmetic NC1 in two settings:
(i) the plain model tolerating up to $t < n/2$ corruptions; and
(ii) in the OLE-correlation model tolerating any number of corruptions.
Our protocols achieve adaptive security and require only black-box access to the underlying field, whereas previous results only achieve static security and require non-black-box field access. Moreover, both results extend to polynomial-size circuits with computational and adaptive security, while relying on black-box access to a pseudorandom generator. In the OLE correlation model, the extended protocols for circuits tolerate up to $n-1$ corruptions.
Along the way, we introduce a conceptually novel framework for 2-round MPC that does not rely on the round collapsing framework underlying all of the recent advances in 2-round MPC.

2019

EUROCRYPT

Compact Adaptively Secure ABE for $\mathsf {NC^1}$ from k-Lin
Abstract

We present compact attribute-based encryption (ABE) schemes for $$\mathsf {NC^1}$$ that are adaptively secure under the k-Lin assumption with polynomial security loss. Our KP-ABE scheme achieves ciphertext size that is linear in the attribute length and independent of the policy size even in the many-use setting, and we achieve an analogous efficiency guarantee for CP-ABE. This resolves the central open problem posed by Lewko and Waters (CRYPTO 2011). Previous adaptively secure constructions either impose an attribute “one-use restriction” (or the ciphertext size grows with the policy size), or require q-type assumptions.

2019

CRYPTO

ABE for DFA from k-Lin
📺
Abstract

We present the first attribute-based encryption (ABE) scheme for deterministic finite automaton (DFA) based on static assumptions in bilinear groups; this resolves an open problem posed by Waters (CRYPTO 2012). Our main construction achieves selective security against unbounded collusions under the standard k-linear assumption in prime-order bilinear groups, whereas previous constructions all rely on q-type assumptions.

2019

PKC

Obfuscating Simple Functionalities from Knowledge Assumptions
Abstract

This paper shows how to obfuscate several simple functionalities from a new Knowledge of OrthogonALity Assumption (KOALA) in cyclic groups which is shown to hold in the Generic Group Model. Specifically, we give simpler and stronger security proofs for obfuscation schemes for point functions, general-output point functions and pattern matching with wildcards. We also revisit the work of Bishop et al. (CRYPTO 2018) on obfuscating the pattern matching with wildcards functionality. We improve upon the construction and the analysis in several ways:attacks and stronger guarantees: We show that the construction achieves virtual black-box security for a simulator that runs in time roughly $$2^{n/2}$$, as well as distributional security for larger classes of distributions. We give attacks that show that our results are tight.weaker assumptions: We prove security under KOALA.better efficiency: We also provide a construction that outputs $$n+1$$ instead of 2n group elements.
We obtain our results by first obfuscating a simpler “big subset functionality”, for which we establish full virtual black-box security; this yields a simpler and more modular analysis for pattern matching. Finally, we extend our distinguishing attacks to a large class of simple linear-in-the-exponent schemes.

2019

TCC

Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation
Abstract

We initiate a systematic study of pseudorandom functions (PRFs) that are computable by simple matrix branching programs; we refer to these objects as “matrix PRFs”. Matrix PRFs are attractive due to their simplicity, strong connections to complexity theory and group theory, and recent applications in program obfuscation.Our main results are:We present constructions of matrix PRFs based on the conjectured hardness of computational problems pertaining to matrix products.We show that any matrix PRF that is computable by a read-c, width w branching program can be broken in time poly$$(w^c)$$; this means that any matrix PRF based on constant-width matrices must read each input bit $$\omega (\log (\lambda ))$$ times. Along the way, we simplify the “tensor switching lemmas” introduced in previous IO attacks.We show that a subclass of the candidate local-PRG proposed by Barak et al. [Eurocrypt 2018] can be broken using simple matrix algebra.We show that augmenting the CVW18 IO candidate with a matrix PRF provably immunizes the candidate against all known algebraic and statistical zeroizing attacks, as captured by a new and simple adversarial model.

2018

CRYPTO

GGH15 Beyond Permutation Branching Programs: Proofs, Attacks, and Candidates
📺
Abstract

We carry out a systematic study of the GGH15 graded encoding scheme used with general branching programs. This is motivated by the fact that general branching programs are more efficient than permutation branching programs and also substantially more expressive in the read-once setting. Our main results are as follows:Proofs. We present new constructions of private constrained PRFs and lockable obfuscation, for constraints (resp. functions to be obfuscated) that are computable by general branching programs. Our constructions are secure under LWE with subexponential approximation factors. Previous constructions of this kind crucially rely on the permutation structure of the underlying branching programs. Using general branching programs allows us to obtain more efficient constructions for certain classes of constraints (resp. functions), while posing new challenges in the proof, which we overcome using new proof techniques.Attacks. We extend the previous attacks on indistinguishability obfuscation (iO) candidates that use GGH15 encodings. The new attack simply uses the rank of a matrix as the distinguisher, so we call it a “rank attack”. The rank attack breaks, among others, the iO candidate for general read-once branching programs by Halevi, Halevi, Shoup and Stephens-Davidowitz (CCS 2017).Candidate Witness Encryption and iO. Drawing upon insights from our proofs and attacks, we present simple candidates for witness encryption and iO that resist the existing attacks, using GGH15 encodings. Our candidate for witness encryption crucially exploits the fact that formulas in conjunctive normal form (CNFs) can be represented by general, read-once branching programs.

2018

TCC

Traitor-Tracing from LWE Made Simple and Attribute-Based
Abstract

A traitor tracing scheme is a public key encryption scheme for which there are many secret decryption keys. Any of these keys can decrypt a ciphertext; moreover, even if a coalition of users collude, put together their decryption keys and attempt to create a new decryption key, there is an efficient algorithm to trace the new key to at least one the colluders.Recently, Goyal, Koppula and Waters (GKW, STOC 18) provided the first traitor tracing scheme from LWE with ciphertext and secret key sizes that grow polynomially in $$\log n$$, where n is the number of users. The main technical building block in their construction is a strengthening of (bounded collusion secure) secret-key functional encryption which they refer to as mixed functional encryption (FE).In this work, we improve upon and extend the GKW traitor tracing scheme:We provide simpler constructions of mixed FE schemes based on the LWE assumption. Our constructions improve upon the GKW construction in terms of expressiveness, modularity, and security.We provide a construction of attribute-based traitor tracing for all circuits based on the LWE assumption.

2018

ASIACRYPT

Improved Inner-Product Encryption with Adaptive Security and Full Attribute-Hiding
Abstract

In this work, we propose two IPE schemes achieving both adaptive security and full attribute-hiding in the prime-order bilinear group, which improve upon the unique existing result satisfying both features from Okamoto and Takashima [Eurocrypt ’12] in terms of efficiency.
Our first IPE scheme is based on the standard $$k\textsc {-lin}$$ assumption and has shorter master public key and shorter secret keys than Okamoto and Takashima’s IPE under weaker $${\textsc {dlin} }=2\textsc {-lin}$$ assumption.Our second IPE scheme is adapted from the first one; the security is based on the $${\textsc {xdlin}}$$ assumption (as Okamoto and Takashima’s IPE) but now it also enjoys shorter ciphertexts.
Technically, instead of starting from composite-order IPE and applying existing transformation, we start from an IPE scheme in a very restricted setting but already in the prime-order group, and then gradually upgrade it to our full-fledged IPE scheme. This method allows us to integrate Chen et al.’s framework [Eurocrypt ’15] with recent new techniques [TCC ’17, Eurocrypt ’18] in an optimized way.

2015

CRYPTO

2013

EUROCRYPT

2008

TCC

#### Program Committees

- PKC 2021
- Asiacrypt 2019
- Crypto 2018
- TCC 2018
- PKC 2017
- TCC 2017
- PKC 2014
- TCC 2013
- Asiacrypt 2013
- PKC 2013
- Crypto 2011
- Asiacrypt 2011
- Asiacrypt 2010
- Crypto 2010
- TCC 2008

#### Coauthors

- Michel Abdalla (2)
- Shweta Agrawal (2)
- Akshima (1)
- Fabrice Benhamouda (1)
- Ward Beullens (1)
- Florian Bourse (1)
- Xavier Boyen (1)
- Zvika Brakerski (2)
- Ran Canetti (2)
- David Cash (2)
- Shuchi Chawla (1)
- Jie Chen (4)
- Yilei Chen (3)
- Seung Geol Choi (5)
- Valerio Cini (1)
- Geoffroy Couteau (1)
- Dana Dachman-Soled (5)
- Lalita Devadas (1)
- Fangqi Dong (1)
- Andrew Drucker (1)
- Cynthia Dwork (2)
- Serge Fehr (1)
- Juan A. Garay (1)
- Romain Gay (5)
- Junqing Gong (6)
- Sergey Gorbunov (3)
- S. Dov Gordon (1)
- Iftach Haitner (1)
- Zihan Hao (1)
- Carmit Hazay (2)
- Minki Hhan (1)
- Dennis Hofheinz (2)
- Thomas Holenstein (1)
- Yuval Ishai (1)
- Jonathan Katz (1)
- Iordanis Kerenidis (1)
- Eike Kiltz (4)
- Dimitris Kolonelos (1)
- Lucas Kowalczyk (3)
- Hugo Krawczyk (1)
- Ranjit Kumaresan (1)
- Benoît Libert (1)
- Henry Lin (1)
- Huijia Lin (1)
- Tianren Liu (3)
- Adriana López-Alt (2)
- Ji Luo (1)
- Giulio Malavolta (2)
- Tal Malkin (5)
- Frank McSherry (1)
- Pierrick Méaux (1)
- Michele Minelli (1)
- Ethan Mook (1)
- Moni Naor (1)
- Ngoc Khanh Nguyen (1)
- Jiaxin Pan (1)
- Rafael Pass (2)
- Alain Passelègue (1)
- Kenneth G. Paterson (1)
- Rafaël Del Pino (1)
- David Pointcheval (1)
- Willy Quach (1)
- Mariana Raykova (1)
- Omer Reingold (1)
- Ronald L. Rivest (1)
- Mike Rosulek (1)
- Adam Smith (1)
- Madhu Sudan (1)
- Luca Trevisan (2)
- Rotem Tsabary (2)
- Salil P. Vadhan (2)
- Vinod Vaikuntanathan (13)
- Panagiotis Voulgaris (1)
- Brent Waters (3)
- Hoeteck Wee (80)
- Daniel Wichs (7)
- David J. Wu (5)
- Hong-Sheng Zhou (1)