## CryptoDB

### Willy Susilo

#### Publications

Year
Venue
Title
2020
ASIACRYPT
Public key encryption (PKE) schemes are usually deployed in an open system with numerous users. In practice, it is common that some users are corrupted. A PKE scheme is said to be receiver selective opening (RSO) secure if it can still protect messages transmitted to uncorrupted receivers after the adversary corrupts some receivers and learns their secret keys. This is usually defined by requiring the existence of a simulator that can simulate the view of the adversary given only the opened messages. Existing works construct RSO secure PKE schemes in a single-challenge setting, where the adversary can only obtain one challenge ciphertext for each public key. However, in practice, it is preferable to have a PKE scheme with RSO security in the multi-challenge setting, where public keys can be used to encrypt multiple messages. In this work, we explore the possibility for achieving PKE schemes with receiver selective opening security in the multi-challenge setting. Our contributions are threefold. First, we demonstrate that PKE schemes with RSO security in the single-challenge setting are not necessarily RSO secure in the multi-challenge setting. Then, we show that it is impossible to achieve RSO security for PKE schemes if the number of challenge ciphertexts under each public key is a priori unbounded. In particular, we prove that no PKE scheme can be RSO secure in the $k$-challenge setting (i.e., the adversary can obtain $k$ challenge ciphertexts for each public key) if its secret key contains less than $k$ bits. On the positive side, we give a concrete construction of PKE scheme with RSO security in the $k$-challenge setting, where the ratio of the secret key length to $k$ approaches the lower bound 1.
2017
CRYPTO
2016
ASIACRYPT
2016
ASIACRYPT
2015
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2012
PKC
2010
PKC
2010
FSE
2010
EPRINT
In this paper, we revisit security notions for dedicated-key hash functions, considering two essential theoretical aspects; namely, formal definitions for security notions, and the relationships among them. Our contribution is twofold. First, we provide a new set of enhanced security notions for dedicated-key hash functions. The provision of this set of enhanced properties has been motivated by the introduction of enhanced target collision resistance (eTCR) property by Halevi and Krawczyk at Crypto 2006. We notice that the eTCR property does not belong to the set of the seven security notions previously investigated by Rogaway and Shrimpton at FSE 2004, namely: Coll, Sec, aSec, eSec, Pre, aPre and ePre. The fact that eTCR, as a new useful property, is the enhanced variant of the well-known TCR (a.k.a. eSec or UOWHF) property motivates one to investigate the possibility of providing enhanced variants for the other properties. We provide such an enhanced set of properties. Interestingly, there are six enhanced variants of security notions available, excluding ePre'' which can be demonstrated to be non-enhanceable. As the second and main part of our contribution, we provide a full picture of relationships (i.e. implications and separations) among the (thirteen) security properties including the (six) enhanced properties and the previously considered seven properties. The implications and separations are supported by formal proofs (reductions) and/or counterexamples in the concrete-security framework.
2009
EUROCRYPT
2009
FSE
2009
EPRINT
Enhanced Target Collision Resistance (eTCR) property for a hash function was put forth by Halevi and Krawczyk in Crypto 2006, in conjunction with the randomized hashing mode that is used to realize such a hash function family. eTCR is a strengthened variant of the well-known TCR (or UOWHF) property for a hash function family (i.e. a dedicated-key hash function). The contributions of this paper are twofold. First, we compare the new eTCR property with the well-known collision resistance (CR) property, where both properties are considered for a dedicated-key hash function. We show there is a separation between the two notions, that is, in general, eTCR property cannot be claimed to be weaker (or stronger) than CR property for any arbitrary dedicated-key hash function. Second, we consider the problem of eTCR property preserving domain extension. We study several domain extension methods for this purpose, including (Plain, Strengthened, and Prefix-free) Merkle-Damg{\aa}rd, Randomized Hashing (considered in dedicated-key hash setting), Shoup, Enveloped Shoup, XOR Linear Hash (XLH), and Linear Hash (LH) methods. Interestingly, we show that the only eTCR preserving method is a nested variant of LH which has a drawback of having high key expansion factor. Therefore, it is interesting to design a new and efficient eTCR preserving domain extension in the standard model.
2008
PKC
2008
EPRINT
In this paper, we propose two new certificate-based signature (CBS) schemes with new features and advantages. The first one is very efficient as it does not require any pairing computation and its security can be proven using Discrete Logarithm assumption in the random oracle model. We also propose another scheme whose security can be proven in the standard model without random oracles. To the best of our knowledge, these are the \emph{first} CBS schemes in the literature that have such kind of features.
2008
EPRINT
We propose a new variant of the Cramer-Shoup KEM (key encapsulation mechanism). The proposed variant is more efficient than the original Cramer-Shoup KEM scheme in terms of public key size and encapsulation cost, but is proven to be (still) secure against chosen ciphertext attack in the standard model, relative to the Decisional Diffie-Hellman problem.
2008
ASIACRYPT
2008
EPRINT
$k$-times anonymous authentication ($k$-TAA) schemes allow members of a group to be authenticated anonymously by application providers for a bounded number of times. Dynamic $k$-TAA allows application providers to independently grant or revoke users from their own access group so as to provide better control over their clients. In terms of time and space complexity, existing dynamic $k$-TAA schemes are of complexities O($k$), where $k$ is the allowed number of authentication. In this paper, we construct a dynamic $k$-TAA scheme with space and time complexities of $O(log(k))$. We also outline how to construct dynamic $k$-TAA scheme with a constant proving effort. Public key size of this variant, however, is $O(k)$. We then describe a trade-off between efficiency and setup freeness of AP, in which AP does not need to hold any secret while maintaining control over their clients. To build our system, we modify the short group signature scheme into a signature scheme and provide efficient protocols that allow one to prove in zero-knowledge the knowledge of a signature and to obtain a signature on a committed block of messages. We prove that the signature scheme is secure in the standard model under the $q$-SDH assumption. Finally, we show that our dynamic $k$-TAA scheme, constructed from bilinear pairing, is secure in the random oracle model.
2007
PKC
2007
EPRINT
In this paper we construct two new fuzzy identity-based encryption (IBE) schemes in the random oracle model. Not only do our schemes provide public parameters whose size is independent of the number of attributes in each identity (used as public key) but they also have useful structures which result in more e±cient key extraction and/or encryption than the random oracle version of Sahai and Water's fuzzy IBE scheme, considered recently by Pirretti et al. We prove that the confidentiality of the proposed schemes is relative to the Bilinear Decisional Bilinear Diffie-Hellman problem.
2007
EPRINT
We propose a convertible undeniable signature scheme without random oracles. Our construction is based on Waters' and Kurosawa and Heng's schemes that were proposed in Eurocrypt 2005. The security of our scheme is based on the CDH and the decision linear assumption. Comparing only the part of undeniable signatures, our scheme uses more standard assumptions than the existing undeniable signatures without random oracles due to Laguillamie and Vergnaud.
2007
EPRINT
Anonymity is one of the main concerns in group-oriented cryptography. However, most efforts, for instance, group signatures and ring signatures, are only made to provide anonymity on the sender's point of view. There is only a few work done to ensure anonymity in a cryptographic sense on the recipient's point of view n group-oriented communications. In this paper, we formalize the notion of group decryptions. It can be viewed as an analogousof group signatures in the context of public key encryptions. In this notion, a sender can encrypt a committed message intended to any member of a group, managed by a group manager, while the recipient of the ciphertext remains anonymous. The sender can convince a verifier about this fact without leaking the plaintext or the identity of the recipient. If required, the group manager can verifiably open the identity of the recipient. We propose an efficient group decryption scheme that is proven secure in the random oracle model. The overhead in both computation and communication is independent of the group size. A full ciphertex is about 0.2K bytes in a typical implementation and the scheme is practical to protect the recipient identity in privacy-sensitive group-oriented communications.
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
Compact e-cash schemes allow a user to withdraw a wallet containing $k$ coins in a single operation, each of which the user can spend unlinkably. One big open problem for compact e-cash is to allow multiple denominations of coins to be spent efficiently without executing the spend protocol a number of times. In this paper, we give a (\emph{partial}) solution to this open problem by introducing two additional protocols, namely, compact spending and batch spending. Compact spending allows spending all the $k$ coins in one operation while batch spending allows spending any number of coins in the wallet in a single execution. We modify the security model of compact e-cash to accommodate these added protocols and present a generic construction. While the spending and compact spending protocol are of constant time and space complexities, complexities of batch spending is linear in the number of coins to be spent together. Thus, we regard our solution to the open problem as {\it partial}. We provide two instantiations under the $q$-SDH assumption and the LRSW assumption respectively and present security arguments for both instantiations in the random oracle model.
2007
EPRINT
We present an efficient off-line divisible e-cash scheme which is \emph{truly anonymous} without a trusted third party. This is the second scheme in the literature which achieves full unlinkability and anonymity, after the seminal work proposed by Canard and Gouget. The main trick of our scheme is the use of a bounded accumulator in combination with the classical binary tree approach. The aims of this paper are twofold. Firstly, we analyze Canard and Gouget's seminal work on the efficient off-line divisible e-cash. We point out some subtleties on the parameters generation of their scheme. Moreover, spending a coin of small value requires computation of several hundreds of multi-based exponentiations, which is very costly. In short, although this seminal work provides a new approach of achieving a truly anonymous divisible e-cash, unfortunately it is rather impractical. Secondly, we present our scheme that uses a novel approach of incorporating a bounded accumulator. In terms of time and space complexities, our scheme is $50$ to $100$ times more efficient than Canard and Gouget's work in the spend protocol at the cost of an $10$ to $500$ (the large range is due to whether pre-processing is taken into account and the probabilistic nature of our withdrawal protocol) times less efficient withdrawal protocol. We believe this trade-off between the withdrawal protocol and the spend protocol is reasonable as the former protocol is to be executed much less frequent than the latter. Nonetheless, while their scheme provides an affirmative answer to whether divisible e-cash can be \emph{truly anonymous}, our result puts it a step further and we show that truly anonymous divisible e-cash can be \emph{practical}.
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
The notion of concurrent signatures was recently introduced by Chen, Kudla and Paterson. In concurrent signature schemes, two entities can produce two signatures that are not binding, until an extra piece of information (namely the keystone) is released by one of the parties. Subsequently, it was noted that the concurrent signature scheme proposed in the seminal paper cannot provide perfect ambiguity. Then, the notion of perfect concurrent signatures was introduced. In this paper, we define the notion of identity-based (or ID-based) perfect concurrent signature schemes. We provide the first generic construction of (ID-based) perfect concurrent signature schemes from ring signature schemes. Using the proposed framework, we give two concrete ID-based perfect concurrent signature schemes based on two major paradigms of ID-based ring signature schemes. Security proofs are based on the random oracle model.
2006
EPRINT
Certificateless Public Key Cryptography (CL-PKC) enjoys a number of features of Identity-Based Cryptography (IBC) while without having the problem of key escrow. However, it \textit{does} suffer to an attack where the adversary, Carol, replaces Alice's public key by someone's public key so that Bob, who wants to send an encrypted message to Alice, uses Alice's identity and other's public key as the inputs to the encryption function. As a result, Alice cannot decrypt the message while Bob is unaware of this. We call it \textit{Denial-of-Decryption (DoD) Attack} as its nature is similar to the well known Denial-of-Service (DoS) Attack. Based on CL-PKC, we propose a new paradigm called \textit{Self-Generated-Certificate Public Key Cryptography (SGC-PKC)} that captures the DoD Attack. We also provide a generic construction of a self-generated-certificate public key encryption scheme in the standard model. Our generic construction uses certificateless signature and certificateless encryption as the building block. In addition, we further propose a certificateless signature and a certificateless encryption scheme with concrete implementation that are all provably secure in the standard model, which are the first in the literature regardless of the generic constructions by Yum and Lee which may contain security weaknesses as pointed out by others. We believe these concrete implementations are of independent interest.
2005
ASIACRYPT
2005
PKC
2005
EPRINT
Group signature schemes allow a member of a group to sign messages anonymously on behalf of the group. In the case of later dispute, a designated group manager can revoke the anonymity and identify the originator of a signature. In Asiacrypt 2004, Nguyen and Safavi-Naini proposed a group signature scheme that has a constant-size public key and signature length, and more importantly, their group signature scheme does not require trapdoor. Their scheme is very efficient and the sizes of signatures are shorter compared to the existing schemes that were proposed earlier. In this paper, we point out that Nguyen and Safavi-Naini's scheme is insecure. In particular, we provide a cryptanalysis of the scheme that allows a non-member of the group to sign on behalf of the group. The resulting group signature can convince any third party that a member of the group has indeed generated such a signature, although none of the members has done it. Therefore, in the case of dispute, the group manager cannot identify who has signed the message. We also provide a new scheme that does not suffer against this problem.
2005
EPRINT
The public key encryption with keyword search (PEKS) scheme recently proposed by Boneh, Di Crescenzo, Ostrovsky, and Persiano enables one to search encrypted keywords without compromising the security of the original data. In this paper, we address three important issues of a PEKS scheme, refreshing keywords'', removing secure channel'', and processing multiple keywords'', which have not been considered in Boneh et. al.'s paper. We argue that care must be taken when keywords are used frequently in the PEKS scheme as this situation might contradict the security of PEKS. We then point out the inefficiency of the original PEKS scheme due to the use of the secure channel. We resolve this problem by constructing an efficient PEKS scheme that removes secure channel. Finally, we propose a PEKS scheme that encrypts multiple keywords efficiently.
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.
2004
PKC
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
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.
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.

Asiacrypt 2020
Asiacrypt 2013
Asiacrypt 2011
Asiacrypt 2010