## CryptoDB

### Duncan S. Wong

#### Publications

Year
Venue
Title
2015
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2012
PKC
2008
ASIACRYPT
2008
EPRINT
We propose a new architecture for performing Elliptic Curve Scalar Multiplication (ECSM) on elliptic curves over GF(2^m). This architecture maximizes the parallelism that the projective version of the Montgomery ECSM algorithm can achieve. It completes one ECSM operation in about $2(m-1)( \lceil m/D \rceil +4)+m$ cycles, and is at least three times the speed of the best known result currently available. When implemented on a Virtex-4 FPGA, it completes one ECSM operation over GF(2^163) in 12.5us with the maximum achievable frequency of 222MHz. Two other implementation variants for less resource consumption are also proposed. Our first variant reduces the resource consumption by almost 50% while still maintaining the utilization efficiency, which is measured by a performance to resource consumption ratio. Our second variant achieves the best utilization efficiency and in our actual implementation on an elliptic curve group over GF(2^163), it gives more than 30% reduction on resource consumption while maintaining almost the same speed of computation as that of our original design. For achieving this high performance, we also propose a modified finite field inversion algorithm which takes only m cycles to invert an element over GF(2^m), rather than 2m cycles as the traditional Extended Euclid algorithm does, and this new design yields much better utilization of the cycle time.
2008
EPRINT
Recently, a fast modular multiexponentiation algorithm for computing A^X B^Y (mod N) was proposed. The authors claimed that on average their algorithm only requires to perform 1.306k modular multiplications (MMs), where k is the bit length of the exponents. This claimed performance is significantly better than all other comparable algorithms, where the best known result by other algorithms achieves 1.503k MMs only. In this paper, we give a formal complexity analysis and show the claimed performance is not true. The actual computational complexity of the algorithm should be 1.556k. This means that the best modular multiexponentiation algorithm based on canonical-sighed-digit technique is still not able to overcome the 1.5k barrier.
2008
EPRINT
In Pattern Recognition, vol. 36, 2003, Hou proposed a four-share visual cryptography scheme for color images. The scheme splits a secret image into four shares, the black mask and the other three shares. It was claimed that without knowing the black mas, no information about the secret image can be obtained even if all the other three shares are known. In this paper, we show that this may be true for a few specific two-color secret images only. In all other cases however, security cannot be guaranteed. We show that an attacker can compromise a randomly chosen two-color secret image from any two of the other three shares with probability 4/7. The advantage will increase to 6/7 if all the other three shares are known. If the secret image has three or four colors, we show that the attacker can compromise it with probability 4/7 and 8/35, respectively. Finally, we show that our technique can be extended to compromising secret images with more than four colors.
2007
PKC
2007
EPRINT
The only known constructions of Hierarchical Identity Based Signatures that are proven secure in the strongest model without random oracles are based on the approach of attaching certificate chains or hierarchical authentication tree with one-time signature. Both construction methods lead to schemes that are somewhat inefficient and leave open the problem of efficient direct construction. In this paper, we propose the first direct construction of Hierarchical Identity Based Signature scheme that is proven under the strongest model without relying on random oracles and using more standard $q$-SDH assumption. It is computationally efficient and the signature size is constant. When the number of hierarchical level is set to be one, our scheme is a normal identity based signature scheme. It enjoys the shortest size in public parameters and signatures when compare with others in the literature, with the same security level.
2007
EPRINT
Since the introduction of nominative signature in 1996, there have been only a few schemes proposed and all of them have already been found flawed. In addition, there is no formal security model defined. Even more problematic, there is no convincing application proposed. Due to these problems, the research of nominative signature has almost stalled and it is unknown if a secure nominative signature scheme can be built or there exists an application for it. In this paper, we give positive answers to these problems. First, we illustrate that nominative signature is a better tool for building user certification systems which are originally believed to be best implemented using a universal designated-verifier signature. Second, we propose a formal definition and a rigorous set of adversarial models for nominative signature. Third, we show that Chaum's undeniable signature can be transformed efficiently to a nominative signature and prove its security.
2007
EPRINT
Despite the large number of certificateless encryption schemes recently proposed, many of them have been found to be insecure under a practical attack called \emph{malicious-but-passive} KGC attack, since they all follow the same key generation procedure as that of the one proposed by Al-Riyami and Paterson in ASIACRYPT 2003. The only provably secure certificateless encryption scheme against this attack is due to Libert and Quisquater (PKC 2006). However, the security can only be shown in the random oracle model. % In this paper, we first show that a scheme which has a different key generation procedure from that of Al-Riyami and Paterson also suffers from the malicious-but-passive KGC attack. Our attacking techniques are different from the previous attacks and may cause greater extent of damage than the previous ones. We also propose a generic construction of certificateless encryption which can be proven secure against this attack \emph{in the standard model}. This generic scheme is not only the first one proven secure in the standard model, but is also very efficient to instantiate. We also describe how to use short signature and hybrid encryption to construct highly efficient instantiations of this generic scheme.
2007
EPRINT
Time Capsule Signature, first formalized by Dodis and Yum in Financial Cryptography 2005, is a digital signature scheme which allows a signature to bear a (future) time t so that the signature will only be valid at time t or later, when a trusted third party called time server releases time-dependent information for checking the validity of a time capsule signature. Also, the actual signer of a time capsule signature has the privilege to make the signature valid before time t. In this paper, we provide a new security model of time capsule signature such that time server is not required to be fully trusted. Moreover, we provide two e±cient constructions in random oracle model and standard model. Our improved security model and proven secure constructions have the potential to build some new E-Commerce applications.
2007
EPRINT
A signer in a Nominative Signature (NS) scheme can arbitrarily choose a nominee, then jointly generate a signature in such a way that the signature can only be verified with the nominee's consent. NS is particularly useful in user certification systems. Currently, the only secure NS scheme available requires multi-round communications between the nominator and the nominee during signature generation. This implies that an NS-based user certification system requires a certification issuer to interact with a user using a complicated multi-round protocol for certificate issuance. It remains an open problem to construct an efficient and non-interactive NS scheme. In this paper, we solve this problem by proposing the first efficient one-move (i.e. non-interactive) NS scheme. In addition, we propose an enhanced security requirement called Strong Invisibility, and prove that our scheme satisfies this strong security requirement.
2007
EPRINT
The strongest security definition for public key encryption (PKE) schemes is indistinguishability against adaptive chosen ciphertext attacks (IND-CCA). A practical IND-CCA secure PKE scheme in the standard model is well-known to be difficult to construct given the fact that there are only a few such kind of PKE schemes available. From another perspective, we observe that for a large class of PKE-based applications, although IND-CCA security is sufficient, it is not a necessary requirement. Examples are Key Encapsulation Mechanism (KEM), MT-authenticator, providing pseudorandomness with a-priori information, and so on. This observation leads us to propose a slightly weaker version of IND-CCA, which requires ciphertexts of two randomly selected messages are indistinguishable under chosen ciphertext attacks. Under this new security notion, we show that highly efficient schemes proven secure in the standard model can be built in a straightforward way. We also demonstrate that such a security definition is already sufficient for the applications above.
2006
PKC
2006
EPRINT
The only known construction of ID-based ring signature schemes which maybe secure in the standard model is to attach certificates to non-ID-based ring signatures. This method leads to schemes that are somewhat inefficient and it is an open problem to find more efficient and direct constructions. In this paper, we propose two such constructions. Our first scheme, with signature size linear in the cardinality of the ring, is secure in the standard model under the computational Diffie-Hellman assumption. The second scheme, achieving constant signature size, is secure in a weaker attack model (the selective ID and weak chosen message model), under the Diffie-Hellman Inversion assumption.
2006
EPRINT
A nominative signature scheme allows a nominator (or signer) and a nominee (or verifier) to jointly generate and publish a signature in such a way that \emph{only} the nominee can verify the signature and if necessary, \emph{only} the nominee can prove to a third party that the signature is valid. In a recent work, Huang and Wang proposed a new nominative signature scheme which, in addition to the above properties, \emph{only} allows the nominee to convert a nominative signature to a publicly verifiable one. In ACISP 2005, Susilo and Mu presented several algorithms and claimed that these algorithms can be used by the nominator to verify the validity of a published nominative signature, show to a third party that the signature is valid, and also convert the signature to a publicly verifiable one, all \emph{without} any help from the nominee. In this paper, we point out that Susilo and Mu's attacks are actually \emph{incomplete} and {\it inaccurate}. In particular, we show that there exists no efficient algorithm for a nominator to check the validity of a signature if this signature is generated by the nominator and the nominee {\it honestly} and the Decisional Diffie-Hellman Problem is hard. On the other hand, we point out that the Huang-Wang scheme is indeed {\it insecure}, since there is an attack that allows the nominator to generate valid nominative signatures alone and prove the validity of such signatures to a third party.
2006
EPRINT
Identity-based cryptosystems have an inherent key escrow issue, that is, the Key Generation Center (KGC) always knows user secret key. If the KGC is malicious, it can always impersonate the user. Certificateless cryptography, introduced by Al-Riyami and Paterson in 2003, is intended to solve this problem. However, in all the previously proposed certificateless schemes, it is always assumed that the malicious KGC starts launching attacks (so-called Type II attacks) only after it has generated a master public/secret key pair honestly. In this paper, we propose new security models that remove this assumption for both certificateless signature and encryption schemes. Under the new models, we show that a class of certificateless encryption and signature schemes proposed previously are insecure. These schemes still suffer from the key escrow problem. On the other side, we also give new proofs to show that there are two generic constructions, one for certificateless signature and the other for certificateless encryption, proposed recently that are secure under our new models.
2006
EPRINT
One of the most commonly used two-factor authentication mechanisms is based on smart card and user's password. Throughout the years, there have been many schemes proposed, but most of them have already been found flawed due to the lack of formal security analysis. On the cryptanalysis of this type of schemes, in this paper, we further review two recently proposed schemes and show that their security claims are invalid. To address the current issue, we propose a new and simplified property set and a formal adversarial model for analyzing the security of this type of schemes. We believe that the property set and the adversarial model themselves are of independent interest. We then propose a new scheme and a generic construction framework. In particular, we show that a secure password based key exchange protocol can be transformed efficiently to a smartcard and password based two-factor authentication scheme provided that there exist pseudorandom functions and collision-resistant hash functions.
2006
EPRINT
Recently, there are several generic transformation techniques proposed for converting unforgeable signature schemes (the message in the forgery has not been signed yet) into strongly unforgeable ones (the message in the forgery could have been signed previously). Most of the techniques are based on trapdoor hash functions and all of them require adding supplementary components onto the original key pair of the signature scheme. In this paper, we propose a new generic transformation which converts \emph{any} unforgeable signature scheme into a strongly unforgeable one, and also keeps the key pair of the signature scheme unchanged. Our technique is based on \emph{strong one-time signature schemes}. We show that they can be constructed efficiently from any one-time signature scheme that is based on one-way functions. The performance of our technique also compares favorably with that of those trapdoor-hash-function-based ones. In addition, this new generic transformation can also be used for attaining strongly unforgeable signature schemes in other cryptographic settings which include certificateless signature, identity-based signature, and several others. To the best of our knowledge, similar extent of versatility is not known to be supported by any of those comparable techniques. Finally and of independent interest, we show that our generic transformation technique can be modified to an \emph{on-line/off-line} signature scheme, which possesses a very efficient signing process.
2006
EPRINT
In this paper, we propose a Hierarchical Identity Based Encryption scheme that is proven secure under the strongest model of \cite{BonehFr01} directly, without relying on random oracles. The size of the ciphertext is a constant while the size of public parameters is independent to the number of bit representing an identity. It is the first in the literature to achieve such a high security level and space efficiency at the same time. In addition, we also propose the first Hierarchical Identity Based Signature scheme that is proven under the strongest model without relying on random oracles and using more standard $q$-SDH assumption. Similar to the proposed encryption scheme, the space complexity of the signature and public parameters are as efficient as the proposed encryption scheme.
2005
EPRINT
Since the introduction of Identity-based (ID-based) cryptography by Shamir in 1984, numerous ID-based signature schemes have been proposed. In 2001, Rivest et al. introduced ring signature that provides irrevocable signer anonymity and spontaneous group formation. In recent years, ID-based ring signature schemes have been proposed and all of them are based on bilinear pairings. In this paper, we propose the first ID-based threshold ring signature scheme that is not based on bilinear pairings. We also propose the first ID-based threshold linkable' ring signature scheme. We emphasize that the anonymity of the actual signers is maintained even against the private key generator (PKG) of the ID-based system. Finally we show how to add identity escrow to the two schemes. Due to the different levels of signer anonymity they support, the schemes proposed in this paper actually form a suite of ID-based threshold ring signature schemes which is applicable to many real-world applications with varied anonymity requirements.
2005
EPRINT
Digital signature is one of the most important primitives in public key cryptography. It provides authenticity, integrity and non-repudiation to many kinds of applications. On signer privacy however, it is generally unclear or suspicious of whether a signature scheme itself can guarantee the anonymity of the signer. In this paper, we give some affirmative answers to it. We formally define the signer anonymity for digital signature and propose some schemes of this type. We show that a signer anonymous signature scheme can be very useful by proposing a new anonymous key exchange protocol which allows a client Alice to establish a session key with a server Bob securely while keeping her identity secret from eavesdroppers. In the protocol, the anonymity of Alice is already maintained when Alice sends her signature to Bob in clear, and no additional encapsulation or mechanism is needed for the signature. We also propose a method of using anonymous signature to solve the collusion problem between organizers and reviewers of an anonymous paper review system.
2005
EPRINT
In this paper, we suggest solutions to the key exposure problem in ring signature. In particular, we propose the first forward secure ring signature scheme and the first key-insulated ring signature schemes. Both constructions allow a $(t,n)$-threshold setting. That is, even $t$ secret keys are compromised, the validity of all forward secure ring signatures generated in the past is still preserved. In the other way, the compromise of up to all secret keys does not allow any adversary to generate a valid key-insulated ring signature for the remaining time periods.
2005
EPRINT
In 2001, Canetti and Krawczyk proposed a security model (CK-model) for authentication protocols. They also gave an indistinguishability-based definition for key exchange protocols. Since then the model has almost exclusively been used for analyzing key exchange protocols, although it can be applied to authentication protocols in general. The model not only captures a large class of attacks but also provides a modular approach to the design of authentication protocols. However, the model does not capture the property of Key Compromise Impersonation (KCI) Resilience. Until now, analysis concerning this property has mostly been done heuristically and restricted to key exchange protocols only. Previous attempts on formalizing KCI have mostly been done in some ad hoc manner and additional proofs have to be given, specifically for the security of KCI resilience. In this paper, we propose an extension to the CK-model, which allows, for the first time, the KCI attacks to be considered in authentication protocols in general, rather than restricted to key exchange protocols, and no more additional proofs are required specifically for KCI security. With the revival of interest in identity-based (ID-based) cryptography, there have been many new ID-based key exchange protocols proposed. Despite the fact that some of them have been proven in some restricted versions of a model proposed by Bellare and Rogaway in 1993 and some others have been proven in the original CK-model, there is no rigorous model specifically for ID-based key exchange security. In particular, forward secrecy against compromised Key Generation Server (KGS-FS) has never been captured even though this notion is more important and stronger than the perfect forward secrecy in ID-based key exchange. For this, we further extend our model to ID-based setting and capture the property of KGS-FS for ID-based key exchange security.
2004
EPRINT
We present a linkable spontaneously anonymous group (LSAG) signature scheme (alternatively known as linkable ring signature scheme) satisfying the following three properties. (1) Anonymity, or signer indistinguishability. (2) Linkability: That two signatures by the same signer can be linked. (3) Spontaneity: No group secret, therefore no group manager or group secret sharing setup. We reduce the security of our scheme to well-known problems under the random oracle model. Using the scheme, we construct a new efficient one-round e-voting system which does not have a registration phase. We also present a new efficient reduction of famous rewind simulation lemma which only relies on elementary probability theory. Threshold extensions of our scheme are also presented.
2004
EPRINT
In a verifiable encryption, an asymmetrically encrypted ciphertext can be publicly verified to be decipherable by a designated receiver while maintaining the semantic security of the message \cite{AsokanShWa98,CamenischDa00,CamenischSh03}. In this paper, we introduce {\em Custodian-Hiding Verifiable Encryption}, where it can be publicly verified that there exists at least one custodian (user), out of a designated group of $n$ custodians (users), who can decrypt the message, while the semantic security of the message and the anonymity of the actual decryptor are maintained. Our scheme is proven secure in the random oracle model. We also introduce two extensions to decryption by a subset of more than one user.
2004
EPRINT
We present an algebraic cryptanalysis of Bresson, et al.'s spontaneous anonymous threshold signature for ad hoc groups. The technique is to reduce a degenerate condition in Lagrange interpolation to an algebraically solvable high-density knapsack problem over $GF(2^\ell)$. We repair their protocol by revisiting and updating Cramer, et al.'s result on spontaneous anonymous threshold proof-of-knowledge (partial proof-of-knowledge). We generalize their proof by removing two assumptions, and reduce its security to a new candidate hard problem, PoK-Collision, in the random oracle model. To add to the urgency of our update, we present major versions of major PoK schemes that do not satisfy their special soundness assumption.
2004
EPRINT
A ring signature scheme is a group signature scheme with no group manager to setup a group or revoke a signer. A linkable ring signature, introduced by Liu, et al. \cite{LWW04}, additionally allows anyone to determine if two ring signatures are signed by the same group member (a.k.a. they are \emph{linked}). In this paper, we present the first separable linkable ring signature scheme, which also supports an efficient thresholding option. We also present the security model and reduce the security of our scheme to well-known hardness assumptions. In particular, we introduce the security notions of {\em accusatory linkability} and {\em non-slanderability} to linkable ring signatures. Our scheme supports `event-oriented'' linking. Applications to such linking criterion is discussed.
2001
ASIACRYPT

Asiacrypt 2014
Eurocrypt 2012
PKC 2010