International Association
for Cryptologic Research

This document provides a simple standard specification for the Rescue-Prime family of arithmetization-oriented hash functions.

Given a non-square n=pq, since p, q are two roots of x^2-\theta x+n=0, where \theta=p+q is unknown, one can pick the initial values l, r and use Newton method to construct A(\theta, l, k), B(\theta, r, k) approximating to p, q, respectively, where k is the iteration depth. Solve A(\theta, l, k)B(\theta, r, k)=n && \theta>2\sqrt{n} && l< A(\theta, l, k)<\sqrt{n}< B(\theta, r, k)<r to obtain the approximations of \theta. Accumulate and sort the approximations for different initial values. Then pivot these approximations to search for the target \theta such that \theta^2-4n is a square. The success probability of this algorithm depends on the choice of initial values, the iteration depth, and the search scope around the pivots. The algorithm can be easily parallelized, and its complexity can be restricted to O(\log^9n).

In this paper we present a signature scheme based on the difficulty of finding a point in a shifted Grassmannian variety or on its secant variety from a knowledge of its defining polynomials. An advantage of using the secant variety of the Grassmannian is that it is defined by sparse cubic equations, which are in general more difficult to solve than quadratic ones, thereby reducing the size of the public key.

The min-entropy is an important metric to quantify randomness of generated random numbers in cryptographic applications; it measures the difficulty of guessing the most-likely output. One of the important min-entropy estimator is the compression estimator of NIST Special Publication (SP) 800-90B, which relies on Maurer's universal test. In this paper, we propose two kinds of min-entropy estimators to improve computational complexity and estimation accuracy by leveraging two variations of Maurer's test: Coron's test (for Shannon entropy) and Kim's test (for Renyi entropy). First, we propose a min-entropy estimator based on Coron's test which is computationally efficient than the compression estimator while maintaining the estimation accuracy. The secondly proposed estimator relies on Kim's test that computes the Renyi entropy. This proposed estimator improves estimation accuracy as well as computational complexity. We analytically characterize an interesting trade-off relation between theoretical gap of accuracy and variance of min-entropy estimates, which depends on the order of Renyi entropy. By taking into account this trade-off relation, we observe that the order of two is a proper assignment since the proposed estimator based on the collision entropy (i.e., the Renyi entropy of order two) provides the most accurate estimates. Moreover, the proposed estimator based on the collision entropy has a closed-form solution whereas both the compression estimator and the proposed estimator based on Coron's test do not have closed-from solutions. Numerical evaluations demonstrate that the first proposed estimator achieves the same accuracy as the compression estimator with much less computations. Moreover, the second estimator can even improve the accuracy as well as reduce the computational complexity.

We present succinct and adaptively secure attribute-based encryption (ABE) schemes for arithmetic branching programs, based on k-Lin in pairing groups. Our key-policy ABE scheme has ciphertexts of constant size, independent of the length of the attributes, and our ciphertext-policy ABE scheme has secret keys of constant size. Our schemes improve upon the recent succinct ABE schemes in [Tomida and Attrapadung, ePrint '20], which only handle Boolean formulae. All other prior succinct ABE schemes either achieve only selective security or rely on q-type assumptions.

Our schemes are obtained through a general and modular approach that combines a public-key inner product functional encryption satisfying a new security notion called gradual simulation security and an information-theoretic randomized encoding scheme called arithmetic key garbling scheme.

We introduce formal definitions for deniability in group chats by extending a pre-existing model that did not have this property. We then introduce “epochal signatures” as an almost drop-in replacement for signatures, which can be used to make certain undeniable group-chats deniable by just performing that replacement. Following that we provide a practical epochal signature scheme and prove its security.

We present MOTION, an efficient and generic framework for mixed-protocol secure multi-party computation (MPC). Our framework is built from the ground up and incorporates several important engineering decisions such as full communication serialization which enables MPC over arbitrary messaging interfaces and removes the need of owning network sockets. It is available under the liberal MIT license and independent of external MPC libraries, which often have stricter licenses. MOTION is extensive and thoroughly tested: it currently consists of more than 36000 lines of code, 20% of which are unit and component tests. It is built in a user-friendly, modular, and extensible way, intended to be used as tool in MPC research and to increase adoption of MPC protocols in practice. MOTION incorporates several novel performance optimizations that improve the communication complexity and latency, e.g., 2x better online round complexity of precomputed correlated Oblivious Transfer (OT).

We instantiate our framework with protocols for $N$ parties and security against up to $N-1$ passive corruptions: the MPC protocols of Goldreich-Micali-Wigderson (GMW) in its arithmetic and Boolean version and oblivious transfer (OT)-based BMR (Ben-Efraim et al., CCS'16), as well as novel and highly efficient conversions between them, including a non-interactive conversion from BMR to arithmetic GMW. Moreover, we design a novel garbling technique that saves 20% of communication in the BMR protocol.

MOTION is highly efficient, which we demonstrate in our experiments by measuring its run-times in various network settings with different numbers of parties. For secure evaluation of AES-128 with $N=3$ parties in the high-latency network setting from the OT-based BMR paper, we achieve a 16x better throughput of 16 AES/s using BMR. This shows that the BMR protocol is much more competitive than previously assumed. For $N=3$ parties and full-threshold protocols in the LAN setting, MOTION is 10x-18x faster than the previous best passively secure implementation from the MP-SPDZ framework, and 190x-586x faster than the actively secure SCALE-MAMBA framework. Finally, we show that our framework is highly efficient for privacy preserving neural network inference.

This paper is devoted to a more precise classification of the family of curves $E_b:y^2=x^3+b/\mathbb{F}_p$. For prime $p\equiv 1 \pmod 3$, explicit formula of the number of $\mathbb{F}_p$-rational points on $E_b$ is given based on the the coefficients of a (primary) decomposition of $p=(c+d\omega)\overline{(c+d\omega)}$ in the ring $\mathbb{Z}[\omega]$ of Eisenstein integers. More specifically, \[ \#E_b(\mathbb{F}_p)\in p+1-\big\{\pm(d-2c),\pm(c+d), \pm(c-2d)\big\}. \] The correspondence between these $6$ number of points and the $6$ isomorphism classes of the groups $E_b(\mathbb{F}_p)$ can be efficiently determined.

For prime $p\equiv 2 \pmod 3$, it is shown that $E_b(\mathbb{F}_p)\cong \mathbb{Z}_{p+1}$. Two efficiently computable isomorphisms are described within the single isomorphism class of groups for representatives $E_1(\mathbb{F}_p)$ and $E_{-3}(\mathbb{F}_p)$

The explicit formulas $\#E_b(\mathbb{F}_p)$ for $p\equiv 1 \pmod p$ are used in searching prime (or almost prime) order Koblitz curves over prime fields. An efficient procedure is described and analyzed. The procedure is proved to be deterministic polynomial time, assuming the Generalized Riemann Hypothesis.

Several tools that are useful in computing cubic residues are also developed in this paper.

Attribute-based encryption (ABE) is an advanced form of encryption scheme allowing for access policies to be embedded within the secret keys and ciphertexts. By now, we have ABEs supporting numerous types of policies based on hardness assumptions over bilinear maps and lattices. However, one of the distinguishing differences between ABEs based on these two breeds of assumptions is that the former can achieve adaptive security for quite expressible policies (e.g., inner-products, boolean formula) while the latter can not. Recently, two adaptively secure lattice-based ABEs have appeared and changed the state of affairs: a non-zero inner-product (NIPE) encryption by Katsumata and Yamada (PKC'19) and an ABE for $t$-CNF policies by Tsabary (CRYPTO'19). However, the policies supported by these ABEs are still quite limited and do not embrace the more interesting policies that have been studied in the literature. Notably, constructing an adaptively secure inner-product encryption (IPE) based on lattices still remains open.

In this work, we propose the first adaptively secure IPE based on the learning with errors (LWE) assumption with sub-exponential modulus size (without resorting to complexity leveraging). Concretely, our IPE supports inner-products over the integers $\mathbb{Z}$ with polynomial sized entries and satisfies adaptively weakly-attribute-hiding security. We also show how to convert such an IPE to an IPE supporting inner-products over $\mathbb{Z}_p$ for a polynomial-sized $p$ and a fuzzy identity-based encryption (FIBE) for small and large universes. Our result builds on the ideas presented in Tsabary (CRYPTO'19), which uses constrained pseudorandom functions (CPRF) in a semi-generic way to achieve adaptively secure ABEs, and the recent lattice-based adaptively secure CPRF for inner-products by Davidson et al. (CRYPTO'20). Our main observation is realizing how to weaken the conforming CPRF property introduced in Tsabary (CRYPTO'19) by taking advantage of the specific linearity property enjoyed by the lattice evaluation algorithms by Boneh et al. (EUROCRYPT'14).

Deep learning approaches have become popular for Side-Channel Analysis (SCA) in the recent years. Especially Convolutional Neural Networks (CNN) due to their natural ability to overcome jitter-based as well as masking countermeasures. However, most efforts have focused on finding optimal architecture for a given dataset and bypass the need for trace pre-processing. However, trace pre-processing is a long studied topic and several proven techniques exist in the literature. There is no straightforward manner to integrate those techniques into deep learning based SCA. In this paper, we propose a generic framework which allows seamless integration of multiple, user defined pre-processing techniques into the neural network architecture. The framework is based on Multi-scale Convolutional Neural Networks (MCNN) that were originally proposed for time series analysis. MCNN are composed of multiple branches that can apply independent transformation to input data in each branch to extract the relevant features and allowing a better generalization of the model. In terms of SCA, these transformation can be used for integration of pre-processing techniques, such as phase-only correlation, principal component analysis, alignment methods etc. We present successful results on publicly available datasets. Our findings show that it is possible to design a network that can be used in a more general way to analyze side-channel leakage traces and perform well across datasets.

Subterranean 2.0 is a cipher suite that can be used for hashing, authenticated encryption, MAC computation, etc. It was designed by Daemen, Massolino, Mehrdad, and Rotella, and has been selected as a candidate in the second round of NIST's lightweight cryptography standardization process. Subterranean 2.0 is a duplex-based construction and utilizes an extremely simple one-round permutation in the duplex. It is the simplicity of the round function that makes it an attractive target of cryptanalysis. In this paper, we examine the one-round permutation in various phases of Subterranean 2.0 and specify three related attack scenarios that deserve further investigation: keystream biases in the keyed squeezing phase, state collisions in the keyed absorbing phase, and one-round differential analysis in the nonce-misuse setting. First, to facilitate cryptanalysis, we propose two size-reduced toy versions of Subterranean 2.0: Subterranean-m and Subterranean-s. Then we exploit the resemblance between the non-linear layer in the round function of Subterranean 2.0 and SIMON's round function to construct our models for searching characteristics to be used in the keystream bias evaluation and state collision attack. Our results show that there exists no linear trail under the constraint of data limit imposed by the designers with a minimal number of output blocks. This partially confirms the designers' claim on the bias of keystream. Regarding state collisions in keyed modes, we find useful characteristics of two toy versions with which forgery attacks can be mounted successfully. However, due to the time-consuming search, the security of Subterranean 2.0 against the state collision attack in keyed modes still remains an open question. Finally, we observe that one-round differentials allow to recover state bits in the nonce-misuse setting. By proposing nested one-round differentials, we obtain a sufficient number of state bits, leading to a practical state recovery with only 20 repetitions of the nonce and 88 blocks of data. It is noted that our work does not threaten the security of Subterranean 2.0.

An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e., for every input the observed locations accessed are similarly distributed. In recent years there has been great progress both in terms of upper bounds as well as in terms of lower bounds, essentially pinning down the smallest overhead possible in various settings of parameters.

We observe that there is a very natural setting of parameters in which no non-trivial lower bound is known, even not ones in restricted models of computation (like the so called balls and bins model). Let $N$ and ${\boldsymbol w}$ be the number of cells and bit-size of cells, respectively, in the RAM that we wish to simulate obliviously. Denote by ${\boldsymbol b}$ the cell bit-size of the ORAM. All previous ORAM lower bounds have a multiplicative ${\boldsymbol w}/{\boldsymbol b}$ factor which makes them trivial in many settings of parameters of interest.

In this work, we prove a new ORAM lower bound that captures this setting (and in all other settings it is at least as good as previous ones, quantitatively). We show that any ORAM must make (amortized) $$ \Omega\left(\log \left(\frac{N{\boldsymbol w}}{m}\right)/\log\left(\frac{{\boldsymbol b}}{{\boldsymbol w}}\right)\right) $$ memory probes for every logical operation. Here, $m$ denotes the bit-size of the local storage of the ORAM. Our lower bound implies that logarithmic overhead in accesses is necessary, even if $ {\boldsymbol b} \gg {\boldsymbol w}$. Our lower bound is tight for all settings of parameters, up to the $\log({\boldsymbol b}/{\boldsymbol w})$ factor. Our bound also extends to the non-colluding multi-server setting.

As an application, we derive the first (unconditional) separation between the overhead needed for ORAMs in the online vs. offline models. Specifically, we show that when ${\boldsymbol w}=\log N$ and ${\boldsymbol b},m \in \mathsf{poly}\log N$, there exists an offline ORAM that makes (on average) $o(1)$ memory probes per logical operation while every online one must make $\Omega(\log N/\log\log N)$ memory probes per logical operation. No such previous separation was known for any setting of parameters, not even in the balls and bins model.

Minimal linear codes are a special class of codes which have important applications in secret sharing and secure two-party computation. These codes are characterized by the property that none of the codewords is covered by some other codeword. Denoting by $w_{min}$ and $w_{max}$ minimal and maximal weight of the codewords respectively, such codes are relatively easy to design when the ratio $w_{min}/w_{max} > 1/2$ (known as Aschikhmin-Barg's bound). On the other hand, there are few known classes of minimal codes violating this bound, hence having the property $w_{min}/w_{max} \leq 1/2$. In this article, we provide several explicit classes of minimal binary linear codes violating the Aschikhmin-Barg's bound, at the same time achieving a great variety of the ratio $w_{min}/w_{max}$. Our first generic method employs suitable characteristic functions of relatively low weight within the range $[n+1, 2^{n-2}]$. The second approach addresses a specification of characteristic functions covering the weights in $[2^{n-2}+1, 2^{n-2} + 2^{n-3}-1]$ and containing a skewed (removing one element) affine subspace of dimension $n-2$. Finally, we also characterize an infinite family of such codes that utilize the class of so-called root Boolean functions of weight $2^{n-1}-(n-1)$, which are useful in certain hardware testing applications. Consequently, many infinite classes of minimal codes crossing the Aschikhmin-Barg's bound, with a wide range of the weight of their characteristic functions, are deduced. In certain cases we also completely specify the weight distribution of resulting codes.

We apply multiparty computation (MPC) techniques to show, given a database that is secret-shared among multiple mutually distrustful parties, how the parties may obliviously construct a decision tree based on the secret data. We consider data with continuous attributes (i.e., coming from a large domain), and develop a secure version of a learning algorithm similar to the C4.5 or CART algorithms. Previous MPC-based work only focused on decision tree learning with discrete attributes (De Hoogh et al. 2014).

Our starting point is to apply an existing generic MPC protocol to a standard decision tree learning algorithm, which we then optimize in several ways. We exploit the fact that even if we allow the data to have continuous values, which a priori might require fixed or floating point representations, the output of the tree learning algorithm only depends on the relative ordering of the data. By obliviously sorting the data we reduce the number of comparisons needed per node to $O(N \log^2 N)$ from the naive $O(N^2)$, where $N$ is the number of training records in the dataset, thus making the algorithm feasible for larger datasets. This does however introduce a problem when duplicate values occur in the dataset, but we manage to overcome this problem with a relatively cheap subprotocol. We show a procedure to convert a sorting network into a permutation network of smaller complexity, resulting in a round complexity of $O(\log N)$ per layer in the tree.

We implement our algorithm in the MP-SPDZ framework and benchmark our implementation for both passive and active three-party computation using arithmetic modulo $2^{64}$. We apply our implementation to a large scale medical dataset of $\approx 290\,000$ rows using random forests, and thus demonstrate practical feasibility of using MPC for privacy-preserving machine learning based on decision trees for large datasets.

The connectivity is increasing in the world with the increased usage of IoT (Internet of Things) devices. To this end, amount of data that needs to be stored and retrieved securely has increased tremendously, but the IoT devices have a small amount of memory and computation capacity. Consequently, a storage area with a large amount of secured storage space is needed. Software-defined Networking (SDN) is an emerging network technology which implements a new paradigm of insecure applications and IoT services. To build a heterogeneous secure network, we introduced SDN controller broadcast encryption using the Open Network Operating System integrated with network switches and SDN Controllers. In this paper, we propose a secured data sharing system in IoT devices in which the IoT devices are connected to an SDN controller and data from the IoT device is encrypted. Only the corresponding authorized switch receives the data and knows the exact key to decrypt the ciphertext, so the data is stored and retrieved securely. In this system, we use Wheatstone algorithm to encrypt the data from the IoT devices. The usage of this algorithm helps to avoid botnet attacks and other types of attacks on the data. The proposed system established new forwarding paths through controller and it communicated with authorized switches for secure data transmissions. We analyzed the performance of our proposed algorithm using OMNeT++ to simulate our entire scenario and confirmed that the algorithm is efficient and secure in IoT applications. This extends the security features of IoT applications.

Recently, division property based cube attack has acheived new progress and some cryptanalytic results against well-known stream ciphers. At EUROCRYPT 2020, Hao~\emph{et~al.} proposed a new modeling method for three-subset division property without unknown subset. With this method, the exact expression of the superpoly in cube attack can be recovered. In this paper, we propose a method to search good cubes for both distinguishing attacks and key recovery attacks in the division property based cube attack scenario. Our cube searching procedure is based on the algorithm of degree evaluation of the superpoly and the algorithm of superpoly recovery. In the process of cube searching, we mainly use the embedded property to narrow down the searching space. As a result, we find some new cube testers of dimension $126$ on $775$-round ACORN. We also find a new key recovery attack on $775$-round ACORN with a $126$-dimensional cube, whose corresponding superpoly is a 2-degree polynomial with respect to key bits.

To meet the ever-growing need for performance in silicon devices, SoC providers have been increasingly relying on software-hardware cooperation. By controlling hardware resources such as power or clock management from the software, developers earn the possibility to build more flexible and power efficient applications. Despite the benefits, these hardware components are now exposed to software code and can potentially be misused as open-doors to jeopardize trusted environments, perform privilege escalation or steal cryptographic secrets. In this work, we introduce SideLine, a novel side-channel vector based on delay-line components widely implemented in high-end SoCs. After providing a detailed method on how to access and convert delay-line data into power consumption information, we demonstrate that these entities can be used to perform remote power side-channel attacks. We report experiments carried out on two SoCs from distinct vendors and we recount several core-vs-core attack scenarios in which an adversary process located in one processor core aims at eavesdropping the activity of a victim process located in another core. For each scenario, we demonstrate the adversary ability to fully recover the secret key of an OpenSSL AES running in the victim core. Even more detrimental, we show that these attacks are still practicable if the victim or the attacker program runs over an operating system.

In blockchains where hashed timelock contracts are possible atomic swaps are already deployed, but when one of the blockchains doesn't have this capability it becomes a challenge. This protocol describes how to achieve atomic swaps between Bitcoin and Monero with two transactions per chain without trusting any central authority, servers, nor the other swap participant. We propose a swap between two participants, one holding bitcoin and the other monero, in which when both follow the protocol their funds are not at risk at any moment. The protocol does not require timelocks on the Monero side nor script capabilities but does require two proofs of knowledge of equal discrete logarithm across the edward25519 and the secp256k1 groups and ECDSA one-time VES.

The supersingular isogeny key encapsulation (SIKE) protocol, as one of the post-quantum protocol candidates, is widely regarded as the best alternative for curve-based cryptography. However, the long latency, caused by the serial large-degree isogeny computation which is dominated by modular multiplications, has made it hard for practical applications. In this paper, we present a fast FPGA implementation for the SIKE by incorporating algorithmic transformations and architectural optimizations. Firstly, we introduce a novel data representation, which can facilitate faster and higher-parallel field arithmetic computing than prior arts. Secondly, an extremely low-latency modular multiplier is devised based on the new algorithm by fully parallelizing and highly optimizing the small-size multipliers and reduction modules. Thirdly, a compact control logic is developed based on the benchmark provided in the newest SIKE library, well fitting our arithmetic logic unit (ALU). Finally, we code the proposed architectures using the Verilog language and integrate them into the SIKE library. The implementation results on a Xilinx Virtex-7 FPGA show that for the SIKEp751, our design only costs 13.2 ms with a frequency of 138.9 MHz, about 2x faster than the state-of-the-art. Particularly, the modular multiplier merely needs 16 clock cycles, reducing the delay by nearly one order of magnitude with a small factor of increase in hardware resource.

This paper addresses V &#776;oronoi cell-based algorithms, specifically the ”Relevant Vectors” algorithm, used to solve the Shortest Vector Problem, a fundamental challenge in lattice-based cryptanalysis. Several optimizations are proposed to reduce the execution time of the original algorithm. It is also shown that the algorithm is highly suited for parallel execution on both CPUs and GPUs. The proposed optimizations are based on pruning, i.e., avoiding computations that will not, with high probability, improve the solution. The pruning criteria is related to the target vectors norm relative to the current best solution vector norm. When pruning is performed without pre-processing, speedups up to 69× are observed compared to the original algorithm. If a pre-process sorting step is performed, which requires storing the norm ordered target vectors and therefore significantly more memory, this speedup increases to 77×. On the parallel processing side, the multi-core version of the optimized algorithm exhibits linear scalability on a CPU with up to 28 threads and keeps scaling, albeit at a lower rate, with Simultaneous Multi-Threading with up to 56 threads. The lack of support for efficient global synchronization among threads in GPUs does not allow for a scalable implementation of the pruning optimization using these devices. Nevertheless, a parallel GPU version of the non optimized algorithm is demonstrated to be competitive with the parallel non optimized CPU version, although the latter outperforms the former when using 56 threads. It is argued that the GPU version would outperform the CPU for higher lattice dimensions, although this statement cannot be experimentally verified due to the limited memory available on current GPU boards.