1,720,986 research outputs found
Efficient Round-Optimal Blind Signatures in the Standard Model
Full text linkBlind signatures are at the core of e-cash systems and have numerous other applications. In this work we construct efficient blind and partially blind signature schemes over bilinear groups in the standard model. Our schemes yield short signatures consisting of only a couple of elements from the shorter source group and have very short communication overhead consisting of group element on the user side and group elements on the signer side.
At -bit security, our schemes yield signatures consisting of only bytes which is shorter than the most efficient existing scheme with the same security in the standard model. Verification in our schemes requires only a couple of pairings.
Our schemes compare favorably in every efficiency measure to all existing counterparts offering the same security in the standard model. In fact, the efficiency of our signing protocol as well as the signature size compare favorably even to many existing schemes in the random oracle model. For instance, our signatures are shorter than those of Brands\u27 scheme which is at the heart of the U-Prove anonymous credential system used in practice. The unforgeability of our schemes is based on new intractability assumptions of a ``one-more\u27\u27 type which we show are intractable in the generic group model, whereas their blindness holds w.r.t.~malicious signing keys in the information-theoretic sense.
We also give variants of our schemes for a vector of messages
More Efficient Structure-Preserving Signatures - Or: Bypassing the Type-III Lower Bounds
Full text linkStructure-preserving signatures are an important cryptographic primitive that is useful for the design of modular cryptographic protocols.
It has been proven that structure-preserving signatures (in the most efficient Type-III bilinear group setting) have a lower bound of 3 group elements in the signature (which must include elements from both source groups) and require at least 2 pairing-product equations for verification.
In this paper, we show that such lower bounds can be circumvented. In particular, we define the notion of Unilateral Structure-Preserving Signatures on Diffie-Hellman pairs (USPSDH) which are structure-preserving signatures in the efficient Type-III bilinear group setting with the message space being the set of Diffie-Hellman pairs, in the terminology of Abe et al. (Crypto 2010). The signatures in these schemes are elements of one of the source groups, i.e. unilateral, whereas the verification key elements\u27 are from the other source group. We construct a number of new structure-preserving signature schemes which bypass the Type-III lower bounds and hence they are much more efficient than all existing structure-preserving signature schemes. We also prove optimality of our constructions by proving lower bounds and giving some impossibility results.
Our contribution can be summarized as follows:
\begin{itemize}
\item We construct two optimal randomizable CMA-secure schemes with signatures consisting of only 2 group elements from the first short source group and therefore our signatures are at least half the size of the best existing structure-preserving scheme for unilateral messages in the (most efficient) Type-III setting. Verifying signatures in our schemes requires, besides checking the well-formedness of the message, the evaluation of a single Pairing-Product Equation (PPE) and requires a fewer pairing evaluations than all existing structure-preserving signature schemes in the Type-III setting. Our first scheme has a feature that permits controlled randomizability (combined unforgeability) where the signer can restrict some messages such that signatures on those cannot be re-randomized which might be useful for some applications.
\item We construct optimal strongly unforgeable CMA-secure one-time schemes with signatures consisting of 1 group element, and which can also sign a vector of messages while maintaining the same signature size.
\item We give a one-time strongly unforgeable CMA-secure structure-preserving scheme that signs unilateral messages, i.e. messages in one of the source groups, whose efficiency matches the best existing optimal one-time scheme in every respect.
\item We investigate some lower bounds and prove some impossibility results regarding this variant of structure-preserving signatures.
\item We give an optimal (with signatures consisting of 2 group elements and verification requiring 1 pairing-product equation) fully randomizable CMA-secure partially structure-preserving scheme that simultaneously signs a Diffie-Hellman pair and a vector in .
\item As an example application of one of our schemes, we obtain
efficient instantiations of randomizable weakly blind signatures which do not rely on random oracles.
The latter is a building block that is used, for instance, in constructing Direct Anonymous Attestation (DAA) protocols, which are protocols deployed in practice.
\end{itemize}
Our results offer value along two fronts: On the practical side, our constructions are more efficient than existing ones and thus could lead to more efficient instantiations of many cryptographic protocols. On the theoretical side, our results serve as a proof that many of the lower bounds for the Type-III setting can be circumvented
Short Structure-Preserving Signatures
Full text linkWe construct a new structure-preserving signature scheme in the efficient Type-III asymmetric bilinear group setting with signatures shorter than all existing schemes.
Our signatures consist of 3 group elements from the first source group and therefore have shorter size than all existing schemes as existing ones have at least one component of the signature in the second source group whose elements bit size is at least double their first group counterparts.
Besides enjoying short signatures, our scheme is fully re-randomizable which is a useful property for many applications. Our result also constitutes a proof that the impossibility of unilateral structure-preserving signatures in the Type-III setting result of Abe et al.~(Crypto 2011) does not apply to constructions in which the message space is dual in both source groups.
Besides checking the well-formedness of the message, verifying a signature in our scheme requires checking Pairing Product Equations (PPE) and require the evaluation of only pairings in total which matches the best existing scheme and outperforms many other existing ones.
Reducing the number of pairings in the verification equations is very important when combining structure-preserving signature schemes with Groth-Sahai proofs as the number of pairings required for verifying Groth-Sahai proofs for PPE equations grows linearly with the number of pairing monomials in the source equations.
We give some examples of how using our new scheme instead of existing
ones improves the efficiency of some existing cryptographic protocols such as direct anonymous attestation and group signature related constructions
Partially Structure-Preserving Signatures: Lower Bounds, Constructions and More
Full text linkIn this work we first provide a framework for defining a large subset of pairing-based digital signature schemes
which we call Partially Structure-Preserving Signature (PSPS) schemes. PSPS schemes are similar in nature to structure-preserving signatures with the exception that in these schemes messages are scalars from instead of being source group elements. This class encompasses various existing schemes which have a number of desirable features which makes them an ideal building block for many privacy-preserving cryptographic protocols. They include the widely-used schemes of Camenisch-Lysyanskaya (CRYPTO 2004) and Pointcheval-Sanders (CT-RSA 2016). We then provide various impossibility and lower bound results for variants of this class. Our results include bounds for the signature and verification key sizes as well as lower bounds for achieving strong unforgeability.
We also give a generic framework for transforming variants of PSPS schemes into structure-preserving ones. As part of our contribution, we also give a number of optimal PSPS schemes which may be of independent interest.
Our results aid in understanding the efficiency of pairing-based signature schemes and show a connection between this class of signature schemes and structure-preserving ones
How Low Can You Go? Short Structure-Preserving Signatures for Diffie-Hellman Vectors
Full text linkStructure-Preserving Signatures (SPSs) are an important tool for the design of modular cryptographic protocols.
It has been proven that such schemes in the most efficient Type-3 bilinear group setting have a lower bound of 3-element signatures, which must include elements from both base groups, and a verification overhead of at least 2 Pairing-Product Equations (PPEs). Very recently, Ghadafi (ESORICS 2017) showed that by restricting the message space to the set of Diffie-Hellman pairs (which does not hinder applicability of the schemes), some of the existing lower bounds for the single message case can be circumvented. However, the case of signing multiple messages, which is required for many applications, was left as an open problem since the techniques used for signing single messages do not seem to lend themselves to the
multi-message setting. In this work we investigate this setting and answer the question in the affirmative. We construct schemes that sign vectors of messages and which yield shorter signatures than optimal schemes for vectors of unilateral messages.
More precisely, we construct 2 fully randomiazble schemes that sign vectors of Diffie-Hellman pairs yielding signatures consisting of only 2 elements regardless of the size of the vector signed. We also construct a unilateral scheme that signs a pair of messages yielding signatures consisting of 3 elements from the shorter base group. All of our schemes require a single PPE for verification (not counting the cost of verifying the well-formedness of the messages). Thus, all of our schemes compare favourably to all existing schemes with respect to signature size and verification overhead.
Even when considering single messages, our first 2 schemes compare favourably to the best existing schemes in many aspects including the verification overhead and the key size
Further Lower Bounds for Structure-Preserving Signatures in Asymmetric Bilinear Groups
Full text linkStructure-Preserving Signatures (SPSs) are a useful tool for the design of modular cryptographic protocols. Recent series of works have shown that by limiting the message space of those schemes to the set of Diffie-Hellman (DH) pairs, it is possible to circumvent the known lower bounds in the Type-3 bilinear group setting thus obtaining the shortest signatures consisting of only 2 elements from the shorter source group. It has been shown that such a variant yields efficiency gains for some cryptographic constructions, including attribute-based signatures and direct anonymous attestation. Only the cases of signing a single DH pair or a DH pair and a vector from have been considered. Signing a vector of group elements is required for various applications of SPSs, especially if the aim is to forgo relying on heuristic assumptions.
An open question is whether such an improved lower bound also applies to signing a vector of messages. We answer this question negatively for schemes existentially unforgeable under an adaptive chosen-message attack (EUF-CMA) whereas we answer it positively for schemes existentially unforgeable under a random-message attack (EUF-RMA) and those which are existentially unforgeable under a combined chosen-random-message attack (EUF-CMA-RMA). The latter notion is a leeway between the two former notions where it allows the adversary to adaptively choose part of the message to be signed whereas the remaining part of the message is chosen uniformly at random by the signer.
Another open question is whether strongly existentially unforgeable under an adaptive chosen-message attack (sEUF-CMA) schemes with 2-element signatures exist. We answer this question negatively, proving it is impossible to construct sEUF-CMA schemes with 2-element signatures even if the signature consists of elements from both source groups. On the other hand, we prove that sEUF-RMA and sEUF-CMA-RMA schemes with 2-element (unilateral) signatures are possible by giving constructions for those notions.
Among other things, our findings show a gap between random-message/combined chosen-random-message security and chosen-message security in this setting
- …
