International Association
for Cryptologic Research

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.

Payment channel networks (PCNs) are a layer-2 blockchain scalability solution, with its main entity, the payment channel, enabling transactions between pairs of nodes "off-chain," thus reducing the burden on the layer-1 network. Nodes with multiple channels can serve as relays for multihop payments over a path of channels: they relay payments of others by providing the liquidity of their channels, in exchange for part of the amount withheld as a fee. Relay nodes might after a while end up with one or more unbalanced channels, and thus need to trigger a rebalancing operation. In this paper, we study how a relay node can maximize its profits from fees by using the rebalancing method of submarine swaps. We introduce a stochastic model to capture the dynamics of a relay node observing random transaction arrivals and performing occasional rebalancing operations, and express the system evolution as a Markov Decision Process. We formulate the problem of the maximization of the node's fortune over time over all rebalancing policies, and approximate the optimal solution by designing a Deep Reinforcement Learning (DRL)-based rebalancing policy. We build a discrete event simulator of the system and use it to demonstrate the DRL policy's superior performance under most conditions by conducting a comparative study of different policies and parameterizations. In all, our approach aims to be the first to introduce DRL for network optimization in the complex world of PCNs.

QROM (quantum random oracle model), introduced by Boneh et al. (Asiacrypt 2011), captures all generic algorithms. However, it fails to describe non-uniform quantum algorithms with preprocessing power, which receives a piece of bounded classical or quantum advice. As non-uniform algorithms are largely believed to be the right model for attackers, starting from the work by Nayebi, Aaronson, Belovs, and Trevisan (QIC 2015), a line of works investigates non-uniform security in the random oracle model. Chung, Guo, Liu, and Qian (FOCS 2020) provide a framework and establish non-uniform security for many cryptographic applications.

In this work, we continue the study on quantum advice in the QROM. We provide a new idea that generalizes the previous multi-instance framework, which we believe is more quantum-friendly and should be the quantum analogue of multi-instance games. To this end, we match the bounds with quantum advice to those with classical advice by Chung et al., showing quantum advice is almost as good/bad as classical advice for many natural security games in the QROM.

Finally, we show that for some contrived games in the QROM, quantum advice can be exponentially better than classical advice for some parameter regimes. To our best knowledge, it provides some evidence of a general separation between quantum and classical advice relative to an unstructured oracle.

Byzantine broadcast is a central component of several cryptographic protocols, from secure multiparty computation to consensus mechanisms for blockchains. Many practical applications require increasingly weaker trust assumptions, as well as scalability for an ever-growing number of users, which rules out existing solutions with linear number of rounds or trusted setup requirements. This poses the question of achieving broadcast with efficient communication and round complexity against powerful adversarial models and without trusted setup assumptions. In this paper, we answer this question positively. We present a Broadcast protocol that runs in rounds sublinear in $n$, the number of users, with asymptotic communication $\tilde O(n^3)$. Our protocol does not assume the existence of a trusted dealer who issues keys or common random strings. Instead, it is built upon a trustless verifiable delay function and the existence of random oracles in order to achieve a graded form of shared randomness between parties. This graded shared randomness acts as an untrusted online setup that can be used to securely run a committee-based protocol, similar to Chan et al. (PKC 2020). We also show that the graded shared randomness protocol we design can be used to seed multiple instances of Broadcast, which further amortizes the communication cost per instance to $\tilde O(n^2)$ over $n$ instances or even to $\tilde O(n)$ per $n$ instances of parallel Broadcast.

We demonstrate how to apply some ideas from group theory to quagmire ciphers. Techniques are shown for amplifying one's knowledge of the keys. This is useful when breaking a ciphertext with a crib. The basic idea is that only a small amount of information goes into building a key table for a quagmire cipher, so we should only need that much information to reconstruct it.

We present a rather generic backdoor mechanism that can be applied to many LWE-like public-key cryptosystems. Our construction manipulates the key generation algorithm of such schemes in a way that allows a malicious adversary in possession of secret backdoor information to recover generated secret keys from corresponding public keys. To any user of the cryptosystem however, the output of our backdoored key generation is indistinguishable from output of the legitimate key generation algorithm. Our construction relies on elliptic-curve cryptography and draws on existing work on encoding of elliptic curve points as bit strings.

Our backdoor mechanism can be applied to public-key cryptosystems where the secret key is generated from a secret seed and the public key includes a public seed of the same length. This holds - though not exclusively - for many cryptosystems based on LWE. In particular, we point out that our construction can be applied to backdoor HQC, FrodoKEM, Kyber and Dilithium.

We also suggest a countermeasure that makes our backdoor detectable by users of the cryptosystem. To this end, we modify the key generation such that the public and secret key are pseudorandomly generated from a single seed which is included in the generated secret key. This allows any user of the key generation algorithm to regenerate keys using an independent implementation, making our backdooring attempt detectable.

The traditional definition of quantum zero-knowledge stipulates that the knowledge gained by any quantum polynomial-time verifier in an interactive protocol can be simulated by a quantum polynomial-time algorithm. One drawback of this definition is that it allows the simulator to consume significantly more computational resources than the verifier. We argue that this drawback renders the existing notion of quantum zero-knowledge not viable for certain settings, especially when dealing with near-term quantum devices. In this work, we initiate a fine-grained notion of post-quantum zero-knowledge that is more compatible with near-term quantum devices. We introduce the notion of $(s,f)$ space-bounded quantum zero-knowledge. In this new notion, we require that an $s$-qubit malicious verifier can be simulated by a quantum polynomial-time algorithm that uses at most $f(s)$-qubits, for some function $f(\cdot)$, and no restriction on the amount of the classical memory consumed by either the verifier or the simulator. We explore this notion and establish both positive and negative results: - For verifiers with logarithmic quantum space $s$ and (arbitrary) polynomial classical space, we show that $(s,f)$-space-bounded QZK, for $f(s)=2s$, can be achieved based on the existence of post-quantum one-way functions. Moreover, our protocol runs in constant rounds. - For verifiers with super-logarithmic quantum space $s$, assuming the existence of post-quantum secure one-way functions, we show that $(s,f)$-space-bounded QZK protocols, with fully black-box simulation (classical analogue of black-box simulation) can only be achieved for languages in BQP.

Optimal simple rules for the monetary policy of the first stochastically dominant crypto-currency are derived in a Dynamic Stochastic General Equilibrium (DSGE) model, in order to provide optimal responses to changes in inflation, output, and other sources of uncertainty.

The optimal monetary policy stochastically dominates all the previous crypto-currencies, thus the efficient portfolio is to go long on the stochastically dominant crypto-currency: a strategy-proof arbitrage featuring a higher Omega ratio with higher expected returns, inducing an investment-efficient Nash equilibrium over the crypto-market.

Zero-knowledge proofs of the monetary policy are committed on the blockchain: an implementation is provided.

We give a first construction of an ϵ-balanced hash family based on linear transformations of vectors in $\mathbb{F}_2$, where ϵ = 1/(2n − 1) for n-bit hash values, regardless of the message size. The parameter n is also the bit length of the input blocks and the internal state, and can be chosen arbitrarily without design changes, This hash family is fast, easily parallelized, and requires no initial setup. A secure message authentication code can be obtained by combining the hash family with a pseudo random function. These features make the hash family attractive for memory integrity protection, while allowing generic use cases.

ASCON is a family of cryptographic primitives for authenticated encryption and hashing introduced in 2015. It is selected as one of the ten finalists in the NIST Lightweight Cryptography competition. Since its introduction, ASCON has been extensively cryptanalyzed, and the results of these analyses can indicate the good resistance of this family of cryptographic primitives against known attacks, like differential and linear cryptanalysis. Proving upper bounds for the differential probability of differential trails and for the squared correlation of linear trails is a standard requirement to evaluate the security of cryptographic primitives. It can be done analytically for some primitives like AES. For other primitives, computer assistance is required to prove strong upper bounds for differential and linear trails. Computer-aided tools can be classified into two categories: tools based on general-purpose solvers and dedicated tools. General-purpose solvers such as SAT and MILP are widely used to prove these bounds, however they seem to have lower capabilities and thus yield less powerful bounds compared to dedicated tools. In this work, we present a dedicated tool for trail search in ASCON. We arrange 2-round trails in a tree and traverse this tree in an efficient way using a number of new techniques we introduce. Then we extend these trails to more rounds, where we also use the tree traversal technique to do it efficiently. This allows us to scan much larger spaces of trails faster than the previous methods using general-purpose solvers. As a result, we prove tight bounds for 3-rounds linear trails, and for both differential and linear trails, we improve the existing upper bounds for other number of rounds. In particular, for the first time, we prove bounds beyond $2^{-128}$ for 6 rounds and beyond $2^{-256}$ for 12 rounds of both differential and linear trails.

While being decentralized, secure, and reliable, Bitcoin and many other blockchain-based cryptocurrencies suffer from scalability issues. One of the promising proposals to address this problem is off-chain payment channels. Since, not all nodes are connected directly to each other, they can use a payment network to route their payments. Each node allocates a balance that is frozen during the channel's lifespan. Spending and receiving transactions will shift the balance to one side of the channel. A channel becomes unbalanced when there is not sufficient balance in one direction. In this case, we say the effective lifespan of the channel has ended. In this paper, we develop a mathematical model to predict the expected effective lifespan of a channel based on the network's topology. We investigate the impact of channel unbalancing on the payment network and individual channels. We also discuss the effect of certain characteristics of payment channels on their lifespan. Our case study on a snapshot of the Lightning Network shows how the effective lifespan is distributed, and how it is correlated with other network characteristics. Our results show that central unbalanced channels have a drastic effect on the network performance.

Recently, Aaronson et al. (arXiv:2009.07450) showed that detecting interference between two orthogonal states is as hard as swapping these states. While their original motivation was from quantum gravity, we show its applications in quantum cryptography.

1. We construct the first public key encryption scheme from cryptographic non-abelian group actions. Interestingly, ciphertexts of our scheme are quantum even if messages are classical. This resolves an open question posed by Ji et al. (TCC ’19). We construct the scheme through a new abstraction called swap-trapdoor function pairs, which may be of independent interest.

2. We give a simple and efficient compiler that converts the flavor of quantum bit commitments. More precisely, for any prefix X, Y $\in$ {computationally,statistically,perfectly}, if the base scheme is X-hiding and Y-binding, then the resulting scheme is Y-hiding and X-binding. Our compiler calls the base scheme only once. Previously, all known compilers call the base schemes polynomially many times (Crépeau et al., Eurocrypt ’01 and Yan, Asiacrypt ’22). For the security proof of the conversion, we generalize the result of Aaronson et al. by considering quantum auxiliary inputs.