Invited Talks

Optimal Structure-Preserving Signatures

Abstract

Structure preservation captures the notion of pairing-based schemes that rely on generic group operations and where the components are group elements. Their structural properties make it easy to compose them with other pairing-based schemes.

In this talk, we will take a closer look at structure-preserving signatures. The structure preserving property allows us to analyze the efficiency of signature schemes in the generic group model. Using the generic group model to analyze the efficiency of a cryptographic scheme stands in contrast to the more common usage of the generic group model to rule out certain types of attack. We will show that structure-preserving signatures need to consist of at least 3 group elements.

We also discuss recent constructions of structure-preserving signatures that consist of 3 group elements. These constructions match our lower bounds, thus giving us provably optimal structure-preserving signatures.

Jens Groth

Secure Composition of Cryptographic Protocols

Talk Overview

General positive results for secure computation were obtained more than two decades ago. These results were for the setting where each protocol execution is done in isolation. With the proliferation of the network setting (and especially the internet), an ambitious effort to generalize these results and obtain concurrently secure protocols was started. However it was soon shown that designing secure protocols in the concurrent setting is unfortunately impossible in general. In this talk, we will first describe the so called chosen protocol attack. This is an explicit attack which establishes general impossibility of designing secure protocols in the concurrent setting. The negative results hold for the so called plain model where there is no trusted party, no honest majority, etc.

Vipul Goyal

Cryptographic Primitives

Secure Two-Party Computation over a Z-Channel

Abstract

In secure two-party computation, two mutually distrusting parties are interested in jointly computing a function, while preserving the privacy of their respective inputs. However, when communicating over a clear channel, security against computationally unbounded adversaries is impossible. Thus is the importance of noisy channels, over which we can build Oblivious Transfer (OT), a fundamental primitive in cryptography and the basic building block for any secure multi-party computation. The noisy channels commonly used in current constructions are mostly derived from the Binary Symmetric Channel (BSC), which is modified to extend the capabilities of an attacker. Still, these constructions are based on very strong assumptions, in particular on the error probability, which makes them hard to implement.

In this paper, we provide a protocol achieving oblivious transfer over a Z-channel, a natural channel model in various contexts, ranging from optical to covert communication. The protocol proves to be particularly efficient for a large range of error probabilities p (e.g., for 0.17 ≤ p ≤ 0.29 when a security parameter ε = 10^− 9 is chosen), where it requires a limited amount of data to be sent through the channel. Our construction also proves to offer security against unfair adversaries, who are able to select the channel probability within a fixed range. We provide coding schemes that can further increase the efficiency of the protocol for probabilities distant from the range mentioned above, and also allow the use of a Z-channel with an error probability greater than 0.5. The flexibility and the efficiency of the construction make an actual implementation of oblivious transfer a more realistic prospect.

Paolo Palmieri, Olivier Pereira

Precise Time and Space Simulatable Zero-Knowledge

Abstract

Traditionally, the definition of zero-knowledge states that an interactive proof of x ∈ L provides zero (additional) knowledge if the view of any polynomial-time verifier can be reconstructed by a polynomial-time simulator. Since this definition only requires that the worst-case running-time of the verifier and simulator are polynomials, zero- knowledge becomes a worst-case notion.

In STOC’06, Micali and Pass proposed a new notion of precise zero-knowledge, which captures the idea that the view of any verifier in every interaction can be reconstructed in (almost) the same time (i.e., the view can be “indistinguishably reconstructed”). This is the strongest notion among the known works towards precislization of the definition of zero-knowledge.

However, as we know, there are two kinds of resources (i.e. time and space) each algorithm consumes in computation. Although the view of a verifier in the interaction of a precise zero-knowledge protocol can be reconstructed in almost the same time, the simulator may run in very large space while at the same time the verifier only runs in very small space. In this case it is still doubtful to take indifference for the verifier to take part in the interaction or to run the simulator. Thus the notion of precise zero-knowledge may be still insufficient. This shows that precislization of the definition of zero-knowledge needs further investigation.

In this paper, we propose a new notion of precise time and space simulatable zero-knowledge (PTSSZK), which captures the idea that the view of any verifier in each interaction can be reconstructed not only in the same time, but also in the same space. We construct the first PTSSZK proofs and arguments with simultaneous linear time and linear space precisions for all languages in NP. Our protocols do not use noticeably more rounds than the known precise zero-knowledge protocols.

Ning Ding, Dawu Gu

Weak Oblivious Transfer from Strong One-Way Functions

Abstract

We consider weak oblivious transfer (OT) from strong one-way functions and the paradigm of transforming unconditionally secure protocols in Maurer’s bounded storage model into computational secure protocols in the random oracle model. Weak OT is secure against adversaries which have a quadratic resource gap to honest parties. We prove that the random oracle can be replaced with strong one-way functions in the OT protocol. We construct an OT protocol achieving quadratic security from strong one-way functions.

Keisuke Tanaka, Akihiro Yamada, Kenji Yasunaga

Simulatable Adaptive Oblivious Transfer with Statistical Receiver’s Privacy

Abstract

During an adaptive oblivious transfer (OT), a sender has n private documents, and a receiver can adaptively fetch k documents from them such that the sender learns nothing about the receiver’s selection and the receiver learns nothing more than those k documents. Most recent fully simulatable adaptive OT schemes are based on so-called “assisted decryption” or “blind decryption”. In this paper, we revisit another technique, “blind permute-decryption”, for designing adaptive OT. We propose an efficient generic fully simulatable oblivious transfer framework with statistical receiver’s privacy that based on “blind permute-decryption” together with three concrete installations. The first one is based on Elgamal, so the corresponding OT is secure under classical DDH assumption. The second one is based on Paillier, so the corresponding OT is secure under Decisional n-th Residuosity assumption. Besides, we introduce an extended zero-knowledge proof framework with several applications.

Bingsheng Zhang

Encryption

Verifiable Security of Boneh-Franklin Identity-Based Encryption

Abstract

Identity-based encryption (IBE) allows one party to send ciphered messages to another using an arbitrary identity string as an encryption key. Since IBE does not require prior generation and distribution of keys, it greatly simplifies key management in public-key cryptography. Although the concept of IBE was introduced by Shamir in 1981, constructing a practical IBE scheme remained an open problem for years. The first satisfactory solution was proposed by Boneh and Franklin in 2001 and constitutes one of the most prominent applications of pairing-based cryptography. We present a game-based machine-checked reduction of the security of the Boneh-Franklin IBE scheme to the Bilinear Diffie-Hellman assumption, and analyze its tightness by providing an exact security bound. Our proof simplifies and clarifies the original proof by Boneh and Franklin and can be automatically verified by running a trusted checker.

Gilles Barthe, Federico Olmedo, Santiago Zanella Béguelin

Efficient Ciphertext Policy Attribute-Based Encryption with Constant-Size Ciphertext and Constant Computation-Cost

Abstract

Attribute-based encryption provides good solutions to the problem of anonymous access control by specifying access policies among private keys or ciphertexts over encrypted data. In ciphertext-policy attribute-based encryption (CP-ABE), each user is associated with a set of attributes, and data is encrypted with access structures on attributes. A user is able to decrypt a ciphertext if and only if his attributes satisfy the ciphertext access structure. CP-ABE is very appealing since the ciphertext and data access policies are integrated together in a natural and effective way.

Most current CP-ABE schemes incur large ciphertext size and computation costs in the encryption and decryption operations which depend at least linearly on the number of attributes involved in the access policy. In this paper, we present two new CP-ABE schemes, which have both constant-size ciphertext and constant computation costs for a non-monotone AND gate access policy, under chosen plaintext and chosen ciphertext attacks. The security of first scheme can be proven CPA-secure in standard model under the decision n-BDHE assumption. And the security of second scheme can be proven CCA-secure in standard model under the decision n-BDHE assumption and the existence of collision-resistant hash functions. Our scheme can also be extended to the decentralizing multi-authority setting.

Cheng Chen, Zhenfeng Zhang, Dengguo Feng

Fully Distributed Broadcast Encryption

Abstract

Broadcast encryption schemes rely on a centralized authority to generate decryption keys for each user. It is observed that, when a broadcast encryption scheme is deployed for secret escrows, a dishonest dealer can read the escrowed secrets without leaving any witnesses. We present a new broadcast encryption paradigm referred to as fully distributed broadcast encryption (FDBE) without suffering from this vulnerability. In the new paradigm, there are multiple dealers, and by contacting a number of them equal to a threshold or more, any user can join the system; then the secrets can be encrypted to any subset of users and only the intended receivers can decrypt, while an attacker cannot get any information about the encrypted message even if the attacker controls all the users outside the receiver set and corrupts some dealers, provided that the number of corrupted dealers is less than a threshold. We realize the first fully distributed broadcast encryption scheme which is proven secure under the decision Bilinear Diffie-Hellman Exponentiation assumption in the standard model. A variant is also shown to achieve sub-linear complexity in terms of public key, decryption key and ciphertext, comparable to up-to-date regular broadcast encryption schemes without robustness and strong security against misbehaving dealers.

Qianhong Wu, Bo Qin, Lei Zhang, Josep Domingo-Ferrer

Efficient Identity-Based Signcryption in the Standard Model

Abstract

Signcryption is a cryptographic primitive that fulfills both the functions of digital signature and public key encryption simultaneously, at a cost significantly lower than that required by the traditional signature-then-encryption approach. Signcryption has been shown to be useful in many applications, such as electronic commerce, mobile communications and smart cards. Recently, three identity-based signcryption schemes in the standard model were proposed. However, the three schemes are broken soon. How to construct a secure identity-based signcryption scheme in the standard model is still an open problem. In this paper, we solve this problem and propose an efficient identity-based signcryption scheme in the standard model. We prove that our scheme has the indistinguishability against adaptive chosen ciphertext attacks under the modified decisional bilinear Diffie-Hellman assumption and the existential unforgeability against adaptive chosen messages attacks under the computational Diffie-Hellman assumption.

Fagen Li, Fahad Bin Muhaya, Mingwu Zhang, Tsuyoshi Takagi

Toward Compact Public Key Encryption Based on CDH Assumption via Extended Twin DH Assumption

Abstract

IND-CCA secure public key encryption schemes based on the CDH assumption in the standard model use a hardcore function as a key derivation function for a shared key. Therefore, many secret and public key size are necessary for sending a sufficiently long shared key. Yamada et al. [17,16] and Haralambiev et al. [12] proposed efficient public key encryption schemes based on the CDH assumption. Moreover, they proposed a method that drastically reduces the secret and the public key sizes by using a bilinear map, and they also proposed IND-CCA secure public key encryption based on the bilinear DH assumption. Unfortunately, many secret and public key sizes are still necessary in general cyclic groups that lack known efficient bilinear map.

In this paper, we propose a compact public key scheme based on the CDH assumption in the standard model. The public and secret key sizes are trivially reduced by sending several block of the ciphertext. By using batch verification, our scheme succeeded in reducing the ciphertext size compared with that in the case of the trivially extended scheme. To prove IND-CCA security of our scheme, we define a new computational assumption, namely, the extended hashed strong twin Diffie-Hellman assumption. Moreover, we construct an extended trapdoor test to simulate a decisional oracle, and prove that if the CDH assumption holds and the hash function is the hardcore function for DH key, then the extended hashed strong twin DH assumption also holds. Our reducing technique is also applicable to other schemes [17,16,15] based on the CDH assumption.

Yoshikazu Hanatani, Hirofumi Muratani, Tomoko Yonemura

Anonymous Encryption with Partial-Order Subset Delegation Functionality

Abstract

We present a general encryption model with partial order delegation ability, which is a generalized extension for hierarchical identity-based encryption, broadcast encryption and delegatable functional encryption, etc. We also construct a concrete anonymous encryption scheme with constant-size ciphertext which may perform key derivation with partial-order subset delegation functionality, and prove its security in the standard model including semantic security, anonymity, and delegation indistinguishability. We give some practical application scenarios and deployments for our scheme.

Mingwu Zhang, Takashi Nishide, Bo Yang, Tsuyoshi Takagi

Cryptographic Protocols

Concurrent Signatures with Fully Negotiable Binding Control

Abstract

Since the introduction of concurrent signatures, the authorship binding of concurrent signatures has always been initiator-controlled, that is, only the initiator of a concurrent signature exchange can control “whether” and “when” to convert the exchanging ambiguous signatures to publicly verifiable ones concurrently. This binding control is not negotiable. In some applications however, this limitation is undesirable, and instead, as of optimistic fair exchange does, letting the responder control “whether” and “when” to have exchanged ambiguous signatures bound is needed. This motivates us towards constructing a new concurrent signature variant which supports negotiation between the original initiator-controlled binding and a new responder-controlled binding. In this paper, we formalize the notion and propose the first construction, which allows either the initiator or the responder to control “whether” and “when” the binding of the exchanging ambiguous signatures will take place concurrently. The scheme is backward compatible to the original concurrent signature and is also comparable in performance to the existing ones.

Tsz Hon Yuen, Duncan S. Wong, Willy Susilo, Qiong Huang

Secure Obfuscation of Encrypted Verifiable Encrypted Signatures

Abstract

Since obfuscation was brought into the field of cryptography, it has become one of the most difficult and hottest problems. Because a general secure obfuscating method, if exists, will lead to the solution of many open problems in cryptography. However, after Bark et al.’s negative impossibility result for general obfuscation became well-known, only a few positive results was brought out. In \(\emph{EUROCRYPT 2010}\), Hada proposed a secure obfuscator of encrypted signatures (ES), which signs a message under Alice’s secret signing key and then encrypts the signature using Bob’s public encryption key. This result is the only few secure obfuscation of complicated cryptographic primitives. In this paper, we consider the obfuscation of encrypted verifiable encrypted signatures (EVES). There is a trusted third party (TTP) in our protocol, and EVES first generates a verifiable encrypted signature (VES) under Alice’s secret signing key and the TTP’s public encryption key and then the VES is encrypted using Bob’s public encryption key. We give out the detailed EVES protocol and securely obfuscate it. We prove the security requirement of virtual black box property under standard assumptions and the secure obfuscation result will have many practical applications as we issue.

Rong Cheng, Bo Zhang, Fangguo Zhang

Identity-Based Trace and Revoke Schemes

Abstract

Trace and revoke systems allow for the secure distribution of digital content in such a way that malicious users, who collude to produce pirate decoders, can be traced back and revoked from the system. In this paper, we consider such schemes in the identity-based setting, by extending the model of identity-based traitor tracing scheme by Abdalla et al. to support revocation.

The proposed constructions rely on the subset cover framework. We first propose a generic construction which transforms an identity-based encryption with wildcard (WIBE) of depth log(N) (N being the number of users) into an identity-based trace and revoke scheme by relying on the complete subtree framework (of depth log(N)). This leads, however, to a scheme with log(N) private key size (as in a complete subtree scheme). We improve this scheme by introducing generalized WIBE (GWIBE) and propose a second construction based on GWIBE of two levels. The latter scheme provides the nice feature of having constant private key size (3 group elements).

In our schemes, we also deal with advanced attacks in the subset cover framework, namely pirate evolution attacks (PEvoA) and pirates 2.0. The only known strategy to protect schemes in the subset cover framework against pirate evolution attacks was proposed by Jin and Lotspiech but decreases seriously the efficiency of the original schemes: each subset is expanded to many others subsets; the total number of subsets to be used in the encryption could thus be O(N ^1/b) to prevent a traitor from creating more than b generations. Our GWIBE based scheme, resisting PEvoA better than the Jin and Lotspiech’s method. Moreover, our method does not need to change the partitioning procedure in the original complete subtree scheme and therefore, the resulted schemes are very competitive compared to the original scheme, with r log(N/r) logN –size ciphertext and constant size private key.

Duong Hieu Phan, Viet Cuong Trinh

Universally Composable Private Proximity Testing

Abstract

This paper aims at studying privacy-preserving tests for proximity. In a private proximity test, Alice can verify if she is close to Bob without either party revealing any other information about their location. We propose a system for private proximity testing based on the pre-distribution of data: the so-called commodity-based model. Our system is proven secure in the Universal Composability (UC) framework and uses as the core building block an efficient UC-secure equality testing protocol. To our knowledge this is the first work in the literature that contemplates this problem in the UC framework.

Rafael Tonicelli, Bernardo Machado David, Vinícius de Morais Alves

Generic Constant-Round Oblivious Sorting Algorithm for MPC

Abstract

Various information-theoretically secure Multi-Party Computation (MPC) schemes have been proposed over some finite field \(\mathbb{F}\) or some finite ring ℝ. A function f that can be evaluated on MPC is usually represented by boolean or arithmetic circuits. In general, the function class that have constant-depth arithmetic circuit is studied. Additionally, some literatures show that one can represent any formulas and branching program by low-degree randomizing polynomials, which can be evaluated in constant rounds. However, these approaches have their limitations, and it is not easy to construct the optimal branching program for a complex function. Therefore, it is not obvious how to efficiently perform oblivious sort in constant rounds, but oblivious sort is one of the most important primitive protocols for MPC in practice. In this paper, we are going to show several constant-round 0-error oblivious sorting algorithms, together with some useful applications.

Bingsheng Zhang

General Construction of Chameleon All-But-One Trapdoor Functions

Abstract

Lossy trapdoor functions enable black-box construction of public key encryption (PKE) schemes secure against chosen-ciphertext attack [18]. Recently, a more efficient black-box construction of public key encryption was given in [12] with the help of chameleon all-but-one trapdoor functions (ABO-TDFs).

In this paper, we propose a black-box construction for transforming any ABO-TDFs into chameleon ABO-TDFs with the help of chameleon hash functions. Instantiating the proposed general black-box construction of chameleon ABO-TDFs, we can obtain the first chameleon ABO-TDFs based on the Decisional Diffie-Hellman (DDH) assumption.

Shengli Liu, Junzuo Lai, Robert H. Deng

Security Models and Framework

PolyE+CTR: A Swiss-Army-Knife Mode for Block Ciphers

Abstract

In this paper, we propose a new kind of mode of operation for block ciphers. By a single key, such a mode can protect data for privacy, authenticity and they both respectively, so we call it Swiss-Army-Knife mode. The purpose of SAK mode is to increase diversity of security services for a single key, thus we can provide different protections for data with different security requirements, without rekeying the underlying block cipher. As an example, we propose PolyE+CTR, an SAK mode that combines an authentication mode PolyE and a nonce-based encryption mode CTR in the authentication-and-encryption method. PolyE+CTR is provably secure with high efficiency.

Liting Zhang, Wenling Wu, Peng Wang

Security of Practical Cryptosystems Using Merkle-Damgård Hash Function in the Ideal Cipher Model

Abstract

In this paper, we clarify the security of practical cryptosystems with hash functions based on key derivation functions (KDFs). We use the indifferentiability framework in order to discuss the security because the indifferentiability from Random Oracle (and its variants) guarantees that cryptosystems remain secure even if Random Oracles (ROs) are instantiated with hash functions. Though previous works on the indifferentiability of Merkle-Damgård (MD) hash functions focus on stand-alone hash functions, there is no work which focuses on MD hash functions with KDFs. Many cryptosystems need longer output lengths of hash functions than stand-alone hash functions and KDFs are used to generate longer digests as specified in PKCS #1 v2.1 and IEEE P1363. Specifically, we obtain the following results. We denote the MD hash function using Stam’s type-II compression function by MD-SCFII and MD-SCFII with KDFs by KDF-MD-SCFII.

Cryptosystems secure in the pub-RO model (FDH, PSS, Fiat-Shamir, and so on): Dodis et al. proposed the indifferentiability from pub-RO to prove the security of these cryptosystems using MD-SCFII while did not consider the KDF structures. So we propose a different framework, indifferentiability from privleak-RO. Using this framework and their result, we show that these cryptosystems using KDF-MD-SCFIIs are secure.
Encryption schemes secure in the RO model (OAEP, RSA-KEM, PSEC-KEM, ECIES-KEM and so on): The encryption schemes are secure in the “fixed inputl length” RO model because the input lengths of ROs from the encryption schemes are fixed. We show that this fact guarantees the security of the encryption schemes using KDF-MD-SCFII.

Yusuke Naito, Kazuki Yoneyama, Lei Wang, Kazuo Ohta

Key-Dependent Message Security for Division Function: Discouraging Anonymous Credential Sharing

Abstract

Key-dependent message (KDM) security means that the encryption scheme remains secure even encrypting f(sk), where f is an efficient computable function chosen by the adversary and sk = sk ₁, ⋯ , sk _n are private keys. We concentrate on a special case that the function f is a division function. Namely, the messages of the form sk _i/sk _j are encrypted. We prove that if a public key encryption (PKE) scheme is IND-CPA (chosen plaintext attacks) secure and has the properties of public-key blinding and secret-key homomorphism, then it is KDM secure for division function (KDM-div secure). For concrete scheme, we show that the hybrid ElGamal scheme is KDM-div secure based on the decisional Diffie-Hellman (DDH) assumption in the standard model. We show that KDM-div secure scheme is useful in the design of anonymous credential systems.

Xianhui Lu, Bao Li, Qixiang Mei, Haixia Xu

Randomness Leakage in the KEM/DEM Framework

Abstract

Recently, there have been many studies on constructing cryptographic primitives that are secure even if some secret information leaks. In this paper, we consider the problem of constructing public-key encryption schemes that are resilient to leaking the randomness used in the encryption algorithm. In particular, we consider the case in which public-key encryption schemes are constructed from the KEM/DEM framework, and the leakage of randomness in the encryption algorithms of KEM and DEM occurs independently. For this purpose, we define a new security notion for KEM. Then we provide a generic construction of a public-key encryption scheme that is resilient to randomness leakage from any KEM scheme satisfying this security. Also we construct a KEM scheme that satisfies the security under the decisional Diffie-Hellman assumption.

Hitoshi Namiki, Keisuke Tanaka, Kenji Yasunaga

Generalized Learning Problems and Applications to Non-commutative Cryptography

(Extended Abstract)

Abstract

We propose a generalization of the learning parity with noise (LPN) and learning with errors (LWE) problems to an abstract class of group-theoretic learning problems that we term learning homomorphisms with noise (LHN). This class of problems contains LPN and LWE as special cases, but is much more general. It allows, for example, instantiations based on non-abelian groups, resulting in a new avenue for the application of combinatorial group theory to the development of cryptographic primitives. We then study a particular instantiation using relatively free groups and construct a symmetric cryptosystem based upon it.

Gilbert Baumslag, Nelly Fazio, Antonio R. Nicolosi, Vladimir Shpilrain, William E. Skeith III

A Novel Framework for Protocol Analysis

Abstract

We describe a novel reformulation of Canetti’s Universal Composability (UC) framework for the analysis of cryptographic protocols. Our framework is different mainly in that it is (a) based on systems of interactive Turing machines with a fixed communication graph and (b) augmented with a global message queue that allows the sending of multiple messages per activation. The first feature significantly simplifies the proofs of some framework results, such as the UC theorem, while the second can lead to more natural descriptions of protocols and ideal functionalities.

Kristian Gjøsteen, George Petrides, Asgeir Steine

Key Agreement

Taxonomical Security Consideration of Authenticated Key Exchange Resilient to Intermediate Computation Leakage

Abstract

SMQV authenticated key exchange scheme was stated to be secure against leakage of intermediate computations, i.e., secure in the seCK model. However, in this paper, we show errors in the security proof of SMQV. The found errors proceed from a failure in a simulation of leakage of intermediate computations. Moreover, we identify flaws in the security proofs of the underlying building tools of both SMQV and FHMQV, showing that both SMQV and FHMQV are not proven secure even in the traditional CK model. Then, we consider the cause of difficulty to prove security in the seCK model and classify previous Diffie-Hellman type authenticated key exchange schemes in the sense of achievable security levels. As a result, unfortunately, known schemes fall into hard to prove or insecure. Accordingly, we suggest that Diffie-Hellman type schemes provably secure in the seCK model are hard (or highly subtle) to achieve. Therefore, this paper clarifies the technical limitations (or high subtleties) of Diffie-Hellman type schemes for achieving provable security in the seCK model against leakage of intermediate computations.

Kazuki Yoneyama, Yunlei Zhao

Gateway-Oriented Password-Authenticated Key Exchange Protocol with Stronger Security

Abstract

A gateway-oriented password-based authenticated key exchange (GPAKE) is a three-party protocol, which allows a client and a gateway to establish a common session key with the help of an authentication server. To date, most of the published GPAKE protocols have been subjected to undetectable on-line dictionary attacks. The security models for GPAKE are not strong enough to capture such attacks. In this paper, we define a new security model for GPAKE, which is stronger than previous models and captures desirable security requirement of GPAKE. We also propose an efficient GPAKE protocol and prove its security under the DDH assumption in our model. Our scheme assumes no pre-established secure channels between the gateways and the server unlike previous schemes, but just authenticated channels between them. Compared with related schemes, our protocol achieves both higher efficiency and stronger security.

Fushan Wei, Chuangui Ma, Zhenfeng Zhang

TMQV: A Strongly eCK-Secure Diffie-Hellman Protocol without Gap Assumption

Abstract

In this paper, we propose an authenticated key exchange (AKE) protocol under the computational Diffie-Hellman (CDH) assumption with respect to the strengthened eCK-security (seCK-security) of Sarr et al.. To date, many AKE protocols either are provably secure under a rather strong and non-standard assumption named as the gap Diffie-Hellman (GDH) assumption, or fall to practical attacks on the intermediate result leakage which can be captured by the seCK model. In order to remove the gap assumption and achieve stronger security requirements, we present the TMQV protocol using the twinning technique and the MQV key derivation method. With the help of trapdoor test theorem, TMQV is provably seCK-secure under the standard CDH assumption in the random oracle model. Compared with the related works, TMQV achieves not only stronger security but also higher implementation efficiency with weaker cryptographic assumptions.

Jiaxin Pan, Libin Wang

Strongly Secure One Round Authenticated Key Exchange Protocol with Perfect Forward Security

Abstract

So far, there exist no two-pass authenticated key exchange protocols which are provably secure in the eCK model and meanwhile achieve perfect forward security against active adversary in one round.

The paper proposes a new two-pass (one round) authenticated key exchange protocol which enjoys following desirable properties. First, our protocol is shown secure in the eCK model under the gap Diffie-Hellman (GDH) assumption. Moreover, our protocol does not use the NAXOS transformation, the drawback of which will be discussed in the introduction. Second, under the same assumption, we prove that our protocol achieves perfect forward security against active adversary in one round.

To the best of our knowledge, our proposal is the first two-pass (one round) authenticated key exchange protocol provably secure in the eCK model and achieving perfect forward security against active adversary.

Hai Huang

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Invited Talks

Optimal Structure-Preserving Signatures

Secure Composition of Cryptographic Protocols

Cryptographic Primitives

Secure Two-Party Computation over a Z-Channel

Precise Time and Space Simulatable Zero-Knowledge

Weak Oblivious Transfer from Strong One-Way Functions

Simulatable Adaptive Oblivious Transfer with Statistical Receiver’s Privacy

Encryption

Verifiable Security of Boneh-Franklin Identity-Based Encryption

Efficient Ciphertext Policy Attribute-Based Encryption with Constant-Size Ciphertext and Constant Computation-Cost

Fully Distributed Broadcast Encryption

Efficient Identity-Based Signcryption in the Standard Model

Toward Compact Public Key Encryption Based on CDH Assumption via Extended Twin DH Assumption

Anonymous Encryption with Partial-Order Subset Delegation Functionality

Cryptographic Protocols

Concurrent Signatures with Fully Negotiable Binding Control

Secure Obfuscation of Encrypted Verifiable Encrypted Signatures

Identity-Based Trace and Revoke Schemes

Universally Composable Private Proximity Testing

Generic Constant-Round Oblivious Sorting Algorithm for MPC

General Construction of Chameleon All-But-One Trapdoor Functions

Security Models and Framework

PolyE+CTR: A Swiss-Army-Knife Mode for Block Ciphers

Security of Practical Cryptosystems Using Merkle-Damgård Hash Function in the Ideal Cipher Model

Key-Dependent Message Security for Division Function: Discouraging Anonymous Credential Sharing

Randomness Leakage in the KEM/DEM Framework

Generalized Learning Problems and Applications to Non-commutative Cryptography

A Novel Framework for Protocol Analysis

Key Agreement

Taxonomical Security Consideration of Authenticated Key Exchange Resilient to Intermediate Computation Leakage

Gateway-Oriented Password-Authenticated Key Exchange Protocol with Stronger Security

TMQV: A Strongly eCK-Secure Diffie-Hellman Protocol without Gap Assumption

Strongly Secure One Round Authenticated Key Exchange Protocol with Perfect Forward Security

Backmatter