CryptoDB

Fangguo Zhang

Publications

Year
Venue
Title
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2010
EPRINT
Edwards curves have attracted great interest for their efficient addition and doubling formulas. Furthermore, the addition formulas are strongly unified or even complete, i.e., work without change for all inputs. In this paper, we propose the first halving algorithm on binary Edwards curves, which can be used for scalar multiplication. We present a point halving algorithm on binary Edwards curves in case of $d_1\neq d_2$. The halving algorithm costs about $3I+5M+4S$, which is slower than the doubling one. We also give a theorem to prove that the binary Edwards curves have no minimal two-torsion in case of $d_1= d_2$, and we briefly explain how to achieve the point halving algorithm using an improved algorithm in this case. Finally, we apply our halving algorithm in scalar multiplication with $\omega$-coordinate using Montgomery ladder.
2010
EPRINT
Self-pairings have found interesting applications in cryptographic schemes. In this paper, we present a novel method for constructing a self-pairing on supersingular elliptic curves with even embedding degrees, which we call the Ateil pairing. This new pairing improves the efficiency of the self-pairing computation on supersingular curves over finite fields with large characteristics. Based on the $\eta_T$ pairing, we propose a generalization of the Ateil pairing, which we call the Ateil$_i$ pairing. The optimal Ateil$_i$ pairing which has the shortest Miller loop is faster than previously known self-pairings on supersingular elliptic curves over finite fields with small characteristics. We also present a new self-pairing based on the Weil pairing which is faster than the self-pairing based on the Tate pairing on ordinary elliptic curves with embedding degree $one$.
2009
EPRINT
Chameleon signatures are based on well established hash-and-sign paradigm, where a \emph{chameleon hash function} is used to compute the cryptographic message digest. Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message. However, the initial constructions of chameleon signatures suffer from the problem of key exposure: the signature forgery results in the signer recovering the recipient's trapdoor information, $i.e.,$ the private key. This creates a strong disincentive for the recipient to forge signatures, partially undermining the concept of non-transferability. Recently, some specific constructions of key-exposure free chameleon hashing are presented, based on RSA or pairings, using the idea of Customized Identities". In this paper, we propose the first key-exposure free chameleon hash scheme based on discrete logarithm systems, without using the gap Diffile-Hellman groups. Moreover, one distinguished advantage of the resulting chameleon signature scheme is that the property of message hiding" or message recovery" can be achieved freely by the signer. Another main contribution in this paper is that we propose the first identity-based chameleon hash scheme without key exposure, which gives a positive answer for the open problem introduced by Ateniese and de Mederious in 2004.
2008
EPRINT
In this paper, we suggest that all pairings be in a group from an abstract angle. It is possible that our observation can be applied into other aspects of pairing-based cryptosystems.
2008
EPRINT
In this paper, a super-optimal pairing based on the Weil pairing is proposed with great efficiency. It is the first approach to reduce the Miller iteration loop when computing the variants of the Weil pairing. The super-optimal pairing based on the Weil pairing is computed rather fast, while it is slightly slower than the previous fastest pairing on the corresponding elliptic curves.
2008
EPRINT
In this paper, we investigate to compute the variants based on the Weil pairing with short Miller iteration loops.
2008
EPRINT
In this paper we show that the twisted Ate pairing on elliptic curves can be generalized to hyperelliptic curves, we also give a series of variations of the hyperelliptic Ate and twisted Ate pairings. Using the hyperelliptic Ate pairing and twisted Ate pairing, we propose a new approach to speed up the Weil pairing computation, and obtain an interested result: For some hyperelliptic curves with high degree twist, using this approach to compute Weil pairing will be faster than Tate pairing, Ate pairing etc. all known pairings.
2007
EPRINT
The Ate pairing has been suggested since it can be computed efficiently on ordinary elliptic curves with small values of the traces of Frobenius $t$. However, not all pairing-friendly elliptic curves have this property. In this paper, we generalize the Ate pairing and find a series of variations of the Ate pairing. We show that the shortest Miller loop of the variations of the Ate pairing can possibly be as small as $r^{1/\varphi(k)}$ on more pairing-friendly curves generated by the method of complex multiplications, and hence speed up the pairing computation significantly.
2007
EPRINT
Restrictive partially blind signature (RPBS) plays an important role in designing secure electronic cash system. Very recently, Wang, Tang and Li proposed a new ID-based restrictive partially blind signature (ID-RPBS) and gave the security proof. In this paper, we present a cryptanalysis of the scheme and show that the signature scheme does not satisfy the property of {\bf unforgeability} as claimed. More precisely, a user can forge a valid message-signature pair $(ID, msg, {\bf info'}, \sigma')$ instead of the original one $(ID, msg, {\bf info}, \sigma)$, where {\bf info} is the original common agreed information and ${\bf info}'\neq {\bf info}$. Therefore, it will be much dangerous if Wang-Tang-Li's ID-RPBS scheme is applied to the off-line electronic cash system. For example, a bank is supposed to issue an electronic coin (or bill) of \$100 to a user, while the user can change the denomination of the coin (bill) to any value, say \$100, 000, 000, at his will.
2007
EPRINT
For AES 128 security level there are several natural choices for pairing-friendly elliptic curves. In particular, as we will explain, one might choose curves with $k=9$ or curves with $k=12$. The case $k=9$ has not been studied in the literature, and so it is not clear how efficiently pairings can be computed in that case. In this paper, we present efficient methods for the $k=9$ case, including generation of elliptic curves with the shorter Miller loop, the denominator elimination and speed up of the final exponentiation. Then we compare the performance of these choices. From the analysis, we conclude that for pairing-based cryptography at the AES 128 security level, the Barreto-Naehrig curves are the most efficient choice, and the performance of the case $k=9$ is comparable to the Barreto-Naehrig curves.
2006
EPRINT
Pairing-based cryptosystems have been developing very fast in the last few years. The efficiencies of the cryptosystems are determined by the computation of the Tate pairing. In this paper a new efficient algorithm based on double-base chain for computing the Tate pairing is proposed for odd characteristic $p>3$. The inherent sparseness of double-base number system reduces the computational cost for computing the Tate pairing evidently. It is $9\%$ faster than the previous fastest method for MOV degree k=6.
2006
EPRINT
In this paper we present an algorithm for computing the bilinear pairings on a family of non-supersingular elliptic curves with non-trivial automorphisms. We obtain a short iteration loop in Miller's algorithm using non-trivial ecient automorphisms. The proposed algorithm is as ecient as Scott's algorithm in [12].
2006
EPRINT
Efficient authentication is one of important security requirements in mobile ad hoc network (MANET) routing systems. The techniques of digital signatures are generally considered as the best candidates to achieve strong authentication. However, using normal digital signature schemes is too costly to MANET due to the computation overheads. Considering the feasibility of incorporating digital signatures in MANET, we incorporate the notion of online/offline signatures, where the computational overhead is shifted to the offline phase. However, due to the diversity of different routing protocols, a universal scheme that suits all MANET routing systems does not exist in the literature. Notably, an authentication scheme for the AODV routing is believed to be not suitable to the DSR routing. In this paper, we first introduce an efficient ID-based online/offline scheme for authentication in AODV and then provide a formal transformation to convert the scheme to an ID-based online/offline multisignature scheme. Our scheme is unique, in the sense that a single ID-based online/offline signature scheme can be applied to both AODV and DSR routing protocols. We provide the generic construction as well as the concrete schemes to show an instantiation of the generic transformation. We also provide security proofs for our schemes based on the random oracle model. Finally, we provide an application of our schemes in the dynamic source routing protocol.
2006
EPRINT
Recently, Boneh, Gentry, and Waters '05 presented an efficient broadcast encryption, and Boneh, Sahai, and Waters '06 presented an efficient traitor tracing scheme. The former broadcast encryption result contains both a simpler chosen plaintext secure version and a more complicated but chosen ciphertext secure version. The latter traitor tracing scheme is only chosen plaintext secure. In this paper, we use the twin encryption technique of Naor and Yung '90 to add chosen ciphertext security to both papers. Bytwinning", we extend the simpler chosen plaintext secure broadcast encryption to achieve chosen ciphertext security, and we extend the chosen plaintext secure traitor tracing to achieve chosen ciphertext security. We also extend both schemes to versions corresponding to threshold encryption which we call "broadcast threshold encryption" and "threshold-traitor tracing", i.e. tracing of threshold traitors. In these schemes, any $\theta$ un-revoked users can decrypt while $\theta-1$ users cannot. The tracing is to a set of $\theta$ users. We call this set a "threshold-traitor". Our broadcast threshold encryption is collusion resistant. Our threshold-traitor tracing is collusion resistant in its traceability.
2006
EPRINT
A new public key cryptosystem, called REESSE1+, was proposed. REESSE1 consists of two primitive algorithms, a public key encryptio/decryption algorithm and a digital signature algorithm. We give some analysis to REESSE1+, and show that the system is totally unsecure. We show how to derive the private key from the public key. As the same time, we also show how to forge signatures for any messages, given two valid signatures.
2005
EPRINT
An ad-hoc anonymous identification scheme is a new multi-user cryptographic primitive that allows participants from a user population to form ad hoc groups, and then prove membership anonymously in such groups. Recently, Nguyen \cite{Lan05} proposed an ID-based ad-hoc anonymous identification scheme from bilinear pairings. However, in this paper, we propose an attack on Nguyen's ID-based ad-hoc anonymous identification scheme. We show that any one can impersonate a valid group member to perform the anonymous identification protocol successfully. Furthermore, we propose a solution to improve this scheme against our attack.
2005
EPRINT
We present an attack on a new short signature scheme from bilinear pairing proposed by Okamoto $et$ $al.$ at ITCC'05. We show that any one can derive the secret key of the signer from any two message-signature pairs and so can forge the signer's signature for any message. This means the scheme is totally broken.
2005
EPRINT
In this paper, we propose a new signature scheme that is existentially unforgeable under a chosen message attack without random oracle. The security of our scheme depends on a new complexity assumption called the $k$+1 square roots assumption. We also discuss the relationship between the $k$+1 square roots assumption and some related problems and provide some conjectures. Moreover, the $k$+1 square roots assumption can be used to construct shorter signatures under the random oracle model. As some applications, a new chameleon hash signature scheme and a on-line/off-line signature scheme and a new efficient anonymous credential scheme based on the proposed signature scheme are presented.
2005
EPRINT
We present the first group signature scheme with provable security and signature size $O(\lambda)$ bits where the group manager, the group members, and the Open Authority (OA) are all identity-based. We use the security model of Bellare, Shi, and Zhang, except to add three identity managers for manager, members, and OA respectively, and we discard the Open Oracle. Our construction uses identity-based signatures summarized in Bellare, Namprempre, and Neven for manager, Boneh and Franklin's IBE for OA, and we extend Bellare et al.'s group signature construction by verifiably encrypt an image of the member public key, instead of the public key itself. The last innovation is crucial in our efficiency; otherwise, Camenisch and Damgard's verifiable encryption would have to be used resulting in lower efficiency.
2005
EPRINT
In recent years, cryptographic protocols based on the bilinear pairings have attracted much attention. One of the most distinguished achievements in this area was the solution to design short signatures. Up to now, there exist two short signature schemes with random oracles and one without random oracles from bilinear pairings. In this paper, we describe another short signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The security of our scheme depends on a new complexity assumption we call the $k$+1 square roots assumption. We discuss the relationship between the $k$+1 square roots assumption and some related problems and give some conjectures. Further more, the $k$+1 square roots assumption gives even shorter signatures under the random oracles.
2005
EPRINT
Restrictive blind signatures allow a recipient to receive a blind signature on a message not known to the signer but the choice of message is restricted and must conform to certain rules. Partially blind signatures allow a signer to explicitly include necessary information (expiration date, collateral conditions, or whatever) in the resulting signatures under some agreement with receiver. Restrictive partially blind signatures incorporate the advantages of these two blind signatures. The existing restrictive partially blind signature scheme was constructed under certificate-based (CA-based) public key systems. In this paper we follow Brand's construction to propose the first identity-based (ID-based) restrictive blind signature scheme from bilinear pairings. Furthermore, we first propose an ID-based restrictive partially blind signature scheme, which is provably secure in the random oracle model. As an application, we use the proposed signature scheme to build an untraceable off-line electronic cash system followed Brand's construction.
2005
EPRINT
Identity-based (simply ID-based) cryptosystem was proposed in order to simplify key management procedures of certificate-based public key infrastructures. In 2003 Sakai and Kasahara proposed a new ID-based encryption scheme (SK-IBE). In our paper, it is intended to build a new ID-based signature (IBS) scheme which shares the same system parameters with SK-IBE. SK-IBE and our signature scheme yield a new complete ID-based public key cryptosystem. The proposed signature scheme is provably secure against existential forgery for adaptive chosen message and identity attack in the random oracle model based on a reasonably well-explored hardness assumption. Another contribution of this paper is that we first propose the notion of key-insulated threshold signature and present a generic method for constructing key-insulated threshold signature scheme.
2004
PKC
2004
EPRINT
We point out that the notion of {\em ambiguity} introduced in the concurrent signatures proposed by Chen, Kudla, and Paterson in Eurocrypt 2004 is incorrect. Any third party who observed two signatures can differentiate who has/have produced the signatures by performing the verification algorithm. We note that the model proposed in the paper is sound, but the concrete scheme does not really provide what is required in the model.
2004
EPRINT
Verifiably encrypted signatures are used when Alice wants to sign a message for Bob but does not want Bob to possess her signature on the message until a later date. Such signatures are used in optimistic contact signing to provide fair exchange. Partially blind signature schemes are an extension of blind signature schemes that allows a signer to sign a partially blinded message that include pre-agreed information such as expiry date or collateral conditions in unblinded form. These signatures are used in applications such as electronic cash (e-cash) where the signer requires part of the message to be of certain form. In this paper, we propose a new verifiably encrypted signature scheme and a partially blind signature scheme, both based on bilinear pairings. We analyze the security and efficiency of these schemes and show that they are more efficient than the previous schemes of their kinds.
2004
EPRINT
Chameleon signatures are based on well established hash-and-sign paradigm, where a \emph{chameleon hash function} is used to compute the cryptographic message digest. Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message, $i.e.,$ the designated recipient is capable of verifying the validity of the signature, but cannot disclose the contents of the signed information to convince any third party without the signer's consent. One disadvantage of the initial chameleon signature scheme is that signature forgery results in the signer recovering the recipient's trapdoor information, $i.e.,$ private key. Therefore, the signer can use this information to deny \emph{other} signatures given to the recipient. This creates a strong disincentive for the recipient to forge signatures, partially undermining the concept of non-transferability. In this paper, we firstly propose a chameleon hashing scheme in the gap Diffie-Hellman group to solve the problem of key exposure. We can prove that the recipient's trapdoor information will never be compromised under the assumption of Computation Diffie-Hellman Problem (CDHP) is intractable. Moreover, we use the proposed chameleon hashing scheme to design a chameleon signature scheme.
2004
EPRINT
Recently, Chang \textit{et al}. \cite{Chang} proposed a new digital signature scheme with message recovery and claimed that neither one-way hash functions nor message redundancy schemes were employed in their scheme. However, in this letter, two forgery attacks are proposed to show that Chang \textit{et al.}'s signature scheme is not secure. To resist these attacks, the message redundancy schemes may be still used.
2003
EPRINT
Key authentication is very important in secret communications and data security. Recently, Lee, Hwang and Li proposed a new public key authentication scheme for cryptosystems with a trusty server. However, in this paper, we will show that Lee-Hwang-Li's key authentication scheme is not secure, from the obtained public information, any one can get the private key of the user. And then, we propose an improved scheme. We conclude that our new key authentication scheme not only resolves the problems appeared but also is secure.
2003
EPRINT
Blackmailing may be the most serious drawback of the known electronic cash systems offering unconditional anonymity. Recently, D.Kugler proposed an on-line payment system without trusted party to prevent blackmailing based on the idea of marking. In this paper, some disadvantages of D.Kugler??s scheme are analyzed and then a new online electronic cash scheme to prevent blackmailing is present by using group blind signature technique. In our scheme, the blackmailed cash was marked by an entity, called supervisor, therefore the bank can distinguish it from the valid cash. Also, we can modify our scheme to be offline so that it can used to decrease other crimes, e.g., money laundering, bribery etc. in electronic cash system.
2003
EPRINT
In this paper, the authors propose a new structured multisignature scheme that considers the signing order among co-signers. The proposed scheme can resolve signing structures of serial, parallel, and the mix of them. Moreover, the size and the verification of a structured multisignature is the same as those of an individual signature generated by any co-signer. Arithmetically, the proposed scheme makes use of the Gap Diffie-Hellman (GDH) signature scheme recently presented by Boneh, Shacham, and Lynn. Due to the underlying GDH group, our scheme has the merits of simplicity in construction and efficiency in performance.
2003
EPRINT
We argue that traditional ID-based systems from pairings seem unsuitable for designing group signature schemes due to the problem of key escrow. In this paper we propose new ID-based public key systems without trustful KGC from bilinear pairings. In our new ID-based systems, if dishonest KGC impersonates an honest user to communicate with others, the user can provide a proof of treachery of the KGC afterwards, which is similar to CA-based systems. Furthermore, we propose a group signature scheme under the new systems, the security and performance of which rely on the new systems. The size of the group public key and the length of the signature are independent on the numbers of the group.
2003
EPRINT
At the fourth ACM conference on electronic commerce (EC'03), S. Han, K.Y. Yeung and J. Wang proposed an ID-based confirmer signature scheme using pairings (actually, this is an ID-based undeniable signature scheme). However, in this paper, we will show that this signature scheme is not secure. The signer can deny any signature, even this signature is his valid signature and any one can forge a valid confirmer signature of a signer with identity ID on an arbitrary message and confirm this signature to the verifier.
2003
EPRINT
Chameleon hash function is a trapdoor one-way hash function. The ID-based chameleon hash function was first introduced by Ateniese and Medeiros \cite{AM03}. As discussed by \cite{AM03}, the general advantages of ID-based cryptography over conventional cryptography with respect to key distribution are even more pronounced in a chameleon hashing scheme, because the owner of a public key does not necessarily need to retrieve the associated secret key. In this paper, we propose two new ID-based Chameleon hashing schemes from bilinear pairings. Also we analyze their security and efficiency. Based on these ID-based chameleon hashes, ID-based chameleon signature schemes can be designed.
2003
EPRINT
Proxy signatures are very useful tools when one needs to delegate his/her signing capability to other party. After Mambo $et\ al.$'s first scheme was announced, many proxy signature schemes and various types of proxy signature schemes have been proposed. Due to the various applications of the bilinear pairings in cryptography, there are many ID-based signature schemes have been proposed. In this paper, we address that it is easy to design proxy signature and proxy blind signature from the conventional ID-based signature schemes using bilinear pairings, and give some concrete schemes based on existed ID-based signature schemes. At the same time, we introduce a new type of proxy signature -- proxy ring signature, and propose the first proxy ring signature scheme based on an existed ID-based ring signature scheme.
2003
EPRINT
Authenticated group key agreement problem is important in many modern collaborative and distributed applications. Recently, there are two ID-based authenticated group key agreement schemes have been proposed, one is Choi $et\ al.$'s \cite{CHL04} scheme, the other is Du $et\ al.$'s \cite{Du03} scheme. They are all constructed from bilinear pairings based on Burmester and Desmedt scheme \cite{BD94}. In this paper, we propose an impersonation attack on the two schemes. We show that any two malicious users can impersonate an entity to agree some session keys in a new group if these two malicious users have the previous authentication transcripts of this entity. So, the two ID-based authenticated group key agreement schemes can not provide the authenticity as claimed. We propose a proposal to repair these schemes.
2002
ASIACRYPT
2002
EPRINT
With positive applications of Weil pairing (Tate pairing) to cryptography, ID-based encryption schemes, digital signature schemes, blind signature scheme, two-party authenticated key agreement schemes, and tripartite key agreement scheme were proposed recently, all of them using bilinear pairing (Weil or Tate pairing). In this paper, we propose an ID-based one round authenticated tripartite key agreement protocol. The authenticity of the protocol is assured by a special signature scheme, so that messages carrying the information of two ephemeral keys can be broadcasted authentically by an entity. Consequently, one instance of our protocol results in eight session keys for the three entities. Security attributes of our protocol are presented, and the computational overhead and bandwidth of the broadcast messages are analyzed as well.
2002
EPRINT
Group signature and blind signature are very important primitives in cryptography. A group signature scheme allows a group member to sign messages anonymously on behalf of the group and a blind signature scheme can ensure anonymity of the sender of a message. Recently, S. Xia and J. You proposed a group signature scheme with strong separability in which the revocation manager can work without the involvement of the membership manager and J.J-R. Chen and A.P. Chen proposed a blind signature scheme based on dual complexities (which combines factorization and discrete logarithm problem). In this paper, we give a universal forgery attack on Xia-You's group signature scheme which any one (not necessarily a group member) can produce a valid group signature on an arbitrary message, and it is untraceable by the group revocation manager. For Chen-Chen's blind signature scheme, we show that it could not meet the untraceability property of a blind signature, $i.e.$, it could not ensure anonymity of the user.
2002
EPRINT
In ISC 2002, J. Zheng proposed a new public key cryptosystem whose security is based upon the algebraic problem of reducing a high degree matrix to its canonical form by similarity transformations. In this paper, we show that factoring a polynomial over a finite field can be used to break down Zheng's public key cryptosystem. The complexity of our attack is polynomial time. In other word, the underlying problem of Zheng's public key cryptosystem is not a hard'' problem.

Asiacrypt 2019