TY - GEN
T1 - Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions
AU - Libert, Benoît
AU - Ling, San
AU - Mouhartem, Fabrice
AU - Nguyen, Khoa
AU - Wang, Huaxiong
PY - 2016
Y1 - 2016
N2 - A recent line of works – initiated by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010) – gave lattice-based constructions allowing users to authenticate while remaining hidden in a crowd. Despite five years of efforts, known constructions are still limited to static sets of users, which cannot be dynamically updated. This work provides new tools enabling the design of anonymous authentication systems whereby new users can join the system at any time. Our first contribution is a signature scheme with efficient protocols, which allows users to obtain a signature on a committed value and subsequently prove knowledge of a signature on a committed message. This construction is well-suited to the design of anonymous credentials and group signatures. It indeed provides the first lattice-based group signature supporting dynamically growing populations of users. As a critical component of our group signature, we provide a simple joining mechanism of introducing new group members using our signature scheme. This technique is combined with zero-knowledge arguments allowing registered group members to prove knowledge of a secret short vector of which the corresponding public syndrome was certified by the group manager. These tools provide similar advantages to those of structure-preserving signatures in the realm of bilinear groups. Namely, they allow group members to generate their own public key without having to prove knowledge of the underlying secret key. This results in a two-message joining protocol supporting concurrent enrollments, which can be used in other settings such as group encryption. Our zero-knowledge arguments are presented in a unified framework where: (i) The involved statements reduce to arguing possession of a {−1, 0, 1}-vector x with a particular structure and satisfying P · x = v mod q for some public matrix P and vector v; (ii) The reduced statements can be handled using permuting techniques for Stern-like protocols. Our framework can serve as a blueprint for proving many other relations in lattice-based cryptography.
AB - A recent line of works – initiated by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010) – gave lattice-based constructions allowing users to authenticate while remaining hidden in a crowd. Despite five years of efforts, known constructions are still limited to static sets of users, which cannot be dynamically updated. This work provides new tools enabling the design of anonymous authentication systems whereby new users can join the system at any time. Our first contribution is a signature scheme with efficient protocols, which allows users to obtain a signature on a committed value and subsequently prove knowledge of a signature on a committed message. This construction is well-suited to the design of anonymous credentials and group signatures. It indeed provides the first lattice-based group signature supporting dynamically growing populations of users. As a critical component of our group signature, we provide a simple joining mechanism of introducing new group members using our signature scheme. This technique is combined with zero-knowledge arguments allowing registered group members to prove knowledge of a secret short vector of which the corresponding public syndrome was certified by the group manager. These tools provide similar advantages to those of structure-preserving signatures in the realm of bilinear groups. Namely, they allow group members to generate their own public key without having to prove knowledge of the underlying secret key. This results in a two-message joining protocol supporting concurrent enrollments, which can be used in other settings such as group encryption. Our zero-knowledge arguments are presented in a unified framework where: (i) The involved statements reduce to arguing possession of a {−1, 0, 1}-vector x with a particular structure and satisfying P · x = v mod q for some public matrix P and vector v; (ii) The reduced statements can be handled using permuting techniques for Stern-like protocols. Our framework can serve as a blueprint for proving many other relations in lattice-based cryptography.
KW - lattice-based cryptography
KW - anonymity
KW - signatures with efficient protocols
KW - dynamic group signatures
KW - anonymous credentials
UR - http://www.scopus.com/inward/record.url?scp=85008156746&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-53890-6_13
DO - 10.1007/978-3-662-53890-6_13
M3 - Conference proceeding contribution
AN - SCOPUS:85008156746
SN - 9783662538890
T3 - Lecture Notes in Computer Science
SP - 373
EP - 403
BT - Advances in cryptology - ASIACRYPT 2016
A2 - Cheon, Jung Hee
A2 - Takagi, Tsuyoshi
PB - Springer, Springer Nature
CY - Berlin
T2 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016
Y2 - 4 December 2016 through 8 December 2016
ER -