Biblio

We present a group signature scheme, based on the hardness of lattice problems, whose outputs are more than an order of magnitude smaller than the currently most efficient schemes in the literature. Since lattice-based schemes are also usually non-trivial to efficiently implement, we additionally provide the first experimental implementation of lattice-based group signatures demonstrating that our construction is indeed practical – all operations take less than half a second on a standard laptop. A key component of our construction is a new zero-knowledge proof system for proving that a committed value belongs to a particular set of small size. The sets for which our proofs are applicable are exactly those that contain elements that remain stable under Galois automorphisms of the underlying cyclotomic number field of our lattice-based protocol. We believe that these proofs will find applications in other settings as well. The motivation of the new zero-knowledge proof in our construction is to allow the efficient use of the selectively-secure signature scheme (i.e. a signature scheme in which the adversary declares the forgery message before seeing the public key) of Agrawal et al. (Eurocrypt 2010) in constructions of lattice-based group signatures and other privacy protocols. For selectively-secure schemes to be meaningfully converted to standard signature schemes, it is crucial that the size of the message space is not too large. Using our zero-knowledge proofs, we can strategically pick small sets for which we can provide efficient zero-knowledge proofs of membership.

Funded under the European Union's Horizon 2020 research and innovation programme, SAFEcrypto will provide a new generation of practical, robust and physically secure post-quantum cryptographic solutions that ensure long-term security for future ICT systems, services and applications. The project will focus on the remarkably versatile field of Lattice-based cryptography as the source of computational hardness, and will deliver optimised public key security primitives for digital signatures and authentication, as well identity based encryption (IBE) and attribute based encryption (ABE). This will involve algorithmic and design optimisations, and implementations of lattice-based cryptographic schemes addressing cost, energy consumption, performance and physical robustness. As the National Institute of Standards and Technology (NIST) prepares for the transition to a post-quantum cryptographic suite B, urging organisations that build systems and infrastructures that require long-term security to consider this transition in architectural designs; the SAFEcrypto project will provide Proof-of-concept demonstrators of schemes for three practical real-world case studies with long-term security requirements, in the application areas of satellite communications, network security and cloud. The goal is to affirm Lattice-based cryptography as an effective replacement for traditional number-theoretic public-key cryptography, by demonstrating that it can address the needs of resource-constrained embedded applications, such as mobile and battery-operated devices, and of real-time high performance applications for cloud and network management infrastructures.