International Association
for Cryptologic Research

Recent progress in interactive zero-knowledge (ZK) proofs has improved the efficiency of proving large-scale computations significantly. Nevertheless, real-life applications (e.g., in the context of private inference using deep neural networks) often involve highly complex computations, and existing ZK protocols lack the expressiveness and scalability to prove results about such computations efficiently.

In this paper, we design, develop, and evaluate a ZK system (Mystique) that allows for efficient conversions between arithmetic and Boolean values, between publicly committed and privately authenticated values, and between fixed-point and floating-point numbers. Targeting large-scale neural-network inference, we also present an improved ZK protocol for matrix multiplication that yields a 7× improvement compared to the state-of-the-art. Finally, we incorporate Mystique in Rosetta, a TensorFlow-based privacy-preserving framework.

Mystique is able to prove correctness of an inference on a private image using a committed (private) ResNet-101 model in 28 minutes, and can do the same task when the model is public in 5 minutes, with only a 0.02% decrease in accuracy compared to a non-ZK execution when testing on the CIFAR-10 dataset. Our system is the first to support ZK proofs about neural-network models with over 100 layers with virtually no loss of accuracy.

Fully Homomorphic Encryption (FHE) schemes enable to compute over encrypted data. Among them, TFHE [CGGI17] has the great advantage of offering an efficient method for bootstrapping noisy ciphertexts, i.e., reduce the noise. Indeed, homomorphic computation increases the noise in ciphertexts and might compromise the encrypted message. TFHE bootstrapping, in addition to reducing the noise, also evaluates (for free) univariate functions expressed as look-up tables. It however requires to have the most significant bit of the plaintext to be known a priori, resulting in the loss of one bit of space to store messages. Furthermore it represents a non negligible overhead in terms of computation in many use cases.

In this paper, we propose a solution to overcome this limitation, that we call Programmable Bootstrapping Without Padding (WoP-PBS). This approach relies on two building blocks. The first one is the multiplication à la BFV [FV12] that we incorporate into TFHE. This is possible thanks to a thorough noise analysis showing that correct multiplications can be computed using practical TFHE parameters. The second building block is the generalization of TFHE bootstrapping introduced in this paper. It offers the flexibility to select any chunk of bits in an encrypted plaintext during a bootstrap. It also enables to evaluate many LUTs at the same time when working with small enough precision. All these improvements are particularly helpful in some applications such as the evaluation of Boolean circuits (where a bootstrap is no longer required in each evaluated gate) and, more generally, in the efficient evaluation of arithmetic circuits even with large integers. Those results improve TFHE circuit bootstrapping as well. Moreover, we show that bootstrapping large precision integers is now possible using much smaller parameters than those obtained by scaling TFHE ones.

Consider a server with a large set $S$ of strings $\{x_1,x_2, \dots,x_N\}$ that would like to publish a small hash $h$ of its set $S$ such that any client with a string $y$ can send the server a short message allowing it to learn $y$ if $y \in S$ and nothing otherwise. In this work, we study this problem of two-round private set intersection (PSI) with low (asymptotically optimal) communication cost, or what we call laconic private set intersection ($\ell$PSI) and its extensions. This problem is inspired by the recent general frameworks for laconic cryptography [Cho et al. CRYPTO 2017, Quach et al. FOCS'18].

We start by showing the first feasibility result for realizing $\ell$PSI based on the CDH assumption, or LWE with polynomial noise-to-modulus ratio. However, these feasibility results use expensive non-black-box cryptographic techniques leading to significant inefficiency. Next, with the goal of avoiding these inefficient techniques, we give a construction of $\ell$PSI schemes making only black-box use of cryptographic functions. Our construction is secure against semi-honest receivers, malicious senders and reusable in the sense that the receiver's message can be reused across any number of executions of the protocol. The scheme is secure under the $\phi$-hiding, decisional composite residuosity and subgroup decision assumptions.

Finally, we show natural applications of $\ell$PSI to realizing a semantically-secure encryption scheme that supports detection of encrypted messages belonging to a set of ``illegal'' messages (e.g., an illegal video) circulating online. Over the past few years, significant effort has gone into realizing laconic cryptographic protocols. Nonetheless, our work provides the first black-box constructions of such protocols for a natural application setting.

Cryptocurrency and blockchain continue to build on an innovative computation model that has paved the way for a large variety of applications. However, privacy is a huge concern as most (permissionless) blockchains log everything in the clear. This has resulted in several academic and industrial initiatives to address privacy. Starting with the UTXO model introduced by Bitcoin, initial works brought confidentiality and anonymity to payments. Recent works have expanded to support more generalized forms of private computation. Such solutions tend to be highly involved as they rely on advanced cryptographic primitives and creative techniques to handle issues related to dealing with private blockchain records (e.g. concurrency, private coin tracking to prevent double spending, efficiency). This situation makes it hard to comprehend the current state-of-the-art, much less build on top of it.

To address these challenges, we provide a systematization of knowledge for privacy-preserving solutions in blockchain. To the best of our knowledge, our work is the first of its kind. After motivating design challenges, we provide an overview of the zero-knowledge proof systems used in supporting blockchain privacy, focusing on their key features and limitations. Then, we develop a systematization of knowledge framework using which we group the state-of-the-art privacy preserving solutions under three categories: private payments, computation with input/output privacy, and function privacy. We briefly touch upon challenges and implications including misuse, regulations and compliance, usability, and limited functionality. Our work seeks to highlight open problems and research questions to guide future work directions.

In this paper, we initiate a study of asymmetric all-or-nothing transforms (or asymmetric AONTs). A (symmetric) $t$-all-or-nothing transform is a bijective mapping defined on the set of $s$-tuples over a specified finite alphabet. It is required that knowledge of all but $t$ outputs leaves any $t$ inputs completely undetermined. There have been numerous papers developing the theory of AONTs as well as presenting various applications of AONTs in cryptography and information security.

In this paper, we replace the parameter $t$ by two parameters $t_o$ and $t_i$, where $t_i \leq t_o$. The requirement is that knowledge of all but $t_o$ outputs leaves any $t_i$ inputs completely undetermined. When $t_i < t_o$, we refer to the AONT as asymmetric.

We give several constructions and bounds for various classes of asymmetric AONTs, especially those with $t_i = 1$ or $t_i = 2$. We pay particular attention to linear transforms, where the alphabet is a finite field $F_q$ and the mapping is linear.

The recent KEMTLS protocol (Schwabe, Stebila and Wiggers, CCS’20) is a promising design for a quantum-safe TLS handshake protocol. Focused on the web setting, wherein clients learn server public-key certificates only during connection establishment, a drawback compared to TLS 1.3 in terms of latency is that KEMTLS introduces an additional round trip before the server can send data. In many scenarios, including IoT and embedded settings, client devices may however have the targeted server certificate pre-loaded, so that such performance penalty seems unnecessarily restrictive.

This work proposes a variant of KEMTLS tailored to such scenarios. The protocol leverages the fact that clients know the server public keys in advance to decrease handshake latency while protecting client identities. It combines medium-lived with long-term server public keys to enable a delayed form of forward secrecy even from the first data flow on, and full forward secrecy upon the first round trip. The protocol is proved to achieve strong security guarantees, based on the security of the underlying building blocks, in a new model for multi-stage key exchange with medium-lived keys.

Established in 2020, Dfns is a cybersecurity startup operating within decentralized finance (DeFi). From our office in Paris, we are building an API for digital asset security. More specifically, Xkey provides safe, cloud-native custody as a service to help companies secure cryptos & tokens. Dfns is also a stellar team incubated at Station F (the world's biggest startup campus), the Garage (#1 blockchain ecosystem in Europe), and Techstars Future of Finance in collaboration with ABN AMRO.

We are looking for a highly motivated candidate to fill a cryptography researcher position at Dfns. Topics include:

Secure multi-party computation

Threshold Signature

Anonymity and privacy

Cryptocurrencies

Blockchain-based cryptography

Closing date for applications:

Contact: Houda Ferradi: Houda@dfns.io

More information: https://www.dfns.co/

A candidate will work in the area of post-quantum cryptography. A candidate will conduct research on code-based, lattice-based cryptography in term of design, its security and performance analysis; and possibly its applications, etc. The work requires to carry out some simulations.

Applicants are expected to have a PhD degree in Mathematics/Computer Science and a strong background in algebra, linear algebra, algebraic number theory or algebraic coding theory.

Preferred candidates are expected to be proficient in Magma software or SAGEMATH software, a team worker and able to conduct independent research.

Interested candidates will kindly include their full CV and transcripts in their applications and send to Dr Chik How Tan, tsltch@nus.edu.sg.

Only shortlisted applicants will be notified. Review of applicants will start immediately.

Closing date for applications:

Contact: Dr Chik How Tan (tsltch@nus.edu.sg)

Event date: 9 November to 11 November 2021
Submission deadline: 1 July 2021
Notification: 15 August 2021

Event date: 6 October to 8 October 2021
Submission deadline: 7 July 2021
Notification: 10 August 2021

TU Wien is Austria's largest institution of research and higher education in the fields of technology and natural sciences. The Security and Privacy research unit at the Institute of Logic and Computation at TU Wien is offering a 4-year PhD student position in symmetric cryptography.

A successful candidate should have an excellent academic record from a completed master or diploma curriculum in Mathematics, Computer Science, or related fields. Previous knowledge or experience in the area of cryptography or security is a plus.

The Security and Privacy research unit at TU Wien is internationally renowned with its expertise in the fields of cryptography, security and privacy. Our working language is English.

Formal applications must be submitted via https://jobs.tuwien.ac.at/Job/153314. We look forward to receiving your application until 29.07.2021.

Closing date for applications:

Contact: Inquiries about the position and process to Asst. Prof. Elena Andreeva elena[dot]andreeva[at]tuwien[dot]ac[dot]at

More information: https://jobs.tuwien.ac.at/Job/153314

In distributed computations and cryptography, it is desirable to record events on a public ledger, such that later alterations are computationally infeasible. An implementation of this idea is called blockchain, which is a distributed protocol that allows the creation of an immutable ledger. While such an idea is very appealing, the ledger may be contaminated with incorrect, illegal, or even dangerous data, and everyone running the blockchain protocol has no option but to store and propagate the unwanted data. The ledger is bloated over time, and it is not possible to remove redundant information. Finally, missing data cannot be inserted later. Redactable blockchains were invented to allow the ledger to be mutated in a controlled manner. To date, redactable blockchains support at most two types of redactions: block modification and removal. The next logical step is to support block insertions. However, we show that this seemingly innocuous enhancement renders all previous constructs insecure. We put forward a model for blockchains supporting all three redaction operations, and construct a blockchain that is provably secure under this formal definition.

Abstract: Side-channel attacks exploit information from the physical implementation of cryptographic systems, rather than from theoretical weaknesses. In recent years, cache attacks have made significant progress in their ability to recover secret information by combining observations of the victim's cache access and knowledge of the internal structure of the cipher. So far, cache attacks have been implemented for most Feistel-structured and SPN-structured block cipher algorithms, but the security of algorithms for special structures has little attention. In this paper, the Flush+Reload attack is performed on the implementation of MISTY1. Unlike Feistel and SPN structures, MISTY1 is a class of the block cipher with a recursive structure. The FL function is performed before the plaintext input S-box and after the ciphertext output S-box, making it difficult to attack the first and last rounds. However, we find that the key scheduling part of MISTY1 leaks many bits of key, which, together with the leakage of partial bits of the round key during encryption, was sufficient to recover the key of the MISTY1 algorithm. We design the algorithm that only needs to observe one time encryption to recover the MISTY1 128-bit key and use leakage during encryption to reduce the complexity of the algorithm. We experiment on 32-byte cache line and 64-byte cache line environment, respectively. In the 32-byte cache line environment, an adversary only needs to observe five times encryption to recover the all 128-bit key of the MISTY1 in 0.035 seconds; in the 64-byte cache line environment, an adversary needs to observe 10 times encryption to recover the entire 128-bit key in 2.1 hours.

Keywords: Side Channel, Cache attack, Flush+Reload, MISTY1, Key Scheduling Part

Homomorphic encryption (HE) is a useful variant of public key encryption (PKE), but it has a drawback that HE cannot fully achieve IND-CCA2 security, which is a standard security notion for PKE. Beyond existing HE schemes achieving weaker IND-CCA1 security, Emura et al.\ (PKC 2013) proposed the notion of \lq\lq keyed\rq\rq{} version of HE, called KH-PKE, which introduces an evaluation key controlling the functionality of homomorphic operations and achieves security stronger than IND-CCA1 and as close to IND-CCA2 as possible. After Emura et al.'s scheme which can evaluate linear polynomials only, Lai et al.\ (PKC 2016) proposed a fully homomorphic KH-PKE, but it requires indistinguishability obfuscation and hence has a drawback in practical feasibility. In this paper, we propose a \lq\lq two-level\rq\rq{} KH-PKE scheme for evaluating degree-two polynomials, by cleverly combining Emura et al.'s generic framework with a recent efficient two-level HE by Attrapadung et al.\ (ASIACCS 2018). Our scheme is the first KH-PKE that can handle non-linear polynomials while keeping practical efficiency.

For a hyperelliptic curve defined over a finite field $\bbbf_{q^n}$ with $n>1$, the discrete logarithm problem is subject to index calculus attacks. We exploit the endomorphism of the curve to reduce the size of the factorization basis and hence improve the complexity of the index calculus attack for certain families of ordinary elliptic curves and genus 2 hyperelliptic Jacobians defined over finite fields. This approach adds an extra cost when performing operation on the factor basis, but the experiences show that reducing the size of the factor basis allows to have a gain on the total complexity of index calculus algorithm with respect to the generic attacks.

In recent years machine learning has become increasingly mainstream across industries. Additionally, Graphical Processing Unit (GPU) accelerators are widely deployed in various neural network (NN) applications, including image recognition for autonomous vehicles and natural language processing, among others. Since training a powerful network requires expensive data collection and computing power, its design and parameters are often considered a secret intellectual property of their manufacturers. However, hardware accelerators can leak crucial information about the secret neural network designs through side-channels, like Electro-Magnetic (EM) emanations, power consumption, or timing.

We propose and evaluate non-invasive and passive reverse engineering methods to recover NN designs deployed on GPUs through EM side-channel analysis. We employ a well-known technique of simple EM analysis and timing analysis of NN layers execution. We consider commonly used NN architectures, namely Multilayer Perceptron and Convolutional Neural Networks. We show how to recover the number of layers and neurons as well as the types of activation functions. Our experimental results are obtained on a setup that is as close as possible to a real-world device in order to properly assess the applicability and extendability of our methods.

We analyze the NN execution of a PyTorch python framework implementation running on Nvidia Jetson Nano, a module computer embedding a Tegra X1 SoC that combines an ARM Cortex-A57 CPU and a 128-core GPU within a Maxwell architecture. Our results show the importance of side-channel protections for NN accelerators in real-world applications.

In CRYPTO 2019, Gohr introduced deep learning into cryptanalysis, and for the first time successfully applied it to key recovery attacks on Speck32/64 reduced to 11 and 12 rounds, with complexities comparable with traditional differential cryptanalysis. In this paper, we introduce the technique of generalized neutral bits into Gohr's framework, and successfully mount the first practical key recovery attacks against 13-round Speck32/64 with time $2^{48}$ and data $2^{29}$ for a success rate of 0.21. Compared against the best differential attacks in literature with time $2^{51}$ for 12 rounds or impractical time $2^{57}$ on a single GPU for 13 rounds, the full implementation of our 13-round attack is able to complete execution within 3 days. We also extend the framework to Simon32/64, and reduce the data complexity for the practical 16-round attack from 1/6 of the codebook to $2^{21}$. This is arguably the first time to witness deep learning based cryptanalysis having a considerable advantage over traditional methods.

In this work, we propose novel side-channel assisted chosen-ciphertext attacks applicable to IND-CCA secure NTRU-based PKE/KEMs. In particular, we propose two types of chosen-ciphertext attacks on Streamlined NTRU Prime which instantiate respectively, a plaintext-checking oracle and decryption-failure oracle to perform full key recovery. We propose efficient strategies to construct chosen ciphertexts to instantiate the aforementioned oracles to perform full key recovery. We perform experimental validation of our attacks on the optimized implementation of Streamlined NTRU Prime KEM obtained from the pqm4 public library, a testing and benchmarking framework for post quantum cryptographic schemes on the ARM Cortex-M4 microcontroller. We positively confirm that both the PC and DF oracle- based attacks result in full key recovery in a few thousand traces with 100% success rate. Masking serves as a concrete countermeasure against our proposed attacks and thus our work stresses on the need for concrete masking countermeasures for the NTRU-based PKE/KEMs to protect against similar chosen-ciphertext based side-channel attacks.

Deep learning-based side-channel analysis represents a powerful option for profiling attacks on power and electromagnetic leakages as it breaks targets protected with countermeasures. While most of the papers report successful results, it is not difficult to find cases where deep learning works better or worse, especially concerning various countermeasures. Current approaches concentrate on various data augmentations or hyperparameter tuning options to make the attacks more powerful. At the same time, understanding what makes an attack difficult has received very little attention. This paper proposes a side-channel analysis methodology based on the ablation paradigm to explain how neural networks process countermeasures. Our results show that an ablation is a powerful tool as it allows to understand 1) in which layers various countermeasures are processed, 2) whether it is possible to use smaller neural network architectures without performance penalties, and 3) how to redesign neural networks to improve the attack performance when the results indicate that the target cannot be broken. By using the ablation-based approach, we manage to mount more powerful attacks or use simpler neural networks without any attack performance penalties. We hope this is just the first of the works in the direction of countermeasure explainability for deep learning-based side-channel analysis.

Searchable Symmetric Encryption (SSE) enables a client to outsource a database to an untrusted server, while retaining the ability to securely search the data. The performance bottleneck of classic SSE schemes typically does not come from their fast, symmetric cryptographic operations, but rather from the cost of memory accesses. To address this issue, many works in the literature have considered the notion of locality, a simple design criterion that helps capture the cost of memory accesses in traditional storage media, such as Hard Disk Drives. A common thread among many SSE schemes aiming to improve locality is that they are built on top of new memory allocation schemes, which form the technical core of the constructions. The starting observation of this work is that for newer storage media such as Solid State Drives (SSDs), which have become increasingly common, locality is not a good predictor of practical performance. Instead, SSD performance mainly depends on page efficiency, that is, reading as few pages as possible. We define this notion, and identify a simple memory allocation problem, Data-Independent Packing (DIP), that captures the main technical challenge required to build page-efficient SSE. As our main result, we build a page-efficient and storage-efficient data-independent packing scheme, and deduce the Tethys SSE scheme, the first SSE scheme to achieve at once O(1) page efficiency and O(1) storage efficiency. The technical core of the result is a new generalization of cuckoo hashing to items of variable size. Practical experiments show that this new approach achieves excellent performance.