Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/90155
Title: Group signatures with advanced features and lattices
Authors: Xu, Yanhong
Keywords: DRNTU::Science::Mathematics::Discrete mathematics::Cryptography
Issue Date: 31-Dec-2018
Source: Xu, Y. (2018). Group signatures with advanced features and lattices. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: Building cryptographic schemes only on the number-theoretic assumptions such as the hardness of factoring or computing discrete logarithms seems to put us at the risk of the emerging technologies such as the quantum computers. Therefore it is better to design cryptographic schemes based on as many fundamentally different hardness problems as possible. Many lattice problems, such as finding the shortest non-zero vector problem, seem to withstand the quantum adversaries. Furthermore, the worst-case/average-case reduction discovered by Ajtai (STOC 1996) makes lattice-based cryptography outstanding among other fields of cryptography; instead of assuming the hardness of a random instance, it suffices for lattice-based cryptosystems to assume the hardness of lattice problems in the worst case. Recently, lattice-based cryptography has witnessed a great improvement with many remarkable results such as realization of fully homomorphic encryption by Gentry (STOC 2009). In this thesis, we are particularly interested in lattice-based group signatures. Since the pioneering work by Gordon, Katz, and Vaikuntanathan (Asiacrypt 2010), many other schemes have been suggested. In contrast to their counterparts that are based on number-theoretic assumptions, however, lattice-based group signatures are not fully developed. In particular, most of the existing proposals are designed for static groups and there are only three of them with some advanced features/functionalities, which are motivated by special needs of applications. The three exceptions are the schemes proposed by Langlois et al. (PKC 2014) that is motivated by the desire to revoke some misbehaving/leaving users, by Libert et al. (Asiacrypt 2016) that is designed to admit new users, and by Libert et al. (ACNS 2016) that is driven by the need to open all signatures related to a specific message. Observing the fact that the ordinary group signatures are often not enough for specific requirements of real-life applications, in this thesis, we construct several lattice-based group signature schemes with different functionalities that can find applications in different situations. Specifically, we design the following lattice-based group signatures with some advanced features. (1) We construct the first lattice-based group signature scheme that achieves full dynamicity, where users are able to join and leave the group at any time. Prior to our work, this feature is only achieved from number-theoretic assumptions. In this thesis, we thus solve a prominent open question posed by previous works. In addition, we achieve this non-trivial feat in a relatively simple manner. (2) Incorporating a new property - deniability - into the above scheme, we obtain a lattice-based fully dynamic group signature scheme with deniability. Group signature with deniability was first introduced by Ishida et al. (CANS 2016), motivated by a situation where we are more interested in whether a suspect generated a specific signature. In the case the signature was not generated by the suspect, we should be able to generate an evidence showing that this suspect did not produce that signature without revealing the actual signer, thus serving as a way to protect the privacy of the real signer. (3) We construct the first lattice-based group signature scheme that features constant-size signatures, which means that the size of the group signatures is independent of the group size N. In particular, all the parameters in our scheme do not depend on N. This result is appealing to applications in which group size is too large. (4) We design the first lattice-based forward-secure group signature scheme. Forward-security was put forward by Anderson (Technical report 2002) to minimize the damage caused by the key exposure problem. It preserves the security of the scheme in previous time periods even when the keys are compromised at current time period. This feature is attractive to group signatures for the following reasons. Once a break in occurs, all prior signed signatures are rendered invalid since it is not clear how to distinguish signatures generated by honest users from those generated by malicious adversaries. In addition, a misbehaving user could repudiate his illegally signed signatures by exposing his secret key somewhere in the internet and then claiming to be the victim of the key exposure problem. What is worse, the damage escalates when the group size increases. However, these problems would not arise if the underlying group signature scheme is forward-secure. Thus group signature with forward-security is imperative in applications that are more susceptible to key exposure attacks. (5) We propose the first accountable tracing signatures from lattices. This notion was initially proposed by Kohlweiss et al. (PoPETs 2015) to ensure the accountability of the group manager. In all other group signatures, the group manager is granted too much power, i.e., he is able to open any signature and we do not have any mechanism to verify whether this trust is well placed. This would seriously violate the privacy of all group members. However, in an accountable tracing signature scheme, there is an "accounting'' mechanism to check the behaviour of the group manager and thus keeping him accountable.
URI: https://hdl.handle.net/10356/90155
http://hdl.handle.net/10220/47353
DOI: https://doi.org/10.32657/10220/47353
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
thesis-softcopy.pdf1.72 MBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.