Wolf, Stefan Camenisch, Jan Boschini, Cecilia 2020-03-12 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. application/pdf https://n2t.net/ark:/12658/srd1319176 https://susi.usi.ch/global/documents/319176 https://susi.usi.ch/documents/319176/files/2020INFO002.pdf eng info:eu-repo/semantics/altIdentifier/urn/urn:nbn:ch:rero-006-121521 info:eu-repo/semantics/altIdentifier/ark/12658/srd1319176 info:eu-repo/semantics/openAccess License undefined Lattices Post-quantum schemes Group signatures NIZK proofs Relaxed cryptography Anonymous attribute tokens info:eu-repo/classification/udc/004 Lattice-based protocols for privacy http://purl.org/coar/resource_type/c_db06