The aim of this technical report is to complement the work in [To et al. 2014] by proposing a Group Key Exchange protocol so that the Querier and TDSs (and TDSs themselves) can securely create and exchange the shared key. Then, the security of this protocol is formally proved using the game-based model. Finally, we perform the comparison between this protocol and other related works.
The aim of this technical report is to complement the work in [To et al. 2014] by proposing a Group Key Exchange protocol so that the Querier and TDSs (and TDSs themselves) can securely create and exchange the shared key. Then, the security of this protocol is formally proved using the game-based model. Finally, we perform the comparison between this protocol and other related works.
Key exchange protocols allow two parties to agree on a shared secret over an untrusted channel. A huge number of scientific works on key exchange have been published since the discovery of the first key exchange protocol, designed in 1976 by Diffie and Hellman [DH76]. The most prominent of these works is the game-based security model by Bellare and Rogaway [BR93], published in 1993 and, today, known as the "golden standard" for the security of key exchange protocols. The main purpose of key exchange protocols is to establish keys for a symmetric-key protocol such as a secure channel. Ideally, if both, the key exchange protocol and the channel protocol, are secure, then we would hope that they can be securely composed. While this is true for simulation-based security models [Can01, KT11, BPW03], game-based models usually lack composition theorems altogether. That is unfortunate, as they are often more suitable for real-life protocols such as TLS. Our first two composition theorems address the composition of BR-secure key exchange protocols with arbitrary symmetric-key protocols. We formally establish that an additional condition is necessary, namely, the key exchange requires a public session matching algorithm. Maybe surprisingly, many important key agreement protocols are not BR-secure due to the popular technique of explicit key confirmation. We devise a more flexible yet sufficiently strong model for this class of protocols and prove that it is closed under reductions. Overall, we devellop a tool for the modular analysis of real-life protocols and exemplify the use of our framwork on a profile of the TLS protocol. As in the case of most practical cryptography, information-theoretic security for key exchange protocols is out of reach, i.e., impossible in a formal sense. Therefore, protocols such as TLS rely on computational assumptions, e.g., the Diffie-Hellmann assumption or the hardness of factoring numbers. As the security of protocols is tightly related to the underlying complexity assumptions, researchers have been striving for simpler and weaker assumptions. The holy grail in this area is to base key agreement, one-way functions or simply any type of cryptography on the mere assumptions that NP does not equal P [FF93, BT03, AGGM06]. While positive results in this area remain elusive, there has been some recent progress on negative results [HMX10, PTV11], showing that cryptographic primitives such as hash functions cannot be based on NP-hardness unless coAM is contained in NP. In this thesis, we provide two oracle results that show that, via relativizing techniques, these negative results do not carry over to key agreement and regular one-way functions. In particular, we give an oracle relative to which the intersection of NP and coNP is easy while infinitely many often secure key agreement exists; and we give an oracle relative to which languages in the intersection of AM and coAM is easy while regular function families exists that are infinitely many often one-way.
Key exchange protocols, first introduced by Diffie and Hellman in 1976, are one of the most widely-deployed cryptographic protocols. They allow two parties, that have never interacted before, to establish shared secrets. These shared cryptographic keys may subsequently be used to establish a secure communication channel. Use cases include the classic client-server setting that is for example at play when browsing the internet, but also chats via end-to-end-encrypted instant messaging applications. Security-wise, we generally demand of key exchange protocols to achieve key secrecy and authentication. While, informally, authentication ensures that the communicating parties have confidence in the identity of their peers, key secrecy ensures that any shared cryptographic key that is established via the key exchange protocol is only known to the participants in the protocol and can be used securely in cryptographic protocols, i.e., is sufficiently random. In 1993, Bellare and Rogaway gave a first formalization of key exchange protocol security that captures these properties with respect to powerful adversaries with full control over the network. Their model constitutes the basis of the many subsequent treatments of authenticated key exchange security, including the models presented in this thesis. The common methodological approach underlying all of these formalizations is the provable security paradigm, which has become a standard tool in assessing the security of cryptographic protocols and primitives. So-called security models specify the expected security guarantees of the scheme in question with regards to a well-defined class of adversaries. Proofs that validate these security claims do so by reducing the security of the overall scheme to the security of the underlying cryptographic primitives and hardness assumptions. However, advances in computational power and more sophisticated cryptanalytic capabilities often render exactly these components insecure. Especially the advent of quantum computers will have a devastating effect on much of today's public key cryptography. This is especially true for key exchange protocols since they rely crucially on public-key algorithms. In this thesis, our focus in future-proofing key exchange protocols is two-fold. First, we focus on extending security models for key exchange protocols to capture the (un)expected break of cryptographic primitives and hardness assumptions. The aim is to gain assurances with respect to future adversaries and to investigate the effects of primitive failures on key exchange protocols. More specifically, we explore how key exchange protocols can be safely transitioned to new, post-quantum secure algorithms with hybrid techniques. Hybrids combine classical and post-quantum algorithms such that the overall key agreement scheme remains secure as long as one of the two base schemes remains secure. For this, we introduce security notions for key encapsulation mechanisms that account for adversaries with varying levels of quantum capabilities and present three new constructions for hybrid key encapsulation mechanisms. Our hybrid designs are practice-inspired and for example capture draft proposals for hybrid modes in the Transport Layer Security (TLS) protocol, which is one of the most widely-deployed cryptographic protocols that enables key agreement. Furthermore, our notion of breakdown resilience for key exchange protocols allows to gauge the security of past session keys in the event of a failure of a cryptographic component in the key exchange. We exercise our model on variants of the post-quantum secure key exchange protocol NewHope by Alkim et al. Thereby, we confirm the intuition that, in order to guard against adversaries that only have access to quantum computing power in the (more distant) future, it is sufficient to use classically-secure authentication mechanisms alongside post-quantum key agreement to achieve authenticated key exchange. As with any mathematical statement, theorems in the provable security paradigm are only as valid as the underlying assumptions. A careful consideration of any newly made assumption is thus essential to ensure the meaningfulness of the statement itself and make the assumption a viable tool for future analyses. Thus, secondly, we systematically classify the PRF-ODH assumption, a complexity-theoretic hardness assumption that has been used in key exchange security analyses of such prominent protocols as TLS, Signal, and Wireguard. In particular, we give a unified, parametrized definition of the assumption encompassing different variants that are present in the literature. We relate the resulting parametrized notions in terms of their strength and show where these assumptions fit in the collection of well-understood related hardness assumptions. We finally sketch our result on the impossibility of instantiating this assumption in the standard model, thereby disposing of the uncertainty in the community whether PRF-ODH is in fact a standard model assumption, i.e., removes the usage of some idealized assumptions in key exchange protocol proofs.
Group key exchange protocols allow their participants to compute a secret key which can be used to ensure security and privacy for various multi- party applications. The resulting group key should be computed through coop- eration of all protocol participants such that none of them is trusted to have any advantage concerning the protocol's output. This trust relationship states the main difference between group key exchange and group key transport protocols. Obvi- ously, misbehaving participants in group key exchange protocols may try to influ- ence the resulting group key, thereby disrupting this trust relationship, and also causing further security threats. This paper analyzes the currently known secu- rity models for group key exchange protocols with respect to this kind of attacks by malicious participants and proposes an extended model to remove the identi- fied limitations. Additionally, it proposes an efficient and provably secure generic solution, a compiler, to guarantee these additional security goals for group keys exchanged in the presence of malicious participants.
In 2004, Hwang et al. proposed a group key exchange protocol for sharing a secure key in a group. Their protocol is an extension from the two party key exchange protocol to the group one. Recently, Jung-San Lee et al. noted that Hwang et al. group key exchange protocol has two security weaknesses. First, the forward secrecy is not confirmed in case that a new member joins the group and second, if a group member leaves the group, the backward secrecy is compromised. They proposed an improvement over this key exchange protocol in order to provide both forward and backward secrecy among group members. In this paper, we propose another improvement over Lee et al. key exchange, and we show that our key exchange protocol not only preservers both forward and backward secrecy, but also it is more efficient than their protocol when a member leaves the group. Finally, we give a formal analysis for the correctness of the proposed protocol via Scyther model checking tool.
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.
Group Diffie-Hellman protocols for Authenticated Key Exchange (AKE) are designed to provide a pool of players with a shared secret key which may later be used, for example, to achieve multicast message integrity. Over the years, several schemes have been offered. However, no formal treatment for this cryptographic problem has ever been suggested. In this paper, we present a security model for this problem and use it to precisely define AKE (with "implicit" authentication) as the fundamental goal, and the entity-authentication goal as well. We then define in this model the execution of an authenticated group Diffie-Hellman scheme and prove its security.