International Association
for Cryptologic Research

The Luxembourg Institute of Science and Technology (LIST) is a Research and Technology Organization (RTO) active in the fields of materials, environment and IT. By transforming scientific knowledge into technologies, smart data and tools, LIST empowers citizens in their choices, public authorities in their decisions and businesses in their strategies.

For its recent H2020 project PRECINCT (Cyber-physical security management for critical infrastructures), a research engineer vacancy is immediately available in the TRUST research group at LIST. The duty of this vacancy is mainly to implement a Digital Twins solution in the context of interdependent critical systems (telecommunications and energy).

Closing date for applications:

Contact: Dr. Qiang Tang (qiang.tang@list.lu)

More information: https://app.skeeled.com/offer/62024729a7d5b0db47a87221?language=en&show_description=true

Secure two-party neural network inference (2PC-NN) can offer privacy protection for both the client and the server and is a promising technique in the machine-learning-as-a-service setting. However, the large overhead of the current 2PC-NN in- ference systems is still being a headache, especially when applied to deep neural networks such as ResNet50. In this work, we present Cheetah, a new 2PC-NN inference system that is faster and more communication-efficient than state-of-the-arts. The main contributions of Cheetah are two-fold: the first part includes carefully designed homomorphic encryption-based protocols that can evaluate the linear layers (namely convolution, batch normalization, and fully-connection) without any expensive rotation operation. The second part includes several lean and communication-efficient primitives for the non-linear functions (e.g., ReLU and truncation). Using Cheetah, we present intensive benchmarks over several large-scale deep neural networks. Take ResNet50 for an example, an end- to-end execution of Cheetah under a WAN setting costs less than 2.5 minutes and 2.3 gigabytes of communication, which outperforms CrypTFlow2 (ACM CCS 2020) by about 5.6× and 12.9×, respectively.

Zero-knowledge (ZK) protocols enable one party to prove to others that it knows a fact without revealing any information about the evidence for such knowledge. There exist ZK protocols for all problems in NP, and recent works developed highly efficient protocols for proving knowledge of satisfying assignments to Boolean formulas, circuits and other NP formalisms. This work shows an efficient protocol for the the converse: proving formula *unsatisfiability* in ZK (when the prover posses a non-ZK proof). An immediate practical application is efficiently proving safety of secret programs.

The key insight is to prove, in ZK, the validity of *resolution proofs* of unsatisfiability. This is efficiently realized using an algebraic representation that exploits resolution proofs' structure to represent formula clauses as low-degree polynomials, combined with ZK random-access arguments. Only the proof's dimensions are revealed. We implemented our protocol and used it to prove unsatisfiability of formulas that encode combinatoric problems and program correctness conditions in standard verification benchmarks, including Linux kernel drivers and Intel cryptography modules. The results demonstrate both that our protocol has practical utility, and that its aggressive optimizations, based on non-trivial encodings, significantly improve practical performance.

Lattice and code based hard problems such as Learning With Errors (LWE) or syndrome decoding (SD) form cornerstones of post-quantum cryptography. However, signature schemes built on these assumptions remain rather complicated. Indeed, signature schemes from LWE problems are built on the Fiat-Shamir with abort paradigm with no apparent means for knowledge extraction. On the code side, signature schemes mainly stem from Stern's zero-knowledge identification scheme. However, because of its large soundness error of $2/3$, it is costly to turn into a signature scheme. The latest developments rely on complicated cut-and-choose and multiparty-in-the-head techniques. As a consequence, they apply the Fiat-Shamir transformation on protocols with at least 5 rounds, leading to additional complexity and degraded security parameters. In the present paper, we propose an alternative approach to build a simple zero-knowledge $\Sigma$-protocol with a small soundness error, based on the hardness of Ring-and-Noise assumptions, a general family of assumptions that encompasses both lattices and codes. With such a $\Sigma$-protocol at hand, signatures can directly be derived by invoking the standard Fiat-Shamir transform, without the need for aborts. The main novel tool that allows us to achieve this is the use of specifically tailored locality sensitive hash functions. We outline our schemes for general Ring-and-Noise assumptions and present them in detail for the ring of residues modulo Mersenne numbers endowed with the Hamming metric. This Mersenne setting is ideal to illustrate our schemes, since it is close in spirit to both lattice and code based assumptions.

This paper demonstrates the first side-channel attack on homomorphic encryption (HE), which allows computing on encrypted data. We reveal a power-based side-channel leakage of Microsoft SEAL prior to v3.6 that implements the Brakerski/Fan-Vercauteren (BFV) protocol. Our proposed attack targets the Gaussian sampling in the SEAL’s encryption phase and can extract the entire message with a single power measurement. Our attack works by (1) identifying each coefficient index being sampled, (2) extracting the sign value of the coefficients from control-flow variations, (3) recovering the coefficients with a high probability from data-flow variations, and (4) using a Blockwise Korkine-Zolotarev (BKZ) algorithm to efficiently explore and estimate the remaining search space. Using real power measurements, the results on a RISC-V FPGA implementation of the SEAL (v3.2) show that the proposed attack can reduce the plaintext encryption security level from 2ˆ128 to 2ˆ4.4. Therefore, as HE gears toward real-world applications, such attacks and related defenses should be considered.

We present here the analysis of a new perturbation, that seems to strengthen significantly the security of some families of multivariate schemes. Thanks to this new perturbation, we are indeed able to get interestingly efficient signature and encryption public key schemes, in particular when combining this perturbation to the well known trapdoors HFE and UOV. We present here the best attacks that we know against these variant schemes and we give practical examples of parameters for current standard of security.

Comparisons are a basic component of the commonly used ReLU functions, ever more present in Machine Learning and specifically in Neural Networks. Motivated by the increasing interest on privacy-preserving Artificial Intelligence, we explore the current state of the art of MPC protocols for privacy preserving comparisons. We then introduce constant round variations of these protocols, which are compatible with commonly used fixed point arithmetic MPC protocols, and geared towards realistic ReLU implementations. Furthermore, we provide novel constructions, inspired by other commonly used comparisons, and incorporate state of the art elements. Additionally, we translate these results into practice, using state of the art MPC tools and providing an open source implementation. Finally, we cater for an extensive benchmarking of the described protocols on various adversarial settings, and offer conclusions about their viability when adopted for privacy-preserving Machine Learning.

We present two new provably secure finality layers for Nakamoto style blockchains. One is for partially synchronous networks and the other is for networks with periods of synchrony. Both protocols are player replaceable and therefore enjoy protection against denial of service attacks when run with a proof-of-stake lottery to elect the parties. The finality layers are proven secure to run on top of any Nakamoto style blockchain which has a property called \emph{finality friendliness}. Both finality layers improve on all existing provably secure finality layers in terms of communication complexity or security. A proof-of-stake finality layer has $v$-validity if whenever it declares a block $B$ final then honest parties holding a fraction $v$ of the stake had $B$ on the longest chain. Validity is important to prevent that the finality layer finalises blocks that were not ``good'' according to the Nakamoto style blockchain. We prove upper bounds on the achievable validity in partially synchronous networks and networks with periods of synchrony. Both our finality layers match these upper bounds.

The round complexity of secure two-party computation is a long studied problem with matching upper and lower bounds for the case of black-box simulators (i.e., the simulators that use the adversary as a black-box). In this work, we focus on going beyond this black-box barrier via non-black-box techniques. Specifically, based on standard cryptographic assumptions, we give a construction of a 3-round two-party computation protocol for computing inputless functionalities (such as coin-tossing) that satisfies standard security against malicious senders and $\epsilon$-security against malicious receivers. Prior to our work such protocols were only known for the case of (weak) zero-knowledge.

Nowadays, together with stormy technology advancement, billions of interconnected devices are constantly collecting data around us. In that fashion, privacy protection has become a major concern. The data must be in encrypted form before being stored on the cloud servers. As a result, the cloud servers are unable to perform calculations on en- crypted data, such as searching and matching keywords. In the PKE- MET setting, a cloud server can perform an equality test on a number of ciphertexts which encrypted with the same designated number. In this paper, we propose, for the first time, an efficient construction of a quantum-safe PKE-MET system based on the hardness of the Learning with Errors (LWE) problem in the lattice setting. Furthermore, we also discuss the first lattice-base public key encryption with flexible multi- ciphertext equality test (PKE-FMET) constructions, which allow per- forming equality test on multiple ciphertexts whose designated numbers are less than a threshold number. Our proposed schemes are proven to be secure in the standard model.

The FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) and its TFHE variant (Chillotti et al., Asiacrypt 2016) are the best-known methods to perform bit-level homomorphic computations on encrypted data. There are two competing bootstrapping approaches to FHEW-like schemes: the AP bootstrapping method (Alperin-Sheriff and Peikert, Crypto 2014) which is the basis of the original FHEW scheme, and the GINX bootstrapping method (Gama et al., Eurocrypt 2016), adopted by TFHE. An attractive feature of the AP/FHEW method is that it supports arbitrary secret key distributions, which are both critical for a number of important applications (like threshold and some multi-key homomorphic encryption (HE) schemes), and provides better security guarantees. On the other hand, GINX/TFHE bootstrapping uses much smaller evaluation keys, but it is directly applicable only to binary secret keys, which are less standard and restrict the scheme's applicability. (Extensions of GINX/TFHE bootstrapping to arbitrary keys are known, but they incur a substantial performance penalty.) In this paper, we present a new bootstrapping procedure for FHEW-like schemes that achieves the best features of both schemes and further improves on them: support for arbitrary secret key distributions at no additional runtime costs, while using small evaluation keys (even smaller than GINX). As an added benefit, our new bootstrapping procedure results in smaller noise growth than both AP and GINX, regardless of the key distribution. Our improvements are both theoretically significant (offering asymptotic savings, up to a O(log n) multiplicative factor, either on the running time or public evaluation key size), and practically relevant. We demonstrate the practicality of the proposed methods by building a prototype implementation within the PALISADE open-source HE library. Our experimental results show that our methods have minimal overhead, and improve on the practical performance of previous schemes, by factors ranging from small constants (already in the case of ternary keys) to an order of magnitude or more (e.g., when comparing to FHEW evaluation key size for arbitrary secret keys.) We illustrate the benefits of our method by providing a simple construction of threshold HE based on FHEW.

This paper discusses the implications of choosing a computational model to study the cost of cryptographic attacks and therefore quantify how dangerous they are. This choice is often unconscious and the chosen model itself is usually implicit; but it has repercussions on security evaluations.

We compare three reasonable computational models: $i$) the usual Random Access Machine (RAM) model; $ii$) the ``Expensive Memory Model'' explicitly introduced by several 3rd-round submissions to the Post-Quantum NIST competition (it states that a single access to a large memory costs as much as many local operations); $iii)$ the venerable VLSI model using the Area-Time cost measure.

It is well-known that costs in the RAM model are lower that costs in the last two models. These have been claimed to be more realistic, and therefore to lead to more precise security evaluations. The main technical contribution of this paper is to show that the last two these models are incomparable. We identify a situation where the expensive memory model overestimates costs compared to the (presumably even more realistic) VLSI model.

In addition, optimizing the cost in each model is a distinct objective that leads to different attack parameters, and raises the question of what is the ``best'' way to proceed for an eventual attacker. We illustrate these discrepancies by studying several generic attacks against hash function and Feistel networks in the three models.

In this paper we generalise Ti's fault attack and the loop abort fault attacks on supersingular isogeny cryptosystems (genus one) to genus two. Genus two isogeny based cryptosystems are generalisations of its genus one counterpart, as such, attacks on the the latter are believed to generalise to the former.

Fault attacks on supersingular elliptic curve isogeny cryptography has been shown to be practical. We show in this paper that fault attacks continue to be practical in genus two, albeit with a few additional traces required.

In this paper, we provide a comprehensive overview of a recent debate over the quantum versus classical solvability of bounded distance decoding (BDD). Specifically, we review the work of Eldar and Hallgren [EH22], [Hal21] demonstrating a quantum algorithm solving $\lambda_1 2^{-\Omega(\sqrt{k \log q})}$-BDD in polynomial time for lattices of periodicity $q$, finite group rank $k$, and shortest lattice vector length $\lambda_1$. Subsequently, we prove the results of [DvW21a], [DvW21b] with far greater detail and elaboration than in the original work. Namely, we show that there exists a deterministic, classical algorithm achieving the same result.

The Keccak sponge function family, designed by Bertoni et al. in 2007, was selected by the U.S. National Institute of Standards and Technology (NIST) in 2012 as the next generation of Secure Hash Algorithm (SHA-3). Due to its theoretical and practical importance, cryptanalysis against SHA-3 has attracted an increasing attention. To the best of our knowledge, the most powerful collision attack on SHA-3 up till now is the linearisation technique proposed by Jian Guo et al. However, that technique is infeasible to work on variants with a smaller input space, such as SHA3-384.

In this work we improve previous results with three ideas which were not used in previous works against SHA-3. First, in order to reduce constraints and increase flexibility in our solutions, we use 2-block messages instead of 1-block messages. Second, we reduce the connectivity problem into a satisfiability (SAT) problem, instead of applying the linearisation technique. Finally, we consider two new non-random properties of the Keccak non-linear layer and propose an efficient deduce-and-sieve algorithm based on these properties.

The resulting collision-finding algorithm on 4-round SHA3-384 has a practical time complexity of $2^{59.64}$ (and memory complexity of $2^{45.93}$). This greatly improves the previous best known collision attack by Dinur et al., whose $2^{147}$ time complexity was far from being practical. Although our attack does not threaten the security margin of the SHA-3 hash function, the tools developed in this paper could be useful in future analysis of other cryptographic primitives and also in development of new and faster SAT solvers.

Distributed random beacons publish random numbers at regular intervals, which anyone can obtain and verify. The design of public distributed random beacons has been an exciting research direction with significant implication to blockchains, voting and beyond. Random beacons, in addition to being bias-resistant and unpredictable, also need to have low communication cost, low latency, and ease of reconfigurability. Existing works on synchronous random beacons sacrifice one or more of these properties.

In this work, we design an efficient unpredictable synchronous random beacon protocol, OptRand, with quadratic (in the number $n$ of system nodes) communication complexity per beacon output. First, we innovate by employing a novel combination of bilinear pairing based publicly verifiable secret sharing and non-interactive zero-knowledge proofs to build a linear (in $n$) sized publicly verifiable random sharing. Second, we develop a state machine replication protocol with linear-sized inputs that is also optimistically responsive, i.e., it can progress responsively at actual network speed during optimistic conditions, despite the synchrony assumption, and thus incur low latency. In addition, we present an efficient reconfiguration mechanism for OptRand that allows nodes to leave and join the system.

Given a small number of base oblivious transfers (OTs), how does one generate a large number of extended OTs as efficiently as possible? The answer has long been the seminal work of IKNP (Ishai et al., Crypto 2003) and the family of protocols it inspired, which only use Minicrypt assumptions. Recently, Boyle et al. (Crypto 2019) proposed the Silent-OT technique that improves on IKNP, but at the cost of a much stronger, non-Minicrypt assumption: the learning parity with noise (LPN) assumption. We present SoftSpokenOT, the first OT extension to improve on IKNP's communication cost in the Minicrypt model. While IKNP requires security parameter $\lambda$ bits of communication for each OT, SoftSpokenOT only needs $\lambda / k$ bits, for any $k$, at the expense of requiring $2^{k-1} / k$ times the computation. For small values of $k$, this tradeoff is favorable since IKNP-style protocols are network-bound. We implemented SoftSpokenOT and found that our protocol gives almost a $5 \times$ speedup over IKNP in the LAN setting.

Our technique is based on a novel silent protocol for vector oblivious linear evaluation (VOLE) over polynomial-sized fields. We created a framework to build maliciously secure 1-of-N OT extension from this VOLE, revisiting the existing work for each step. Along the way, we found several flaws in the existing work, including a practical attack against the consistency check of Patra et al. (NDSS 2017), while also making some improvements.

We propose a new garbled RAM construction called NanoGRAM, which achieves an amortized cost of $\widetilde{O}(\lambda \cdot (W \log N + \log^3 N))$ bits per memory access, where $\lambda$ is the security parameter, $W$ is the block size, and $N$ is the total number of blocks, and $\widetilde{O}(\cdot)$ hides $poly\log\log$ factors. For sufficiently large blocks where $W = \Omega(\log^2 N)$, our scheme achieves $\widetilde{O}(\lambda \cdot W \log N)$ cost per memory access, where the dependence on $N$ is optimal (barring $poly\log\log$ factors), in terms of the evaluator's runtime. Our asymptotical performance matches even the {\it interactive} state-of-the-art (modulo $poly\log\log$ factors), that is, running Circuit ORAM atop garbled circuit, and yet we remove the logarithmic number of interactions necessary in this baseline. Furthermore, we achieve asymptotical improvement over the recent work of Heath et al. Our scheme adopts the same assumptions as the mainstream literature on practical garbled circuits, i.e., circular correlation-robust hashes or a random oracle. We evaluate the concrete performance of NanoGRAM and compare it with a couple of baselines that are asymptotically less efficient. We show that NanoGRAM starts to outperform the naive linear-scan garbled RAM at a memory size of $N = 2^9$ and starts to outperform the recent construction of Heath et al. at $N = 2^{13}$.

Finally, as a by product, we also show the existence of a garbled RAM scheme assuming only one-way functions, with an amortized cost of $\widetilde{O}(\lambda^2 \cdot (W \log N + \log^3 N))$ per memory access. Again, the dependence on $N$ is nearly optimal for blocks of size $W = \Omega(\log^2 N)$ bits.

We introduce the short-lived proof, a non-interactive proof of knowledge with a novel feature: after a specified period of time, the proof is no longer convincing. This time-delayed loss of soundness happens "naturally" without further involvement from the prover or any third party. We propose formal definitions for short-lived proofs as well as the special case of short-lived signatures. We show several practical constructions built using verifiable delay functions (VDFs). The key idea in our approach is to allow any party to forge any proof by executing a large sequential computation. Some constructions achieve a stronger property called reusable forgeability in which one sequential computation allows forging an arbitrary number of proofs of different statements. Our work also introduces two novel types of VDFs, re-randomizable VDFs and zero-knowledge VDFs, which may be of independent interest.

Meet-in-the-middle (MITM) is a general paradigm where internal states are computed along two independent paths ('forwards' and 'backwards') that are then matched. Over time, MITM attacks improved using more refined techniques and exploiting additional freedoms and structure, which makes it more involved to find and optimize such attacks. This has led to the use of detailed attack models for generic solvers to automatically search for improved attacks, notably a MILP model developed by Bao et al. at EUROCRYPT 2021. In this paper, we study a simpler MILP modeling combining a greatly reduced attack representation as input to the generic solver, together with a theoretical analysis that, for any solution, proves the existence and complexity of a detailed attack. This modeling allows to find both classical and quantum attacks on a broad class of cryptographic permutations. First, Present-like constructions, with the permutations of the Spongent hash functions: we improve the MITM step in distinguishers by up to 3 rounds. Second, AES-like designs: despite being much simpler than Bao et al.'s, our model allows to recover the best previous results. The only limitation is that we do not use degrees of freedom from the key schedule. Third, we show that the model can be extended to target more permutations, like Feistel networks. In this context we give new Guess-and-determine attacks on reduced Simpira v2 and Sparkle. Finally, using our model, we find several new quantum preimage and pseudo-preimage attacks (e.g. Haraka v2, Simpira v2 ... ) targeting the same number of rounds as the classical attacks.