International Association
for Cryptologic Research

Secure messaging applications are deployed on devices that can be compromised, lost, stolen, or corrupted in many ways. Thus, recovering from attacks to get back to a clean state is essential and known as healing. Signal is a widely-known, privacy-friendly messaging application, that uses key-ratcheting mechanism updates keys at each stage to provide end-to-end channel security, forward secrecy, and post-compromise security. We strengthen this last property, by providing a faster healing. Signal needs up to two full chains of messages before recovering, our protocol enables recovery after the equivalent of a chain of only one message. We also provide an extra protection against session-hijacking attacks. We do so, while building on the pre-existing Signal backbone, without weakening its other security assumptions, and still being compatible with Signal's out-of-order message handling feature. Our implementation results show that, while slower than Signal (as expected), MARSHAL's spectacular gain in healing speed comes at a surprisingly low cost, with individual stages (including key-derivation, encryption, and decryption) taking less than 6 ms.

Let $q$ be an odd prime power and ${\mathbb F}_{q^3}$ be the finite field with $q^3$ elements. In this paper, we propose two classes of permutation trinomials of ${\mathbb F}_{q^3}$ for an arbitrary odd characteristic based on the multivariate method and some subtle manipulation of solving equations with low degrees over finite fields. Moreover, we demonstrate that these two classes of permutation trinomials are QM inequivalent to all known permutation polynomials over ${\mathbb F}_{q^3}$. To the best of our knowledge, this paper is the first to study the construction of nonlinearized permutation trinomials of ${\mathbb F}_{q^3}$ with at least one coefficient lying in ${\mathbb F}_{q^3}\backslash{\mathbb F}_{q}$.

Physical attacks, including passive Side-Channel Analysis and active Fault Injection Analysis, are considered among the most powerful threats against physical cryptographic implementations. These attacks are well known and research provides many specialized countermeasures to protect cryptographic implementations against them. Still, only a limited number of combined countermeasures, i.e., countermeasures that protect implementations against multiple attacks simultaneously, were proposed in the past. Due to increasing complexity and reciprocal effects, design of efficient and reliable combined countermeasures requires longstanding expertise in hardware design and security. With the help of formal security specifications and adversary models, automated verification can streamline development cycles, increase quality, and facilitate development of robust cryptographic implementations. In this work, we revise and refine formal security notions for combined protection mechanisms and specifically embed them in the context of hardware implementations. Based on this, we present the first automated verification framework that can verify physical security properties of hardware circuits with respect to combined physical attacks. To this end, we conduct several case studies to demonstrate the capabilities and advantages of our framework, analyzing secure building blocks (gadgets), S-boxes build from Toffoli gates, and the ParTI scheme. For the first time, we reveal security flaws in analyzed structures due to reciprocal effects, highlighting the importance of continuously integrating security verification into modern design and development cycles.

We tackle a challenging problem at the intersection of two emerging technologies: Post-quantum cryptography (PQC) and vehicle-to-vehicle (V2V) communications. Connected vehicles use V2V technology to exchange safety messages that allow them to increase proximity awareness, improving roadway safety. The integrity and authenticity of these messages is critical to prevent an adversary from abusing V2V technology to cause a collision, traffic jam, or other unsafe and/or disruptive situations. The IEEE 1609.2 standard (2016) specifies authentication mechanisms for V2V communications that rely on the elliptic curve digital signature algorithm (ECDSA) and are therefore not secure against quantum attackers. In this paper, we are the first to devise and evaluate PQC for authenticating messages in IEEE 1609.2. By analyzing the properties of the NIST PQC standardization finalists, as well as XMSS (RFC 8391), we propose three practical, ECDSA-PQ hybrid designs for use during the transition from classical to PQ-secure cryptography.

Privacy preservation is a sensitive issue in our modern society. It is becoming increasingly important in many applications in this ever-growing and highly connected digital era. Functional encryption is a computation on encrypted data paradigm that allows users to retrieve the evaluation of a function on encrypted data without revealing the data, thus effectively protecting users' privacy. However, existing functional encryption implementations are still very time-consuming for practical deployment, especially when applied to machine learning applications that involve a huge amount of data. In this paper, we present a high-performance implementation of inner-product functional encryption (IPFE) based on ring-learning with errors on graphics processing units. We propose novel techniques to parallelize the Gaussian sampling, which is one of the most time-consuming operations in the IPFE scheme. We further execute a systematic investigation to select the best strategy for implementing number theoretic transform and inverse number theoretic transform for different security levels. Compared to the existing AVX2 implementation of IPFE, our implementation on a RTX 2060 GPU device can achieve 34.24x, 40.02x, 156.30x, and 18.76x speed-up for Setup, Encrypt, KeyGen, and Decrypt respectively. Finally, we propose a fast privacy-preserving Support Vector Machine (SVM) application to classify data securely using our GPU-accelerated IPFE scheme. Experimental results show that our implementation can classify 100 inputs with 591 support vectors in 688 ms (less than a second), which is 33.12x faster than the AVX2 version which takes 23 seconds.

India's Aadhaar is the largest biometric identity system in history, designed to help deliver subsidies, benefits, and services to India's 1.4 billion residents. The Unique Identification Authority of India (UIDAI) is responsible for providing each resident (not each citizen) with a distinct identity - a 12-digit Aadhaar number - using their biometric and demographic details. We provide the first comprehensive description of the Aadhaar infrastructure, collating information across thousands of pages of public documents and releases, as well as direct discussions with Aadhaar developers. Critically, we describe the first known cryptographic issue within the system, and discuss how a workaround prevents it from being exploitable at scale. Further, we categorize and rate various security and privacy limitations and the corresponding threat actors, examine the legitimacy of alleged security breaches, and discuss improvements and mitigation strategies.

Homomorphic encryption enables computation on encrypted data, and hence it has a great potential in privacy-preserving outsourcing of computations to the cloud. Hardware acceleration of homomorphic encryption is crucial as software implementations are very slow. In this paper we present design methodologies for building a programmable hardware accelerator for speeding up the cloud-side homomorphic evaluations on encrypted data. First, we propose a divide-and-conquer technique that enables homomorphic evaluations in the polynomial ring $R_{Q,2N} = \mathbb{Z}_{Q}[x]/(x^{2N} + 1)$ to use a hardware accelerator that has been built for the smaller ring $R_{Q,N} = \mathbb{Z}_{Q}[x]/(x^{N} + 1)$. The technique makes it possible to use a single hardware accelerator flexibly for supporting several homomorphic encryption parameter sets. Next, we present several architectural design methods that we use to realize the flexible and instruction-set accelerator architecture, which we call as `Medha'. At every level of the implementation hierarchy, we explore possibilities for parallel processing. Starting from hardware-friendly parallel algorithms for the basic building blocks, we gradually build heavily parallel RNS polynomial arithmetic units. Next, many of these parallel units are interconnected elegantly so that their interconnections require the minimum number of nets, therefore making the overall architecture placement-friendly on the platform. As homomorphic encryption is computation- as well as data-centric, the speed of homomorphic evaluations depends greatly on the way the data variables are handled. For Medha, we take a memory-conservative design approach and get rid of any off-chip memory access during homomorphic evaluations. Finally, we implement Medha in a Xilinx Alveo U250 FPGA and measure timing performances of the microcoded homomorphic addition, multiplication, key-switching, and rescaling routines for the leveled fully homomorphic encryption scheme RNS-HEAAN at 200 MHz clock frequency. For the large parameter sets $(\log Q, N) = (438, 2^{14})$ and $(546, 2^{15})$, Medha achieves accelerations by up to $68\times$ and $78\times$ times respectively compared to a highly optimized software implementation Microsoft SEAL running at 2.3 GHz.

We propose a short signature scheme under the ring-SIS assumption in the standard model. Specifically, by revisiting an existing construction [Ducas and Micciancio, CRYPTO 2014], we demonstrate lattice-based signatures with improved reduction loss. As far as we know, there are no ways to use multiple tags in the signature simulation of security proof in the lattice tag-based signatures. We address the tag-collision possibility in the lattice setting, which improves reduction loss. Our scheme generates tags from messages by constructing a scheme under a mild security condition that is existentially unforgeable against random message attack with auxiliary information. Thus our scheme can reduce the signature size since it does not need to send tags with the signatures. Our scheme has short signature sizes of ?(1) and achieves tighter reduction loss than that of Ducas et al.’s scheme. Our proposed scheme has two variants. Our scheme with one property has tighter reduction and the same verification key size of ?(log ?) as that of Ducas et al.’s scheme, where ? is the security parameter. Our scheme with the other property achieves much tighter reduction loss of ?(?/?) and verification key size of ?(?), where ? is the number of signing queries.

Property-preserving hash (PPH) function is a class of hash functions that allows an evaluation of the property of inputs from their hash values. Boyle et al. at ITCS 2019 recently introduced it and considered the robustness of PPH against an adversary who accesses the internal randomness of PPH, and proposed two robust PPH constructions for a weak form of Hamming distance predicate. The second construction received attention for its short hash value, although it relies on an ad-hoc security assumption. The first construction, which is entirely hash-based and based on the classical collision-resistance assumption, has been largely overlooked. We study their first construction and discover its close connection to a seemingly different field of hash/MAC-based (adversarial) error detection using the theory of Combinatorial Group Testing (CGT). We show some consequences of this discovery. In particular, we show that some existing proposals in the field of CGT-based error detection can be converted into a PPH for the Hamming distance property, and they immediately improve and generalize Boyle et al.'s hash-based PPH proposal. We also show that the idea of Boyle et al. is useful in the context of a variant of CGT problem.

In this work we study and formalize security notions for algorithm substitution attacks (ASAs) on cryptographic puzzles. Puzzles are difficult problems that require an investment of computation, memory or some other related resource. They are heavily used as a building block for the consensus networks used by cryptocurrencies, where they include primitives such as proof-of-work, proof-of-space, and verifiable delay functions (VDFs). Due to economies of scale, these networks increasingly rely on a small number of companies to construct opaque hardware or software (e.g., GPU or FPGA images): this dependency raises concerns about cryptographic subversion. Unlike the algorithms considered by previous ASAs, cryptographic puzzles do not rely on secret keys and thus enable a very different set of attacks. We first explore the threat model for these systems and then propose concrete attacks that (1) selectively reduce a victim's solving capability (e.g., hashrate) and (2) exfiltrate puzzle solutions to an attacker. We then propose defenses, several of which can be applied to existing cryptocurrency hardware with minimal changes. Given that these attacks are relevant to all proof of work cryptocurrencies that have a combined market capitalization around a $1 trillion USD (March, 2022), we recommend that all vulnerable mining protocols consider making the suggested adaptations today.

{\sf TrCBC} is a variant of CBC-MAC which appeared in {\em Information Processing Letters}, 112(7):302-307, 2012. The authors claimed {\sf TrCBC} to be a secure message authentication code (MAC) with some interesting properties. If ${\sf TrCBC}$ is instantiated with a block cipher with block length $n$, then it requires $\lceil \lambda /n \rceil$ block cipher calls for authenticating a $\lambda$-bit message and requires a single key, which is the block cipher key. We show that with high probability, an adversary can forge {\sf TrCBC} with just three queries. The attack that we show can be applied to forge a large class of messages.

We analyze and implement the SIDH PoK-based construction from De Feo, Dobson, Galbraith, and Zobernigl. We improve the SIDH-PoK built-in functions to allow an efficient constant-time implementation. After that, we combine it with Fiat-Shamir transform to get an SIDH PoK-based signature scheme that we short label as SIDH-sign. We suggest SIDH-sign-p377, SIDH-sign-p546, and SIDH-sign-p697 as instances that provide security compared to NIST L1, L3, and L5. To the best of our knowledge, the three proposed instances provide the best performance among digital signature schemes based on isogenies.

Polynomial multiplication algorithms such as Toom-Cook and the Number Theoretic Transform are fundamental building blocks for lattice-based post-quantum cryptography. In this work, we present correlation power analysis-based side-channel analysis methodologies targeting every polynomial multiplication strategy for all lattice-based post-quantum key encapsulation mechanisms in the final round of the NIST post-quantum standardization procedure. We perform practical experiments on real side-channel measurements demonstrating that our method allows to extract the secret key from all lattice-based post-quantum key encapsulation mechanisms. Our analysis demonstrates that the used polynomial multiplication strategy can significantly impact the time complexity of the attack.

This paper reviews, from bottom to top, a polynomial-time algorithm to correct t errors in classical binary Goppa codes defined by squarefree degree-t polynomials. The proof is factored through a proof of a simple Reed--Solomon decoder, and the algorithm is simpler than Patterson's algorithm. All algorithm layers are expressed as Sage scripts. The paper also covers the use of decoding inside the Classic McEliece cryptosystem, including reliable recognition of valid inputs.

The Module Learning With Errors problem (M-LWE) is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE, i.e., uniform secret modulo $q$ and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress towards narrowing this gap. More precisely, we prove that M-LWE with $\eta$-bounded secret for any $2 \leq \eta \ll q$ and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of M-LWE, provided that the module rank $d$ is at least logarithmic in the ring degree $n$. We also prove that the search version of M-LWE with large uniform secret and uniform $\eta$-bounded error is at least as hard as the standard M-LWE problem, if the number of samples $m$ is close to the module rank $d$ and with further restrictions on $\eta$. The latter result can be extended to provide the hardness of M-LWE with uniform $\eta$-bounded secret and error under specific parameter conditions.

In this paper we present our solution to the CHES Challenge 2020, the task of which it was to break masked hardware respective software implementations of the lightweight cipher Clyde by means of side-channel analysis. We target the secret cipher state after processing of the first Sbox layer. Using the provided trace data we obtain a strongly biased posterior distribution for the secret-shared cipher state at the targeted point; this enables us to see exploitable biases even before the secret sharing based masking. These biases on the unshared state can be evaluated one $S$-box at a time and combined across traces, which enables us to recover likely key hypotheses $S$-box by $S$-box.

In order to see the shared cipher state, we employ a deep neural network similar to the one used by Gohr, Jacob and Schindler to solve the CHES 2018 AES challenge. We modify their architecture to predict the exact bit sequence of the secret-shared cipher state. We find that convergence of training on this task is unsatisfying with the standard encoding of the shared cipher state and therefore introduce a different encoding of the prediction target, which we call the scattershot encoding. In order to further investigate how exactly the scattershot encoding helps to solve the task at hand, we construct a simple synthetic task where convergence problems very similar to those we observed in our side-channel task appear with the naive target data encoding but disappear with the scattershot encoding.

We complete our analysis by showing results that we obtained with a classical method (as opposed to an AI-based method), namely the stochastic approach, that we generalize for this purpose first to the setting of shared keys. We show that the neural network draws on a much broader set of features, which may partially explain why the neural-network based approach massively outperforms the stochastic approach. On the other hand, the stochastic approach provides insights into properties of the implementation, in particular the observation that the $S$-boxes behave very different regarding the easiness respective hardness of their prediction.

We introduce Designated-Verifier Linkable Ring Signatures (DVLRS), a novel cryptographic primitive which combines designated-verifier and linkable ring signatures. Our goal is to guarantee signer ambiguity and provide the capability to the designated verifier to add ‘noise’ using simulated signatures that are publicly verifiable. This increases the privacy of the participants, as it does not allow an adversary to bypass the anonymity provided by ring signatures by using the content of a message to identify the signer. We model unforgeability, anonymity, linkability and non-transferability for DVLRS and provide a secure construction in the Random Oracle model. Finally, we explore some first applications for our primitive, which revolve around the use case of an anonymous assessment system that also protects the subject of the evaluation, even if the private key is compromised.

Post-quantum cryptography addresses the increasing threat that quantum computing poses to modern communication systems. Among the available "quantum-resistant" systems, the Niederreiter cryptosystem is positioned as a conservative choice with strong security guarantees. As a code-based cryptosystem, the Niederreiter system enables high performance operations and is thus ideally suited for applications such as the acceleration of server workloads. However, until now, no ASIC architecture is available for low latency computation of Niederreiter operations. Therefore, the present work targets the design, implementation and optimization of tailored archi- tectures for low latency Niederreiter decryption. Two architectures utilizing different decoding algorithms are proposed and implemented using a 22nm FDSOI CMOS technology node. One of these optimized architectures improves the decryption latency by 27% compared to a state-of-the-art reference and requires at the same time only 25% of the area.

The General Sieve Kernel (G6K) implemented a variety of lattice reduction algorithms based on sieving algorithms. One of the representative of these lattice reduction algorithms is Pump and jump-BKZ (pnj-BKZ) algorithm which is currently considered as the fastest lattice reduction algorithm. The pnj-BKZ is a BKZ-type lattice reduction algorithm which includes the jump strategy, and uses Pump as the SVP Oracle. Here, Pump which was also proposed in G6K, is an SVP sloving algorithm that combines progressive sieve technology and dimforfree technology. However unlike classical BKZ, there is no simulator for predicting the behavior of the pnj-BKZ algorithm when jump greater than 1, which is helpful to find a better lattice reduction strategy. There are two main differences between pnj-BKZ and the classical BKZ algorithm: one is that after pnj-BKZ performs the SVP Oracle on a certain projected sublattice, it won't calling SVP Oracle for the next nearest projected sublattice. Instead, pnj-BKZ jumps to the corresponding projected sublattice after J indexs to run the algorithm for solving the SVP. By using this jump technique, the number of times that the SVP algorithm needs to be called for each round of pnj-BKZ will be reduced to about 1/J times of original. The second is that pnj-BKZ uses Pump as the SVP Oracle on the projected sublattice. Based on the BKZ2.0 simulator, we proposes a pnj-BKZ simulator by using the properties of HKZ reduction basis. Experiments show that our proposed pnj-BKZ simulator can well predicate the behavior of pnj-BKZ with jump greater than 1. Besides, we use this pnj-BKZ simulator to give the optimization strategy for choosing jump which can improve the reducing efficiency of pnj-BKZ. Our optimized pnj-BKZ is 2.9 and 2.6 times faster in solving TU LWE challenge ( n=75,alpha=0.005 ) and TU LWE challenge ( n=60,alpha=0.010 ) than G6K's default LWE sloving strategy.

Side channel attacks are powerful attacks for retrieving secret data by exploiting physical measurements such as power consumption or electromagnetic emissions. Masking is a popular countermeasure as it can be proven secure against an attacker model. In practice, software masked implementations suffer from a security reduction due to a mismatch between the considered leakage sources in the security proof and the real ones, which depend on the micro-architecture. We present the model of a system comprising an Arm Cortex-M3 obtained from its RTL description and test-vectors, as well as a model of the memory of a STM32F1 board, built exclusively using test-vectors. Based on these models, we propose Armistice, a framework for formally verifying the absence of leakage in first-order masked implementations taking into account the modelled micro-architectural sources of leakage. We show that Armistice enables to pinpoint vulnerable instructions in real world masked implementations and helps design masked software implementations which are practically secure.