## Lattice-Based CryptographyLattice-based cryptography is one of the leading candidates for post-quantum cryptography. A major focus of my work has been on constructing new cryptographic primitives such as zero-knowledge proof systems, watermarking, and more, from standard lattice assumptions. ## Spiral: Fast, High-Rate Single-Server PIR via FHE Composition
Abstract:
We introduce the Spiral family of single-server private information
retrieval (PIR) protocols. Spiral relies on a composition of two
lattice-based homomorphic encryption schemes: the Regev encryption scheme and
the Gentry-Sahai-Waters encryption scheme. We introduce new ciphertext
translation techniques to convert between these two schemes and in doing so,
enable new trade-offs in communication and computation. Across a broad range
of database configurations, the basic version of Spiral
**Paper:**[PDF], [ePrint Version]**Code:**[Github]
BibTeX:
@inproceedings{MW22, author = {Samir Jordan Menon and David J. Wu}, title = {\textsc{Spiral}: Fast, High-Rate Single-Server {PIR} via {FHE} Composition}, booktitle = {{IEEE} {S\&P}}, year = {2022} } ## Multi-Theorem Preprocessing NIZKs from Lattices
Abstract:
Non-interactive zero-knowledge (NIZK) proofs are fundamental to modern
cryptography. Numerous NIZK constructions are known in both the random oracle
and the common reference string (CRS) models. In the CRS model, there exist
constructions from several classes of cryptographic assumptions such as
trapdoor permutations, pairings, and indistinguishability obfuscation. Notably
absent from this list, however, are constructions from standard In this work, we make progress on this problem by giving the first
construction of a We begin by constructing a multi-theorem preprocessing NIZK directly from
context-hiding homomorphic signatures. Then, we show how to efficiently
implement the preprocessing step using a new cryptographic primitive called
**Paper:**[PDF], [Journal Version], [ePrint Version]
BibTeX (Conference):
@inproceedings{KW18, author = {Sam Kim and David J. Wu}, title = {Multi-Theorem Preprocessing {NIZKs} from Lattices}, booktitle = {{CRYPTO}}, year = {2018} } BibTeX (Journal):
@article{KW20, author = {Sam Kim and David J. Wu}, title = {Multi-Theorem Preprocessing {NIZKs} from Lattices}, journal = {J. Cryptology}, volume = {33}, number = {3}, pages = {619--702}, year = {2020} } ## Lattice-Based SNARGs and Their Application to More Efficient Obfuscation
Abstract:
Succinct non-interactive arguments (SNARGs) enable verifying NP computations with substantially lower complexity than that required for classical NP verification. In this work, we first construct a lattice-based SNARG candidate with quasi-optimal succinctness (where the argument size is quasilinear in the security parameter). Further extension of our methods yields the first SNARG (from any assumption) that is quasi-optimal in terms of both prover overhead (polylogarithmic in the security parameter) as well as succinctness. Moreover, because our constructions are lattice-based, they plausibly resist quantum attacks. Central to our construction is a new notion of linear-only vector encryption which is a generalization of the notion of linear-only encryption introduced by Bitansky et al. (TCC 2013). We conjecture that variants of Regev encryption satisfy our new linear-only definition. Then, together with new information-theoretic approaches for building statistically-sound linear PCPs over small finite fields, we obtain the first quasi-optimal SNARGs. We then show a surprising connection between our new lattice-based SNARGs and
the concrete efficiency of program obfuscation. All existing obfuscation
candidates currently rely on multilinear maps. Among the constructions that
make black-box use of the multilinear map, obfuscating a circuit of even
moderate depth (say, 100) requires a multilinear map with multilinearity
degree in excess of 2
**Paper:**[PDF], [ePrint Version]**Talk:**[Video]
BibTeX:
@inproceedings{BISW17, author = {Dan Boneh and Yuval Ishai and Amit Sahai and David J. Wu}, title = {Lattice-Based {SNARGs} and Their Application to More Efficient Obfuscation}, booktitle = {{EUROCRYPT}}, year = {2017} } ## Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices
Abstract:
Zero-knowledge succinct arguments of knowledge (zkSNARKs) enable efficient
privacy-preserving proofs of membership for general \( \mathsf{NP} \) languages.
Our focus in this work is on Our construction follows the general blueprint of Bitansky et al. (TCC 2013) and Boneh et al. (Eurocrypt 2017) of combining a linear probabilistically checkable proof (linear PCP) together with a linear-only vector encryption scheme. We develop a concretely-efficient lattice-based instantiation of this compiler by considering quadratic extension fields of moderate characteristic and using linear-only vector encryption over rank-2 module lattices.
**Paper:**[PDF], [ePrint Version]**Code:**[Github]
BibTeX:
@inproceedings{ISW21, author = {Yuval Ishai and Hang Su and David J. Wu}, title = {Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices}, booktitle = {ACM Conference on Computer and Communications Security ({ACM} {CCS})}, year = {2021} } ## Watermarking Cryptographic Functionalities from Standard Lattice Assumptions
Abstract:
A software watermarking scheme allows one to embed a “mark” into a program without significantly altering the behavior of the program. Moreover, it should be difficult to remove the watermark without destroying the functionality of the program. Recently, Cohen et al. (STOC 2016) and Boneh et al. (PKC 2017) showed how to watermark cryptographic functions such as PRFs using the full power of general-purpose indistinguishability obfuscation. Notably, in their constructions, the watermark remains intact even against arbitrary removal strategies. A natural question is whether we can build watermarking schemes from standard assumptions that achieve this strong mark-unremovability property. We give the first construction of a watermarkable family of PRFs that satisfy this strong mark-unremovability property from standard lattice assumptions (namely, the learning with errors (LWE) and the one-dimensional short integer solution (SIS) problems). As part of our construction, we introduce a new cryptographic primitive called a translucent PRF. Next, we give a concrete construction of a translucent PRF family from standard lattice assumptions. Finally, we show that using our new lattice-based translucent PRFs, we obtain the first watermarkable family of PRFs with strong unremovability against arbitrary strategies from standard assumptions.
**Paper:**[PDF], [Journal Version], [ePrint Version]
BibTeX (Conference):
@inproceedings{KW17, author = {Sam Kim and David J. Wu}, title = {Watermarking Cryptographic Functionalities from Standard Lattice Assumptions}, booktitle = {{CRYPTO}}, year = {2017} } BibTeX (Journal):
@article{KW21, author = {Sam Kim and David J. Wu}, title = {Watermarking Cryptographic Functionalities from Standard Lattice Assumptions}, journal = {J. Cryptology}, volume = {34}, number = {28}, pages = {1--76}, year = {2021} } ## Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs
Abstract:
A software watermarking scheme enables one to embed a “mark” (i.e., a message)
within a program while preserving the program's functionality. Moreover, there
is an extraction algorithm that recovers an embedded message from a program.
The main security goal is that it should be difficult to remove the watermark
without destroying the functionality of the program. Existing constructions of
watermarking focus on watermarking cryptographic functions like pseudorandom
functions (PRFs); even in this setting, realizing watermarking from standard
assumptions remains difficult. The first lattice-based construction of
secret-key watermarking due to Kim and Wu (CRYPTO 2017) only ensures
mark-unremovability against an adversary who does not have access to the
mark-extraction oracle. The construction of Quach et al. (TCC 2018) achieves
the stronger notion of mark-unremovability even if the adversary can make
extraction queries, but has the drawback that the watermarking authority (who
holds the watermarking secret key) can break pseudorandomness of all PRF keys
in the family (including In this work, we construct new lattice-based secret-key watermarking schemes
for PRFs that both provide unremovability against adversaries that have access
to the mark-extraction oracle and offer a strong and meaningful notion of
pseudorandomness even against the watermarking authority (i.e., the outputs of
unmarked keys are pseudorandom almost everywhere). Moreover, security of
several of our schemes can be based on the hardness of computing
**Paper:**[PDF], [ePrint Version]
BibTeX:
@inproceedings{KW19, author = {Sam Kim and David J. Wu}, title = {Watermarking {PRFs} from Lattices: Stronger Security via Extractable {PRFs}}, booktitle = {{CRYPTO}}, year = {2019} } |