Modular exponentiation is a vital function in public key cryptography. Dozens of protocols, including encryption schemes, signature schemes, pseudorandom functions, and more, perform this operation on a secret base and/or a secret exponent. In a multiparty computation setting, these secret data might be shared over multiple parties who wish to compute this modular exponentiation in a secure and distributed way. However, whereas typical frameworks for secure multiparty computation based on secret sharing provide a basic tool box of secure distributed computation of, most importantly, randomness generation, addition, and multiplication, the status quo of secure distributed modular exponentiation is unsatisfactory. In this work, we provide a complete and comprehensive overview on existing protocols for perfectly secure distributed exponentiation differing depending on whether the inputs and outcomes are public or shared. We perform a detailed complexity computation of the currently existing protocols, observing that earlier authors have overestimated the complexity of their own protocols, and close the remaining open problem: protocols for secure distributed exponentiation with secret base, secret exponent, and public outcome. We prove that the presented protocol is universally composably secure in the presence of malicious adversaries. We finally exemplify the practical relevance of the new protocol by demonstrating how it can be used for pseudorandom generation and signing.

Implementation attacks such as power analysis and fault attacks have shown that, if potential attackers have physical access to a cryptographic device, achieving practical security requires more considerations apart from just cryptanalytic security. In recent years, and with the advent of micro-architectural or hardware-oriented attacks, it became more and more clear that similar attack vectors can also be exploited on larger computing platforms and without the requirement of physical proximity of an attacker. While newly discovered attacks typically come with implementation recommendations that help counteract a specific attack vector, the process of constantly patching cryptographic code is quite time consuming in some cases, and simply not possible in other cases.

We propose HERMES, a scalable, secure, and privacy-enhancing system for users to share and access vehicles. HERMES securely outsources operations of vehicle access token (AT) generation to a set of untrusted servers. It builds on an earlier proposal, namely, SePCAR, and extends the system design for improved efficiency and scalability. To cater to system and user needs for secure and private computations, HERMES utilizes and combines several cryptographic primitives with secure multiparty computation (MPC) efficiently. It conceals secret keys of vehicles and transaction details from the servers, including vehicle booking details, AT information, and user and vehicle identities. It also provides user accountability in case of disputes. Besides, we provide semantic security analysis and prove that HERMES meets its security and privacy requirements. Last but not least, we demonstrate that HERMES is efficient and, in contrast to SePCAR, scales to a large number of users and vehicles, making it practical for real-world deployments. We build our evaluations with two different MPC protocols: 1) HtMAC-MiMC and 2) CBC-MAC-AES. Our results demonstrate that HERMES is in the range of milliseconds for generating an AT, whether it operates for a single-vehicle owner or a large rental-company branch with over 1000 vehicles; handling 546 and 84 AT generations per second, respectively. As a result, HERMES is an order of magnitude faster compared to SePCAR. Specifically, it delivers 696 (with HtMAC-MiMC) and 42 (with CBC-MAC-AES) more ATs compared to in SePCAR for a single-vehicle owner AT generation. Furthermore, we show that HERMES is practical on the vehicle side, too, as AT operations performed on a prototype vehicle on-board unit take only$\approx 62 $ms.

Abstract Symmetric cryptographic primitives are often exposed to invariances: deterministic relations between plaintexts and ciphertexts that propagate through the primitive. Recent invariant subspace attacks have shown that these can be a serious issue. One way to mitigate invariant subspace attacks is at the primitive level, namely by proper use of round constants (Beierle et al., CRYPTO 2017). In this work, we investigate how to thwart invariance exploitation at the mode level, namely by assuring that a mode never evaluates its underlying primitive under any invariance. We first formalize the use of invariant cryptographic permutations from a security perspective, and analyze the Even-Mansour block cipher construction. We further demonstrate how the model composes, and apply it to the keyed sponge construction. The security analyses exactly pinpoint how the presence of linear invariances affects the bounds compared with analyses in the random permutation model. As such, they give an exact indication how invariances can be exploited. From a practical side, we apply the derived security bounds to the case where the Even-Mansour construction is instantiated with the 512-bit ChaCha permutation, and derive a distinguishing attack against Even-Mansour-ChaCha in $$2^{128}$$ 2 128 queries, faster than the birthday bound. Comparable results are derived for instantiation using the 200-bit Keccak permutation without round constants (attack in $$2^{50}$$ 2 50 queries), the 1024-bit CubeHash permutation (attack in $$2^{256}$$ 2 256 queries), and the 384-bit Gimli permutation without round constants (attack in $$2^{96}$$ 2 96 queries). The attacks do not invalidate the security of the permutations themselves, but rather they demonstrate the tightness of our bounds and confirm that care should be taken when employing a cryptographic primitive that has nontrivial linear invariances.

We consider a generalized construction of stream ciphers with forward security. The design framework is modular: it is built from a so-called layer function that updates the key and (optionally) the nonce and generates a new pseudorandom output stream. We analyze the generalized construction for four different instantiations: two possible layer functions that are in turn instantiated with either a block cipher or a pseudorandom function. We prove that each of these instantiations gives a stream cipher that is pseudorandom and forward secure in the multi-user setting with a very tight bound. A comprehensive analysis shows that the two block cipher based instantiations achieve very similar bounds. For the pseudorandom function based instantiations there is no clear winner: either layer can be beneficial over the other one, depending on the choice of parameters. By instantiating the pseudorandom function with a generic construction such as the sum of permutations, we obtain a highly efficient and competitive stream cipher based on an n-bit block cipher that is secure beyond the$2^{\text {n}/2}$birthday bound.

We analyze the authenticated encryption algorithm of ORANGE, a submission to the NIST lightweight cryptography standardization process. We show that it is practically possible to craft forgeries out of two observed transmitted messages that encrypt the same plaintext. The authors of ORANGE have confirmed the attack, and they discuss a fix for this attack in their second-round submission of ORANGE to the NIST lightweight cryptography competition.

The Sponge function is known to achieve $$2^{c/2}$$ security, where c is its capacity. This bound was carried over to its keyed variants, such as SpongeWrap, to achieve a $$\min \{2^{c/2},2^\kappa \}$$ security bound, with $$\kappa $$ the key length. Similarly, many CAESAR competition submissions were designed to comply with the classical $$2^{c/2}$$ security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of $$\min \{2^{b/2},2^c,2^\kappa \}$$ , with $$b>c$$ the permutation size, by proving that the CAESAR submission NORX achieves this bound. The proof relies on rigorous computation of multi-collision probabilities, which may be of independent interest. We additionally derive a generic attack based on multi-collisions that matches the bound. We show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of some of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. We finally consider the remaining one of the three PRIMATEs, APE, and derive a blockwise adaptive attack in the nonce-respecting setting with complexity $$2^{c/2}$$ , therewith demonstrating that the techniques cannot be applied to APE.

The significance of understanding blockcipher security in the multi-key setting is highlighted by the extensive literature on attacks, and how effective key size can be significantly reduced. Nevertheless, little attention has been paid in formally understanding the design of multi-key secure blockciphers. In this work, we formalize the multi-key security of tweakable blockciphers in case of general key derivation functions. We show an equivalence between blockcipher multi-key security and tweakable blockcipher security. Our equivalence connects two objects of study, the iterated Even–Mansour (EUROCRYPT 2012) and the iterated Tweakable Even–Mansour (CRYPTO 2015), which establishes that results in both areas are, to a certain extent, transferable. Using our novel equivalence relation, we derive new bounds for both constructions, pave the path towards the solution of two well-studied conjectures, and show that, contrary to common knowledge, key derivation functions need not necessarily be pseudorandom functions in order to provide security: for the iterated Even–Mansour universal hash functions suffice.