Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLattice-Based Group Signatures: Achieving Full Dynamicity (and Deniability) with Ease
84
0
0.0
(
0
)
Added by
Khoa Nguyen
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this work, we provide the first lattice-based group signature that offers full dynamicity (i.e., users have the flexibility in joining and leaving the group), and thus, resolve a prominent open problem posed by previous works. Moreover, we achieve this non-trivial feat in a relatively simple manner. Starting with Libert et al.s fully static construction (Eurocrypt 2016) - which is arguably the most efficient lattice-based group signature to date, we introduce simple-but-insightful tweaks that allow to upgrade it directly into the fully dynamic setting. More startlingly, our scheme even produces slightly shorter signatures than the former, thanks to an adaptation of a technique proposed by Ling et al. (PKC 2013), allowing to prove inequalities in zero-knowledge. Our design approach consists of upgrading Libert et al.s static construction (EUROCRYPT 2016) - which is arguably the most efficient lattice-based group signature to date - into the fully dynamic setting. Somewhat surprisingly, our scheme produces slightly shorter signatures than the former, thanks to a new technique for proving inequality in zero-knowledge without relying on any inequality check. The scheme satisfies the strong security requirements of Bootle et al.s model (ACNS 2016), under the Short Integer Solution (SIS) and the Learning With Errors (LWE) assumptions. Furthermore, we demonstrate how to equip the obtained group signature scheme with the deniability functionality in a simple way. This attractive functionality, put forward by Ishida et al. (CANS 2016), enables the tracing authority to provide an evidence that a given user is not the owner of a signature in question. In the process, we design a zero-knowledge protocol for proving that a given LWE ciphertext does not decrypt to a particular message.
rate research
Read More
Releasing full data records is one of the most challenging problems in data privacy. On the one hand, many of the popular techniques such as data de-identification are problematic because of their dependence on the background knowledge of adversaries. On the other hand, rigorous methods such as the exponential mechanism for differential privacy are often computationally impractical to use for releasing high dimensional data or cannot preserve high utility of original data due to their extensive data perturbation. This paper presents a criterion called plausible deniability that provides a formal privacy guarantee, notably for releasing sensitive datasets: an output record can be released only if a certain amount of input records are indistinguishable, up to a privacy parameter. This notion does not depend on the background knowledge of an adversary. Also, it can efficiently be checked by privacy tests. We present mechanisms to generate synthetic datasets with similar statistical properties to the input data and the same format. We study this technique both theoretically and experimentally. A key theoretical result shows that, with proper randomization, the plausible deniability mechanism generates differentially private synthetic data. We demonstrate the efficiency of this generative technique on a large dataset; it is shown to preserve the utility of original data with respect to various statistical analysis and machine learning measures.
Group signature is a fundamental cryptographic primitive, aiming to protect anonymity and ensure accountability of users. It allows group members to anonymously sign messages on behalf of the whole group, while incorporating a tracing mechanism to identify the signer of any suspected signature. Most of the existing group signature schemes, however, do not guarantee security once secret keys are exposed. To reduce potential damages caused by key exposure attacks, Song (ACMCCS 2001) put forward the concept of forward-secure group signature (FSGS), which prevents attackers from forging group signatures pertaining to past time periods even if a secret group signing key is revealed at the current time period. For the time being, however, all known secure FSGS schemes are based on number-theoretic assumptions, and are vulnerable against quantum computers. In this work, we construct the first lattice-based FSGS scheme. Our scheme is proven secure under the Short Integer Solution and Learning With Errors assumptions. At the heart of our construction is a scalable lattice-based key evolving mechanism, allowing users to periodically update their secret keys and to efficiently prove in zero-knowledge that key evolution process is done correctly. To realize this essential building block, we first employ the Bonsai tree structure by Cash et al. (EUROCRYPT 2010) to handle the key evolution process, and then develop Langlois et al.s construction (PKC 2014) to design its supporting zero-knowledge protocol.
Policy-based signatures (PBS) were proposed by Bellare and Fuchsbauer (PKC 2014) to allow an {em authorized} member of an organization to sign a message on behalf of the organization. The users authorization is determined by a policy managed by the organizations trusted authority, while the signature preserves the privacy of the organizations policy. Signing keys in PBS do not include user identity information and thus can be passed to others, violating the intention of employing PBS to restrict users signing capability. In this paper, we introduce the notion of {em traceability} for PBS by including user identity in the signing key such that the trusted authority will be able to open a suspicious signature and recover the signers identity should the needs arise. We provide rigorous definitions and stringent security notions of traceable PBS (TPBS), capturing the properties of PBS suggested by Bellare-Fuchsbauer and resembling the full traceability requirement for group signatures put forward by Bellare-Micciancio-Warinschi (Eurocrypt 2003). As a proof of concept, we provide a modular construction of TPBS, based on a signature scheme, an encryption scheme and a zero-knowledge proof system. Furthermore, to demonstrate the feasibility of achieving TPBS from concrete, quantum-resistant assumptions, we give an instantiation based on lattices.
The concept of universal designated verifier signatures was introduced by Steinfeld, Bull, Wang and Pieprzyk at Asiacrypt 2003. These signatures can be used as standard publicly verifiable digital signatures but have an additional functionality which allows any holder of a signature to designate the signature to any desired verifier. This designated verifier can check that the message was indeed signed, but is unable to convince anyone else of this fact. We propose new efficient constructions for pairing-based short signatures. Our first scheme is based on Boneh-Boyen signatures and its security can be analyzed in the standard security model. We prove its resistance to forgery assuming the hardness of the so-called strong Diffie-Hellman problem, under the knowledge-of-exponent assumption. The second scheme is compatible with the Boneh-Lynn-Shacham signatures and is proven unforgeable, in the random oracle model, under the assumption that the computational bilinear Diffie-Hellman problem is untractable. Both schemes are designed for devices with constrained computation capabilities since the signing and the designation procedure are pairing-free. Finally, we present extensions of these schemes in the multi-user setting proposed by Desmedt in 2003.
In this paper we introduce a variant of the Syndrome Decoding Problem (SDP), that we call Restricted SDP (R-SDP), in which the entries of the searched vector are defined over a subset of the underlying finite field. We prove the NP-completeness of R-SDP, via a reduction from the classical SDP, and describe algorithms which solve such new problem. We study the properties of random codes under this new decoding perspective, in the fashion of traditional coding theory results, and assess the complexity of solving a random R-SDP instance. As a concrete application, we describe how Zero-Knowledge Identification (ZK-ID) schemes based on SDP can be tweaked to rely on R-SDP, and show that this leads to compact public keys as well as significantly reduced communication costs. Thus, these schemes offer an improved basis for the construction of code-based digital signature schemes derived from identification schemes through the well-know Fiat-Shamir transformation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
