## CryptoDB

### Tancrède Lepoint

#### Affiliation: Google

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

New Techniques for Obfuscating Conjunctions
📺
Abstract

A conjunction is a function $$f(x_1,\dots ,x_n) = \bigwedge _{i \in S} l_i$$ where $$S \subseteq [n]$$ and each $$l_i$$ is $$x_i$$ or $$\lnot x_i$$. Bishop et al. (CRYPTO 2018) recently proposed obfuscating conjunctions by embedding them in the error positions of a noisy Reed-Solomon codeword and placing the codeword in a group exponent. They prove distributional virtual black box (VBB) security in the generic group model for random conjunctions where $$|S| \ge 0.226n$$. While conjunction obfuscation is known from LWE [31, 47], these constructions rely on substantial technical machinery.In this work, we conduct an extensive study of simple conjunction obfuscation techniques.
We abstract the Bishop et al. scheme to obtain an equivalent yet more efficient “dual” scheme that can handle conjunctions over exponential size alphabets. This scheme admits a straightforward proof of generic group security, which we combine with a novel combinatorial argument to obtain distributional VBB security for |S| of any size.If we replace the Reed-Solomon code with a random binary linear code, we can prove security from standard LPN and avoid encoding in a group. This addresses an open problem posed by Bishop et al. to prove security of this simple approach in the standard model.We give a new construction that achieves information theoretic distributional VBB security and weak functionality preservation for $$|S| \ge n - n^\delta $$ and $$\delta < 1$$. Assuming discrete log and $$\delta < 1/2$$, we satisfy a stronger notion of functionality preservation for computationally bounded adversaries while still achieving information theoretic security.

2019

ASIACRYPT

Public-Key Function-Private Hidden Vector Encryption (and More)
Abstract

We construct public-key function-private predicate encryption for the “small superset functionality,” recently introduced by Beullens and Wee (PKC 2019). This functionality captures several important classes of predicates:Point functions. For point function predicates, our construction is equivalent to public-key function-private anonymous identity-based encryption.Conjunctions. If the predicate computes a conjunction, our construction is a public-key function-private hidden vector encryption scheme. This addresses an open problem posed by Boneh, Raghunathan, and Segev (ASIACRYPT 2013).d-CNFs and read-once conjunctions of d-disjunctions for constant-size d.
Our construction extends the group-based obfuscation schemes of Bishop et al. (CRYPTO 2018), Beullens and Wee (PKC 2019), and Bartusek et al. (EUROCRYPT 2019) to the setting of public-key function-private predicate encryption. We achieve an average-case notion of function privacy, which guarantees that a decryption key
$$\mathsf {sk} _f$$
reveals nothing about f as long as f is drawn from a distribution with sufficient entropy. We formalize this security notion as a generalization of the (enhanced) real-or-random function privacy definition of Boneh, Raghunathan, and Segev (CRYPTO 2013). Our construction relies on bilinear groups, and we prove security in the generic bilinear group model.

2018

TCHES

CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
Abstract

In this paper, we present the lattice-based signature scheme Dilithium, which is a component of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite that was submitted to NIST’s call for post-quantum cryptographic standards. The design of the scheme avoids all uses of discrete Gaussian sampling and is easily implementable in constant-time. For the same security levels, our scheme has a public key that is 2.5X smaller than the previously most efficient lattice-based schemes that did not use Gaussians, while having essentially the same signature size. In addition to the new design, we significantly improve the running time of the main component of many lattice-based constructions – the number theoretic transform. Our AVX2-based implementation results in a speed-up of roughly a factor of 2 over the previously best algorithms that appear in the literature. The techniques for obtaining this speed-up also have applications to other lattice-based schemes.

2015

ASIACRYPT

#### Program Committees

- Eurocrypt 2020
- CHES 2020
- PKC 2019
- Crypto 2018
- CHES 2018
- Eurocrypt 2017
- CHES 2017
- CHES 2016

#### Coauthors

- Shi Bai (3)
- James Bartusek (2)
- Daniel Benarroch (1)
- Zvika Brakerski (2)
- Anne Canteaut (3)
- Brent Carmer (1)
- Sergiu Carpov (3)
- Jung Hee Cheon (1)
- Jean-Sébastien Coron (10)
- Léo Ducas (2)
- Alain Durmus (1)
- Caroline Fontaine (3)
- Pierre-Alain Fouque (1)
- Craig Gentry (3)
- Shai Halevi (3)
- Abhishek Jain (1)
- Zhengzhong Jin (1)
- Eike Kiltz (1)
- Jinsu Kim (1)
- Adeline Langlois (2)
- Moon Sung Lee (4)
- Vadim Lyubashevsky (2)
- Fermi Ma (2)
- Hemanta K. Maji (2)
- Tal Malkin (1)
- Alex J. Malozemoff (1)
- Eric Miles (2)
- Michael Naehrig (1)
- María Naya-Plasencia (3)
- Pascal Paillier (3)
- Mariana Raykova (3)
- Adeline Roux-Langlois (1)
- Amit Sahai (3)
- Amin Sakzad (1)
- Peter Schwabe (1)
- Gregor Seiler (1)
- Renaud Sirdey (3)
- Damien Stehlé (4)
- Ron Steinfeld (3)
- Mehdi Tibouchi (13)
- Aaram Yun (1)
- Mark Zhandry (1)