## 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. ## 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
BibTeX:
@inproceedings{KW18, author = {Sam Kim and David J. Wu}, title = {Multi-Theorem Preprocessing {NIZKs} from Lattices}, booktitle = {{CRYPTO}}, year = {2018} } ## 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
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} } ## 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.
BibTeX:
@inproceedings{KW17, author = {Sam Kim and David J. Wu}, title = {Watermarking Cryptographic Functionalities from Standard Lattice Assumptions}, booktitle = {{CRYPTO}}, year = {2017} } ## 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
BibTeX:
@inproceedings{KW19, author = {Sam Kim and David J. Wu}, title = {Watermarking {PRFs} from Lattices: Stronger Security via Extractable {PRFs}}, booktitle = {{CRYPTO}}, year = {2019} } |