Abstract. In this paper, we propose a new notion of timed encryption, in which the encryption is secure within time t while it is totally insecure after some time T> t. We are interested in the case where t and T are both polynomial. We propose a concrete construction that is provably secure in the random oracle model. We show that it can be generically (although inefficient) constructed from a timed commitment of Boneh and Naor (CRYPTO’00). Finally, we apply this primitive to construct a deniable secure key exchange protocol, where the deniability and secrecy both hold adaptively and the adversary can conduct session state reveal attacks and eavesdropping attacks in the non-eraser model. Our protocol is the first to achieve each of the following properties: adaptive deniability admitting eavesdropping attacks and deniability admitting session state reveal attacks in the non-eraser model. Our protocol is constructed using a timing restriction (inherited from the timed encryption). However, the requirement is rather weak. It essentially asks a user to respond to a ciphertext as soon as possible and hence does not artificially cause any delay. Our usage of timed encryption for the deniability is to use the forceful decryption to obtain the plaintext and hence does not use any random oracle assumption (even if the secrecy proof needs this).
Abstract. In this paper, we propose a new notion of timed encryption, in which the encryption is secure within time t while it is totally insecure after some time T> t. We are interested in the case where t and T are both polynomial. We propose a concrete construction that is provably secure in the random oracle model. We show that it can be generically (although inefficient) constructed from a timed commitment of Boneh and Naor (CRYPTO’00). Finally, we apply this primitive to construct a deniable secure key exchange protocol, where the deniability and secrecy both hold adaptively and the adversary can conduct session state reveal attacks and eavesdropping attacks in the non-eraser model. Our protocol is the first to achieve each of the following properties: adaptive deniability admitting eavesdropping attacks and deniability admitting session state reveal attacks in the non-eraser model. Our protocol is constructed using a timing restriction (inherited from the timed encryption). However, the requirement is rather weak. It essentially asks a user to respond to a ciphertext as soon as possible and hence does not artificially cause any delay. Our usage of timed encryption for the deniability is to use the forceful decryption to obtain the plaintext and hence does not use any random oracle assumption (even if the secrecy proof needs this).
Abstract. The primitive of deniable encryption was first introduced by Canetti et al. (CRYPTO, 1997). Deniable encryption is a regular public key encryption scheme with the added feature that after running the protocol honestly and transmitting a message m, both Sender and Receiver may produce random coins showing that the transmitted ciphertext was an encryption of any message m ′ in the message space. Deniable encryption is a key tool for constructing incoercible protocols, since it allows a party to send one message and later provide apparent evidence to a coercer that a different message was sent. In addition, deniable encryption may be used to obtain adaptively-secure multiparty computation (MPC) protocols and is secure under selective-opening attacks. Different flavors such as sender-deniable and receiver-deniable encryption, where only the Sender or Receiver can produce fake random coins, have been considered. Recently, several open questions regarding the feasibility of deniable encryption have been resolved (c.f. (O’Neill et al., CRYPTO, 2011), (Bendlin et al., ASIACRYPT, 2011)). A fundamental remaining open question is whether it is possible to construct sender-deniable Encryption Schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. The primitive of simulatable public key encryption (PKE), introduced by Damg˚ard and Nielsen (CRYPTO, 2000), is a public key encryption scheme with additional properties that allow oblivious sampling of public keys and
Abstract. A deniable cryptosystem allows a sender and a receiver to communicate over an insecure channel in such a way that the communication is still secure even if the adversary can threaten the parties into revealing their internal states after the execution of the protocol. This is done by allowing the parties to change their internal state to make it look like a given ciphertext decrypts to a message di erent from what it really decrypts to. Deniable encryption was in this way introduced to allow to deny a message exchange and hence combat coercion. Depending on which parties can be coerced, the security level, the avor and the number of rounds of the cryptosystem, it is possible to de ne a number of notions of deniable encryption. In this paper we prove that there does not exist any non-interactive receiver-deniable cryptosystem with better than polynomial security. This also shows that it is impossible to construct a non-interactive bi-deniable public-key encryption scheme with better than polynomial security. Speci cally, we give an explicit bound relating the security of the scheme to how e cient the scheme is in terms of key size. Our impossibility result establishes a lower bound on the security. As a nal contribution we give constructions of deniable public-key encryption schemes which establishes upper bounds on the security in terms of key length. There is a gap between our lower and upper bounds, which leaves the interesting open problem of nding the tight bounds. 1
Abstract. Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of alreadycorrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure. Impossibility holds even if secure data erasure is possible. We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about the frequency of communication between parties. Using this approach, we construct adaptively-secure, completely non-interactive encryption schemes supporting secure encryption of arbitrarily-many messages from arbitrarilymany senders. Our schemes additionally provide forward security and security against chosen-ciphertext attacks. 1
Abstract. We extend the definitional work of Dwork, Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE) protocol. The two protocols require distinct approaches to their deniability analysis, hence highlighting important definitional issues as well as necessitating different tools in the analysis. SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME’s deniability is possibly the first “natural ” application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security); in particular this use of plaintext awareness is not tied to the random oracle model. SIGMA, on the other hand, uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, “partial deniability ” property: a party may not be able to deny that it was “alive ” at some point in time but can fully deny the contents of its communications and the identity of its interlocutors. We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.
We extend the definitional work of Dwork,Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE)protocol.SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME's deniability is possibly the first "natural" application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security).SIGMA, on the other hand,uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, "partial deniability" property: a party may not be able to deny that it was "alive" at some point in time but can fully deny the contents of its communications and the identity of its interlocutors.We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.
Abstract. Deniable authentication is a technique that allows one party to send messages to another while the latter can not prove to a third party the fact of communication. In this paper, we first formalize a natural notion of deniable security and naturally extend the basic authenticator theorem by Bellare et al. [2] to the setting of deniable authentication. Of independent interest, this extension is achieved by defining a deniable MT-authenticator via a game. This game is essentially borrowed from the notion of universal composition [8] although we do not assume any result or background about it. Then we construct two deniable MT-authenticators: uncontrollable random oracle based and the PKI based, both of which are just 3-round protocols. The second construction assumes the receiver owns a secret key. Such a setup assumption is very popular in the real world. (Without this assumption), all the previous protocols do not have a widely satisfiable performance when applied in the Internet-like environment. Finally, as our application, we obtain key exchange protocols that is deniably secure in the real world. 1