International Association
for Cryptologic Research

Deniable public-key encryption (DPKE) is a cryptographic primitive that allows the sender of an encrypted message to later claim that they sent a different message.

DPKE's threat model assumes powerful adversaries who can coerce users to reveal plaintexts; it is thus reasonable to consider other advanced capabilities, such as the ability to subvert algorithms in a so-called Algorithm Substitution Attack (ASA). An ASA replaces a trusted algorithm with a subverted version that undermines security from the point of view of the adversary while remaining undetected by users. ASAs have been considered against a number of primitives including digital signatures, symmetric encryption and pseudo-random generators. However, public-key encryption has presented a less fruitful target, as the sender's only secrets are plaintexts and ASA techniques generally do not provide sufficient bandwidth to leak these.

In this work, we show that subversion attacks against deniable encryption schemes present an attractive opportunity for an adversary. We note that whilst the notion is widely accepted, there are as yet no practical deniable PKE schemes; we demonstrate the feasibility of ASAs targeting deniable encryption using a representative scheme as a proof of concept. We also provide a formal model and discuss how to mitigate ASAs targeting deniable PKE schemes. Our results strengthen the security model for deniable encryption and highlight the necessity of considering subversion in the design of practical schemes.

An emerging direction of investigating the resilience of post-quantum cryptosystems under side-channel attacks is to consider the situations where leaked information is combined with traditional attack methods in various forms. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This idea is further developed in this paper. An accurate characterization of the information from perfect hints and modular hints is obtained through the establishment of an interesting decomposition of $\mathbb{Z}^n$. It is observed that modular hints with modulus $p$ produce some orthogonal projection of the secret in $\mathbb{Z}_p$, which is exactly an extension of the case of perfect hints in $\mathbb{R}$. Based on these, a new attack framework is described when some modular hints with modulus $q$ are available. In this framework, an adversary first reduces the LWE instance using such hints, and then performs various attacks on the new instance. One of the key characters of our framework is that the dimension of the secret in the new instance always decreases under some moderate conditions. A comparison with the previous work shows that our approach is in some sense more essential and applicable to various kinds of attacks. The new way of integrating modular hints to primal attack improves the existing work. The first attempt of using modular hints in dual attack and BKW attack is also discussed in the paper and better analysis results are produced. Experiments have been carried out and shown that multiple modular hints with modulus $q$ can indeed significantly reduce their attack costs. For examples, with just 100 hints, the blocksize can be reduced by 101 and the time complexity can be reduced by a factor of $2^{30}$ in both primal attack and dual attack against a Newhope1024 instance. As for the BKW attack, if 90 hints are available, the number of queries to the LWE oracle can be decreased by a factor of $2^{60}$, as do the time complexity and memory complexity when attacking an instance of Regev cryptosystem $(384,147457,39.19)$.

Combining theoretical-based traditional attack method with practical-based side-channel attack method provides more accurate security estimations for post-quantum cryptosystems. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This paper develops a general Fourier analytic framework to work with the dual attack in the presence of hints. Distinguishers that depend on specific geometric properties related to hints are established. The Fourier transform of discretized multivariate conditional Gaussian distribution on $\mathbb{Z}_q^d$ is carefully computed and estimated, some geometric characteristics of the resulting distinguisher are explored and a new model of dual attack is proposed. In our framework, an adversary performs the BKZ algorithm directly in a projected lattice to find short projection components, and then recovers them by MLLL algorithm to make a distinction. This method relies on a reasonable assumption and is backed up by naturally formed mathematical arguments. The improvements and the assumption are validated by experiments. For examples, for a Kyber768 instance, with 200 hints, the blocksize can be reduced by at least 188 and the time complexity can be reduced by a factor of greater than $2^{55}$. After adding 300 hints to a FireSaber instance, even in the worst case, the blocksize drops from 819 to 542, and the cost drops from $2^{255.61}$ to $2^{174.72}$.

Physically Unclonable Functions (PUFs) have emerged as a viable and cost-effective method for device authentication and key generation. Recently, CMOS image sensors have been exploited as PUF for hardware fingerprinting in mobile devices. As CMOS image sensors are readily available in modern devices such as smartphones, laptops etc., it eliminates the need for additional hardware for implementing a PUF structure. In ISIC2014, an authentication protocol has been proposed to generate PUF signatures using a CMOS image sensor by leveraging the fixed pattern noise (FPN) of certain pixel values. This makes the PUF candidate an interesting target for adversarial attacks. In this work, we testify that a simple sorting attack and a win-rate (WR) based sorting attack can be launched in this architecture to predict the PUF response for given a challenge. We also propose a modified authentication protocol as a countermeasure to make it resilient against simple sorting and WR sorting attacks. The proposed work reduces the accuracy of prediction due to simple sorting attack and WR sorting attack by approximately 14% compared to the existing approach.

Homomorphic equality operator is essential for many secure computation tasks such as private information retrieval (PIR). However, the folklore homomorphic equality operator is typically considered to be impractical as its multiplicative depth depends on the input bit-length. In Usenix SEC '22, Mahdavi-Kerschbaum propose a homomorphic equality operator with a constant multiplicative depth, based on constant-weight code. On that basis, they propose constant-weight PIR (CwPIR for short); compared with other PIR protocols, CwPIR is more friendly to databases with large payloads and can support keyword query almost for free. Unfortunately, CwPIR cannot support databases with a large number of elements, which limits its real-world impact.

In this paper, we propose a homomorphic constant-weight equality operator that supports batch processing, hence it can perform thousands of equality checks with a much smaller amortized cost. Based on this improved homomorphic equality operator, we propose a novel PIR protocol named PIRANA, which inherits all advantages of CwPIR with a significant improvement in supporting more elements. We further extend PIRANA to support multi-query. To the best of our knowledge, PIRANA is the first multi-query PIR that can save both computation and communication. Our experimental results show that our single-query PIRANA is upto 30.8× faster than CwPIR; our multi-query PIRANA saves upto 163.9× communication over the state-of-the-art multi-query PIR (with a similar computational cost).

The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. This is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Accelerating the MSM over these curves on mobile devices is critical for deployment of recursive proof systems on mobile applications. This work is implemented in Go and uses hand-written arm64 assembly for accelerating the finite field arithmetic (bigint). This work was implemented as part of a submission to the ZPrize competition in the open division “Accelerating MSM on Mobile” (https://www.zprize.io/). We achieved a 78% speedup over the ZPrize baseline implementation in Rust.

Lightweight cryptography is a viable solution for constrained computational environments that require a secure communication channel. To standardize lightweight primitives, NIST has published a call for algorithms that address needs like compactness, low-latency, low-power/energy, etc. Among the candidates, the GIFT family of block ciphers was utilized in various NIST candidates due to its high-security margin and small gate footprint. As a result of their hardware-oriented design, software implementations of GIFT require additional optimization techniques such as bitslicing and fixslicing to achieve optimal performance. Even though the performance of these methods has been assessed for several ISA families such as x86 and ARM, there is currently a lack of data with regards to their acceleration capabilities for RISC-V. Since this ISA is an important element of the growing open-hardware movement, our goal is to address this knowledge gap. Therefore, we have developed several assembly implementations for both GIFT-64 and GIFT-128, using the RV32I ISA, and performed a quantitative assessment of their performance using a physical board i.e., Hifive1 Rev B. Our study has shown that by using bitslicing the number of clock cycles can be reduced by 69.33% for GIFT-64 and 71.38% for GIFT-128, compared to a naive assembly implementation, while fixslicing decreases the number of clock cycles by 85.7% (GIFT-64) and 81.28% (GIFT-128). Nonetheless, the preferred technique is fixslicing with key pre-computation, which can achieve a reduction of 88.69% (GIFT-64) and 95.05% (GIFT-128), while maintaining relatively low memory requirements of 938 bytes (GIFT-64) and 1388 bytes (GIFT-128), respectively.

FUTURE is a recently proposed, lightweight block cipher. It has an AES-like, SP-based, 10-round encryption function, where, unlike most other lightweight constructions, the diffusion layer is based on an MDS matrix. Despite its relative complexity, it has a remarkable hardware performance due to careful design decisions.

In this paper, we conducted a MILP-based analysis of the cipher, where we incorporated exact probabilities rather than just the number of active S-boxes into the model. Through the MILP analysis, we were able to find differential and linear distinguishers for up to 5 rounds of FUTURE, extending the known distinguishers of the cipher by one round.

Secure message transmission (SMT) constitutes a fundamental network-layer building block for distributed protocols over incomplete networks. More specifically, a sender $\mathbf{S}$ and a receiver $\mathbf{R}$ are connected via $\ell$ disjoint paths, of which at most $t$ paths are controlled by the adversary.

\emph{Perfectly-secure} SMT protocols in synchronous and asynchronous networks are resilient up to $\ell/2$ and $\ell/3$ corruptions respectively. In this work, we ask whether it is possible to achieve a perfect SMT protocol that simultaneously tolerates $t_s < \ell/2$ corruptions when the network is synchronous, and $t_a < \ell/3$ when the network is asynchronous.

We completely resolve this question by showing that perfect SMT is possible if and only if $2t_a + t_s < \ell$. In addition, we provide a concretely round-efficient solution for the (slightly worse) trade-off $t_a + 2t_s < \ell$.

As a direct application of our results, following the recent work by Appan, Chandramouli, and Choudhury [PODC'22], we obtain an $n$-party perfectly-secure synchronous multi-party computation protocol with asynchronous fallback over any network with connectivity $\ell$, as long as $t_a + 3t_s

Multi-Scalar Multiplication (MSM) on elliptic curves is one of the primitives and bottlenecks at the core of many zero-knowledge proof systems. Speeding up MSM typically results in faster proof generation, which in turn makes ZK-based applications practical.

We focus on accelerating large MSM on FPGA, and we present speed records for $\texttt{BLS12-377}$ on FPGA: 5.66s for $N=2^{26}$, sub-second for $N=2^{22}$.

We developed a fully-pipelined curve adder in extended Twisted Edwards coordinates that runs at 250MHz. Our architecture incorporates a scheduler to reorder curve operations, that's suitable not just for hardware acceleration, but also for software implementations using affine coordinates with batch inversion. The software implementation achieves +$10-20$\% performance improvement over the state-of-the-art $\texttt{gnark-crypto}$ library.

Anonymous routing is an important cryptographic primitive that allows users to communicate privately on the Internet, without revealing their message contents or their contacts. Until the very recent work of Shi and Wu (Eurocrypt’21), all classical anonymous routing schemes are interactive protocols, and their security rely on a threshold number of the routers being honest. The recent work of Shi and Wu suggested a new abstraction called Non-Interactive Anonymous Router (NIAR), and showed how to achieve anonymous routing non-interactively for the first time. In particular, a single untrusted router receives a token which allows it to obliviously apply a permutation to a set of encrypted messages from the senders. While Shi and Wu’s scheme is efficient in other dimensions, one unsatisfying aspect of their construction is that the router takes time quadratic in the number of senders to obliviously route their messages.

In this work, we show how to construct a non-interactive anonymous router scheme with sub-quadratic router computation, assuming the existence of subexponential indistinguishability obfuscation and one-way permutation. To achieve this, we devise new techniques for reasoning about a network of obfuscated programs.

Microarchitectural side-channel vulnerabilities in modern processors are known to be a powerful attack vector that can be utilized to bypass common security boundaries like memory isolation. As shown by recent variants of transient execution attacks related to Spectre and Meltdown, those side channels allow to leak data from the microarchitecture to the observable architectural state. The vast majority of attacks currently build on the cache-timing side channel, since it is easy to exploit and provides a reliable, fine-grained communication channel. Therefore, many proposals for side-channel secure cache architectures have been made. However, caches are not the only source of side-channel leakage in modern processors and mitigating the cache side channel will inevitably lead to attacks exploiting other side channels. In this work, we focus on defeating side-channel attacks based on page translations. It has been shown that the Translation Lookaside Buffer ( TLB) can be exploited in a very similar fashion to caches. Since the main caches and the TLB share many features in their architectural design, the question arises whether existing countermeasures against cache-timing attacks can be used to secure the TLB. We analyze state-of-the-art proposals for side-channel secure cache architectures and investigate their applicability to TLB side channels. We find that those cache countermeasures are not directly applicable to TLB s, and propose TLBcoat, a new side-channel secure TLB architecture. We provide evidence of TLB side-channel leakage on RISC-V-based Linux systems, and demonstrate that TLBcoat prevents this leakage. We implement TLBcoat using the gem5 simulator and evaluate its performance using the PARSEC benchmark suite.

We study the problem of privacy-preserving proofs on streamed authenticated data. In this setting, a server receives a continuous stream of data from a trusted data provider, and is requested to prove computations over the data to third parties in a correct and private way. In particular, the third party learns no information on the data beyond the validity of claimed results. A challenging requirement here, is that the third party verifies the validity with respect to the specific data authenticated by the provider, while communicating only with the server. This problem is motivated by various application areas, ranging from stock-market monitoring and prediction services; to the publication of government-ran statistics on large healthcare databases. All of these applications require a reliable and scalable solution, in order to see practical adoption.

In this paper, we identify and formalize a key primitive allowing one to achieve the above: homomorphic signatures which evaluate non-deterministic computations (HSNP). We provide a generic construction for an HSNP evaluating universal relations; instantiate the construction; and implement a library for HSNP. This in turn allows us to build SPHINX: a system for proving arbitrary computations over streamed authenticated data in a privacy-preserving manner. SPHINX improves significantly over alternative solutions for this model. For instance, compared to corresponding solutions based on Marlin (Eurocrypt'20), the proof generation of SPHINX is between $15\times$ and $1\,300\times$ faster for various computations used in sliding-window statistics.

Masking of S-boxes using lookup tables is an effective countermeasure to thwart side-channel attacks on block ciphers implemented in software. At first and second orders, the Table-based Masking (TBM) schemes can be very efficient and even faster than circuit-based masking schemes. Ever since the customised second-order TBM schemes were proposed, the focus has been on designing and optimising Higher-Order Table-based Masking (HO-TBM) schemes that facilitate masking at arbitrary order. One of the reasons for this trend is that at large orders HO-TBM schemes are significantly slower and consume a prohibitive amount of RAM memory compared to circuit-based masking schemes such as bit-sliced masking, and hence efforts were targeted in this direction. However, a recent work due to Valiveti and Vivek (TCHES 2021) has demonstrated that the HO-TBM scheme of Coron et al. (TCHES 2018) is feasible to be implemented on memory-constrained devices with pre-processing capability and a competitive online execution time. Yet, currently, there are no customised designs for third-order TBM that are more efficient than instantiating a HO-TBM scheme at third order.

In this work, we propose a third-order TBM scheme for arbitrary S-boxes that is secure in the probing model and under compositions, i.e., 3-SNI secure. It is very efficient in terms of the overall running time, compared to the third-order instantiations of state-of-the-art HO-TBM schemes. It also supports the pre-processing functionality. For example, the overall running time of a single execution of the third-order masked AES-128 on a 32-bit ARM-Cortex M4 micro-controller is reduced by about 80% without any overhead on the online execution time. This implies that the online execution time of the proposed scheme is approximately eight times faster than the bit-sliced masked implementation at third order, and it is comparable to the recent scheme of Wang et al. (TCHES 2022) that makes use of reuse of shares. We also present the implementation results for the third-order masked PRESENT cipher. Our work suggests that there is a significant scope for tuning the performance of HO-TBM schemes at lower orders.

To bound information leakage in outputs of protocols, it is important to construct secure multiparty computation protocols which output differentially private values perturbed by the addition of noise. However, previous noise generation protocols have round and communication complexity growing with differential privacy budgets, or require parties to locally generate non-uniform noise, which makes it difficult to guarantee differential privacy against active adversaries. We propose three kinds of protocols for generating noise drawn from certain distributions providing differential privacy. The two of them generate noise from finite-range variants of the discrete Laplace distribution. For $(\epsilon,\delta)$-differential privacy, they only need constant numbers of rounds independent of $\epsilon,\delta$ while the previous protocol needs the number of rounds depending on $\delta$. The two protocols are incomparable as they make a trade-off between round and communication complexity. Our third protocol non-interactively generates shares of noise from the binomial distribution by predistributing keys for a pseudorandom function. It achieves communication complexity independent of $\epsilon$ or $\delta$ for the computational analogue of $(\epsilon,\delta)$-differential privacy while the previous protocols require communication complexity depending on $\epsilon$. We also prove that our protocols can be extended so that they provide differential privacy in the active setting.

$d$-Multiplicative secret sharing enables $n$ players to locally compute additive shares of the product of $d$ secrets from their shares. Barkol et al. (Journal of Cryptology, 2010) show that it is possible to construct a $d$-multiplicative scheme for any adversary structure satisfying the $Q_d$ property, in which no $d$ sets cover the whole set of players. In this paper, we focus on multipartite adversary structures and propose efficient multiplicative and verifiably multiplicative secret sharing schemes tailored to them. First, our multiplicative scheme is applicable to any multipartite $Q_d$-adversary structure. If the number of parts is constant, our scheme achieves a share size polynomial in the number $n$ of players while the general construction by Barkol et al. results in exponentially large share size in the worst case. We also propose its variant defined over smaller fields. As a result, for a special class of bipartite adversary structures with two maximal points, it achieves a constant share size for arbitrary $n$ while the share size of the first scheme necessarily incurs a logarithmic factor of $n$. Secondly, we devise a more efficient scheme for a special class of multipartite ones such that players in each part have the same weight and a set of players belongs to the adversary structure if and only if the sum of their weights is at most a threshold. Thirdly, if the adversary structure is $Q_{d+1}$, our first scheme is shown to be a verifiably multiplicative scheme that detects incorrect outputs with probability $1$. For multipartite adversary structures with a constant number of parts, it improves the worst-case share and proof sizes of the only known general construction by Yoshida and Obana (IEEE Transactions on Information Theory, 2019). Finally, we propose a more efficient verifiably multiplicative scheme by allowing small error probability $\delta$ and focusing on a more restricted class of multipartite adversary structures. Our scheme verifies computation of polynomials and can achieve a share size independent of $\delta$ while the previous construction only works for monomials and results in a share size involving a factor of $\log\delta^{-1}$.

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol among $n=3t+1$ nodes that can tolerate up to $t$ malicious nodes and support any reconstruction threshold $\ell\ge t$. Our protocol has an expected $O(\kappa n^3)$ communication cost, where $\kappa$ is a security parameter, and only assumes the hardness of Discrete Logarithm. The core ingredient of our ADKG protocol is an asynchronous protocol to secret share a random polynomial of degree $\ell\ge t$, which has other applications such as asynchronous proactive secret sharing and asynchronous multiparty computation. We implement our high-threshold ADKG protocol and evaluate it using a network of up to 128 geographically distributed nodes. Our evaluation shows that our high-threshold ADKG protocol reduces the running time by $90\%$ and reduces the bandwidth usage by $80\%$ over state-of-the-art.

The GIFT-64-128 block cipher encryption is implemented in MIPS assembly language. The program is assembled and simulated using the QtSPIM simu-lator and produces functionally correct results. This implementation requires 22,764 clock cycles per 64-bit block encryption, as well as 1,296 bytes of code, and 192 bytes of data memory. The major functional units of the im-plementation are analyzed in terms of cycle count and bytes of code.

Post-quantum signature schemes based on the MPC-in-the-Head~(MPCitH) paradigm are recently attracting significant attention as their security solely depends on the one-wayness of the underlying primitive, providing diversity for the hardness assumption in post-quantum cryptography. Recent MPCitH-friendly ciphers have been designed using simple algebraic S-boxes operating on a large field in order to improve the performance of the resulting signature schemes. Due to their simple algebraic structures, their algebraic immunity should be comprehensively studied.

In this paper, we refine algebraic cryptanalysis of power mapping based S-boxes over binary extension fields, and cryptographic primitives based on such S-boxes. In particular, for the Gröbner basis attack over $\mathbb{F}_2$, we experimentally show that the exact number of Boolean quadratic equations obtained from the underlying S-boxes is critical to correctly estimate the theoretic complexity based on the degree of regularity. Similarly, it turns out that the XL attack might be faster when all possible quadratic equations are found and used from the S-boxes. This refined cryptanalysis leads to more precise estimation on the algebraic immunity of cryptographic primitives based on algebraic S-boxes.

Considering the refined algebraic cryptanalysis, we propose a new one-way function, dubbed $\mathsf{AIM}$, as an MPCitH-friendly symmetric primitive with high resistance to algebraic attacks. The security of $\mathsf{AIM}$ is comprehensively analyzed with respect to algebraic, statistical, quantum, and generic attacks. $\mathsf{AIM}$ is combined with the BN++ proof system, yielding a new signature scheme, dubbed $\mathsf{AIMer}$. Our implementation shows that $\mathsf{AIMer}$ significantly outperforms existing signature schemes based on symmetric primitives in terms of signature size and signing time.

Recently, new ideas to build homomorphic noise-free encryption schemes have been proposed. The starting point of these schemes deals with private-key encryption schemes whose secret key is a rational function. By construction, these schemes are not homomorphic. To get homomorphic properties, nonlinear homomorphic operators are derived from the secret key. In this paper, we adopt the same approach to build a HE. We obtain a multivariate encryption scheme in the sense that the knowledge of the CPA attacker can be turned into an over-defined system of nonlinear equations. The factoring assumption is introduced in order to make a large class of attacks based on Groebner basis irrelevant. While we did not propose a formal security proof relying on a classical cryptographic assumption, we hopefully provide convincing evidence for security.