International Association
for Cryptologic Research

Event date: 13 November to 16 November 2022

The algebraic group model (AGM), proposed by Fuchsbauer, Kiltz and Loss (CRYPTO 2018) has received huge attention. One of the most appealing properties of the AGM, is that, the hardness of security games in the generic group model (GGM) can be transferred via a generic reduction in the AGM. More concretely, for any two security games, G and H, if there exists a generic reduction from H to G in the AGM, and H is hard in the GGM, then G is also hard in the GGM.

In this work, we analyze the relationship between the AGM and Shoup’s GGM (Eurocrypt 1997) and give evidence that:

• hardness of security games in Shoup’s GGM cannot be transferred via a generic reduction in the AGM;

• the AGM and Shoup’s GGM are incomparable.

In the wake of the Covid-19 pandemic, countries and organizations started looking towards technology to curb the spread of the disease, for instance, conducting contact tracing with smartphones. Many contact tracing applications are on the market, built on different technology, such as Bluetooth, GPS, Sound, and QR code scanning systems. The use of sound is an area that has potential for further exploration; currently, only NOVID is utilizing this technology. On top of that, there is a need for a decentralized backend solution that is both public and auditable to address data manipulation concerns. One of the possible solutions is using a blockchain as the backend for the system. We propose a blockchain-based contact tracing solution that uses sound and Bluetooth to detect proximity. Our proposed solution uses blockchain as the backend of the system for decentralized storage of contact tracing data. In the proposed system, close contact is established if both Bluetooth and sound are detected between the communicating devices. The practicality of the proposed scheme is assessed by a performance evaluation of the proximity detection system and a proof-of-concept of the blockchain backend. The results show that the sound-amplitude based distance measurement can estimate whether an encounter is a close contact (within 3 meters) using a ‘threshold’ of the amplitude. The use of sound amplitude eliminates situations where the usage of only Bluetooth would show false positives. The proposed approach is the first work that integrates Blockchain, Bluetooth and sound amplitude for proximity detection to the best of our knowledge. Overall, the system shows promising results in distance estimation than if only a Bluetooth implementation is used.

ARM-based Android smartphones rely on the TrustZone hardware support for a Trusted Execution Environment (TEE) to implement security-sensitive functions. The TEE runs a separate, isolated, TrustZone Operating System (TZOS), in parallel to Android. The implementation of the cryptographic functions within the TZOS is left to the device vendors, who create proprietary undocumented designs.

In this work, we expose the cryptographic design and implementation of Android's Hardware-Backed Keystore in Samsung's Galaxy S8, S9, S10, S20, and S21 flagship devices. We reversed-engineered and provide a detailed description of the cryptographic design and code structure, and we unveil severe design flaws. We present an IV reuse attack on AES-GCM that allows an attacker to extract hardware-protected key material, and a downgrade attack that makes even the latest Samsung devices vulnerable to the IV reuse attack. We demonstrate working key extraction attacks on the latest devices. We also show the implications of our attacks on two higher-level cryptographic protocols between the TrustZone and a remote server: we demonstrate a working FIDO2 WebAuthn login bypass and a compromise of Google’s Secure Key Import.

We discuss multiple flaws in the design flow of TrustZone based protocols. Although our specific attacks only apply to the $\approx$100 million devices made by Samsung, it raises the much more general requirement for open and proven standards for critical cryptographic and security designs.

Event date: 23 August to 26 August 2022
Submission deadline: 20 April 2022
Notification: 8 June 2022

Event date: 13 February to 16 February 2022
Submission deadline: 21 February 2022

Event date: 17 October to 19 October 2022
Submission deadline: 3 April 2022
Notification: 19 June 2022

Event date: 7 June to 10 June 2022
Submission deadline: 26 March 2022
Notification: 23 April 2022

Event date: 29 May to 30 May 2022
Submission deadline: 15 March 2022
Notification: 7 April 2022

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.