Provable Security

Despite the fact that industry continues to rate confidentiality protection as the least important security goal for a commercial organisation, the cryptographic community has a fascination with developing new encryption technologies. It often seems that the majority of advances in general cryptologic theory are a result of research designed to improve our ability to transmit messages confidentially.

The development of security models are a good example of this phenomenon. The earliest attempts to produce cryptographic schemes with some provable security guarantees centred on encryption technologies (Shannon 1949; Rabin 1979). The modern security model for confidentiality dates back to the early eighties (Goldwasser–Micali 1982; Goldwasser–Micali 1984) when the notion of indistinguishability under chosen plaintext attacks (IND-CPA) was proposed. This was followed by the more advanced notions of IND-CCA1 security (Naor–Yung 1990) and IND-CCA2 security (Rackoff–Simon 1991) which are now so ubiquitous that they are often applied to new cryptographic primitives without thought. Many people have forgotten that the elegant notion of IND-CCA2 security is a simplification of the much more complex notion of semantic security.

In this invited talk, we’ll consider the bedrock of cryptographic confidentiality: the notion of IND-CCA2 security. We’ll show by a series of examples that the simplifications that can be obtained in deriving the indistinguishability security notion from the semantic security notion for public key encryption can’t always be derived for other types of public-key cryptography. For example,

Our ultimate aim will be to define a general model and set of rules for deriving a security notion for confidentiality for an arbitrary public-key primitive.

Rigorous proofs are notoriously difficult to produce and verify even for seemingly simple cryptographic tasks. As a result, many published papers contain proofs that are most of the time incomplete and ocasionally flawed. Arguably, this indicates that the provable security paradigm is heading towards an undesirable crisis of rigor.

Significant research efforts are under way in order to correct this state of affairs. Examples, from the inside of the crypto community, include the works of Shoup, Bellare, and Rogaway on game playing techniques and Shai Halevi manifesto for machine assisted cryptographic proofs. Further inspiration comes from the outside of the crypto community. Symbolic methods and techniques commonly used in the areas of programming languages, language-based security, and logics have recently been employed to create general frameworks for computational security analysis.

The goal of this talk is to highlight the important role that symbolic methods could/should play within the general direction of provable security. I will present some of the existent results, exciting opportunities, and future challenges that stem from bringing together two research directions that for more than twenty years have developed largely indpendently.

Spatial encryption was first proposed by Boneh and Hamburg. They showed that many useful encryption systems can be derived from it. In this paper, we describe two variants of spatial encryption. First we present a scheme that can be proved to be secure under the decisional bilinear Diffie-Hellman assumption, which is much simpler than the BDHE assumption used by Boneh and Hamburg. However, as a compromise, our ciphertext size and private key size are larger. We also discuss some techniques to shrink the private key of this scheme in a real application. Finally, we provide a hybrid construction which allows an optimal tradeoff between efficiency and security.

This paper explains how to design fully secure RSA-type cryptosystems from schemes only secure against passive attacks, in the standard model. We rely on instance-independence assumptions, which, roughly speaking, conjecture that for certain problems, an interactive access to a solver for another problem does not help the challenger. Previously, instance-independence assumptions were used in a “negative” way, to prove that certain schemes proven in the random oracle model were not provable in the standard model.

Our paradigm applies virtually to all (weakly secure) RSA-type encryption schemes for which public-key RSA exponent can be arbitrarily chosen. As an illustration, we present a chosen-ciphertext secure variant of the Naccache-Stern encryption scheme.

A proxy re-encryption scheme enables a proxy to re-encrypt a ciphertext under a delegator’s public-key and designate it to a delegatee. Weng et al. introduced the notion of conditional proxy re-encryption (or C-PRE, for short), whereby only the ciphertext satisfying one condition set by the delegator can be transformed by the proxy and then decrypted by delegatee. Nonetheless, they left an open problem on how to construct CCA-secure C-PRE schemes with anonymity. In this paper, we first formalize the notion of anonymous condition CCA-secure PRE and present a respective security model. Then, we answer the question posed by Weng et al. affirmatively by presenting a new and efficient construction of anonymous conditional proxy re-encryption (C-PRE) scheme without requiring random oracle.

Signcryption is a cryptographic primitive that provides authentication and confidentiality simultaneously in a single logical step. It is often required that multiple senders have to signcrypt a single message to a certain receiver. Obviously, it is inefficient to signcrypt the messages separately. An efficient alternative is to go for multi-signcryption. The concept of multi-signcryption is similar to that of multi-signatures with the added property - confidentiality. Recently, Jianhong et al. proposed an identity based multi-signcryption scheme. They claimed that their scheme is secure against adaptive chosen ciphertext attack and it is existentially unforgeable. In this paper, we show that their scheme is not secure against chosen plaintext attack and is existentially forgeable, we also provide a fix for the scheme and prove formally that the improved scheme is secure against both adaptive chosen ciphertext attack and existential forgery.

Fair exchange protocol plays an important role in electronic commerce in the case of exchanging digital contracts. Verifiably encrypted signatures provide an optimistic solution to these scenarios with an off-line trusted third party. In this paper, we propose an identity-based verifiably encrypted signature scheme. The scheme is non-interactive to generate verifiably encrypted signatures and the resulting encrypted signature consists of only four group elements. Based on the computational Diffie-Hellman assumption, our scheme is proven secure without using random oracles. To the best of our knowledge, this is the first identity-based verifiably encrypted signature scheme provably secure in the standard model.

It is a challenging task to construct a signature that it can be tightly reduced to a weak security assumption in the standard model. In this paper, we introduce a simple chameleon-hash-based transformation and show that it can tighten a security reduction of a signature scheme that suffers from a loose security reduction. Taking the Waters’ signature from Eurocrypt 2005 as an example, we demonstrate an improvement of the security reduction that the probability of success in the security reduction can be made as a constant and independent of the signature queries from an adversary. Our reduction methodology has never been considered in the literature and is applicable to many signature schemes such as identity-based signature schemes, online/offline signatures, and signatures with strong unforeability.

In this paper, we revisit the twin signature scheme by Naccache, Pointcheval and Stern from CCS 2001 that is secure under the Strong RSA (SRSA) assumption and improve its efficiency in several ways. First, we present a new twin signature scheme that is based on the Strong Diffie-Hellman (SDH) assumption in bilinear groups and allows for very short signatures and key material. A big advantage of this scheme is that, in contrast to the original scheme, it does not require a computationally expensive function for mapping messages to primes. We prove this new scheme secure under adaptive chosen message attacks. Second, we present a modification that allows to significantly increase efficiency when signing long messages. This construction uses collision-resistant hash functions as its basis. As a result, our improvements make the signature length independent of the message size. Our construction deviates from the standard hash-and-sign approach in which the hash value of the message is signed in place of the message itself. We show that in the case of twin signatures, one can exploit the properties of the hash function as an integral part of the signature scheme. This improvement can be applied to both the SRSA based and SDH based twin signature scheme.

At FOCS 2003, Goldwasser and Kalai showed the insecurity of the digital signature schemes obtained by the Fiat-Shamir transformation in the standard model. However, the proof of this negative result is complicated. This paper shows a much simpler counter example in the restricted (but realistic) case that the hash functions are designed by iterating an underlying hash function with an a-priori bounded input length, although we slightly extend the Fiat-Shamir paradigm. The result in [19] ruled out the case that the underlying identification schemes are interactive proofs, whereas this result can apply to the case.

On-line/Off-line signatures are useful in many applications where the signer has a very limited response time once the message is presented. The idea is to perform the signing process in two phases. The first phase is performed off-line before the message to be signed is available and the second phase is performed on-line after the message to be signed is provided. Recently, in CT-RSA 2009, Gao et al. made a very interesting observation that most of the existing schemes possess the following structure. In the off-line phase, a partial signature, called the off-line token is computed first. Upon completion of the on-line phase, the off-line token constitutes part of the full signature. They considered the “off-line token exposure problem” in which the off-line token is exposed in the off-line phase and introduced a new model to capture this scenario. While intuitively the new requirement appears to be a stronger notion, Gao et al. cannot discover a concrete attack on any of the existing schemes under the new model. They regard clarifying the relationship between the models as an open problem. In this paper, we provide an affirmative answer to this open problem. We construct an On-line/Off-line signature scheme, which is secure under the ordinary security model whilst it is insecure in the new model. Specifically, we present a security proof under the old model and a concrete attack of the scheme under the new model. This illustrates that the new model is indeed stronger.

This paper presents a (PKI-based) two-pass authenticated key exchange (AKE) protocol that is secure in the extended Canetti-Krawczyk (eCK) security model. The security of the proposed protocol is proven without random oracles (under three assumptions), and relies on no implementation techniques such as a trick by LaMacchia, Lauter and Mityagin (so-called the NAXOS trick). Since an AKE protocol that is eCK-secure under a NAXOS-like implementation trick will be no more eCK-secure if some realistic information leakage occurs through side-channel attacks, it has been an important open problem how to realize an eCK-secure AKE protocol without using the NAXOS tricks (and without random oracles).

A great deal of password authenticated key exchange (PAKE) protocols have been proposed in recent years. Most of them were based on Diffie-Hellman key exchange. While the approach of designing PAKE protocols with RSA is far from maturity and perfection. In fact, the existing PAKE protocols using RSA or other public-key cryptographic techniques provide an authenticated key exchange only between a client and a server. This paper presents a new efficient PAKE protocol using RSA in the three-party settings (3PAKE-RSA). The novel protocol can be resistant to e-residue attack and provably secure under the RSA assumption in the random oracle model.

Both the “eCK” model, by LaMacchia, Lauter and Mityagin, and the “CK01” model, by Canetti and Krawczyk, address the effect of leaking session specific ephemeral data on the security of key establishment schemes. The CK01-adversary is given a SessionStateReveal query to learn session-specific private data defined by the protocol specification, whereas the eCK-adversary is equipped with an EphemeralKeyReveal query to access all ephemeral private input required to carry session computations. SessionStateReveal cannot be issued against the test session; by contrast EphemeralKeyReveal can be used against the test session under certain conditions. On the other hand, it is not obvious how EphemeralKeyReveal compares to SessionStateReveal. Thus it is natural to ask which model is more useful and practically relevant.

While formally the models are not comparable, we show that recent analyses utilizing SessionStateReveal and EphemeralKeyReveal have a similar approach to ephemeral data leakage. First we pinpoint the features that determine the approach. Then by examining common motives for ephemeral data leakage we conclude that the approach is meaningful, but does not take into account timing, which turns out to be critical for security. Lastly, for Diffie-Hellman protocols we argue that it is important to consider security when discrete logarithm values of the outgoing ephemeral public keys are leaked and offer a method to achieve security even if these values are exposed.

We propose zero-knowledge and proof-of-knowledge protocols for NTRU. One is for the relation on secret-key knowledge and the other for that on plaintext knowledge. They are the first non-trivial constructions of these protocols for NTRU. Additionally, the former directly yields an identification scheme based on NTRU.

We present a threshold identity-based authenticated key exchange protocol that can be applied to an authenticated server-controlled gateway-user key exchange. The objective is to allow a user and a gateway to establish a shared session key with the permission of the back-end servers, while the back-end servers cannot obtain any information about the established session key. Our protocol has potential applications in strong access control of confidential resources. In particular, our protocol possesses the semantic security and demonstrates several highly-desirable security properties such as key privacy and transparency. We prove the security of the protocol based on the Bilinear Diffie-Hellman assumption in the random oracle model.

Oracle separation methods are used in cryptography to rule out black-box reductions between cryptographic primitives. It is sufficient to find an oracle relative to which the base primitive exists but there are no secure instances of the constructed primitive. In practice, it is beyond our current reach to construct a fixed oracle with such properties for most of the reductions because it is difficult to guarantee the existence of secure base primitives. For example, to show that there exist no black-box reductions from collision-free functions to one-way permutations we have to show that secure one-way permutations exist relative to the oracle. However, no deterministic constructions for unconditionally secure one-way permutations are known yet. To overcome this gap, randomized oracles are used to create random base primitives that are secure on average. After that, a fixed oracle with the desired properties is extracted from the probability distribution by using non-constructive combinatorial arguments such as the first Borel-Cantelli lemma. This oracle extraction argument only applies to uniform reductions because it uses the countability of the set of all uniform Turing machines. In this work, we show how to adapt oracle separation results to the non-uniform security model. We consider the known separation techniques that are capable of ruling out the so-called fully black-box reductions and show that they can be extended to the non-uniform model with only minor modifications. As almost all separation results known to date fit into our separation framework, we conclude that they imply non-existence of fully black-box reductions in the non-uniform model. We also generalize our approach to a certain strong form of semi-black-box reductions. However, it stays an open question whether it is possible to adapt our technique to the weaker notions of black-box reductions in the non-uniform model.

Secure set-intersection computation is one of the important problems in secure multiparty computation. We propose a general protocol construction for secure 2-party set-intersection computation based-on the anonymous IBE scheme and its user private-keys blind generation techniques. Compared with related works, this construction is provably GUC (generalized universally composable) secure in standard model with acceptable efficiency. In addition, an efficient instantiation based-on the Boyen-Waters IBE scheme is also presented.

Towards instantiating the concept, we formalize a model on self- enforcing private inference control, and propose a concrete provably secure scheme, based on Woodruff and Staddon’s work. In our construction, “penalty” is instantiated to be a deprivation of users’ access privilege: so long as a user makes an inference-enabling query, his access privilege is forfeited and he is rejected to query the database any further. We also discuss several important issues that complement and enhance the basic scheme.