Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption

Benoît Libert*, San Ling, Fabrice Mouhartem, Khoa Nguyen, Huaxiong Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

18 Citations (Scopus)

Abstract

Group encryption (GE) is the natural encryption analogue of group signatures in that it allows verifiably encrypting messages for some anonymous member of a group while providing evidence that the receiver is a properly certified group member. Should the need arise, an opening authority is capable of identifying the receiver of any ciphertext. As introduced by Kiayias, Tsiounis and Yung (Asiacrypt’07), GE is motivated by applications in the context of oblivious retriever storage systems, anonymous third parties and hierarchical group signatures. This paper provides the first realization of group encryption under lattice assumptions. Our construction is proved secure in the standard model (assuming interaction in the proving phase) under the Learning-With-Errors (LWE) and Short-Integer-Solution (SIS) assumptions. As a crucial component of our system, we describe a new zero-knowledge argument system allowing to demonstrate that a given ciphertext is a valid encryption under some hidden but certified public key, which incurs to prove quadratic statements about LWE relations. Specifically, our protocol allows arguing knowledge of witnesses consisting of X ∈ ℤqm×n, s ∈ ℤnq and a small-norm e ∈ ℤm which underlie a public vector b = X · s + e ∈ ℤmq while simultaneously proving that the matrix X ∈ ℤm×nq has been correctly certified. We believe our proof system to be useful in other applications involving zero-knowledge proofs in the lattice setting.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2016
Subtitle of host publication22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4 - 8, 2016, proceedings
EditorsJung Hee Cheon, Tsuyoshi Takagi
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages101-131
Number of pages31
ISBN (Electronic)9783662538906
ISBN (Print)9783662538890
DOIs
Publication statusPublished - 2016
Externally publishedYes
Event22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016 - Hanoi, Viet Nam
Duration: 4 Dec 20168 Dec 2016

Publication series

NameLecture Notes in Computer Science
Volume10032 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016
CountryViet Nam
CityHanoi
Period4/12/168/12/16

Keywords

  • lattices
  • zero-knowledge proofs
  • group encryption
  • anonymity

Fingerprint Dive into the research topics of 'Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption'. Together they form a unique fingerprint.

  • Cite this

    Libert, B., Ling, S., Mouhartem, F., Nguyen, K., & Wang, H. (2016). Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption. In J. H. Cheon, & T. Takagi (Eds.), Advances in Cryptology - ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4 - 8, 2016, proceedings (pp. 101-131). (Lecture Notes in Computer Science; Vol. 10032 LNCS). Berlin: Springer, Springer Nature. https://doi.org/10.1007/978-3-662-53890-6_4