More Like this

1. Short Concurrent Covert Authenticated Key Exchange (Short cAKE)

   https://doi.org/10.1007/978-981-99-8742-9_3  

   Eldefrawy, Karim; Genise, Nicholas; Jarecki, Stanislaw (January 2023, Springer Nature Singapore)

   on Ahn, Hopper and Langford introduced the notion of steganographic a.k.a. covert computation, to capture distributed computation where the attackers must not be able to distinguish honest parties from entities emitting random bitstrings. This indistinguishability should hold for the duration of the computation except for what is revealed by the intended outputs of the computed functionality. An important case of covert computation is mutually authenticated key exchange, a.k.a. mutual authentication. Mutual authentication is a fundamental primitive often preceding more complex secure protocols used for distributed computation. However, standard authentication implementations are not covert, which allows a network adversary to target or block parties who engage in authentication. Therefore, mutual authentication is one of the premier use cases of covert computation and has numerous real-world applications, e.g., for enabling authentication over steganographic channels in a network controlled by a discriminatory entity. We improve on the state of the art in covert authentication by presenting a protocol that retains covertness and security under concurrent composition, has minimal message complexity, and reduces protocol bandwidth by an order of magnitude compared to previous constructions. To model the security of our scheme we develop a UC model which captures standard features of secure mutual authentication but extends them to covertness. We prove our construction secure in this UC model. We also provide a proof-of-concept implementation of our scheme. 

   more » « less
2. Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents

   https://doi.org/10.1145/3578579  

   Geffner, Ivan; Halpern, Joseph Y. (April 2023, Journal of the ACM)

   Abraham, Dolev, Geffner, and Halpern [ 1 ] proved that, in asynchronous systems, a (k, t)-robust equilibrium for n players and a trusted mediator can be implemented without the mediator as long as n > 4( k+t ), where an equilibrium is ( k, t )-robust if, roughly speaking, no coalition of t players can decrease the payoff of any of the other players, and no coalition of k players can increase their payoff by deviating. We prove that this bound is tight, in the sense that if n ≤ 4( k+t ) there exist ( k, t )-robust equilibria with a mediator that cannot be implemented by the players alone. Even though implementing ( k, t )-robust mediators seems closely related to implementing asynchronous multiparty ( k+t )-secure computation [ 6 ], to the best of our knowledge there is no known straightforward reduction from one problem to another. Nevertheless, we show that there is a non-trivial reduction from a slightly weaker notion of ( k+t )-secure computation, which we call ( k+t )-strict secure computation , to implementing ( k, t )-robust mediators. We prove the desired lower bound by showing that there are functions on n variables that cannot be ( k+t )-strictly securely computed if n ≤ 4( k+t ). This also provides a simple alternative proof for the well-known lower bound of 4 t +1 on asynchronous secure computation in the presence of up to t malicious agents [ 4 , 8 , 10 ]. 

   more » « less
3. Bounded Collusion ABE for TMs from IBE

   https://doi.org/yes10.1007/978-3-030-92068-5_13  

   Goyal, Rishab; Syed, Ridwan; Waters, Brent (December 2021, Asiacrypt 2021)

   We give an attribute-based encryption system for Turing Machines that is provably secure assuming only the existence of identity-based encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search Diffie-Hellman assumption, and the Learning with Errors assumption. Our core construction provides security against an attacker that makes a single key query for a machine before declaring a challenge string that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova, and Wichs; however, to prove security we need to introduce a new notion of security called iterated simulation security. We then show how to transform our core construction into one that is secure for an a-priori bounded number of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of non-committing encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this non-committing encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from single-key adaptive security to -key adaptive security. 

   more » « less
4. Password-Protected Threshold Signatures

   https://doi.org/10.1007/978-981-96-0891-1_6  

   Dziembowski, Stefan; Jarecki, Stanislaw; Kedzior, Pawel; Krawczyk, Hugo; Ngo, Chan Nam; Xu, Jiayu (December 2024, Springer Nature Singapore)

   Chung, KM; Sasaki, Y (Ed.)

   We witness an increase in applications like cryptocurrency wallets, which involve users issuing signatures using private keys. To protect these keys from loss or compromise, users commonly outsource them to a custodial server. This creates a new point of failure, because compromise of such a server leaks the user’s key, and if user authentication is implemented with a password then this password becomes open to an offline dictionary attack (ODA). A better solution is to secret-share the key among a set of servers, possibly including user’s own device(s), and implement password authentication and signature computation using threshold cryptography. We propose a notion of augmented password-protected threshold signature (aptSIG) scheme which captures the best possible security level for this setting. Using standard threshold cryptography techniques, i.e. threshold password authentication and threshold signatures, one can guarantee that compromising up to t out of n servers reveals no information on either the key or the password. However, we extend this with a novel property, that compromising even all n servers also does not leak any information, except via an unavoidable ODA attack, which reveals the key only if the attacker guesses the password. We define aptSIG in the Universally Composable (UC) framework and show that it can be constructed very efficiently, using a black-box composition of any UC threshold signature [13] and a UC augmented Password-Protected Secret Sharing (aPPSS), which we define as an extension of prior notion of PPSS [30]. As concrete instantiations we obtain secure aptSIG schemes for ECDSA (in the case of t=n-1) and BLS signatures with very small overhead over the respective threshold signature. Finally, we note that both the notion and our generic solution for augmented password-protected threshold signatures can be generalized to password-protecting MPC for any keyed functions. 

   more » « less
5. Towards Multiparty Computation Withstanding Coercion of All Parties

   Canetti, Ran; Poburinnaya, Oxana (November 2021, Theory of Cryptography Conference)

   null (Ed.)

   Incoercible multi-party computation (Canetti-Gennaro ’96) allows parties to engage in secure computation with the additional guarantee that the public transcript of the computation cannot be used by a coercive outsider to verify representations made by the parties regarding their inputs, outputs, and local random choices. That is, it is guaranteed that the only deductions regarding the truthfulness of such representations, made by an outsider who has witnessed the communication among the parties, are the ones that can be drawn just from the represented inputs and outputs alone. To date, all incoercible secure computation protocols withstand coercion of only a fraction of the parties, or else assume that all parties use an execution environment that makes some crucial parts of their local states physically inaccessible even to themselves. We consider, for the first time, the setting where all parties are coerced, and the coercer expects to see the entire history of the computation. We allow both protocol participants and external attackers to access a common reference string which is generated once and for all by an uncorruptable trusted party. In this setting we construct: - A general multi-party function evaluation protocol, for any number of parties, that withstands coercion of all parties, as long as all parties use the prescribed ``faking algorithm'' upon coercion. This holds even if the inputs and outputs represented by coerced parties are globally inconsistent with the evaluated function. - A general two-party function evaluation protocol that withstands even the %``mixed'' case where some of the coerced parties do follow the prescribed faking algorithm. (For instance, these parties might collude with the coercer and disclose their true local states.) This protocol is limited to functions where the input of at least one of the parties is taken from a small (poly-size) domain. It uses fully deniable encryption with public deniability for one of the parties; when instantiated using the fully deniable encryption of Canetti, Park, and Poburinnaya (Crypto'20), it takes 3 rounds of communication. Both protocols operate in the common reference string model, and use fully bideniable encryption (Canetti Park and Poburinnaya, Crypto'20) and sub-exponential indistinguishability obfuscation. Finally, we show that protocols with certain communication pattern cannot be incoercible, even in a weaker setting where only some parties are coerced. 

   more » « less