Provable Security

This paper proposes a new generalized ElGamal public key encryption scheme based on a new Diffie-Hellman problem, so-called EDDH problem, which DDH problem can be reduced to. This scheme is one-way if and only if ECDH assumption holds and it is semantically secure in the standard model if and only if EDDH assumption holds. Since EDDH assumption still holds for generic bilinear groups, this encryption scheme adds to the growing toolkit of provable security primitives that can be used by the protocol designer looking to build complex secure systems with a sound basis.

Tweakable pseudorandom permutations have wide applications such as the disk sector encryption, and the underlying primitive for efficient MACs and authenticated encryption schemes. Goldenberg et al. showed constructions of a tweakable pseudorandom permutation based on the Feistel structure. In this paper, we explore the possibility of designing tweakable pseudorandom permutations based on the Generalized Feistel Structure. We show that tweakable pseudorandom permutations can be obtained without increasing the number of rounds compared to the non-tweakable versions. We also present designs that take multiple tweaks as input.

Timed-release encryption (TRE) is a two-factor encryption scheme combining public key encryption and time-dependent encryption – decryption requires a trapdoor which is kept confidential by a time-server until at an appointed time. This paper revisits two recent results.

Certificateless cryptography aims at combining the advantages of identity based and public key cryptography, so as to avoid the key escrow problem inherent in the identity based system and cumbersome certificate management in public key infrastructure. Signcryption achieves confidentiality and authentication simultaneously in an efficient manner. Multi-receiver signcryption demands signcrypting the same message efficiently for a large number of receivers. In this paper, we propose the first efficient certificateless multi-receiver signcryption scheme and prove it secure in the random oracle model. Our scheme does not require pairing to signcrypt a message for any number of receivers. We are considering a more realistic adversarial model and proving the security against insider attacks, which guarantees non-repudiation and forward secrecy.

ElGamal encryption, by its efficiency, is one of the most used schemes in cryptographic applications. However, the original ElGamal scheme is only provably secure against passive attacks. Damgård proposed a slight modification of ElGamal encryption scheme (named Damgård’s ElGamal scheme) that provides security against non-adaptive chosen ciphertext attacks under a knowledge-of-exponent assumption. Recently, the CCA1-security of Damgård’s ElGamal scheme has been proven under more standard assumptions.

In this paper, we study the open problem of CCA2-security of Damgård’s ElGamal. By employing a data encapsulation mechanism, we prove that the resulted hybrid Damgård’s ElGamal Encryption is secure against adaptive chosen ciphertext attacks. The down side is that the proof of security is based on a knowledge-of-exponent assumption. In terms of efficiency, this scheme is more efficient (e.g. one exponentiation less in encryption) than Kurosawa-Desmedt scheme, the most efficient scheme in the standard model so far.

Forward secure signatures are proposed to deal with the key exposure problem. Compared to regular signatures, forward secure signatures can protect the security of signatures previous to the time period of key exposure. The efficiency is an important issue of forward secure signatures. In this paper, we construct yet another forward secure signature scheme using bilinear maps. In this scheme, all performance parameters have complexities of log magnitude in terms of the total time periods. In addition, our scheme needs very few pairing operations in verifying algorithm, which is very important because the pairing operation is very time-consuming. At last, we prove that our scheme is forward secure in random oracle model assuming CDH problem is hard.

We propose a novel notion of signature named Optimal Online/Offline Signature. The new notion can be seen as an extension to the notion of online/offline signature, where our signature scheme allows all necessary computations to be carried out in the offline phase before the message is available and the signer does not need to conduct any computation to construct the final signature in the online phase. Although the same feature can be achieved from a one-time signature scheme, the large signature size of a one-time signature is a disadvantage. In this paper, we provide a solution that allows our signature to be aggregated into a short length (about 320 bits); hence it demonstrates a better applicability. We also give a generic construction and then extend it to an identity-based scenario.

We present a round-optimal blind signature scheme based on Waters’ signature scheme. Our construction resembles that of Fischlin [10], but does not rely on generic non-interactive zero-knowledge proofs. In addition to a common reference string, our scheme requires a registered public key for the signer.

In electronic world, proxy signature is a solution of delegation of signing capabilities. Proxy multi-signature schemes allow a proxy signer to generate a proxy signature on behalf of two or more original signers. However, the security of the known proxy multi-signature schemes is proven in the random oracle which does not imply security in the real world. In this paper, we present a proxy multi-signature scheme in the standard model. The size of a proxy multi-signature is independent of the number of the original signers. Our scheme is existentially unforgeable against chosen message attack and chosen warrant attack based on the hardness of the well known CDH problem in the standard model.

A server-aided verification signature scheme consists of a digital signature scheme and a server-aided verification protocol. By executing the server-aided verification protocol with the server, one can perform the verification of signatures with less computational cost compared to the original verification algorithm. This mechanism is therefore indispensable for low-power devices such as smart cards. The contributions of this paper are manyfold. Firstly, we introduce and define the existential unforgeability of server-aided verification signatures. We prove that the new notion includes the existing security requirements in server-aided verification signatures. Then, we analyze the Girault-Lefranc scheme in Asiacrypt 2005 and show that their scheme can be made secure in our model, but the computational cost is more than the claimed in the original scheme. After that, we propose the first server-aided verification BLS, which is existentially unforgeable in the random oracle model under the Bilinear Diffie-Hellman assumption. Finally, we consider the collusion and adaptive chosen message attack in server-aided verification signatures. For the first time in the literature, the security of server-aided verification signatures against such attacks is defined. We provide a concrete construction of a server-aided verification BLS secure against the collusion and chosen message attack.

Direct anonymous attestation (DAA) is a mechanism for a remote user to provide a verifier with some assurance it is using software and/or hardware from trusted sets of software and/or hardware respectively. In addition, the user is able to control if and when a verifier is able to link two signatures: to determine whether or not they were produced by the same platform. The verifier is never able to tell which which particular platform produced a given signature or pair of signatures.

We first address a problem with the proof of security for the original DAA scheme of Brickell, Camenisch and Chen. In particular, we construct an adversary that can tell if its in a simulation or not. We then provide the necessary changes to the simulator such that the adversary can no longer do this and prove this fact, hence repairing the proof.

Our main contribution is a security analysis of the Chen, Morrissey and Smart (CMS) DAA scheme. This scheme uses asymmetric bilinear pairings and was proposed without a proof of security. We use the well established simulation based security model of Brickell, Camenisch and Chen and also use a similar proof technique to theirs. We prove the CMS scheme is secure in the random oracle model relative to the bilinear Lysyanskaya, Rivest, Sahai and Wolf (LRSW) assumption, the hardness of discrete logarithms in the groups used and collision resistance of the hash functions used in the scheme.

D. L. Vo and K. Kim proposed a forward secure signature scheme from bilinear pairings in annual International Conference on Information Security and Cryptology 2005. They claimed that their scheme satisfies several merits including requiring the general security parameters only independent to the total number of time periods and performing key evolving for unlimited time periods while maintaining sizes of keys and signature fixed. They also claimed this scheme is forward secure under the assumption of computational Diffie-Hellman problem. In this paper, we analyze the security of this scheme and point out this scheme doesn’t satisfy the forward security.

Recently, many approaches have been proposed for building simple symbolic proofs of cryptographic protocols with computational soundness. However, most of them support only bare-bone execution model without any ideal setup, such as the existence of authenticated channel, and only deterministic protocols. Thus many protocols are not expressible in those models. Following the work of Canetti and Herzog [1], we propose a probabilistic symbolic model for analyzing cryptographic protocols and a general way of incorporating ideal setups by using a probabilistic process calculus. Each ideal setup in the symbolic model will correspond to an ideal functionality in the computational model. Furthermore, we show the computational faithfulness of this symbolic model with respect to a hybrid computational model in which ideal functionalities are employed.

Different models formalizing the notion of generic groups have been proposed in the literature. Although all models aim to capture the same notion, it is not obvious that a security proof in one model implies security in the other model. Thus the validity of a proven statement may depend on the choice of the model. In this paper we prove the equivalence of the models proposed by Shoup [2] and Maurer [3].

In this paper,we analyze an identity-based threshold signcryption (IDTSC)scheme proposed in ICCCAS’2008, although Li and Yu pointed out that the scheme is the first provably secure scheme which is secure against adaptive chosen ciphertext attacks and secure in the sense of unforgeability, we show that the signcryption in the scheme is easily forged by the appointed clerk who is one of the members , the clerk can impersonate the members to forge valid signcryption to any receiver, then we give a secure version which we prove its confidentiality under the Decisional Bilinear Diffie-Hellman assumption and its unforgeability under the Computational Diffie-Hellman assumption in the random oracle model. Scheme turns out to be more efficient than the previously proposed schemes.

This work focuses on vulnerability of hash functions due to sloppy usage or implementation in the real world. If our cryptographic research community succeeded in development of perfectly secure random function as random oracle, it might be broken in some sense by invalid uses. In this paper, we propose a new variant of the random oracle model in order to analyze security of cryptographic protocols under the situation of an invalid use of hash functions. Our model allows adversaries to obtain contents of the hash list of input and output pairs arbitrarily. Also, we analyze security of several prevailing protocols (FDH, OAEP, Cramer-Shoup cryptosystem, Kurosawa-Desmedt cryptosystem, NAXOS) in our model. As the result of analyses, we clarify that FDH and Cramer-Shoup cryptosystem are still secure but others are insecure in our model. This result shows the separation between our model and the standard model.

This paper reports a thorough standard-model investigation on how attacks on hash functions impact the security of hash-and-sign signature schemes. We identify two important properties that appear to be crucial in analyzing the nature of security relations between signature schemes and their inner hash functions: primitiveness and injectivity. We then investigate the security relations in the general case of hash-and-sign signatures and in the particular case of first-hash-then-sign signatures, showing a gap of security guarantees between the two paradigms. We subsequently apply our results on two operating modes to construct a hash function family from a hash function based on the well-known Merkle-Damgård construction (such as MD5 and SHA-1). For completeness, we give concrete attack workloads for attacking operating modes used in practical implementations of signature schemes.

It has been known for quite some time that collision-resistance of hash functions does not seem to give any actual security guarantees for unbounded hash-tree time-stamping, where the size of the hash-tree created by the time-stamping service is not explicitly restricted. We focus on the possibility of showing that there exist no black-box reductions of unbounded time-stamping schemes to collision-free hash functions. We propose an oracle that is probably suitable for such a separation and give strong evidence in support of that. However, the existence of a separation still remains open. We introduce the problem and give a construction of the oracle relative to which there seem to be no secure time-stamping schemes but there still exist collision-free hash function families. Although we rule out many useful collision-finding strategies (relative to the oracle) and the conjecture seems quite probable after that, there still remains a possibility that the oracle can be abused by some very smartly constructed wrappers. We also argue why it is probably very hard to give a correct proof for our conjecture.

The relationship of three cryptographic channels, secure channels (SC), anonymous channels (AC) and direction-indeterminable channels (DIC), was investigated by Okamoto. He showed that the three cryptographic channels are reducible to each other, but did not consider communication schedules clearly as well as composable security. This paper refines the relationship of the three channels in the light of communication schedules and composable security. We model parties by the task-probabilistic input/output automata (PIOA) to treat communication schedules, and adopt the universally composable (UC) framework by Canetti to treat composable security. We show that a class of anonymous channels, two-anonymous channels (2AC), and DIC are reducible to each other under any schedule and that DIC and SC are reducible to each other under some types of schedules, in the UC framework with the PIOA model.

Browser-based security protocols perform cryptographic tasks within the constraints of commodity browsers. They are the bearer protocols for many security critical applications on the Internet. Roughly speaking, they are the offspring of key exchange and secure sessions protocols. Although browser-based protocols are widely deployed, their security has not been formally proved. We provide a security model for the analysis of browser-based protocols based on the Universal Composability framework.

Various interesting protocols, for example e-voting, make extensive use of primitives that the library currently does not provide. The library can certainly be extended, and in this paper we provide one such extension — we add threshold homomorphic encryption to the universally composable cryptographic library and demonstrate its usefulness by (re)proving the security of a well-known e-voting protocol.

We present a security analysis of the complete TLS protocol in the Universal Composable security framework. This analysis evaluates the composition of key exchange functionalities realized by the TLS handshake with the message transmission of the TLS record layer to emulate secure communication sessions and is based on the adaption of the secure channel model from Canetti and Krawczyk to the setting where peer identities are not necessarily known prior the protocol invocation and may remain undisclosed. Our analysis shows that TLS, including the Diffie-Hellman and key transport suites in the uni-directional and bi-directional models of authentication, securely emulates secure communication sessions.

In this paper, a round optimal oblivious transfer protocol is proposed and analyzed. Our protocol is built upon the top of an oblivious double-trapdoor encryption scheme (the double-trapdoor information consisting of a master key and a local key). The idea behind our construction is that the master key is used to extract the exact input messages of a corrupted sender (as a result, a simulator designated for the corrupted sender is constructed) while the local key is used to extract the exact input message of a corrupted receiver (as a result, a simulator designated for the corrupted receiver is defined). We show that our protocol is universally composable in the common reference string model assuming that the decisional Diffie-Hellman problem over a squared composite modulus of the form N =pq is hard.

To provide a high level of security guarantee cryptography is introduced into the design of the voting machine. The voting machine based on cryptography is vulnerable to attacks through covert channels. An adversary may inject malicious codes into the voting machine and make it leak vote information unnoticeably by exploiting the randomness used in encryptions and zero-knowledge proofs. In this paper a voting machine resistant to covert channels is designed. It has the following properties: Firstly, it is tamper-evident. The randomness used by the voting machine is generated by the election authority. The inconsistent use of the randomness can be detected by the voter from examining a destroyable verification code. Even if malicious codes are run in the voting machine attacks through subliminal channels are thwarted. Next, it is voter-verifiable. The voter has the ability to verify if the ballot cast by the machine is consistent with her intent without doing complicated cryptographic computation. Finally, the voting system is receipt-free. Vote-buying and coercion are prevented.

In this paper, we analyze an existing constant storage self-healing key distribution scheme in wireless sensor networks. Then, we show two attacks and propose a modified scheme to overcome the two flaws. At last, we propose a new self-healing key distribution scheme to improve the modified scheme. The most prominent properties of the new proposed scheme are as follows: achieving forward and backward secrecy and resisting to a collusion attack. So that a revoked user with the assistance of the newly joined users cannot get any information of group session keys which it is not entitled to get.