## CryptoDB

### Hoeteck Wee

#### Publications

**Year**

**Venue**

**Title**

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

EPRINT

2015

CRYPTO

2013

EUROCRYPT

2010

EPRINT

Universal One-Way Hash Functions via Inaccessible Entropy
Abstract

This paper revisits the construction of Universally One-Way Hash Functions (UOWHFs) from any one-way function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs which also obtains better efficiency and security. The construction exploits a strong connection to the recently introduced notion of *inaccessible entropy* (Haitner et al. STOC 2009). With this perspective, we observe that a small tweak of any one-way function f is already a weak form of a UOWHF: Consider F(x, i) that outputs the i-bit long prefix of f(x). If F were a UOWHF then given a random x and i it would be hard to come up with x' \neq x such that F(x, i) = F(x', i). While this may not be the case, we show (rather easily) that it is hard to sample x' with almost full entropy among all the possible such values of x'. The rest of our
construction simply amplifies and exploits this basic property.
With this and other recent works we have that the constructions of three fundamental cryptographic primitives (Pseudorandom Generators, Statistically Hiding Commitments and UOWHFs) out of one-way functions are to a large extent unified. In particular, all three constructions rely on and manipulate computational notions of entropy in similar ways. Pseudorandom Generators rely on the well-established notion of pseudoentropy, whereas Statistically Hiding Commitments and UOWHFs rely on the newer notion of inaccessible entropy.

2008

TCC

2005

EPRINT

On Obfuscating Point Functions
Abstract

We study the problem of obfuscation in the context of point functions
(also known as delta functions). A point function is a Boolean
function that assumes the value 1 at exactly one point. Our main
results are as follows:
- We provide a simple construction of efficient obfuscators for
point functions for a slightly relaxed notion of obfuscation - wherein
the size of the simulator has an inverse polynomial dependency on the
distinguishing probability - which is nonetheless impossible for
general circuits. This is the first known construction of obfuscators
for a non-trivial family of functions under general computational
assumptions. Our obfuscator is based on a probabilistic hash function
constructed from a very strong one-way permutation, and does
not require any set-up assumptions. Our construction also yields
an obfuscator for point functions with multi-bit output.
- We show that such a strong one-way permutation - wherein any
polynomial-sized circuit inverts the permutation on at most a
polynomial number of inputs - can be realized using a random
permutation oracle. We prove the result by improving on the counting
argument used in [GT00]; this result may be of independent
interest. It follows that our construction yields obfuscators for
point functions in the non-programmable random permutation oracle
model (in the sense of [N02]). Furthermore, we prove that an
assumption like the one we used is necessary for our obfuscator
construction.
- Finally, we establish two impossibility results on obfuscating
point functions which indicate that the limitations on our
construction (in simulating only adversaries with single-bit output
and in using non-uniform advice in our simulator) are in some sense
inherent. The first of the two results is a consequence of a simple
characterization of functions that can be obfuscated against general
adversaries with multi-bit output as the class of functions that are
efficiently and exactly learnable using membership queries.
We stress that prior to this work, what is known about obfuscation are
negative results for the general class of circuits [BGI01] and
positive results in the random oracle model [LPS04] or under
non-standard number-theoretic assumptions [C97]. This work
represents the first effort to bridge the gap between the two for a
natural class of functionalities.

#### Program Committees

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

#### Coauthors

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