International Association
for Cryptologic Research

Masking, an effective countermeasure against side-channel attacks, is commonly applied in modern cryptographic implementations. Considering cryptographic algorithms that utilize both Boolean and arithmetic masking, the conversion algorithm between arithmetic masking and Boolean masking is required. Conventional high-order arithmetic masking to Boolean masking conversion algorithms based on Boolean circuits suffer from performance overhead, especially in terms of hardware implementation. In this work, we analyze high latency for the conversion and propose an improved high-order A2B conversion algorithm. For the conversion of 16-bit variables, the hardware latency can be reduced by 47% in the best scenario. For the case study of second-order 32-bit conversion, the implementation results show that the improved scheme reduces the clock cycle latency by 42% in hardware and achieves a 30% speed performance improvement in software. Theoretically, a security proof of arbitrary order is provided for the proposed high-order A2B conversion. Experimental validations are performed to verify the second-order DPA resistance of second-order implementation. The Test Vector Leakage Assessment does not observe side-channel leakage for hardware and software implementations.

Garbling schemes allow to garble a circuit $C$ and an input $x$ such that $C(x)$ can be computed while hiding both $C$ and $x$. In the context of adaptive security, an adversary specifies the input to the circuit after seeing the garbled circuit, so that one can pre-process the garbling of $C$ and later only garble the input $x$ in the online phase. Since the online phase may be time-critical, it is an interesting question how much information needs to be transmitted in this phase and ideally, this should be close to $|x|$. Unfortunately, Applebaum, Ishai, Kushilevitz, and Waters (AIKW, CRYPTO 2013) show that for some circuits, specifically PRGs, achieving online complexity close to $|x|$ is impossible with simulation-based security, and Hubáček and Wichs (HW, ITCS 2015) show that online complexity of maliciously secure two-party computation needs to grow with the incompressibility entropy of the function. We thus seek to understand under which circumstances optimal online complexity is feasible despite these strong lower bounds. Our starting point is the observation that lower bounds (only) concern cryptographic circuits and that, when an embedded secret is not known to the adversary (distinguisher), then the lower bound techniques do not seem to apply. Our main contribution is distributional simulation-based security (DSIM), a framework for capturing weaker, yet meaningful simulation-based (adaptive) security which does not seem to suffer from impossibility results akin to AIKW. We show that DSIM can be used to prove security of a distributed symmetric encryption protocol built around garbling. We also establish a bootstrapping result from DSIM-security for $\text{NC}^0$ circuits to DSIM-security for arbitrary polynomial-size circuits while preserving their online complexity.

The issue of data and information security on the internet and social network has become more serious and pervasive in recent years. Cryptography is used to solve security problems. However, message encryption cannot merely meet the intended goals because access control over the encrypted messages is required in some applications. To achieve these requirements, attribute-based encryption (ABE) is used. This type of encryption provides both security and access structure for the network users simultaneously. Fuzzy Identity-Based Encryption (FIBE) is a special mode of ABE that provides a threshold access structure for the users. This threshold value is set by the authority for users, which is always fixed and cannot be changed. So, the sender (encryptor) will not play a role in determining the threshold value. The mentioned issue exists also in Key Policy Attribute Based Encryption (KP-ABE) schemes. In this paper, we present a FIBE scheme in addition to the authority, the sender also plays a role in determining the threshold value. Thus, the policy will be more flexible than previous FIBE schemes in that the threshold value is selected only by the authority. We can call the proposed scheme a dual-policy ABE. The proposed technique for flexibility of threshold value can be applied in most of the existing KP-ABE schemes. We use the (indistinguishable) selective security model for security proof. The hardness assumption that we use is the modified bilinear decision Diffie-Hellman problem.

In today's systems, privacy is often at odds with utility: users that reveal little information about themselves get restricted functionality, and service providers mistrust them. In practice, systems tip to either full anonymity (e.g. Monero), or full utility (e.g. Bitcoin). Well-known cryptographic primitives for bridging this gap exist: anonymous credentials (AC) let users disclose a subset of their credentials' attributes, revealing to service providers "just what they need"; group signatures (GS) allow users to authenticate anonymously, to be de-anonymized "just when deemed necessary". However, these primitives are hard to deploy.

Current AC and GS variants reach specific points in the privacy-utility tradeoff, which we point as counter-productive engineering-wise, as it requires full and error-prone re-engineering to adjust the tradeoff. Also, so far, GS and AC have been studied separately by theoretical research.

We take the first steps toward unifying and generalizing both domains, with the goal of bringing their benefits to practice, in a flexible way. We give a common model capturing their core properties, and use functional placeholders to subsume intermediate instantiations of the privacy-utility tradeoff under the same model. To prove its flexibility, we show how concrete variants of GS, AC (and others, like ring signatures) can be seen as special cases of our scheme – to which we refer as universal anonymous signatures (UAS). In practice, this means that instantiations following our construction can be configured to behave as variant X of a GS scheme, or as variant Y of an AC scheme, by tweaking a few functions.

The rising tide of data breaches targeting large data storage centres, and servers has raised serious privacy and security concerns. Homomorphic Encryption schemes offer an effective defence against such attacks, but their adoption is hindered by substantial computational and communication overhead, both on the server and client sides. This challenge led to the development of Hybrid Homomorphic Encryption (HHE) schemes to reduce the cost of client-side computation and communication. Despite the existence of a multitude of HHE schemes in the literature, their security analysis is still in its infancy, especially in the context of physical attacks like Differential Fault Analysis (DFA). This work aims to address this critical gap for HHE schemes defined over prime fields (Fp − HHE) by introducing, implementing and validating SASTA, the first DFA on Fp − HHE and the first nonce-respecting FA over any HHE scheme. In this pursuit, we introduce a new nonce-respecting fault model (all current fault attacks on HHE schemes require a nonce-reuse), which leads to a unique attack that completely exploits both the asymmetric and symmetric facets of HHE. We target Fp − HHE schemes as they offer support for integer or real arithmetic, enabling more versatile applications, like machine learning, and better performance. The fault model benefits from what we call the mirror-effect, which allows the attack to work both on the client and the server. Our analysis reveals a significant vulnerability: a single fault within the Keccak permutation, employed as an extendable output function, results in complete key recovery for the Pasta HHE scheme. Moreover, this vulnerability extends to other HHE schemes, including Rasta, Masta, and Hera, amplifying the scope and impact of SASTA. For experimental validation, we mount an actual fault attack using ChipWhisperer-Lite board on the Keccak permutation. Following this, we also discuss the conventional countermeasures to defend against SASTA. Overall, SASTA constitutes the first nonce-respecting FA of HHE that offers new insights into how server-side or client-side computations can be manipulated for Fp − HHE schemes to recover the entire key with just a single fault. This work reaffirms the orthogonality of convenience and attack vulnerability and should contribute to the landscape of future HHE schemes.

Fortanix is a dynamic start-up solving some of the world’s most demanding data protection challenges for companies and governments around the world. Our disruptive technology maintains data privacy across its entire lifecycle -- at rest, in motion, and in use across any enterprise IT infrastructure -- public cloud, on-premise, hybrid cloud, and SaaS.

Fortanix is looking for a Sr. Software Engineer, Cryptography with software development experience.

In this role, you will:

• Implement and maintain production-ready cryptography code in Rust and C/C++, including new algorithms and secure cryptography APIs
• Analyze state-of-the-art attacks and implement side-channel mitigations
• Participate in peer code review, educate
• Write, research
• Help deploy, monitor, and tune the performance of our software
• Analyze existing designs

Requirements
You have:

• Uncompromising integrity
• Outstanding attention to detail
• Critical thinking about complex technical problems
• Proactive and independent, while also being a team player
• Programming experience in Rust, C/C++
• A Master's or PhD in Cryptography or a related field, or equivalent training or work experience
• You currently reside in the EU and have a valid EU work permit

Closing date for applications:

Contact:
Francisco José Vial-Prado
(francisco.vialprado@fortanix.com)

More information: https://jobs.workable.com/view/3HZKGKSmAcrrj6Uetp5Wdd/senior-software-engineer%2C-cryptography-in-eindhoven-at-fortanix

We present ReSolveD, a new candidate post-quantum signature scheme under the regular syndrome decoding (RSD) assumption for random linear codes, which is a well-established variant of the well-known syndrome decoding (SD) assumption. Our signature scheme is obtained by designing a new zero-knowledge proof for proving knowledge of a solution to the RSD problem in the recent VOLE-in-the-head framework using a sketching scheme to verify that a vector has weight exactly one. We achieve a signature size of 3.99 KB with a signing time of 27.3 ms and a verification time of 23.1 ms on a single core of a standard desktop for a 128-bit security level. Compared to the state-of-the-art code-based signature schemes, our signature scheme achieves $1.5\times \sim 2\times$ improvement in terms of the common "signature size + public-key size" metric, while keeping the computational efficiency competitive.

X-Wing is a hybrid key-encapsulation mechanism based on X25519 and ML-KEM-768. It is designed to be the sensible choice for most applications. The concrete choice of X25519 and ML-KEM-768 allows X-Wing to achieve improved efficiency compared to using a generic combiner. In this paper, we introduce the X-Wing construction and provide a proof of security. We show (1) that X-Wing is a classically IND-CCA secure KEM if the strong Diffie-Hellman assumption holds in the X25519 nominal group, and (2) that X-Wing is a post-quantum IND-CCA secure KEM if ML-KEM-768 is itself an IND-CCA secure KEM and SHA3-256 is secure when used as a pseudorandom function. The first result is proved in the ROM, whereas the second one holds in the standard model. Loosely speaking, this means X-Wing is secure if either X25519 or ML-KEM-768 are secure.

A multidimensional scalar multiplication (d-mul) consists of computing $[a_1]P_1+\cdots+[a_d]P_d$, where $d$ is an integer ($d\geq 2)$, $\alpha_1, \cdots, \alpha_d$ are scalars of size $l\in \mathbb{N}^*$ bits, $P_1, P_2, \cdots, P_d$ are points on an elliptic curve $E$. This operation (d-mul) is widely used in cryptography, especially in elliptic curve cryptographic algorithms. In fact, it is utilized in the digital signature verification algorithm (ECDSA), proving and verification algorithms such as the Succinct Non interactive Argument of Knowledge (zkSNARK) protocol, and in isogeny based post-quantum cryptosystems. Several methods in the literature allow to compute the d-mul efficiently (e.g., the bucket method, the Karabina et al. method). This paper aims to present and compare the most recent and efficient methods in the literature for computing the d-mul operation in terms of with, complexity, memory consumption, and proprieties. We will also present our work on the progress of the optimisation of d-mul in two methods. The first method is useful if $2^d-1$ points of $E$ can be stored. It is based on a simple precomputation function. The second method works efficiently when $d$ is large and $2^d-1$ points of $E$ can not be stored. It performs the calculation on the fly without any precomputation. We show that our first method is $100(1-\frac{1}{d})\%$ more efficient, while our second exhibits a $50\%$ improvement in efficiency. These improvements will be substantiated by assessing the number of operations and practical implementation.

We use theta groups to study $2$-isogenies between Kummer lines, with a particular focus on the Montgomery model. This allows us to recover known formula, along with more efficient forms for translated isogenies, which require only $2S+2m_0$ for evaluation. We leverage these translated isogenies to build a hybrid ladder for scalar multiplication on Montgomery curves with rational $2$-torsion which cost $3M+6S+2m_0$ by bits, compared to $5M+4S+1m_0$ for the standard Montgomery ladder.

As the message recovery-based attack poses a serious threat to lattice-based schemes, we conducted a study on the side-channel secu- rity of parallel implementations of lattice-based key encapsulation mech- anisms. Initially, we developed a power model to describe the power leakage during message encoding. Utilizing this power model, we pro- pose a multi-ciphertext message recovery attack, which can retrieve the required messages for a chosen ciphertext attack through a suitable mes- sage recovery oracle. Building upon the successful message recovery, we further develop a key recovery method based on a ciphertext-choosing strategy that maximizes key recovery accuracy, as well as a lattice reduc- tion attack capable of solving the whole private key from the target LWE instance. To assess the effectiveness of the attack, we conducted experi- ments using Kyber768 implemented on a Xilinx FPGA board. The exper- imental results demonstrate that our attack could successfully recover the private key with 9600 power traces and a computational complexity of 100 bikz, which is a significant advantage over existing attacks. Notably, our attack remains effective despite countermeasures such as masking and shuffling being implemented. This study reveals that parallel im- plementations remain vulnerable to side-channel attacks, and highlights the necessity of additional analysis and countermeasures for lattice-based schemes implemented in parallel.

Secure Multi-Party Computation (MPC) constructions typically allow computation over a finite field or ring. While useful for many applications, certain real-world applications require the usage of decimal numbers. While it is possible to emulate floating-point operations in MPC, fixed-point computation has gained more traction in the practical space due to its simplicity and efficient realizations. Even so, current protocols for fixed-point MPC still require computing a secure truncation after each multiplication gate. In this paper, we show a new paradigm for realizing fixed-point MPC. Starting from an existing MPC protocol over arbitrary, large, finite fields or rings, we show how to realize MPC over a residue number system (RNS). This allows us to leverage certain mathematical structures to construct a secure algorithm for efficient approximate truncation by a static and public value. We then show how this can be used to realize highly efficient secure fixed-point computation. In contrast to previous approaches, our protocol does not require any multiplications of secret values in the underlying MPC scheme to realize truncation but instead relies on preprocessed pairs of correlated random values, which we show can be constructed very efficiently, when accepting a small amount of leakage and robustness in the strong, covert model. We proceed to implement our protocol, with SPDZ as the underlying MPC protocol, and achieve significantly faster fixed-point multiplication.

Class groups of imaginary quadratic fields (class groups for short) have seen a resurgence in cryptography as transparent groups of unknown order. They are a prime candidate for being a trustless alternative to RSA groups because class groups do not need a (distributed) trusted setup to sample a cryptographically secure group of unknown order. Class groups have recently found many applications in verifiable secret sharing, secure multiparty computation, transparent polynomial commitments, and perhaps most importantly, in time-based cryptography, i.e., verifiable delay functions, (homomorphic) time-lock puzzles, timed commitments, etc.

However, there are various roadblocks to making class groups widespread in practical cryptographic deployments. We initiate the rigorous study of hashing into class groups. Specifically, we want to sample a uniformly distributed group element in a class group such that nobody knows its discrete logarithm with respect to any public parameter. We point out several flawed algorithms in numerous publicly available class group libraries. We further illustrate the insecurity of these hash functions by showing concrete attacks against cryptographic protocols, i.e., verifiable delay functions, if they were deployed with one of those broken hash-to-class group functions. We propose two families of cryptographically secure hash functions into class groups. We implement these constructions and evaluate their performance. We release our implementation as an open-source library.

Recently, Qiu et al. proposed a quantum voting scheme based on the ring signature (International Journal of Theoretical Physics, 60: 1550–1555(2021)), in which the signer and verifier only need measure the received particles with Z-basis and perform some classical simple encryption/decryption operations on the classical message. Although their scheme is very efficient, it cannot resist against the eavesdropping attacks and forgery attack. In this paper, first, the eavesdropping attacks on Qiu et al.’s scheme are proposed. Second, we show the forgery attack on their scheme. According to the security analysis, it follows that, when desiring the quantum ring signature scheme, we should carefully analysis its security against eavesdropping attacks and forgery under chosen message attack.

Fully Homomorphic Encryption (FHE) is a prevalent cryptographic primitive that allows for computation on encrypted data. In various cryptographic protocols, this enables outsourcing computation to a third party while retaining the privacy of the inputs to the computation. However, these schemes make an honest-but-curious assumption about the adversary. Previous work has tried to remove this assumption by combining FHE with Verifiable Computation (VC). Recent work has increased the flexibility of this approach by introducing integrity checks for homomorphic computations over rings. However, efficient FHE for circuits of large multiplicative depth also requires non-ring computations called maintenance operations, i.e. modswitching and keyswitching, which cannot be efficiently verified by existing constructions. We propose the first efficiently verifiable FHE scheme that allows for arbitrary depth homomorphic circuits by utilizing the double-CRT representation in which FHE schemes are typically computed, and using lattice-based SNARKs to prove components of this computation separately, including the maintenance operations. Therefore, our construction can theoretically handle bootstrapping operations. We also present the first implementation of a verifiable computation on encrypted data for a computation that contains multiple ciphertext-ciphertext multiplications. Concretely, we verify the homomorphic computation of an approximate neural network containing three layers and more than 100 ciphertexts in less than 1 second while maintaining reasonable prover costs.

Verifiable secret sharing (VSS) protocols enable parties to share secrets while guaranteeing security (in particular, that all parties hold valid and consistent shares) even if the dealer or some of the participants are malicious. Most work on VSS focuses on the honest majority case, primarily since it enables one to guarantee output delivery (e.g., a corrupted recipient cannot prevent an honest dealer from sharing their value). Feldman's VSS is a well known and popular protocol for this task and relies on the discrete log hardness assumption. In this paper, we present a variant of Feldman's VSS for the dishonest majority setting and formally prove its security. Beyond the basic VSS protocol, we present a publicly-verifiable version, as well as show how to securely add participants to the sharing and how to refresh an existing sharing (all secure in the presence of a dishonest majority). We prove that our protocols are UC secure, for appropriately defined ideal functionalities.

At the Chair of Mobile Business & Multilateral Security, Department of Business Informatics and Information Management at Goethe University Frankfurt, the position for a Research Assistant (m/f/d, E 13 TV-G-U) is to be filled at the earliest possible date for a period of three years, with the option of extension, on a fixed-term basis. The position is also available on a part-time basis.

To strengthen our team, we are looking for committed, creative, and flexible scientific employees with in-depth expertise in the field of computer science, as well as an interest in current developments in business informatics. The environment of mobile systems or applications will provide you with valuable work experience in an interdisciplinary project involving travel and project responsibility, such as the BMBF project 'FIIPS@Home' (engl. ‘Early warning, information, and intrusion prevention system for the security of private home networks’).

We offer an interesting and varied range of tasks with the opportunity to contribute your own creative ideas. Goethe University Frankfurt is a family-friendly employer with flexible working time models, its own collective labour agreement and a free Hessen State public transport ticket.

If you are interested, please visit https://m-chair.de/career for full details. Application is open until January 30, 2024

Closing date for applications:

Contact: bewerbungen@m-chair.de

More information: https://m-chair.de/images/documents/career/20240103WissMA_eng.PDF

The Learning With Errors ($\mathsf{LWE}$) problem asks to find $\mathbf{s}$ from an input of the form $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s}+\mathbf{e}) \in (\mathbb{Z}/q\mathbb{Z})^{m \times n} \times (\mathbb{Z}/q\mathbb{Z})^{m}$, for a vector $\mathbf{e}$ that has small-magnitude entries. In this work, we do not focus on solving $\mathsf{LWE}$ but on the task of sampling instances. As these are extremely sparse in their range, it may seem plausible that the only way to proceed is to first create $\mathbf{s}$ and $\mathbf{e}$ and then set $\mathbf{b} = \mathbf{A}\mathbf{s}+\mathbf{e}$. In particular, such an instance sampler knows the solution. This raises the question whether it is possible to obliviously sample $(\mathbf{A}, \mathbf{A}\mathbf{s}+\mathbf{e})$, namely, without knowing the underlying $\mathbf{s}$. A variant of the assumption that oblivious $\mathsf{LWE}$ sampling is hard has been used in a series of works constructing Succinct Non-interactive Arguments of Knowledge (SNARKs) in the standard model. As the assumption is related to $\mathsf{LWE}$, these SNARKs have been conjectured to be secure in the presence of quantum adversaries.

Our main result is a quantum polynomial-time algorithm that samples well-distributed $\mathsf{LWE}$ instances while provably not knowing the solution, under the assumption that $\mathsf{LWE}$ is hard. Moreover, the approach works for a vast range of $\mathsf{LWE}$ parametrizations, including those used in the above-mentioned SNARKs.

We explore the issue of anonymously proving account ownership (anonymous PAO). Such proofs allow a prover to prove to a verifier that it owns a valid account at a server without being tracked by the server or the verifier, without requiring any changes at the server's end and without even revealing to it that any anonymous PAO is taking place. This concept is useful in sensitive applications like whistleblowing. The first introduction of anonymous PAOs was by Wang et al., who also introduced the secure channel injection (SCI) protocol to realize anonymous PAO in the context of email account ownership. In this paper, we propose YouChoose, an approach that improves upon Wang et al.'s SCI-based anonymous PAO. Unlike SCI, which demands carefully designed multi-party computation (MPC) protocols for efficiency, YouChoose works without MPC, simply relying on the verifier to selectively forward TLS records. It is faster, more efficient, and more adaptable compared to SCI. Further, the simplicity of the YouChoose approach readily enables anonymous PAO in different settings such as various ciphersuites of TLS, account types other than email, etc., while the SCI approach needs specifically designed MPC protocols for each use case. We also provide formal security definitions for a generalized anonymous PAO of which both YouChoose and SCI are concrete instantiations.

A functional commitment allows a user to commit to an input $\mathbf{x} \in \{0,1\}^\ell$ and later open up the commitment to a value $y = f(\mathbf{x})$ with respect to some function $f$. In this work, we focus on schemes that support fast verification. Specifically, after a preprocessing step that depends only on $f$, the verification time as well as the size of the commitment and opening should be sublinear in the input length $\ell$, We also consider the dual setting where the user commits to the function $f$ and later, opens up the commitment at an input $\mathbf{x}$.

In this work, we develop two (non-interactive) functional commitments that support fast verification. The first construction supports openings to constant-degree polynomials and has a shorter CRS for a broad range of settings compared to previous constructions. Our second construction is a dual functional commitment for arbitrary bounded-depth Boolean circuits. Both schemes are lattice-based and avoid non-black-box use of cryptographic primitives or lattice sampling algorithms. Security of both constructions rely on the $\ell$-succinct short integer solutions (SIS) assumption, a falsifiable $q$-type generalization of the SIS assumption (Preprint 2023).

In addition, we study the challenges of extending lattice-based functional commitments to extractable functional commitments, a notion that is equivalent to succinct non-interactive arguments (when considering openings to quadratic relations). We describe a general methodology that heuristically breaks the extractability of our construction and provides evidence for the implausibility of the knowledge $k$-$R$-$\mathsf{ISIS}$ assumption of Albrecht et al. (CRYPTO 2022) that was used in several constructions of lattice-based succinct arguments. If we additionally assume hardness of the standard inhomogeneous SIS assumption, we obtain a direct attack on a variant of the extractable linear functional commitment of Albrecht et al.