# Lattice-Based Cryptography

Lattice-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

Contributors: Samir Jordan Menon and David J. Wu

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 simultaneously achieves at least a 4.5x reduction in query size, 1.5x reduction in response size, and 2x increase in server throughput compared to previous systems. A variant of our scheme, SpiralStreamPack, is optimized for the streaming setting and achieves a server throughput of 1.9 GB/s for databases with over a million records (compared to 200 MB/s for previous protocols) and a rate of 0.81 (compared to 0.24 for previous protocols). For streaming large records (e.g., a private video stream), we estimate the monetary cost of SpiralStreamPack to be only 1.9x greater than that of the no-privacy baseline where the client directly downloads the desired record.

Resources:

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

Contributors: Sam Kim and David J. Wu

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 lattice assumptions. While there has been partial progress in realizing NIZKs from lattices for specific languages, constructing NIZK proofs (and arguments) for all of NP from standard lattice assumptions remains open.

In this work, we make progress on this problem by giving the first construction of a multi-theorem NIZK for NP from standard lattice assumptions in the preprocessing model. In the preprocessing model, a (trusted) setup algorithm generates proving and verification keys. The proving key is needed to construct proofs and the verification key is needed to check proofs. In the multi-theorem setting, the proving and verification keys should be reusable for an unbounded number of theorems without compromising soundness or zero- knowledge. Existing constructions of NIZKs in the preprocessing model (or even the designated-verifier model) that rely on weaker assumptions like one-way functions or oblivious transfer are only secure in a single-theorem setting. Thus, constructing multi-theorem NIZKs in the preprocessing model does not seem to be inherently easier than constructing them in the CRS model.

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 blind homomorphic signatures. This primitive may be of independent interest. Finally, we show how to leverage our new lattice-based preprocessing NIZKs to obtain new malicious-secure MPC protocols purely from standard lattice assumptions.

Resources:

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

Contributors: Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu

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 2100. In this work, we show that an ideal obfuscation of both the decryption function in a fully homomorphic encryption scheme and a variant of the verification algorithm of our new lattice-based SNARG yields a general-purpose obfuscator for all circuits. Finally, we give some concrete estimates needed to obfuscate this “obfuscation-complete” primitive. We estimate that at 80-bits of security, a (black-box) multilinear map with ≈212 levels of multilinearity suffices. This is over 280 times more efficient than existing candidates, and thus, represents an important milestone towards implementable program obfuscation for all circuits.

Resources:

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

Contributors: Yuval Ishai, Hang Su, and David J. Wu

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 post-quantum zkSNARKs, with a focus on minimizing proof size. Currently, there is a $$1000\times$$ gap in the proof size between the best pre-quantum constructions and the best post-quantum ones. Here, we develop and implement new lattice-based zkSNARKs in the designated-verifier preprocessing model. With our construction, after an initial preprocessing step, a proof for an $$\mathsf{NP}$$ relation of size $$2^{20}$$ is just over 16 KB. Our proofs are $$10.3\times$$ shorter than previous post-quantum zkSNARKs for general $$\mathsf{NP}$$ languages. Compared to previous lattice-based zkSNARKs (also in the designated-verifier preprocessing model), we obtain a $$42\times$$ reduction in proof size and a $$60\times$$ reduction in the prover's running time, all while achieving a much higher level of soundness. Compared to the shortest pre-quantum zkSNARKs by Groth (Eurocrypt 2016), the proof size in our lattice-based construction is $$131\times$$ longer, but both the prover and the verifier are faster (by $$1.2\times$$ and $$2.8\times$$, respectively).

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.

Resources:

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

Contributors: Sam Kim and David J. Wu

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.

Resources:

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

Contributors: Sam Kim and David J. Wu

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 unmarked keys).

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 nearly polynomial approximations to worst-case lattice problems. This is a qualitatively weaker assumption than that needed for existing lattice-based constructions of watermarking (that support message-embedding), all of which require quasi-polynomial approximation factors. Our constructions rely on a new cryptographic primitive called an extractable PRF, which may be of independent interest.

Resources:

BibTeX:
@inproceedings{KW19,
author     = {Sam Kim and David J. Wu},
title      = {Watermarking {PRFs} from Lattices: Stronger Security via Extractable {PRFs}},
booktitle  = {{CRYPTO}},
year       = {2019}
}