Abstract Authenticated Key Exchange ( $${\textsf {AKE}}$$ AKE ) can be used in client-server applications for mutual authentication and key establishment. In scenarios where client authentication is neither feasible nor desirable, One-Sided AKE ( $${\textsf {OS-AKE}}$$ OS - AKE ) allows both parties to establish a key while only the server authenticates to the client. Thus, $${\textsf {OS-AKE}}$$ OS - AKE provides client anonymity with respect to the server, but does not allow the server to enforce any form of access control—that is, the server simply establishes a key with any client. In this paper, we introduce Anonymous AKE ( $${\textsf {A-AKE}}$$ A - AKE ) to strike a balance between classical client authentication of $${\textsf {AKE}}$$ AKE and client anonymity of $${\textsf {OS-AKE}}$$ OS - AKE . In a nutshell $${\textsf {A-AKE}}$$ A - AKE is an $${\textsf {AKE}}$$ AKE protocol where (i) the server authenticates to the client, (ii) the server can enforce access control by deciding which clients are authorized to run the key-establishment protocol, (iii) a key is established between the server and the client only if the latter is one of the authorized clients as defined by the server, and (iv) the authorized client remains anonymous (within the set of all authorized clients) with respect to the server. We introduce a security model for $${\textsf {A-AKE}}$$ A - AKE that extends popular $${\textsf {AKE}}$$ AKE models and design a general framework for instantiating $${\textsf {A-AKE}}$$ A - AKE protocols based on well-established cryptographic primitives. Finally, we instantiate several $${\textsf {AKE}}$$ AKE protocols aiming at strong security guarantees in the classical and post-quantum settings. We implement a prototype of each instantiation and provide an experimental comparison of their performance.

Anonymous Password-Authenticated Key Exchange (\sf APAKEAPAKE) can be seen as the hybrid offspring of standard key exchange and anonymous password authentication protocols. \sf APAKEAPAKE allows a client holding a low-entropy password to establish a session key with a server, provided that the client's password is in the server's set. Moreover, no information about the password input by the client or the set of valid passwords held by the server should leak to the other party-beyond whether the client's password lies or not in the server's password database. To the best of our knowledge, all \sf APAKEAPAKE proposals to date either assume client storage or force the client to remember the index assigned to its password in the server's database. Furthermore, earlier works either provide only informal definitions or fail in some sense to properly model the primitive. In this paper, we provide a formal security model for \sf APAKEAPAKE, capturing security and anonymity provisions for both clients and servers. In addition, we present two \sf APAKEAPAKE protocols that only require clients to remember a password and that attain our sought key secrecy and anonymity guarantees. Our first protocol leverages oblivious pseudo-random functions, while the second one builds upon a special type of identity-based encryption scheme.

In classical secret sharing schemes a dealer shares a secret among a set of participants in such a way that qualified subsets can reconstruct the secret, while forbidden ones do not get any kind of information about it. The basic parameter to optimize is the size of the shares, that is, the amount of secret information that the dealer has to give to participants. In this paper we formalize a notion of probabilistic secret sharing schemes, in which qualified subsets can reconstruct the secret but only with a certain controlled probability. We show that, by allowing a bounded error in the reconstruction of the secret, it is possible to drastically reduce the size of the shares the participants get (with respect to classical secret sharing schemes). We provide efficient constructions both for threshold access structures on a finite set of participants and for evolving threshold access structures, where the set of participants is potentially infinite. Some of our constructions yield shares of constant size (i.e., not depending on the number of participants) and an error probability of successfully reconstructing the secret which can be made as close to 1 as desired.

When a group key exchange protocol is executed, the session key is typically extracted from two types of secrets: long‐term keys (for authentication) and freshly generated (often random) values. The leakage of this latter so‐called ephemeral keys has been extensively analysed in the 2‐party case, yet very few works are concerned with it in the group setting. The authors provide a generic group key exchange construction that is strongly secure, meaning that the attacker is allowed to learn both long‐term and ephemeral keys (but not both from the same participant, as this would trivially disclose the session key). Their design can be seen as a compiler, in the sense that it builds on a 2‐party key exchange protocol which is strongly secure and transforms it into a strongly secure group key exchange protocol by adding only one extra round of communication. When applied to an existing 2‐party protocol from Bergsma et al ., the result is a 2‐round group key exchange protocol which is strongly secure in the standard model, thus yielding the first construction with this property.