International Association
for Cryptologic Research

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 ̈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.

The fixslicing implementation strategy was originally introduced as a new representation for the hardware-oriented GIFT block cipher to achieve very efficient software constant-time implementations. In this article, we show that the fundamental idea underlying the fixslicing technique is not of interest only for GIFT, but can be applied to other ciphers as well. Especially, we study the benefits of fixslicing in the case of AES and show that it allows to reduce by 41% the amount of operations required by the linear layer when compared to the current fastest bitsliced implementation on 32-bit platforms. Overall, we report that fixsliced AES-128 allows to reach 83 and 99 cycles per byte on ARM Cortex-M and RISC-V respectively (assuming pre-computed round keys), improving the previous records on those platforms by 17% and 20%. In order to highlight that our work also directly improves masked implementations that rely on bitslicing, we report implementation results when integrating first-order masking that outperform by 12% the fastest results reported in the literature on ARM Cortex-M4. Finally, we demonstrate the genericity of the fixslicing technique for AES-like designs by applying it to the Skinny-128 tweakable block ciphers.

Superlight blockchain clients learn facts about the blockchain state while requiring merely polylogarithmic communication in the total number of blocks. For proof-of-work blockchains, two known constructions exist: Superblock and FlyClient. Unfortunately, none of them can be deployed to existing blockchains, as they require consensus changes and at least a soft fork to implement. In this paper, we investigate how a blockchain can be upgraded to support superblock clients without a soft fork. We show that it is possible to implement the needed changes without modifying the consensus protocol and by requiring only a minority of miners to upgrade, a process termed a “velvet fork” in the literature. While previous work conjectured that superblock clients can be safely deployed using velvet forks as-is, we show that previous constructions are insecure, and that using velvet techniques to interlink a blockchain can pose insidious security risks. We describe a novel class of attacks, called “chain-sewing”, which arise in the velvet fork setting: an adversary can cut-and-paste portions of various chains from independent temporary forks, sewing them together to fool a superlight client into accepting a false claim. We show how previous velvet fork constructions can be attacked via chain- sewing. Next, we put forth the first provably secure velvet superblock client construction which we show secure against adversaries that are bounded by 1/3 of the upgraded honest miner population. Like non-velvet superlight clients, our approach allows proving generic predicates about chains using infix proofs and as such can be adopted in practice for fast synchronization of transactions and accounts.

When electronic wallets are transferred by more than one party, the level of security can be enhanced by decentralising the distribution of authorisation amongst those parties. Threshold signature schemes enable this functionality by allowing multiple cosigners to cooperate in order to create a joint signature. These cosigners interact to sign a transaction which then confirms that a wallet has been transferred. However, in the event of a post-quantum attack, existing threshold signature schemes that support such an authorisation technique in privacy-preserving cryptocurrency protocols - like Ring Confidential Transaction (RingCT) - would not provide adequate security.

In this paper, we present a new post-quantum cryptographic mechanism, called Lattice-based Linkable Ring Signature with Co-Signing (L2RS-CS), which offers a distributed authorisation feature to protect electronic wallets. A novel security model for L2RS-CS is also formalised to capture the security and privacy requirements to protect transactions in applications to blockchain cryptocurrency protocols, such as the RingCT. To address key-generation security concerns, and to support compression of keys and signatures, the L2RS-CS incorporates a distributed key generation along with a solid public-key aggregation. Finally, we prove the security of our constructed L2RS-CS in the random oracle model and the standard lattice-based Module-SIS hardness assumption.

Diene, Thabet and Yusuf recently proposed a new multivariate signature scheme whose public key is a set of multivariate cubic polynomials over a finite field. This paper studies its security.

Contact discovery allows users of mobile messengers to conveniently connect with people in their address book. In this work, we demonstrate that severe privacy issues exist in currently deployed contact discovery methods.

Our study of three popular mobile messengers (WhatsApp, Signal, and Telegram) shows that, contrary to expectations, large-scale crawling attacks are (still) possible. Using an accurate database of mobile phone number prefixes and very few resources, we have queried 10% of US mobile phone numbers for WhatsApp and 100% for Signal. For Telegram we find that its API exposes a wide range of sensitive information, even about numbers not registered with the service. We present interesting (cross-messenger) usage statistics, which also reveal that very few users change the default privacy settings. Regarding mitigations, we propose novel techniques to significantly limit the feasibility of our crawling attacks, especially a new incremental contact discovery scheme that strictly improves over Signal's current approach.

Furthermore, we show that currently deployed hashing-based contact discovery protocols are severely broken by comparing three methods for efficient hash reversal of mobile phone numbers. For this, we also propose a significantly improved rainbow table construction for non-uniformly distributed inputs that is of independent interest.