The existing discrete-logarithm-based two-round multi-signature schemes without using the idealized model, i.e., the Algebraic Group Model (AGM), have quite large reduction loss. This means that an implementation of these schemes requires an elliptic curve (EC) with a very large order for the standard 128-bit security when we consider concrete security. Indeed, the existing standardized ECs have orders too small to ensure 128-bit security of such schemes. Recently, Pan and Wagner proposed two two-round schemes based on the Decisional Diffie-Hellman (DDH) assumption (EUROCRYPT 2023). For 128-bit security in concrete security, the first scheme can use the NIST-standardized EC P-256 and the second can use P-384. However, with these parameter choices, they do not improve the signature size and the communication complexity over the existing non-tight schemes. Therefore, there is no two-round scheme that (i) can use a standardized EC for 128-bit security and (ii) has high efficiency. In this paper, we construct a two-round multi-signature scheme achieving both of them from the DDH assumption. We prove that an EC with at least a 321-bit order is sufficient for our scheme to ensure 128-bit security. Thus, we can use the NIST-standardized EC P-384 for 128-bit security. Moreover, the signature size and the communication complexity per one signer of our proposed scheme under P-384 are 1152 bits and 1535 bits, respectively. These are most efficient among the existing two-round schemes without using the AGM including Pan-Wagner’s schemes and non-tight schemes which do not use the AGM. Our experiment on an ordinary machine shows that for signing and verification, each can be completed in about 65 ms under 100 signers. This shows that our scheme has sufficiently reasonable running time in practice.

Knowledge-of-exponent assumptions (KEAs) are a somewhat controversial but nevertheless commonly used type of cryptographic assumptions. While traditional cryptographic assumptions simply assert that certain tasks (like factoring integers or computing discrete logarithms) cannot be performed efficiently, KEAs assert that certain tasks can be performed efficiently, but only in certain ways. The controversy surrounding those assumptions is due to their non-falsifiability, which is due to the way this idea is formalised, and to the general idea that these assumptions are “strong”. Nevertheless, their relationship to existing assumptions has not received much attention thus far. In this paper, we show that the first KEA (KEA1), introduced by Damgård in 1991, implies that computing discrete logarithms is equivalent to solving the computational Diffie-Hellman (CDH) problem. Since showing this equivalence in the standard setting (i.e., without the assumption that KEA1 holds) is a longstanding open question, this indicates that KEA1 (and KEAs in general) are indeed quite strong assumptions.

This paper proposes an id-eCK secure identity-based authenticated key exchange (ID-AKE) scheme, where the id-eCK security implies that a scheme resists against leakage of all combinations of master, static, and ephemeral secret keys except ones trivially break the security. Most existing id-eCK secure ID-AKE schemes require two symmetric pairing operations or a greater number of asymmetric pairing, which is faster than symmetric one, operations to establish a session key. However, our scheme is realized with a single asymmetric pairing operation for each party, and this is an advantage in efficiency. The proposed scheme is based on the ID-AKE scheme by McCullagh and Barreto, which is vulnerable to an active attack. To achieve id-eCK security, we apply the HMQV construction and the NAXOS technique to the McCullagh-Barreto scheme. The id-eCK security is proved under the external Diffie-Hellman for target group assumption and the q-gap-bilinear collision attack assumption.

Non-Interactive Key Exchange (NIKE) is a cryptographic primitive that allows two users to compute a shared key without any interaction. The Diffie-Hellman key exchange scheme is probably the most well-known example of a NIKE scheme. Freire et al. (PKC 2013) defined four security notions for NIKE schemes, and showed implications among them. In these notions, we consider an adversary that is challenged to distinguish a shared key of a new pair of users from a random value, using only its knowledge of keys shared between other pairs of users. To take into account side-channel attacks such as tampering and fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In this paper, we introduce four RKA security notions for NIKE schemes. In these notions, we consider an adversary that can also manipulate the secret keys of users and obtain shared keys computed under the modified secret keys. We also show implications and separations among the security notions, and prove that one of the NIKE schemes proposed by Freire et al. is secure in the strongest RKA sense in the random oracle model under the Double Strong Diffie-Hellman (DSDH) assumption over the group of signed quadratic residues, which is implied by the factoring assumption.

Two new authenticated key agreement protocols in the certificateless setting are presented in this paper. Both are proved secure in the extended Canetti-Krawczyk model, under the BDH assumption. The first one is more efficient than the Lippold et al.'s (LBG) protocol, and is proved secure in the same security model. The second protocol is proved secure under the Swanson et al.'s security model, a weaker model. As far as we know, our second proposed protocol is the first one proved secure in the Swanson et al.'s security model. If no pre-computations are done, the first protocol is about 26% faster than LBG, and the second protocol is about 49% faster than LBG, and about 31% faster than the first one. If pre-computations of some operations are done, our two protocols remain faster.

In this letter, we prove that the Kurosawa-Desmedt (KD) scheme [10], which belongs to the hybrid framework, is KDM-CCA secure w.r.t. an ensemble proposed by Qin et al. in [12] under the decisional Diffie-Hellman assumption. Since our proof does not rely on the random oracle model, we partially answer the question presented by Davies and Stam in [7], where they hope to achieve the KDM-CCA security for hybrid encryption scheme in the standard model (i.e. not random oracle model). Moreover, our result may also make sense in practice since KD-scheme is (almost) the most efficient CCA secure scheme.

This paper proposes a generic construction of hierarchical identity-based identification (HIBI) protocols secure against impersonation under active and concurrent attacks in the standard model. The proposed construction converts a digital signature scheme existentially unforgeable against chosen message attacks, where the scheme has a protocol for showing possession of a signing key, not a signature. Our construction is based on the so-called certificate-based construction of hierarchical identity-based cryptosystems, and utilizes a variant of the well-known OR-proof technique to ensure the security against impersonation under active and concurrent attacks. We also present several concrete examples of our construction employing the Waters signature (EUROCRYPT 2005), and other signatures. As results, its concurrent security of each instantiation is proved under the computational Diffie-Hellman (CDH) assumption, the RSA assumption, or their variants in the standard model. Chin, Heng, and Goi proposed an HIBI protocol passively and concurrently secure under the CDH and one-more CDH assumption, respectively (FGIT-SecTech 2009). However, its security is proved in the random oracle model.

In this paper, we propose an identity-based authenticated key exchange (ID-AKE) protocol that is secure in the identity-based extended Canetti-Krawczyk (id-eCK) model in the random oracle model under the gap Bilinear Diffie-Hellman assumption. The proposed ID-AKE protocol is the most efficient among the existing ID-AKE protocols that is id-eCK secure, and it can be extended to use in asymmetric pairing.

This paper examines two-pass authenticated key exchange (AKE) protocols that are secure without the NAXOS technique under the gap Diffie-Hellman assumption in the random oracle model: FHMQV [18], KFU1 [21], SMEN- [13], and UP [17]. We introduce two protocol, biclique DH protocol and multiplied biclique DH protocol, to analyze the subject protocols, and show that the subject protocols use the multiplied biclique DH protocol as internal protocols. The biclique DH protocol is secure, however, the multiplied biclique DH protocol is insecure. We show the relations between the subject protocols from the viewpoint of how they overcome the insecurity of the multiplied biclique DH protocol: FHMQV virtually executes two multiplied biclique DH protocols in sequence with the same ephemeral key on two randomized static keys. KFU1 executes two multiplied biclique DH protocols in parallel with the same ephemeral key. UP is a version of KFU1 in which one of the static public keys is generated with a random oracle. SMEN- can be thought of as a combined execution of two multiplied biclique DH protocols. In addition, this paper provides ways to characterize the AKE protocols and defines two parameters: one consists of the number of static keys, the number of ephemeral keys, and the number of shared secrets, and the other is defined as the total sum of these numbers. When an AKE protocol is constructed based on some group, these two parameters indicate the number of elements in the group, i.e., they are related to the sizes of the storage and communication data.

We propose a security model, referred as g-eCK model, for group key exchange that captures essentially all non-trivial leakage of static and ephemeral secret keys of participants, i.e., group key exchange version of extended Canetti-Krawczyk (eCK) model. Moreover, we propose the first one-round tripartite key exchange (3KE) protocol secure in the g-eCK model under the gap Bilinear Diffie-Hellman (gap BDH) assumption and in the random oracle model.

We propose a generic conversion from a key encapsulation mechanism (KEM) to an identification (ID) scheme. The conversion derives the security for ID schemes against concurrent man-in-the-middle (cMiM) attacks from the security for KEMs against adaptive chosen ciphertext attacks on one-wayness (one-way-CCA2). Then, regarding the derivation as a design principle of ID schemes, we develop a series of concrete one-way-CCA2 secure KEMs. We start with El Gamal KEM and prove it secure against non-adaptive chosen ciphertext attacks on one-wayness (one-way-CCA1) in the standard model. Then, we apply a tag framework with the algebraic trick of Boneh and Boyen to make it one-way-CCA2 secure based on the Gap-CDH assumption. Next, we apply the CHK transformation or a target collision resistant hash function to exit the tag framework. And finally, as it is better to rely on the CDH assumption rather than the Gap-CDH assumption, we apply the Twin DH technique of Cash, Kiltz and Shoup. The application is not “black box” and we do it by making the Twin DH technique compatible with the algebraic trick. The ID schemes obtained from our KEMs show the highest performance in both computational amount and message length compared with previously known ID schemes secure against concurrent man-in-the-middle attacks.

Group key establishment is an important mechanism to construct a common session key for group communications. Conventional group key establishment protocols use an on-line trusted key generation center (KGC) to transfer the group key for each participant in each session. However, this approach requires that a trusted server be set up, and it incurs communication overhead costs. In this article, we address some security problems and drawbacks associated with existing group key establishment protocols. Besides, we use the concept of secret sharing scheme to propose a secure key transfer protocol to exclude impersonators from accessing the group communication. Our protocol can resist potential attacks and also reduce the overhead of system implementation. In addition, comparisons of the security analysis and functionality of our proposed protocol with some recent protocols are included in this article.

In this paper, we propose two authenticated key exchange(AKE) protocols and prove their security in the extended Canetti-Krawczyk model. The first protocol, called NAXOS+, is obtained by slightly modifying the NAXOS protocol proposed by LaMacchia, Lauter and Mityagin [15]. We prove its security under the Computational Diffie-Hellman (CDH) assumption by using the trapdoor test introduced in [6]. To the authors' knowledge, this is the first AKE protocol which is secure under the CDH assumption in the eCK model. The second protocol, called NETS, enjoys a simple and tight security reduction compared to existing schemes including HMQV and CMQV without using the Forking Lemma. Since each session of the NETS protocol requires only three exponentiations per party, its efficiency is also comparable to MQV, HMQV and CMQV.

In this paper, we propose two new chosen-ciphertext (CCA) secure schemes from the computational Diffie-Hellman (CDH) and bilinear computational Diffie-Hellman (BCDH) assumptions. Our first scheme from the CDH assumption is constructed by extending Cash-Kiltz-Shoup scheme. This scheme yields the same ciphertext as that of Hanaoka-Kurosawa scheme (and thus Cramer-Shoup scheme) with cheaper computational cost for encryption. However, key size is still the same as that of Hanaoka-Kurosawa scheme. Our second scheme from the BCDH assumption is constructed by extending Boyen-Mei-Waters scheme. Though this scheme requires a stronger underlying assumption than the CDH assumption, it yields significantly shorter key size for both public and secret keys. Furthermore, ciphertext length of our second scheme is the same as that of the original Boyen-Mei-Waters scheme.

In this paper, we introduce the intermediate hashed Diffie-Hellman (IHDH) assumption which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH assumption), and is stronger than the computational DH assumption. We then present two public key encryption schemes with short ciphertexts which are both chosen-ciphertext secure under this assumption. The short-message scheme has smaller size of ciphertexts than Kurosawa-Desmedt (KD) scheme, and the long-message scheme is a KD-size scheme (with arbitrary plaintext length) which is based on a weaker assumption than the HDH assumption.

This paper introduces a new computational problem on a two-dimensional vector space, called the vector decomposition problem (VDP), which is mainly defined for designing cryptosystems using pairings on elliptic curves. We first show a relation between the VDP and the computational Diffie-Hellman problem (CDH). Specifically, we present a sufficient condition for the VDP on a two-dimensional vector space to be at least as hard as the CDH on a one-dimensional subspace. We also present a sufficient condition for the VDP with a fixed basis to have a trapdoor. We then give an example of vector spaces which satisfy both sufficient conditions and on which the CDH is assumed to be hard in previous work. In this sense, the intractability of the VDP is a reasonable assumption as that of the CDH.

The purpose of this paper is to study sender authenticated key agreements by a third party, which uses the received parameters to verify the fact that a sender of a message knows his long-term private key. In particular, we propose a standard model for the protocol among three entities for the first time. The security of this protocol depends on the difficulty of solving two new problems related to one-way isomorphisms and the decision co-bilinear Diffie-Hellman problem on multiplicative cyclic groups. It is the first time that the security of a key agreement has been formally proven by using negligible probability. We believe that our contribution gives many applications in the cryptographic community.

We present IND-ID-CPA secure identity-based encryption (IBE) schemes with tight reductions to the bilinear Diffie-Hellman (BDH) problem. Since the methods for obtaining IND-ID-CCA secure schemes from IND-ID-CPA secure schemes with tight reductions are already known, we can consequently obtain IND-ID-CCA secure schemes with tight reductions to the BDH problem. Our constructions are based on IBE schemes with tight reductions to the list bilinear Diffie-Hellman (LBDH) problem, and the schemes are converted to those with tight reductions to the BDH problem. Interestingly, it can be shown that there exists a black box construction, in which the former IBE schemes are given as black boxes. Our constructions are very simple and reasonably efficient.

This letter proposes a secure and efficient handover authentication scheme that requires a light-weight Diffie-Hellman operation at mobile nodes. Our scheme provides more enhanced securities like the PFS, PBS, and so on than the existing security-context-transfer schemes. Also, the mobile node delegates the exponent operation for the DH to the access router to reduce computational cost on it.

Password-based authenticated key exchange protocols are more convenient and practical, since users employ human-memorable passwords that are simpler to remember than cryptographic secret keys or public/private keys. Abdalla, Fouque, and Pointcheval proposed the password-based authenticated key exchange protocol in a 3-party model (GPAKE) in which clients trying to establish a secret do not share a password between themselves but only with a trusted server. On the other hand, Canetti presented a general framework, which is called universally composable (UC) framework, for representing cryptographic protocols and analyzing their security. In this framework, the security of protocols is maintained under a general protocol composition operation called universal composition. Canetti also proved a UC composition theorem, which states that the definition of UC-security achieves the goal of concurrent general composition. A server must manage all the passwords of clients when the 3-party password-based authenticated key exchange protocols are realized in large-scale networks. In order to resolve this problem, we propose a hierarchical hybrid authenticated key exchange protocol (H2AKE). In H2AKE, forwarding servers are located between each client and a distribution server, and the distribution server sends the client an authentication key via the forwarding servers. In H2AKE, public/private keys are used between servers, while passwords are also used between clients and forwarding servers. Thus, in H2AKE, the load on the distribution server can be distributed to the forwarding servers concerning password management. In this paper, we define hierarchical hybrid authenticated key exchange functionality. H2AKE is the universal form of the hierarchical (hybrid) authenticated key exchange protocol, which includes a 3-party model, and it has the characteristic that the construction of the protocol can flexibly change according to the situation. We also prove that H2AKE is secure in the UC framework with the security-preserving composition property.