Secret handshakes, introduced by Balfanz et al. [3], allow users associated with various groups to determine if they share a common affiliation. These protocols ensure crucial properties such as fairness (all participants learn the result simultaneously), affiliation privacy (failed handshakes reveal no affiliation information), and result-hiding (even participants within a shared group cannot infer outcomes of unrelated handshakes). Over time, various secret-handshake schemes have been...

In recent work [Crypto'24], Dodis, Jost, and Marcedone introduced Compact Key Storage (CKS) as a modern approach to backup for end-to-end (E2E) secure applications. As most E2E-secure applications rely on a sequence of secrets $(s_1,...,s_n)$ from which, together with the ciphertexts sent over the network, all content can be restored, Dodis et al. introduced CKS as a primitive for backing up $(s_1,...,s_n)$. The authors provided definitions as well as two practically efficient schemes (with...

The Messaging Layer Security (MLS) protocol, recently standardized in RFC 9420, aims to provide efficient asynchronous group key establishment with strong security guarantees. The main component of MLS, which is the source of its important efficiency and security properties, is a protocol called TreeKEM. Given that a major vision for the MLS protocol is for it to become the new standard for messaging applications like WhatsApp, Facebook Messenger, Signal, etc., it has the potential to be...

In large-scale protests, a repressive government will often disable the Internet to thwart communication between protesters. Smartphone mesh networks, which route messages over short range, possibly ephemeral, radio connections between nearby phones, allow protesters to communicate without relying on centralized Internet infrastructure. Unfortunately, prior work on mesh networks does not efficiently support cryptographically secure group messaging (a crucial requirement for protests); prior...

In 2018 Cai et al. proposed a multi-party quantum key agreement with five-qubit Brown states. They confirmed the security of their proposed scheme. However, Elhadad, Ahmed, et al. found the scheme cannot resist the collusion attack launched by legal participants. They suggested a modification and declared that their improved version is capable of resisting this type of attack. Nevertheless, after analysis, we found that the collusion attack still exists. Subsequently, we proposed a...

Key agreement and public key encryption are two elementary cryptographic primitives, suitable for different scenarios. But their differences are still not familiar to some researchers. In this note, we show that the Safkhani et al.'s key agreement scheme [Peer-to-Peer Netw. Appl. 15(3), 1595-1616, 2022] is a public key encryption in disguise. We stress that the ultimate use of key agreement is to establish a shared key for some symmetric key encryption. We also present a simplification of...

The Signal Protocol is a two-party secure messaging protocol used in applications such as Signal, WhatsApp, Google Messages and Facebook Messenger and is used by billions daily. It consists of two core components, one of which is the Double Ratchet protocol that has been the subject of a line of work that aims to understand and formalise exactly what security it provides. Existing models capture strong guarantees including resilience to state exposure in both forward security (protecting...

Much work has been done recently on developing password-authenticated key exchange (PAKE) mechanisms with post-quantum security. However, modern guidance recommends the use of hybrid schemes—schemes which rely on the combined hardness of a post-quantum assumption, e.g., learning with Errors (LWE), and a more traditional assumption, e.g., decisional Diffie-Hellman. To date, there is no known hybrid PAKE construction, let alone a general method for achieving such. In this paper, we present...

Peer-to-peer communication systems can provide many functions, including anonymized routing of network traffic, massive parallel computing environments, and distributed storage. Anonymity refers to the state of being completely nameless, with no attached identifiers. Pseudonymity involves the use of a fictitious name that can be consistently linked to a particular user, though not necessarily to the real identity. Both provide a layer of privacy, shielding the user's true identity from...

The Li et al.'s scheme [Computer Communications, 186 (2022), 110-120)] uses XOR operation to realize the private transmission of sensitive information, under the assumption that if only one parameter in the expression $ a= b\oplus c $ is known, an adversary cannot retrieve the other two. The assumption neglects that the operands $b$ and $c$ must be of the same bit-length, which leads to the exposure of a substring in the longer operand. The scheme wrongly treats timestamps as random...

Smart farming uses different vehicles to manage all the operations on the farm. These vehicles should be put to good use for secure data transmission. The Vangala et al.'s key agreement scheme [IEEE TIFS, 18 (2023), 904-9193] is designed for agricultural IoT networks. In this note, we show that the scheme fails to keep anonymity, instead pseudonymity. The scheme simply thinks that anonymity is equivalent to preventing the real identity from being recovered. But the true anonymity means...

We show that the key agreement scheme [IEEE Trans. Serv. Comput. 16(4): 3000-3013, 2023] fails to keep user anonymity, not as claimed. The scheme simply acknowledges that user anonymity is equivalent to preventing user's identity from being recovered. But the true anonymity means that the adversary cannot attribute different sessions to target users. It relates to entity-distinguishable, not just identity-revealable. To the best of our knowledge, it is the first time to clarify the...

We show that the Chunka-Banerjee-Goswami authentication and key agreement scheme [Wirel. Pers. Commun., 117, 1361-1385, 2021] fails to keep user anonymity, not as claimed. It only keeps pseudonymity. Anonymous actions are designed to be unlinkable to any entity, but pseudonymous actions can be traced back to a certain entity. We also find the scheme is insecure against offline dictionary attack.

As the use of the internet and digital devices has grown rapidly, keeping digital communications secure has become very important. Authenticated Key Agreement (AKA) protocols play a vital role in securing digital communications. These protocols enable the communicating parties to mutually authenticate and securely establish a shared secret key. The emergence of quantum computers makes many existing AKA protocols vulnerable to their immense computational power. Consequently, designing new...

We show that the authentication key agreement scheme [IEEE Trans. Smart Grid, 2023, 14(5), 3816-3827] is flawed due to its inconsistent computations. We also show that the scheme fails to keep anonymity, not as claimed.

In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being "dynamic'' means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the...

Transitioning from classically to quantum secure key agreement protocols may require to exchange fundamental components, for example, exchanging Diffie-Hellman-like key exchange with a key encapsulation mechanism (KEM). Accordingly, the corresponding security proof can no longer rely on the Diffie-Hellman assumption, thus invalidating the security guarantees. As a consequence, the security properties have to be re-proven under a KEM-based security notion. We initiate the study of the...

Common random string model is a popular model in classical cryptography. We study a quantum analogue of this model called the common Haar state (CHS) model. In this model, every party participating in the cryptographic system receives many copies of one or more i.i.d Haar random states. We study feasibility and limitations of cryptographic primitives in this model and its variants: - We present a construction of pseudorandom function-like states with security against computationally...

End-to-End (E2E) encrypted messaging, which prevents even the service provider from learning communication contents, is gaining popularity. Since users care about maintaining access to their data even if their devices are lost or broken or just replaced, these systems are often paired with cloud backup solutions: Typically, the user will encrypt their messages with a fixed key, and upload the ciphertexts to the server. Unfortunately, this naive solution has many drawbacks. First, it often...

ECMQV is a standardized key agreement protocol based on ECC with an additional implicit signature authentication. In this paper we investigate the vulnerability of ECMQV against fault attacks and propose two efficient lattice-based fault attacks. In our attacks, by inducing a storage fault to the ECC parameter $a$ before the execution of ECMQV, we can construct two kinds of weak curves and successfully pass the public-key validation step in the protocol. Then, by solving ECDLP and using a...

Asynchronous Remote Key Generation (ARKG) is a primitive introduced by Frymann et al. at ACM CCS 2020. It enables a sender to generate a new public key $pk'$ for a receiver ensuring only it can, at a later time, compute the corresponding private key $sk'$. These key pairs are indistinguishable from freshly generated ones and can be used in various public-key cryptosystems such as digital signatures and public-key encryption. ARKG has been explored for applications in WebAuthn credential...

The seminal work by Impagliazzo and Rudich (STOC'89) demonstrated the impossibility of constructing classical public key encryption (PKE) from one-way functions (OWF) in a black-box manner. However, the question remains: can quantum PKE (QPKE) be constructed from quantumly secure OWF? A recent line of work has shown that it is indeed possible to build QPKE from OWF, but with one caveat --- they rely on quantum public keys, which cannot be authenticated and reused. In this work, we...

In this document we present a further development of non-commutative algebra based key agreement due to E. Stickel and a way to deal with the algebraic break due to V. Sphilrain.

This paper presents a comprehensive security analysis of the Adh zero-knowledge proof system, a novel lattice-based, quantum-resistant proof of possession system. The Adh system offers compact key and proof sizes, making it suitable for real-world digital signature and public key agreement protocols. We explore its security by reducing it to the hardness of the Module-ISIS problem and introduce three new variants: Module-ISIS+, Module-ISIS*, and Module-ISIS**. These constructions enhance...

We show the authentication mechanism [Ad Hoc Networks, 2023, 103003] fails to keep user anonymity, not as claimed.

Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this paper, we present a new hardness assumption---the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity. Roughly speaking, the promise problem requires telling apart tuples of strings $(\pi,x,y)$ with relatively (w.r.t. $K(\pi)$) low time-bounded Interactive Kolmogorov...

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, in the setting where the only secret shared in advance is a low-entropy password. The standard security notion for PAKE is in the Universal Composability (UC) framework. In recent years there have been a large number of works analyzing the UC-security of Encrypted Key Exchange (EKE), the very first PAKE protocol, and its One-encryption variant (OEKE), both of which compile an...

In this work, we introduce a family of asymmetric cryptographic functions based on dynamic number theoretic transformations with multiple rounds of modular arithmetic to enhance diffusion and difficulty of inversion. This function acts as a basic cryptographic building block for a novel communication-efficient zero-knowledge crypto-system. The system as defined exhibits partial homomorphism and behaves as an additive positive accumulator. By using a novel technique to constructively embed...

In a seminal work, Ishai et al. (FOCS–2006) studied the viability of designing unconditionally secure protocols for key agreement and secure multi-party computation (MPC) using an anonymous bulletin board (ABB) as a building block. While their results establish the feasibility of key agreement and honest-majority MPC in the ABB model, the optimality of protocols with respect to their round and communication complexity is not studied. This paper enriches this study of unconditional security...

In 2016, NIST announced an open competition with the goal of finding and standardizing a suitable quantum-resistant cryptographic algorithm, with the standard to be drafted in 2023. These algorithms aim to implement post-quantum secure key encapsulation mechanism (KEM) and digital signatures. However, the proposed algorithm does not consider authentication and is vulnerable to attacks such as man-in-the-middle. In this paper, we propose an authenticated key exchange algorithm to solve the...

The recently standardized secure group messaging protocol Messaging Layer Security (MLS) is designed to ensure asynchronous communications within large groups, with an almost-optimal communication cost and the same security level as point-to-point se- cure messaging protocols such as Signal. In particular, the core sub-protocol of MLS, a Continuous Group Key Agreement (CGKA) called TreeKEM, must generate a common group key that respects the fundamental security properties of post-compromise...

The existence of a quantum computer is one of the most significant threats cryptography has ever faced. However, it seems that real world protocols received little attention so far with respect to their future security. Indeed merely relying upon post-quantum primitives may not suffice in order for a security protocol to be resistant in a full quantum world. In this paper, we consider the fundamental UMTS key agreement used in 3G but also in 4G (LTE), and in the (recently deployed) 5G...

In May 2020, Zoom Video Communications, Inc. (Zoom) announced a multi-step plan to comprehensively support end-to-end encrypted (E2EE) group video calls and subsequently rolled out basic E2EE support to customers in October 2020. In this work we provide the first formal security analysis of Zoom's E2EE protocol, and also lay foundation to the general problem of E2EE group video communication. We observe that the vast security literature analyzing asynchronous messaging does not translate...

We show that the Nikooghadam-Shahriari-Saeidi authentication and key agreement scheme [J. Inf. Secur. Appl., 76, 103523 (2023)] cannot resist impersonation attack, not as claimed. An adversary can impersonate the RFID reader to cheat the RFID tag. The drawback results from its simple secret key invoking mechanism. We also find it seems difficult to revise the scheme due to the inherent flaw.

Post-compromise security (PCS) has been a core goal of end-to-end encrypted messaging applications for many years, both in one-to-one continuous key agreement (CKA) and for groups (CGKA). At its essence, PCS relies on a compromised party to perform a key update in order to `self-heal'. However, due to bandwidth constraints, receive-only mode, and various other environmental demands of the growing number of use cases for such CGKA protocols, a group member may not be able to issue such...

There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89). However, the distribution of quantum public keys is a...

We show that the Yang et al.'s key agreement scheme [Future Gener. Comput. Syst., 145, 415-428 (2023)] is flawed. (1) There are some inconsistent computations, which should be corrected. (2) The planned route of a target vehicle is almost exposed. The scheme neglects the basic requirement for bit-wise XOR, and tries to encrypt the route by the operator. The negligence results in some trivial equalities. (3) The scheme is insecure against impersonation attack launched by the next roadside unit.

We show that the Cherbal-Benchetioui key agreement scheme [Comput. Electr. Eng., 109, 108759 (2023)] fails to keep user anonymity, not as claimed. The scheme simply thinks that user anonymity is equivalent to protecting the user's real identity. But the true anonymity means that the adversary cannot attribute different sessions to target entities, which relates to entity-distinguishable, not just identity-revealable.

We show that the Xu et al.'s authentication and key agreement scheme [IEEE Trans. Ind. Informatics, 18(10), 7118-7127, 2022] is flawed. (1) It confused some operations for bilinear maps and presented some inconsistent computations. (2) It failed to keep anonymity, not as claimed. The adversary can use any device's public key stored in the blockchain to test some verification equations so as to reveal the identity of a target device.

We show that the key agreement scheme [Quantum Inf. Process., 20:188, 2021] is flawed. (1) It requires that the quantum channel must be intact so as to keep the transferred photon sequences complete and undamaged, even if the channel is tapped. But this is unrealistic because of quantum non-cloning theorem. (2) The user's capability is artificially assumed, who can measure a hybrid photon sequence only with $Z$-basis, unable to measure with $X$-basis. (3) It requires an authenticated...

We show that the scheme [Neurocomputing, 2022 (500), 741-749] fails to keep anonymity, not as claimed. The scheme neglects the basic requirement for bit-wise XOR, and tries to encrypt data by the operator. The negligence results in some trivial equalities. An adversary can retrieve the user's identity from one captured string via the open channel.

We show that the key agreement scheme [J. Supercomput., 78:12093-12113, 2022] is flawed. (1) It neglects the representation of a point over an elliptic curve and the basic requirement for bit-wise XOR, which results in a trivial equality. By the equality, an adversary can recover a target device's identity, which means the scheme fails to keep anonymity. (2) It falsely requires that the central server should share its master secret key with each dew server. (3) The specified certificate...

We show that the key agreement scheme [J. Syst. Archit., 131:102698, 2022] fails to keep user anonymity and service provider anonymity, not as claimed. The scheme simply thinks that user anonymity is equivalent to protecting the target user's identity against exposure, while its long-term pseudo-identity can be exposed. We want to clarify that the true anonymity means that an adversary cannot attribute different sessions to different target users, even if the true identifier cannot be...

A recent series of works (Hecht, IACR ePrint, 2020–2021) propose to build post-quantum public-key encapsulation, digital signatures, group key agreement and oblivious transfer from "R-propped" variants of the Symmetrical Decomposition and Discrete Logarithm problems for matrix groups over $\mathbb{F}_{2^8}$. We break all four proposals by presenting a linearisation attack on the Symmetrical Decomposition platform, a forgery attack on the signature scheme, and a demonstration of the...

Developing end-to-end encrypted instant messaging solutions for group conversations is an ongoing challenge that has garnered significant attention from practitioners and the cryptographic community alike. Notably, industry-leading messaging apps such as WhatsApp and Signal Messenger have adopted the Sender Keys protocol, where each group member shares their own symmetric encryption key with others. Despite its widespread adoption, Sender Keys has never been formally modelled in the...

Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be attacked by an $O(\ell^2)$-query adversary. This quadratic gap matches the key-agreement protocol proposed by Merkle (CACM 78), known as ...

In this paper a method to build Secret Agreement algorithms is pre- sented, which only requires an abelian group and at least one automor- phism of the operator of this group. An example of such an algorithm is also presented. Knowledge of entropic quasigroups and Bruck-Murdoch- Toyoda theorem on how to build a quasigroup with these two elements is assumed.

We show that the scheme [Clust. Comput. 25(1): 451-468, 2022] fails to keep anonymity, not as claimed. The scheme simply acknowledges that user anonymity is equivalent to protecting the target user's identity against exposure, while its long-term pseudo-identity can be exposed. We want to clarify that the true anonymity means that an adversary cannot attribute different sessions to different target users, even though the adversary cannot recover the true identifier from the long-term...

In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a quadratic gap between the query complexity of the honest parties and the eavesdropper. This quadratic gap is known to be optimal, by the works of Impagliazzo and Rudich [STOC ’89] and Barak and Mahmoody [Crypto...

We show that the key agreement scheme [IEEE Trans. Veh. Technol. 71(4): 3470-3479, 2022] fails to keep user anonymity, not as claimed.

The accelerated advances in information communication technologies have made it possible for enterprises to deploy large scale applications in a multi-server architecture (also known as cloud computing environment). In this architecture, a mobile user can remotely obtain desired services over the Internet from multiple servers by initially executing a single registration on a trusted registration server (RS). Due to the hazardous nature of the Internet, to protect user privacy and online...

We instantiate the hash-then-evaluate paradigm for pseudorandom functions (PRFs), $\mathsf{PRF}(k, x) := \mathsf{wPRF}(k, \mathsf{RO}(x))$, which builds a PRF $\mathsf{PRF}$ from a weak PRF $\mathsf{wPRF}$ via a public preprocessing random oracle $\mathsf{RO}$. In applications to secure multiparty computation (MPC), only the low-complexity wPRF performs secret-depending operations. Our construction replaces RO by $f(k_H , \mathsf{elf}(x))$, where $f$ is a non-adaptive PRF and the key $k_H$...

Continuous Group-Key Agreement (CGKA) allows a group of users to maintain a shared key. It is the fundamental cryptographic primitive underlying group messaging schemes and related protocols, most notably TreeKEM, the underlying key agreement protocol of the Messaging Layer Security (MLS) protocol, a standard for group messaging by the IETF. CKGA works in an asynchronous setting where parties only occasionally must come online, and their messages are relayed by an untrusted server. The...

We show that the key agreement scheme [IEEE Internet Things J., 9(12), 2022, 9918--9933] is flawed. In order to authenticate each other, all participants use message authentication code (MAC) to generate tags for exchanged data. But MAC is a cryptographic technique which requires that the sender and receiver share a symmetric key. The scheme tries to establish a new shared key by using an old shared key, which results in a vicious circle. To the best of our knowledge, it is the first time...

We show that the key agreement scheme [Multim. Tools Appl. 80:799-829, 2021] is flawed. (1) The scheme is a hybrid which piles up various tools such as public key encryption, signature, symmetric key encryption, hash function, cancelable templates from thumb fingerprints, and elliptic curve cryptography. These tools are excessively used because key agreement is just a simple cryptographic primitive in contrast to public key encryption. (2) The involved reliance is very intricate....

We show that the key agreement scheme [J. Syst. Archit., 116: 102053, 2021] is flawed. It makes use of a symmetric key encryption to transfer data between the user and server. But the symmetric key is easily retrieved by an adversary, which results in the loss of data confidentiality, and makes it vulnerable to impersonation attack.

We present Owl, an augmented password-authenticated key exchange (PAKE) protocol that is both efficient and supported by security proofs. Owl is motivated by recognized limitations in SRP-6a and OPAQUE. SRP-6a is the only augmented PAKE that has enjoyed wide use in practice to date, but it lacks the support of formal security proofs, and does not support elliptic curve settings. OPAQUE was proposed in 2018 as a provably secure and efficient alternative to SRP-6a, and was chosen by the IETF...

We remark that the key agreement scheme [IEEE Trans. Veh. Technol. 2021, 70(2): 1736--1751] fails to keep anonymity and untraceability, because the user $U_k$ needs to invoke the public key $PK_{U_j}$ to verify the signature generated by the user $U_j$. Since the public key is compulsively linked to the true identity $ID_{U_j}$ for authentication, any adversary can reveal the true identity by checking the signature.

We show that the key agreement scheme [Internet of Things, 2022(18): 100493] is flawed. (1) It neglects the structure of an elliptic curve and presents some false computations. (2) The scheme is insecure against key compromise impersonation attack.

We show that the key agreement scheme [Comput. Commun., 2021(170): 1--18] is insecure against impersonation attacks, because there is a trivial equality which results in the loss of data confidentiality.

We show that the data de-duplication scheme [Internet of Things, 2021(14): 100376] is flawed. (1) There are some inconsistent notations and false equations, which should be corrected. (2) The scheme fails to keep user anonymity, not as claimed. (3) The scheme could fail to keep data confidentiality.

We remark that the key agreement scheme [IEEE Internet Things J., 8(5), 2021, 3801--3811] is flawed. (1) It is insecure against internal attack, because any unauthorized sensing device (not revoked) can retrieve the final session key. (2) It could be insecure against external attack.

Continuous Group Key Agreement (CGKA) lets a evolving group of clients agree on a sequence of group keys. An important application of CGKA is scalable asynchronous end-to-end (E2E) encrypted group messaging. A major problem preventing the use of CGKA over unreliable infrastructure are so-called forks. A fork occurs when group members have diverging views of the group's history (and thus its current state); e.g. due to network or server failures. Once communication channels are restored,...

The Extended Access Control (EAC) protocol for authenticated key agreement is mainly used to secure connections between machine-readable travel documents (MRTDs) and inspection terminals, but it can also be adopted as a universal solution for attribute-based access control with smart cards. The security of EAC is currently based on the Diffie-Hellman problem, which may not be hard when considering quantum computers. In this work we present PQ-EAC, a quantum-resistant version of the EAC...

Motivated by applications to the internet of things (IoT), Cremers, Naor, Paz, and Ronen (CRYPTO '22) recently considered a setting in which multiple parties share a common password and want to be able to pairwise authenticate. They observed that using standard password-authenticated key exchange (PAKE) protocols in this setting allows for catastrophic impersonation attacks whereby compromise of a single party allows an attacker to impersonate any party to any other. To address this, they...

Current messaging protocols are incapable of detecting active man-in-the-middle threats. Even common continuous key agreement protocols such as Signal, which offers forward secrecy and post-compromise security, are dependent on the adversary being passive immediately following state compromise, and healing guarantees are lost if the attacker is not. This work offers the first solution for detecting active man-in-the-middle attacks on such protocols by extending authentication beyond the...

Hecht and Scolnik proposed key agreement using rectangular matrices and determinants. This report describes an attack.

The elliptic curve family of schemes has the lowest computational latency, memory use, energy consumption, and bandwidth requirements, making it the most preferred public key method for adoption into network protocols. Being suitable for embedded devices and applicable for key exchange and authentication, ECC is assuming a prominent position in the field of IoT cryptography. The attractive properties of the relatively new curve Curve448 contribute to its inclusion in the TLS1.3 protocol and...

Secure messaging (SM) protocols allow users to communicate securely over an untrusted infrastructure. The IETF currently works on the standardization of secure group messaging (SGM), which is SM done by a group of two or more people. Alwen et al. formally defined the key agreement protocol used in SGM as continuous group key agreement (CGKA) at CRYPTO 2020. In their CGKA protocol, all of the group members have the same rights and a trusted third party is needed. On the contrary, some SGM...

Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group...

Many real-world group messaging systems delegate group administration to the application level, failing to provide formal guarantees related to group membership. Taking a cryptographic approach to group administration can prevent both implementation and protocol design pitfalls that result in a loss of confidentiality and consistency for group members. In this work, we introduce a cryptographic framework for the design of group messaging protocols that offer strong security guarantees for...

In this paper, we present an original algorithm to generate session keys and a subsequent generalized ElGamal-type cryptosystem. The scheme presented here has been designed to prevent both linear and brute force attacks using rectangular matrices and to achieve high complexity. Our algorithm includes a new generalized Diffie-Hellmann scheme based on rectangular matrices and polynomial field operations. Two variants are presented, the first with a double exchange between the parties and the...

Continuous Group Key Agreement (CGKA) is the basis of modern Secure Group Messaging (SGM) protocols. At a high level, a CGKA protocol enables a group of users to continuously compute a shared (evolving) secret while members of the group add new members, remove other existing members, and perform state updates. The state updates allow CGKA to offer desirable security features such as forward secrecy and post-compromise security. CGKA is regarded as a practical primitive in the...

Cloud storage provides highly available and low cost resources to users. However, as massive amounts of outsourced data grow rapidly, an effective data deduplication scheme is necessary. This is a hot and challenging field, in which there are quite a few researches. However, most of previous works require dual-server fashion to be against brute-force attacks and do not support batch checking. It is not practicable for the massive data stored in the cloud. In this paper, we present a secure...

With the rapid development of Internet of Things (IoT), designing a secure two-factor authentication scheme for these network is increasingly demanding. Recently, historical bigdata has gained interest as a novel authentication factor in this area. In this paper, we focus on a recent authentication scheme using bigdata (Liu et al.’s scheme) which claims to provide additional security properties such as Perfect Forward Secrecy (PFS), Key Compromise Impersonation (KCI) resilience...

Hash chains are a simple way to generate pseudorandom data, but are inefficient in situations that require long chains. This can cause unnecessary overhead for use cases including logical clocks, synchronizing the heads of a pseudorandom stream, or non-interactive key agreement. This paper presents the “skip ratchet”, a novel pseudorandom function that can be efficiently incremented by arbitrary intervals.

In this paper, we proposed some vulnerabilities of a recent pairing-based certificateless authenticated key agreement protocol for blockchain-based wireless body area networks (WBAN). According to our analysis, this protocol is insecure against key offset attack (KOA), basic impersonation attack (BIA), and man-in-the-middle attack (MMA) of the malicious key generation center (KGC) administrators. We also found and pointed out some errors in the description of the protocol.

The potential advent of large-scale quantum computers in the near future poses a threat to contemporary cryptography. One ubiquitous usage of cryptography is currently present in the vibrant field of cellular networks. The cryptography of cellular networks is centered around seven secret-key algorithms $f_1, \ldots, f_5, f_1^{*}, f_5^{*}$, aggregated into an authentication and key agreement algorithm set. Still, to the best of our knowledge, these secret key algorithms have not yet...

Introducing small errors in the lattice-based key exchange protocols, although it is resistant to quantum computing attacks, will cause both parties to only get roughly equal secret values, which brings uncertainty to the negotiation of the key agreement. The role of the error reconciliation mechanism is to eliminate this uncertainty and ensure that both parties can reach a consensus. This paper designs a new error reconciliation mechanism: Speedy Error Reconciliation (SER), which can...

We consider the streaming variant of the Bounded Storage Model (BSM), where the honest parties can stream large amounts of data to each other, while only maintaining a small memory of size $n$. The adversary also operates as a streaming algorithm, but has a much larger memory size $m \gg n$. The goal is to construct unconditionally secure cryptographic schemes in the BSM, and prior works did so for symmetric-key encryption, key agreement, oblivious transfer and multiparty computation. In...

Continuous group key agreement (CGKA) allows a group of users to maintain a continuously updated shared key in an asynchronous setting where parties only come online sporadically and their messages are relayed by an untrusted server. CGKA captures the basic primitive underlying group messaging schemes. Current solutions including TreeKEM ("Messaging Layer Security'' (MLS) IETF RFC 9420) cannot handle concurrent requests while retaining low communication complexity. The exception being...

Quantum computers will break cryptographic primitives that are based on integer factorization and discrete logarithm problems. SABER is a key agreement scheme based on the Learning With Rounding problem that is quantum-safe, i.e., resistant to quantum computer attacks. This article presents a high-speed silicon implementation of SABER in a 65nm technology as an Application Specific Integrated Circuit. The chip measures 1$mm^2$ in size and can operate at a maximum frequency of 715$MHz$ at a...

Implantable Medical Devices (IMDs) are widely deployed today and often use wireless communication. Establishing a secure communication channel to these devices is vital, however, also challenging in practice. To address this issue, numerous researchers have proposed IMD key exchange protocols, in particular ones that leverage an Out-Of-Band (OOB) channel such as audio, vibration and physiological signals. These solutions have advantages over traditional key exchange, e.g.,...

We study witness-authenticated key exchange (WAKE), in which parties authenticate through knowledge of a witness to any NP statement. WAKE achieves generic authenticated key exchange in the absence of trusted parties; WAKE is most suitable when a certificate authority is either unavailable or undesirable, as in highly decentralized networks. In practice WAKE approximates witness encryption, its elusive non-interactive analogue, at the cost of minimal interaction. This work is the first to...

Seminal works by Cohn-Gordon, Cremers, Dowling, Garratt, and Stebila [EuroS&P 2017] and Alwen, Coretti and Dodis [EUROCRYPT 2019] provided the first formal frameworks for studying the widely-used Signal Double Ratchet (DR for short) algorithm. In this work, we develop a new Universally Composable (UC) definition F_DR that we show is provably achieved by the DR protocol. Our definition captures not only the security and correctness guarantees of the DR already identified in the prior...

We study communication complexity in computational settings where bad inputs may exist, but they should be hard to find for any computationally bounded adversary. We define a model where there is a source of public randomness but the inputs are chosen by a computationally bounded adversarial participant after seeing the public randomness. We show that breaking the known communication lower bounds of the private coins model in this setting is closely connected to known cryptographic...

Messaging platforms like Signal are widely deployed and provide strong security in an asynchronous setting. It is a challenging problem to construct a protocol with similar security guarantees that can \emph{efficiently} scale to large groups. A major bottleneck are the frequent key rotations users need to perform to achieve post compromise forward security. In current proposals -- most notably in TreeKEM (which is part of the IETF's Messaging Layer Security (MLS) protocol draft) -- for...

We study the following question, first publicly posed by Hosoyamada and Yamakawa in 2018. Can parties Alice and Bob with quantum computing power and classical communication rely only on a random oracle (that can be queried in quantum superposition) to agree on a key that is private from eavesdroppers? We make the first progress on the question above and prove the following. When only one of the parties is classical and the other party is quantum powered, as long as they ask a total of $d$...

In this paper we investigate the field of privacy-preserving authenticated key exchange protocols (PPAKE). First we make a cryptographic analysis of a previous PPAKE protocol. We show that most of its security properties, including privacy, are broken, despite the security proofs that are provided. Then we describe a strong security model which captures the security properties of a PPAKE: entity authentication, key indistinguishability, forward secrecy, and privacy. Finally, we present a...

Multicast Key Agreement (MKA) is a long-overlooked natural primitive of large practical interest. In traditional MKA, an omniscient group manager privately distributes secrets over an untrusted network to a dynamically-changing set of group members. The group members are thus able to derive shared group secrets across time, with the main security requirement being that only current group members can derive the current group secret. There indeed exist very efficient MKA schemes in the...

We propose design methodologies for building a compact, unified and programmable cryptoprocessor architecture that computes post-quantum key agreement and digital signature. Synergies in the two types of cryptographic primitives are used to make the cryptoprocessor compact. As a case study, the cryptoprocessor architecture has been optimized targeting the signature scheme 'CRYSTALS-Dilithium' and the key encapsulation mechanism (KEM) 'Saber', both finalists in the NIST’s post-quantum...

Continuous Group Key Agreement (CGKA) -- or Group Ratcheting -- lies at the heart of a new generation of scalable End-to-End secure (E2E) cryptographic multi-party applications. One of the most important (and first deployed) CGKAs is ITK which underpins the IETF's upcoming Messaging Layer Security E2E secure group messaging standard. To scale beyond the group sizes possible with earlier E2E protocols, a central focus of CGKA protocol design is to minimize bandwidth requirements (i.e....

Continuous group key agreements (CGKAs) are a class of protocols that can provide strong security guarantees to secure group messaging protocols such as Signal and MLS. Protection against device compromise is provided by commit messages: at a regular rate, each group member may refresh their key material by uploading a commit message, which is then downloaded and processed by all the other members. In practice, propagating commit messages dominates the bandwidth consumption of existing...

Drone-based applications continue to garner a lot of attention due to their significant potential in both commercial and non-commercial use. Owing to this increasing popularity, researchers have begun to pay attention to the communication security requirements involved in deploying drone-based applications and services on a large scale, with particular emphasis on group communication. The majority of existing works in this field focus on the use of symmetric key cryptographic schemes or...

Implantable medical devices, sensors and wearables are widely deployed today. However, establishing a secure wireless communication channel to these devices is a major challenge, amongst others due to the constraints on energy consumption and the need to obtain immediate access in emergencies. To address this issue, researchers have proposed various key agreement protocols based on the measurement of physiological signals such as a person's heart signal. At the core of such protocols are...

The goal of the bounded storage model (BSM) is to construct unconditionally secure cryptographic protocols, by only restricting the storage capacity of the adversary, but otherwise giving it unbounded computational power. Here, we consider a streaming variant of the BSM, where honest parties can stream huge amounts of data to each other so as to overwhelm the adversary's storage, even while their own storage capacity is significantly smaller than that of the adversary. Prior works showed...

In the effort to transition cryptographic primitives and protocols to quantum-resistant alternatives, an interesting and useful challenge is found in the Signal protocol. The initial key agreement component of this protocol, called X3DH, has so far proved more subtle to replace - in part due to the unclear security model and properties the original protocol is designed for. This paper defines a formal security model for the original signal protocol, in the context of the standard eCK and CK+...

We describe a protocol for two-party private set intersection (PSI) based on Diffie-Hellman key agreement. The protocol is proven secure against malicious parties, in the ideal permutation + random oracle model. For small sets (500 items or fewer), our protocol requires the least time and communication of any known PSI protocol, even ones that are only semi-honest secure and ones that are not based on Diffie-Hellman. It is one of the few significant improvements to the 20-year old classical...

Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced)...

Pairings have been widely used since their introduction to cryptography. They can be applied to identity-based encryption, tripartite Diffie-Hellman key agreement, blockchain and other cryptographic schemes. The Acceleration of pairing computations is crucial for these cryptographic schemes or protocols. In this paper, we will focus on the Elliptic Net algorithm which can compute pairings in polynomial time, but it requires more storage than Miller’s algorithm. We use several methods to...