Zur Kurzanzeige

dc.contributor.author
Nguyen, Ngoc Khanh
dc.contributor.supervisor
Hofheinz, Dennis
dc.contributor.supervisor
Lyubashevsky, Vadim
dc.contributor.supervisor
Steinfeld, Ron
dc.date.accessioned
2022-10-10T07:16:06Z
dc.date.available
2022-10-09T16:04:45Z
dc.date.available
2022-10-10T07:16:06Z
dc.date.issued
2022
dc.identifier.uri
http://hdl.handle.net/20.500.11850/574844
dc.identifier.doi
10.3929/ethz-b-000574844
dc.description.abstract
In preparation for the eventual arrival of quantum computers, there has been a significant amount of work to construct quantum-safe cryptographic primitives, as evidenced by the ongoing NIST PQC Standardization. To ensure post-quantum security, the underlying public-key schemes have to be built based on quantum-safe computational hardness assumptions. In this regard, lattice-based primitives appear to be a leading choice. Indeed, the currently most efficient, in terms of size and speed, quantum-safe basic primitives (e.g. signatures and encryption schemes) are based on the hardness of lattice problems with algebraic structure such as Module-SIS and Module-LWE. As a natural next step, lattice-based cryptography can be thus applied to build more advanced primitives such as zero-knowledge arguments. In this thesis, we present $\mathsf{Lantern}$, a new lattice-based zero-knowledge protocol with short proofs based on the hardness of Module-SIS and Module-LWE problems. In particular, our framework is suitable for proving lattice-related statements, e.g. proving knowledge of a short vector $\vec s$ satisfying $A\vec s=\vec t\bmod q$. At the core of our constructions lies a more direct and more efficient way to prove that $\vec s$ has a small Euclidean norm which, unlike in prior works, does not require proving explicitly that each coefficient of $\vec s$ is small, nor any conversion to the CRT representation. Instead, we use the observation that the inner product $\langle \vec{r},\vec{s} \rangle$ between any two vectors $\vec r$ and $\vec s$ can be made to appear as a constant coefficient of a product (or sum of products) between polynomials which are functions of $\vec r$ and $\vec s$. Therefore, by using a polynomial product proof system and hiding all but the constant coefficient, we are able to prove knowledge of the inner product of two vectors (or of a vector with itself) modulo $q$. Using a cheap ``approximate range proof'', we can then lift the proof to be over $\mathbb{Z}$ instead of $\mathbb{Z}_q$. Performance-wise, our framework produces proofs of size $13$KB for basic statements which are $2-3$X smaller than prior works. Furthermore, the new proof system can be plugged into constructions of various lattice-based privacy-oriented primitives in a black-box manner. As examples, we instantiate a verifiable encryption scheme as well as ring and group signatures which are significantly more compact than previously the best solutions.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
Lattice-based cryptography
en_US
dc.subject
zero-knowledge proofs
en_US
dc.title
Lattice-Based Zero-Knowledge Proofs Under a Few Dozen Kilobytes
en_US
dc.type
Doctoral Thesis
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2022-10-10
ethz.size
229 p.
en_US
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.identifier.diss
28574
en_US
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09693 - Hofheinz, Dennis / Hofheinz, Dennis
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09693 - Hofheinz, Dennis / Hofheinz, Dennis
en_US
ethz.tag
Cryptography
en_US
ethz.date.deposited
2022-10-09T16:04:45Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2022-10-10T07:16:07Z
ethz.rosetta.lastUpdated
2023-02-07T06:59:39Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Lattice-Based%20Zero-Knowledge%20Proofs%20Under%20a%20Few%20Dozen%20Kilobytes&rft.date=2022&rft.au=Nguyen,%20Ngoc%20Khanh&rft.genre=unknown&rft.btitle=Lattice-Based%20Zero-Knowledge%20Proofs%20Under%20a%20Few%20Dozen%20Kilobytes
 Printexemplar via ETH-Bibliothek suchen

Dateien zu diesem Eintrag

Thumbnail

Publikationstyp

Zur Kurzanzeige