Facoltà di scienze informatiche

Lattice-based protocols for privacy

Boschini, Cecilia ; Wolf, Stefan (Dir.) ; Camenisch, Jan (Codir.)

Thèse de doctorat : Università della Svizzera italiana, 2020 ; 2020INFO002.

Privacy and control over data have become a public concern. Simultaneously, the increasing likelihood of the construction of a general purpose quantum computer has led companies and governments to demand for quantum safe alternatives to the protocols used today. New schemes have been elaborated, whose conjectured security against a quantum computer relies on the hardness to solve different... More

Add to personal list
    Summary
    Privacy and control over data have become a public concern. Simultaneously, the increasing likelihood of the construction of a general purpose quantum computer has led companies and governments to demand for quantum safe alternatives to the protocols used today. New schemes have been elaborated, whose conjectured security against a quantum computer relies on the hardness to solve different mathematical problems, such as problems defined over lattices. However, while quantum-safe alternatives are known, they tend to output tokens whose size is too large to be considered practical. The goal of this dissertation is to address these concerns by building privacy-preserving signatures whose security is based on the hardness of solving some problems over ideal lattices, and whose token sizes are an improvement over the state of the art. Our first result is a toolbox of primitives (signatures, commitment and NIZK proofs) that are composable and allow building privacy-preserving protocols, such as Anonymous Attribute Tokens. The core building block are non-interactive zero-knowledge proofs with relaxed extractability that we obtained extending the construction in [Lyubashevsky, 2012]. In a second work, we combine them with a verifiable encryption scheme to construct a group signature whose keys and signatures require less that 2MB of storage. Finally, we give efficient statistical zero-knowledge proofs (SNARKs) for Module/Ring LWE and Module/Ring SIS relations, providing the remaining ingredient for building efficient cryptographic protocols from lattice-based hardness assumptions. We apply our approach to the example use case of partially dynamic group signatures and obtain a lattice-based group signature that protects users against corrupted issuers, and that produces signatures smaller than the state of the art. The results contained in this dissertation were published at international conferences.