International Association
for Cryptologic Research

Multiparty computation as a service (MPSaaS) is a promising approach for building privacy-preserving communication systems.However, in this paper, we argue that existing MPC implementations are inadequate for this application as they do not address fairness, let alone robustness. Even a single malicious server can cause the protocol to abort while seeing the output for itself, which in the context of an anonymous communication service would create a vulnerability to censorship and deanonymization attacks. To remedy this we propose a new MPC implementation, HoneyBadgerMPC, that combines a robust online phase with an optimistic offline phase that is efficient enough to run continuously alongside the online phase. We use HoneyBadgerMPC to develop an application case study, called AsynchroMix, that provides an anonymous broadcast functionality. AsynchroMix features a novel MPC program that trades off between computation and communication, allowing for low-latency message mixing in varying settings. In a cloud-based distributed benchmark with 100 nodes, we demonstrate mixing a batch of 512 messages in around 20 seconds and up to 4096 messages in around two minutes.

A tropical version of Stickel’s key exchange protocol was suggested by Grigoriev and Sphilrain [2] and successfully attacked by Kotov and Ushakov [5]. We suggest some modifications of this scheme that use commuting matrices in tropical algebra and discuss some possibilities of attacks on these new modifications. We suggest some simple heuristic attacks on one of our new protocols, and then we generalize the Kotov and Ushakov attack on Stickel’s protocol and discuss the application of that generalised attack to all our new protocols

The boomerang attack, introduced by Wagner in 1999, is a cryptanalysis technique against block ciphers based on differential cryptanalysis. In particular it takes into consideration two differentials, one for the upper part of the cipher and one for the lower part, and it exploits the dependency of these two differentials.

At Eurocrypt'18, Cid et al. introduced a new tool, called the Boomerang Connectivity Table (BCT) that permits to simplify this analysis. Next, Boura and Canteaut introduced an important parameter for cryptographic S-boxes called boomerang uniformity, that is the maximum value in the BCT. Very recently, the boomerang uniformity of some classes of permutations (in particular quadratic functions) have been studied by Li, Qu, Sun and Li, and by Mesnager, Chunming and Maosheng.

In this paper we further study the boomerang uniformity of some non-quadratic differentially 4-uniform functions. In particular, we consider the case of the Bracken-Leander cubic function and three classes of 4-uniform functions constructed by Li, Wang and Yu, obtained from modifying the inverse functions.

At present, the access control schemes in the power grid are centralized. In the centralized system, the data of the network sensor nodes is transmitted by centralized nodes, and the data itself may be illegally tamped with or lost, which can lead to reduced system reliability. For this feature, we apply blockchain technology to the design of access control schemes. In this paper, we propose a blockchain-based access control scheme that is suitable for multiple scenarios in the smart grid. Our access control scheme is based on an identity-based combined encryption, signature and signcryption scheme. In addition, we design a consensus algorithm in the power system for the consortium blockchain architecture to solve the key escrow problem of the untrusted third parties. Our scheme also ensures the confidentiality, integrity, authentication and non-repudiation of the data. Compared with the existing work, our scheme can use the same key pair to encrypt, sign and signcrypt the message, which has lower computation and communication costs in multiple scenarios of smart grids.

Subterranean 2.0 designed by Daemen, Massolino and Rotella is a Round 1 candidate of the NIST Lightweight Cryptography Standardization process. In the official document of Subterranean 2.0, the designers have made a cryptanalysis of the state collisions in unkeyed absorbing by reducing the number of rounds to absorb the message from 2 to 1. However, no cryptanalysis of the authenticated encryption scheme Subterranean-SAE is made. For Subterranean-SAE, the designers introduce 8 blank rounds to separate the controllable input and output, and expect that 8 blank rounds can achieve a sufficient diffusion. Therefore, it is meaningful to investigate the security by reducing the number of blank rounds. Moreover, the designers make no security claim but expect a non-trivial effort to achieve full-state recovery in nonce-misuse scenario. In this paper, we present the first full-state recovery attack in nonce-misuse scenario with practical time complexity $2^{16}$. Moreover, in a nonce-respecting scenario and if the number of blank rounds is reduced to 4, we can mount a key-recovery attack with time complexity $2^{122}$ and data complexity $2^{69.5}$. The distinguishing attack can also be achieved with time and data complexity $2^{33}$. Our cryptanalysis does not threaten the security claim for Subterranean-SAE and we hope it can help further understand the security of Subterranean-SAE.

In recent years, there has been a proliferation of algebraically structured Learning With Errors (LWE) variants, including Ring-LWE, Module-LWE, Polynomial-LWE, Order-LWE, and Middle-Product LWE, and a web of reductions to support their hardness, both among these problems themselves and from related worst-case problems on structured lattices. However, these reductions are often difficult to interpret and use, due to the complexity of their parameters and analysis, and most especially their (frequently large) blowup and distortion of the error distributions.

In this paper we unify and simplify this line of work. First, we give a general framework that encompasses all proposed LWE variants (over commutative base rings), and in particular unifies all prior "algebraic" LWE variants defined over number fields. We then use this framework to give much simpler, more general, and tighter reductions from Ring-LWE to other algebraic LWE variants, including Module-LWE, Order-LWE, and Middle-Product LWE. In particular, all our reductions have easy-to-analyze effects on the error, and in some cases they even leave the error unchanged. A main message of our work is that it is straightforward to use the hardness of the original Ring-LWE problem as a foundation for the hardness of all other algebraic LWE problems defined over number fields, via simple reductions.

We study the security of schemes related to Schnorr signatures in the algebraic group model (AGM) proposed by Fuchsbauer, Kiltz, and Loss (CRYPTO 2018), where the adversary can only compute new group elements by applying the group operation. Schnorr signatures can be proved secure in the random oracle model (ROM) under the discrete logarithm assumption (DL) by rewinding the adversary; but this security proof is loose. We start with giving a tight security proof under DL in the combination of the AGM and the ROM. Our main focus are blind Schnorr signatures, whose only known security proof is in the combination of the ROM and the generic group model, under the assumption that the so-called ROS problem is hard. We show that in the AGM+ROM the scheme is secure assuming hardness of the one-more discrete logarithm problem and the ROS problem. As the latter can be solved in sub-exponential time using Wagner's algorithm, this is not entirely satisfying. Hence, we then propose a very simple modification of the scheme (which leaves key generation and signature verification unchanged) and show that, instead of ROS, its security relies on the hardness of a related problem which appears much harder than ROS. Finally, we give a tight reduction of the CCA2 security of Schnorr-signed ElGamal key encapsulation to DL, again in the AGM+ROM.

In order to propagate transactions and blocks, today’s blockchain systems rely on unstructured peer-to-peer overlay networks. In such networks, broadcast is known to be an inefficient operation in terms of message complexity and overhead. In addition to the impact on the system performance, inefficient or delayed block propagation may have severe consequences regarding security and fairness of the consensus layer. Therefore, we introduce Kadcast, a novel peer-to-peer protocol for block propagation in blockchain networks. Kadcast utilizes the well-known structured overlay topology of Kademlia to realize an efficient broadcast operation with tunable overhead. As our protocol is based on UDP, we incorporate forward error correction (FEC) to increase reliability while still maintaining its lightweight protocol architecture. To this end, we build a probabilistic model to analyze Kadcast’s resilience to packet losses as well as random and adversarial node failures. Moreover, we evaluate Kadcast’s block delivery performance, broadcast reliability, efficiency, and security based on advanced network simulations, which confirm the merits of the Kadcast protocol.

We introduce a Quantum Key Recycling (QKR) protocol that needs no classical communication from Alice to Bob. Alice sends only a cipherstate, which consists of qubits that are individually measured by Bob. Bob merely has to respond with an authenticated one-bit accept/reject classical message. Compared to Quantum Key Distribution (QKD), QKR has reduced round complexity. Compared to other qubit-wise QKR protocols, our scheme has far less classical communication. We provide a security proof proof similar to [LS2018] and find that the communication rate is asymptotically the same as for QKD with one-way postprocessing.

We provide a new frame in this paper, the ciphertext-policy attribute-based encryption with functional keyword search (ABFKS) in fog computing. The ABFKS achieves functional keyword search and peer-peeping resistance, which makes it more practical and secure, while in previous attribute-based encryption with keyword search (ABKS) schemes, keyword search function is limited and ciphertext is vulnerable to man-in-the-middle attacks by adversaries who have sufficient authorities. Specifically, in ABFKS, the search process requires only one keyword, instead of each keyword as previous schemes, to be identical between the target keyword set and the ciphertext keyword set, and outputs the correlation of those two sets. Besides, the ABFKS resists peeping from peers or superiors who have the same or more attributes.

Privacy and efficiency issues haven't been fully considered, therefore we provide a construction of ABFKS with privacy preserving, efficient attribute update and reverse outsourcing (ABKFS-PER). To be specific, we provide a novel method to protect the privacy of access structure by replacing each leaf node with an OR gate. In this scheme, every user has all the attributes in the cloud's view by adding fake ones so to protect the privacy of user authority. We propose a new method for attribute update, in which the key authority center only updates the user who needs update, not everyone. At last, we initially propose the concept of reverse outsourcing, namely the cloud outsourcing computational tasks to idle users to reduce its overhead.

Counting the Boolean functions having specific cryptographic features is an interesting problem in combinatorics and cryptography. Count of bent functions for more than eight variables is unexplored. In this paper, we propose an upper bound for the count of rotational symmetric bent Boolean functions and characterize its truth table representation from the necessary condition of a rotational symmetric bent Boolean function.

At CRYPTO 2018, Cramer et al. introduced a secret-sharing based protocol called SPD$\mathbb{Z}_{2^k}$ that allows for secure multiparty computation (MPC) in the dishonest majority setting over the ring of integers modulo $2^k$, thus solving a long-standing open question in MPC about secure computation over rings in this setting. In this paper we study this problem in the information-theoretic scenario. More specifically, we ask the following question: Can we obtain information-theoretic MPC protocols that work over rings with comparable efficiency to corresponding protocols over fields? We answer this question in the affirmative by presenting an efficient protocol for robust Secure Multiparty Computation over $\mathbb{Z}/p^{k}\mathbb{Z}$ (for \emph{any} prime $p$ and positive integer $k$) that is perfectly secure against active adversaries corrupting a fraction of at most $1/3$ players, and a robust protocol that is statistically secure against an active adversary corrupting a fraction of at most $1/2$ players.

The foundation of zero-knowledge is the simulator: a weak machine capable of pretending to be a weak verifier talking with all-powerful provers. To achieve this, simulators need some kind of advantage such as the knowledge of a trapdoor. In existing zero-knowledge multi-prover protocols, this advantage is essentially signalling, something that the provers are explicitly forbidden to do. In most cases, this advantage is stronger than necessary as it is possible to define a sense in which simulators need much less to simulate. We define a framework in which we can quantify the simulators’ non-local advantage and exhibit examples of zero-knowledge protocols that are sound against local or entangled provers but that are not sound against no-signalling provers precisely because the no-signalling simulation strategy can be adopted by malicious provers.

This paper presents an efficient algorithm for computing $11^{\mathrm{th}}$-power residue symbols in the cyclotomic field $\mathbb{Q}(\zeta_{11})$, where $\zeta_{11}$ is a primitive $11^{\mathrm{th}}$ root of unity. It extends an earlier algorithm due to Caranay and Scheidler (Int. J. Number Theory, 2010) for the $7^{\mathrm{th}}$-power residue symbol. The new algorithm finds applications in the implementation of certain cryptographic schemes.

Security and safety-critical remote applications such as e-voting, online banking, industrial control systems, medical devices, and home automation systems rely upon user interaction that is typically performed through web applications. Trusted path to such remote systems is critical in the presence of an attacker that controls the computer that the user operates. Such a powerful attacker can observe and modify any IO data without being detected by the user or the server. We investigate the security of previous research proposals that address this problem and observe several drawbacks that make them vulnerable to advance UI manipulation attacks.Based on these observations we define a novel set of requirements for secure IO operation in the presence of a compromised host. We propose ProtectIOn, a system that ensures the integrity and confidentiality of the user's IO employing a trusted low-TCB device that sits between the attacker-controlled host and the IO devices. Therefore, ProtectIOn device can intercept the display signal and user inputs from the keyboard and mouse. Furthermore, it can overlay secure UI on top of the HDMI frames generated by the untrusted host. ProtectIOn integrates well in the existing infrastructure, it requires small changes in the server-side, works with any browser without installing any additional software, and does not change significantly the user experience. Finally, we implement a prototype of ProtectIOn which is a plug-and-play device and evaluate its performance.

We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that:

(1) BA protocols resilient against $n/3$ [resp., $n/4$] corruptions terminate (under attack) at the end of the first round with probability at most $o(1)$ [resp., $1/2+ o(1)$].

(2) BA protocols resilient against n/4 corruptions terminate at the end of the second round with probability at most $1-\Theta(1)$.

(3) For a large class of protocols (including all BA protocols used in practice) and under a plausible combinatorial conjecture, BA protocols resilient against $n/3$ [resp., $n/4$] corruptions terminate at the end of the second round with probability at most $o(1)$ [resp., $1/2 + o(1)$].

The above bounds hold even when the parties use a trusted setup phase, e.g., a public-key infrastructure (PKI).

The third bound essentially matches the recent protocol of Micali (ITCS'17) that tolerates up to $n/3$ corruptions and terminates at the end of the third round with constant probability.

Lilliput-AE is a tweakable block cipher submitted as a candidate to the NIST lightweight cryptography standardization process. It is based upon the lightweight block cipher Lilliput, whose cryptanalysis so far suggests that it has a large security margin.

In this note we present an extremely efficient forgery attack on Lilliput-AE: Given a single arbitrary message of length about 2^36 bytes, we can instantly produce another valid message that leads to the same tag, along with the corresponding ciphertext. The attack uses a weakness in the tweakey schedule of Lilliput-AE which leads to the existence of a related tweak differential characteristic with probability 1 in the underlying block cipher. The weakness we exploit, which does not exist in Lilliput, demonstrates the potential security risk in using a very simple tweakey schedule in which the same part of the key/tweak is re-used in every round, even when round constants are employed to prevent slide attacks. Following this attack, the Lilliput-AE submission to NIST was tweaked.

Semi-invasive fault injection attacks, such as optical fault injection, are powerful techniques well-known by attackers and secure embedded system designers. When performing such attacks, the selection of the fault injection parameters is of utmost importance and usually based on the experience of the attacker. Surprisingly, there exists no formal and general approach on how to find such fault injection parameters. In this work, we present a novel methodology to perform a fast characterization of the fault injection impact on a target, depending on the possible attack parameters. We experimentally show our methodology to be a successful one when considering targets running DES and AES encryption. Finally, we show how deep learning can help in estimating the full characterization on the basis of a limited number of measurements.

SipHash is a family of ARX-based MAC algorithms optimized for short inputs. Already, a lot of implementations and applications for SipHash have been proposed, whereas the cryptanalysis of SipHash still lacks behind. In this paper, we study the property of truncated differential in SipHash and find out the output bits with the most imbalanced differential biases. Based on these results, we construct distinguishers with practical complexity $2^{10}$ for SipHash-2-1 and $2^{36}$ for SipHash-2-2. We further reveal the relations between the value of output bias and the difference after first modular addition step, which is directly determined by corresponding key bits. Making use of these relations, we propose a key recovery method for SipHash-2-1 with success rate increased from $2^{-128}$ to $2^{-41}$.

We review several solutions for the Byzantine Fault Tolerance (BFT) problem and discuss some aspects that are frequently overlooked by existing literatures. For example, PBFT and HotStuff BFT protocols (HotStuff has been adopted by Facebook Libra) require a reliable broadcast primitive. We show that if the broadcast primitive is not reliable then the PBFT and HotStuff BFT protocols could not achieve the liveness property (that is, the system will never reach an agreement on a proposal). Though these BFT protocols have been developed for partial synchronous networks, we show that they cannot achieve consensus in partial synchronous networks since the participants do not know what is the Global Stabilization Time (GST) and broadcast channels before GST are defined to be unreliable (e.g., DoS attacks on certain participants). Thus it is important for developers to be aware of these issues when developing applications (such as blockchains) using these BFT protocols.