International Association
for Cryptologic Research

The increasing communication capabilities of vehicles are paving the way for promising road safety and traffic management applications. But the rise of connected vehicles also potentially introduces many security and privacy concerns. Thus, a vision of a successful cooperative vehicular network relies on strong security properties. Proposals such as the Security Credential Management System (SCMS) fulfil these security requirements with the concept of pseudonym certificates, relying on large-scale PKI. But since the on-board units performing these cryptographic operations are usually resource-constrained devices, it is important to consider ways to optimize and devise efficient implementations of the proposed algorithms.

In this work, we study optimizations on the mathematical and algorithmic aspects of the validation of implicit certificates and the verification of ECDSA signatures used in the SCMS. We propose efficient algorithms to validate batches of implicit certificates, providing significant savings compared to the sequential validation of the individual certificates. We also propose optimizations to the verification of ECDSA signatures when the verification is performed with an implicit certificate. Although we focus our work on the SCMS and V2X communications, our contributions are more general and apply to every system combining ECQV and ECDSA.

Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. First, although expected constant-round protocols are known in the honest majority setting, it is unclear whether one has to settle for expected constant-round or whether there exist better protocols that are worst-case constant-round. Second, for the corrupt majority setting, the existence of sublinear-round BA protocols continues to ellude us except for the narrow regime when only sublinearly more than a half are corrupt.

In this paper, we make a couple important steps forward in bridging this gap.

We show two main results:

- No (even randomized) protocol that completes in worst-case $o\left(\log(1/\delta)/\log \log(1/\delta)\right)$ rounds can achieve BA with $1-\delta$ probability, even when only 1% of the nodes are corrupt. In comparison, known expected constant-round, honest-majority protocols complete in $O(\log(1/\delta))$ rounds in the worst-case. Therefore, our lower bound is tight upto a $\log\log$ factor for the honest majority setting.

- There exists a corrupt-majority BA protocol that terminates in $O(\log(1/\delta)/\epsilon)$ rounds in the worst case and tolerates $(1-\epsilon)$ fraction of corrupt nodes. Our upper bound is optimal upto a logarithmic factor in light of the elegant $\Omega(1/\epsilon)$ lower bound by Garay et al. (FOCS'07).

In this paper, we provide a notable step towards filling the gap between theory (estimates of running-time) and practice (a discrete logarithm record computation) for the Tower Number Field Sieve (TNFS) algorithm. We propose a generalisation of ranking formula for selecting the polynomials used in the very first step of TNFS algorithm. For this we provide a definition and an exact implementation (Magma and SageMath) of the alpha function. This function measures the bias in the smoothness probability of norms in number fields compared to random integers of the same size. We use it to estimate the yield of polynomials, that is the expected number of relations, as a generalisation of Murphy's E function, and finally the total amount of operations needed to compute a discrete logarithm with TNFS algorithm in the targeted fields. This is an improvement of the earlier work of Barbulescu and Duquesne on estimating the running-time of the algorithm. We apply our estimates to a wide size range of finite fields GF(p^n), for small composite n = 12, 16, 18, 24, that are target fields of pairing-friendly curves.

In this paper, we present new preimage attacks on KECCAK-384 and KECCAK-512 for 2, 3 and 4 rounds. The attacks are based on non-linear structures (structures that contain quadratic terms). These structures were studied by Guo et al. and Li et al. to give preimage attacks on round reduced KECCAK. We carefully construct non-linear structures such that the quadratic terms are not spread across the whole state. This allows us to create more linear equations between the variables and hash values, leading to better preimage attacks. As a result, we present the best theoretical preimage attack on KECCAK-384 and KECCAK-512 for 2 and 3-rounds and also KECCAK-384 for 4-rounds.

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.