International Association
for Cryptologic Research

Chia is a popular cryptocurrency that relies on proofs of space (PoS) for consensus. Plots are the unit of storage on Chia and form the basis of PoS generation. When a proof is found that meets the challenge requirements, farmers on the network compete to create blocks.

Plot generation and farming involve the use of secret information, which makes plot transfer a non-trivial task in Chia. In this short note, we propose a way to transfer Chia plots in a secure manner with the help of zero-knowledge proofs.

SIDH is a key exchange algorithm proposed by Jao and De Feo that is conjectured to be post-quantum secure. The majority of work based on an SIDH framework uses elliptic curves in Montgomery form; this includes the original work by Jao, De Feo and Plût and the sate of the art implementation of SIKE. Elliptic curves in twisted Edwards form have also been used due to their efficient elliptic curve arithmetic, and complete Edwards curves have been used for their benefit of providing added security against side channel attacks. As far as we know, elliptic curves in Legendre form have not yet been explored for isogeny-based cryptography. Legendre form has the benefit of a very simple defining equation, and the simplest possible representation of the 2-torsion subgroup. In this work, we develop a new framework for constructing $2^a$-isogenies in SIDH using elliptic curves in Legendre form, and in doing so optimize Legendre curve arithmetic and $2$-isogeny computations on Legendre curves by avoiding any square root computations. We also describe an open problem which if solved would skip the strategy traversal altogether in SIDH through the Legendre curve framework.

We show that for many fundamental cryptographic primitives, proving classical security under the learning-with-errors (LWE) assumption, does not imply post-quantum security. This is despite the fact that LWE is widely believed to be post-quantum secure, and our work does not give any evidence otherwise. Instead, it shows that post-quantum insecurity can arise inside cryptographic constructions, even if the assumptions are post-quantum secure.

Concretely, our work provides (contrived) constructions of pseudorandom functions, CPA-secure symmetric-key encryption, message-authentication codes, signatures, and CCA-secure public-key encryption schemes, all of which are proven to be classically secure under LWE via black-box reductions, but demonstrably fail to be post-quantum secure. All of these cryptosystems are stateless and non-interactive, but their security is defined via an interactive game that allows the attacker to make oracle queries to the cryptosystem. The polynomial-time quantum attacker can break these schemes by only making a few classical queries to the cryptosystem, and in some cases, a single query suffices.

Previously, we only had examples of post-quantum insecurity under post-quantum assumptions for stateful/interactive protocols. Moreover, there appears to be a folklore belief that for stateless/non-interactive cryptosystems with black-box proofs of security, a quantum attack against the scheme should translate into a quantum attack on the assumption. This work shows otherwise. Our main technique is to carefully embed interactive protocols inside the interactive security games of the above primitives.

As a result of independent interest, we also show a 3-round quantum disclosure of secrets (QDS) protocol between a classical sender and a receiver, where a quantum receiver learns a secret message in the third round but, assuming LWE, a classical receiver does not.

SHA-3 is considered to be one of the most secure standardized hash functions. It relies on the Keccak-f[1 600] permutation, which operates on an internal state of 1 600 bits, mostly represented as a 5×5×64-bit matrix. While software implementations process the state sequentially in chunks of typically 32 or 64 bits, the Keccak-f[1 600] permutation can benefit a lot from speedup through parallelization. This paper is the first to explore the full potential of parallelization of Keccak-f[1 600] in RISC-V based processors through custom vector extensions on 32-bit and 64-bit architectures. %Such a structure is suitable to work under vector instructions in data-parallel operation mode. This paper uses the RISC-V vector extensions to explore its performance in 64-bit and 32-bit architectures. We analyze the Keccak-f[1 600] permutation, composed of five different step mappings, and propose ten custom vector instructions to speed up the computation. We realize these extensions in a SIMD processor described in SystemVerilog. We compare the performance of our hardware/software co-design to a software-only implementation on the one hand and to existing architectures based on (vectorized) hardware/software co-design on the other hand. We show that our design outperforms all related work thanks to our carefully selected custom vector instructions.

A union-only signature (UOS) scheme (informally introduced by Johnson et al. at CT-RSA 2002) allows signers to sign sets of messages in such a way that (1) any third party can merge two signatures to derive a signature on the union of the message sets, and (2) no adversary, given a signature on some set, can derive a valid signature on any strict subset of that set (unless it has seen such a signature already). Johnson et al. originally posed building a UOS as an open problem. In this paper, we make two contributions: we give the first formal definition of a UOS scheme, and we give the first UOS constructions. Our main construction uses hashing, regular digital signatures, Pedersen commitments and signatures of knowledge. We provide an implementation that demonstrates its practicality. Our main construction also relies on the hardness of the short integer solution (SIS) problem; we show how that this assumption can be replaced with the use of groups of unknown order. Finally, we sketch a UOS construction using SNARKs; this additionally gives the property that the size of the signature does not grow with the number of merges.

We present a new two-party construction for secure logistic regression training, which enables two parties to train a logistic regression model on private secret shared data. Our goal is to minimize online communication and round complexity, while still allowing for an efficient offline phase. As part of our construction we develop many building blocks of independent interest. These include a new approximation technique for the sigmoid function, which results in a secure evaluation protocol with better communication; secure spline evaluation and secure powers computation protocols for fixed-point values; and a new comparison protocol that optimizes online communication. We also present a new two-party protocol for generating keys for distributed point functions (DPFs) over arithmetic sharing, where previous constructions do this only for Boolean outputs. We implement our protocol in an end-to-end system and benchmark its efficiency. We can securely evaluate a sigmoid in $20$ ms online time and $1.12$ KB of online communication. Our system can train a model over a database with $6000$ samples and $5000$ features with online communication of $~40$ MB and online time of $9$min.

Various fault models, each with a distinct effect, have been introduced. The process of injecting a fault is not overly complicated, however it can be challenging to inject an exploitable fault. The influence of a fault model should be evaluated based on characteristics like as cost, repeatability, and practicability of desirable faults. Additionally, there must be efficient techniques for leveraging the injected fault to retrieve the key, especially in the presence of common countermeasures.

In this paper we introduce a new fault analysis technique called ``linked fault analysis''(LFA) which can be interpreted as a more powerful variation of several well-known fault attacks against implementations of symmetric primitives in various scenarios particularly in software implementations. While in a traditional fault attack, the fault model is defined based on the relation between the correct value and the defective one produced by fault injection, the LFA leverages a model in which the fault involves more than one intermediate value, the target variable $X$, and a second variable $Y$. We demonstrate that LFA allows the attacker to perform fault attacks with significantly less data (relative to previously presented fault attacks in the same class) and without the input control need.

Event date: 27 March to 29 March 2023
Submission deadline: 9 September 2022
Notification: 16 January 2023

We present BalanceProofs, the first vector commitment scheme that is maintainable (i.e., supporting sublinear updates) while also supporting fast proof aggregation and verification. The basic version of BalanceProofs has $O(\sqrt{n}\log n)$ update time and $O(\sqrt{n})$ query time and its constant-size aggregated proofs can be produced and verified in milliseconds. In particular, BalanceProofs improves the aggregation time and aggregation verification time of the only known maintainable and aggregatable vector commitment scheme, HyperProofs (USENIX SECURITY 2022), by up to 1000$\times$. Fast verification of aggregated proofs is particularly useful for applications such as stateless cryptocurrencies (and was a major bottleneck for Hyperproofs), where an aggregated proof of balances is produced once but must be verified multiple times and by a large number of nodes. As a limitation, BalanceProofs' update time compared to Hyperproofs roughly doubles, but always stays in the range from 2 to 3 seconds. BalanceProofs can be viewed as a compiler that transforms any non-maintainable vector commitment with fast aggregation to a maintainable one with the aforementioned complexities. We finally study useful tradeoffs in BalanceProofs between (aggregate) proof size, update time and (aggregate) proof computation and verification, by introducing a bucketing technique, and present an extensive evaluation, including a comparison to Hyperproofs as well as applications of BalanceProofs to Verkle trees.

Embedded devices with built-in security features are natural targets for physical attacks. Thus, enhancing their side-channel resistance is an important practical challenge. A standard solution for this purpose is the use of Boolean masking schemes, as they are well adapted to current block ciphers with efficient bit-slice representations. Boolean masking guarantees that the security of an implementation grows exponentially in the number of shares under the assumption that leakages are sufficiently noisy (and independent). Unfortunately, it has been shown that this noise assumption is hardly met on low-end devices. In this paper, we therefore investigate techniques to mask cryptographic algorithms in such a way that their resistance can survive an almost complete lack of noise. Building on seed theoretical results of Dziembowski et al., we put forward that arithmetic encodings in prime fields can reach this goal. We first exhibit the gains that such encodings lead to thanks to a simulated information theoretic analysis of their leakage (with up to six shares). We then provide figures showing that on platforms where optimized arithmetic adders and multipliers are readily available (i.e., most MCUs and FPGAs), performing masked operations in Mersenne-prime fields as opposed to binary extension fields will not lead to notable implementation overheads. We compile these observations into a new AES-like block cipher, called AES-prime, which is well-suited to leverage the remarkable advantages of masking in prime fields. We also confirm the practical relevance of our findings by evaluating concrete software (ARM Cortex-M3) and hardware (Xilinx Spartan-6) implementations. Our experimental results show that security gains over Boolean masking (and, more generally, binary encodings) can reach orders of magnitude.

We present new constructions of multi-party homomorphic secret sharing (HSS) based on a new primitive that we call homomorphic encryption with decryption to shares (HEDS). Our first construction, which we call Scooby, is based on many popular fully homomorphic encryption (FHE) schemes with a linear decryption property. Scooby achieves an $n$-party HSS for general circuits with complexity $O(|F| + \log n)$, as opposed to $O(n^2 \cdot |F|)$ for the prior best construction based on multi-key FHE. Scooby can be based on (ring)-LWE with a super-polynomial modulus-to-noise ratio. In our second construction, Scrappy, assuming any generic FHE plus HSS for NC1-circuits, we obtain a HEDS scheme which does not require a super-polynomial modulus. While these schemes all require FHE, in another instantiation, Shaggy, we show how in some cases it is possible to obtain multi-party HSS without FHE, for a small number of parties and constant-degree polynomials. Finally, we show that our Scooby scheme can be adapted to use multi-key fully homomorphic encryption, giving more efficient spooky encryption and setup-free HSS. This latter scheme, Casper, if concretely instantiated with a B/FV-style multi-key FHE scheme, for functions $F$ which do not require bootstrapping, gives an HSS complexity of $O(n \cdot |F| + n^2 \cdot \log n)$.

The genus is an efficiently computable arithmetic invariant for lattices up to isomorphism. Given the recent proposals of basing cryptography on the lattice isomorphism problem, it is of cryptographic interest to classify relevant families of lattices according to their genus. We propose such a classification for q-ary lattices, and also study their distribution. In particular, for an odd prime q, we show that random q-ary lattices are mostly concentrated on two genera. Because the genus is local, this also provides information on the distribution for general odd q. The case of q a power of 2 is also studied, although we only achieve a partial classification.

Statistical Ineffective Fault Attack (SIFA) has been a threat for implementa-tions of symmetric cryptographic primitives. Unlike Differential Fault At-tacks (DFA) which takes both correct and faulty ciphertexts, SIFA can re-cover the secret key with only correct ciphertexts. The classic SIFA is only effective on fault models with non-uniform distribution of intermediate val-ue. In this paper, we present a new fault model named adjacent-byte model, which describes a non-uniform distribution of relationship between two bytes (i.e. exclusive-or). To the best of our knowledge, it is the first time that this fault model has been proposed. We also show that the adjacent-byte faults can be induced by different fault sources and easy to reproduce. Then a new SIFA attack method called AB-SIFA on symmetric cryptography is proposed. We demonstrate the effectiveness of this new attack by simulating the attack. Finally, our attacks are applied to a software implementations of AES-128 with redundant countermeasure and a hardware AES co-processor, utilizing voltage glitches and clock glitches.

To defend against the rising threat of quantum computers, NIST initiated their Post-Quantum Cryptography(PQC) standardization process in 2016. During the PQC process, the security against side-channel attacks has received much attention. Lattice-based schemes are considered the most promising group to be standardized. Message encoding in lattice-based schemes has been proven to be vulnerable to side-channel attack, and first-order masked message encoder has been presented. However, there is still a lack of security evaluation for the first-order masked message encoder under different implementations. In this paper, we analyzed the security of first-order masked message encoder of Kyber. We found although masked Kyber certainly is able to defend against the previous side-channel attacks, there exists some exploitable byte leakages. By the help of the leakages, we propose a deep learning-based key recovery attack on message encoding of masked Kyber. We recover the original message from masked message encoding and then enable a chosen-ciphertext attack to recover the secret key. In our experiments, the whole secret key of masked Kyber768 was recovered with only 9 traces and the successful rate of attack is close to 100%.

ObliviousRAM(ORAM)isapowerfultechniquetopreventharmful data breaches. Despite tremendous progress in improving the concrete perfor- mance of ORAM, it remains too slow for use in many practical settings; recent breakthroughs in lower bounds indicate this inefficiency is inherent for ORAM and even some natural relaxations. This work introduces snapshot-oblivious RAMs, a new secure memory access primitive. Snapshot-oblivious RAMs bypass lower bounds by providing security only for transcripts whose length (call it c) is fixed and known ahead of time. Intuitively, snapshot-oblivious RAMs provide strong security for attacks of short duration, such as the snapshot attacks targeted by many encrypted databases. We give an ORAM-style definition of this new primitive, and present several constructions. The underlying design principle of our constructions is to store the history of recent operations in a data structure that can be accessed obliviously. We instantiate this paradigm with data structures that remain on the client, giving a snapshot-oblivious RAM with constant bandwidth overhead. We also show how these data structures can be stored on the server and accessed using oblivious memory primitives. Our most efficient instantiation achieves O(log c) bandwidth overhead. By extending recent ORAM lower bounds, we show this performance is asymptotically optimal. Along the way, we define a new hash queue data structure—essentially, a dictionary whose elements can be modified in a first-in- first-out fashion—which may be of independent interest.

Event date: 26 September to 30 September 2022

Event date: 14 December to 16 December 2022
Submission deadline: 25 July 2022
Notification: 5 September 2022

The UCLouvain Crypto Group is recruiting Ph.D. students willing to undertake a thesis in cryptography. The Ph.D. thesis will take place in the dynamic research environment of the group at UCLouvain (Louvain-la-Neuve, Belgium), in collaboration with other Ph.D. students, post-doctoral researchers and professors working on various aspects of cryptography.

The candidates should hold a master or engineering degree in mathematics, computer science or electronics, with strong interest in cryptography and security. A preliminary background in cryptography is useful, but not mandatory. The researcher will be hired for a one-year contract that can be renewed up to three times.

Several positions are open, in various subfields of cryptography, including verifiable computation, privacy-preserving technologies and leakage resilient cryptography.

Closing date for applications:

Contact: Candidates are invited to send a resume and motivation letter to Pr. Olivier Pereira, Pr. Francois-Xavier Standaert, Pr. Thomas Peters and Dr. Francois Koeune (email format: first name dot last name at uclouvain.be).

Applications are invited for a research intern position at the IMDEA Software Institute, Madrid, Spain.

Selected candidates will work under the supervision of Marco Guarnieri (https://mguarnieri.github.io).

The internship will focus on security at the hardware-software interface. The specific topic of the research will be determined based on the common interests of the candidate and the supervisor.

Who should apply?

Ideal candidates should be final year master students in Computer Science, Computer Engineering, or Mathematics with an interest in the aforementioned research topic. Experience in the following areas is a plus:(a) Computer Security, (b) Testing and Fuzzing, (c) Computer architectures, (d) Program analysis and verification, (e) Formal methods and logics. Solid programming skills will be highly valued. The position requires good teamwork and communication skills, including excellent spoken and written English.

Dates

The internship duration is intended to be for 4-6 months (with some flexibility). The ideal starting period is from September 2022. Deadline for applications is July 15th, 2022. Review of applications will begin immediately, and continue until the positions are filled.

How to apply?

Applicants interested in the position should submit their application at https://careers.software.imdea.org/ selecting option 7 - Internship and reference code 2022-06-intern-uarchsec.

Closing date for applications:

Contact: Marco Guarnieri (marco dot guarnieri at imdea dot org)

More information: https://software.imdea.org/open_positions/2022-06-intern-uarchsec.html

Applications are invited for one PhD student position in at the IMDEA Software Institute, Madrid, Spain.

Selected candidates will work under the supervision of Marco Guarnieri (https://mguarnieri.github.io).

The PhD position is in system security with a focus on security at the hardware-software interface. The specific topic of the research will be determined based on the common interests of the candidate and the supervisor.

Who should apply?

Ideal candidates have earned (or are in their last year of) a Master's degree in Computer Science, Computer Engineering, or Mathematics, with experience in at least one of the following areas: (a) Computer Security, (b) Testing and Fuzzing, (c) Computer architectures, (d) Program analysis and verification, (e) Formal methods and logics.

Solid programming skills will be highly valued. The position requires good teamwork and communication skills, including excellent spoken and written English.

Dates

The duration of the position is intended to be for the duration of the doctoral studies. The ideal starting period is from September 2022. Deadline for applications is July 15th, 2022. Review of applications will begin immediately, and continue until the positions are filled.

How to apply?

Applicants interested in the position should submit their application at https://careers.software.imdea.org/ selecting option 5 - PhD Student and reference code 2022-06-phd-uarchsec.

Closing date for applications:

Contact: Marco Guarnieri (marco dot guarnieri at imdea dot org)