International Association
for Cryptologic Research

The selection of a Lightweight Cryptography (LWC) algorithm is crucial for resource limited applications. The National Institute of Standards and Technology (NIST) leads this process, which involves a thorough evaluation of the algorithms’ cryptanalytic strength. Furthermore, careful consideration is given to factors such as algorithm latency, code size, and hardware implementation area. These factors are critical in determining the overall performance of cryptographic solutions at edge devices. Introducing CrISA-X, a Cryptography Instruction Set Architecture extensions designed to improve cryptographic latency on extendable processors. CrISA-X, classified as Generic-Atomic, Block-Specific and Procedure-Specific, leverages RISC processor hardware and a base ISA to effectively execute LWC algorithms. Our study aims to evaluate the execution efficiency of new single-cycle instruction extensions and tightly coupled multicycle instructions on extendable modular RISC processors. CrISA-X provides enhanced speed of various algorithms simultaneously while optimizing ISA adaptability, a feat yet to be accomplished. The extension, diverse for several computation levels, is first specifically tailored for individual algorithms and sets of LWC algorithms, depending on performance, frequency, and area trade-offs. By diligently applying the Min-Max optimization technique, we have configured these extensions to achieve a delicate balance between performance, area code size, etc. Our study presents empirical evidence of the performance enhancement achieved on a real synthesis modular RISC processor. We offer a framework for creating optimized processor hardware and ISA extensions. The CrISA-X framework generally outperforms ISA extensions by delivering significant performance boosts between 3x to 17x while experiencing a relative area cost increase of +12% and +47% in LUTs, in respect to the instruction set category. Notably, as one important example, the utilization of the ASCON algorithm yields a 10x performance boost in contrast to the base ISA instruction implementation

In this paper, we build a framework for constructing Constrained Pseudorandom Functions (CPRFs) with inner-product constraint predicates, using ideas from subtractive secret sharing and related-key-attack security.

Our framework can be instantiated using a random oracle or any suitable Related-Key-Attack (RKA) secure pseudorandom function. We provide three instantiations of our framework:

1. an adaptively-secure construction in the random oracle model; 2. a selectively-secure construction under the DDH assumption; and 3. a selectively-secure construction under the assumption that one-way functions exist.

All three instantiations are constraint-hiding and support inner-product predicates, leading to the first constructions of such expressive CPRFs under each corresponding assumption. Moreover, while the OWF-based construction is primarily of theoretical interest, the random oracle and DDH-based constructions are concretely efficient, which we show via an implementation.

Zero-knowledge proof (ZKP) is a cryptographic primitive that enable a prover to convince a verifier that a statement is true without revealing any other information beyond the correctness of the statement itself. Due to its powerful capabilities, its most practical type, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK), has been widely deployed in various privacy-preserving applications such as cryptocurrencies and verifiable computation. Although state-of-the-art zkSNARKs are highly efficient for the verifier, the computational overhead for the prover is still orders of magnitude too high to warrant use in many applications. This overhead is due to several time-consuming operations, including large-scale matrix-vector multiplication (MUL), number-theoretic transform (NTT), and especially the multi-scalar multiplication (MSM) with the highest proportion. Thus, further efficiency improvements are needed.

In this paper we focus on comprehensive optimization of running time and storage space needed by the MSM algorithm on GPUs. Specifically, we propose a new modular and adaptive parameter configuration technique—elastic MSM to enable us to change the scale of MSM according to our own wishes by performing a corresponding amount of preprocessing. This technique enable us to fully unleash the potential of various efficient parallel MSM algorithms. From another perspective, our technique could also be regarded as a preprocessing technique over the well-known Pippenger algorithm, which is modular and could be used to accelerate almost all the most advanced parallel Pippenger algorithms on GPUs. Meanwhile, our technique provides an adaptive trade-off between the running time and the extra storage space needed by parallel Pippenger algorithms on GPUs. We implemented and tested elastic MSM over two prevailing parallel Pippenger algorithms on GPUs. Given a range of practical parameters, across various preprocessing space limitations (across various MSM scales), our construction achieves up to about 28× and 45× (25× and 40×) speedup versus two state-of-the-art preprocessing parallel Pippenger algorithms on GPUs, respectively.

The polynomial attacks on SIDH by Castryck, Decru, Maino, Martindale and Robert have shown that, while the general isogeny problem is still considered unfeasible to break, it is possible to efficiently compute a secret isogeny when given its degree and image on enough torsion points. A natural response from many researchers has been to propose SIDH variants where one or both of these possible extra pieces of information is masked in order to obtain schemes for which a polynomial attack is not currently known. Example of such schemes are M-SIDH, MD-SIDH and FESTA. However, by themselves, theses SIDH variants are vulnerable to the same adaptive attacks where the adversary sends public keys whose associated isogeny is either unknown or inexistent. For the original SIDH scheme, one possible defense against these attacks is to use zero-knowledge proofs that a secret isogeny has been honestly computed. However, such proofs do not currently exist for most SIDH variants. In this paper, we present new zero-knowledge proofs for isogenies whose degree or torsion points have been masked. The security of these proofs mainly relies on the hardness of DSSP.

Proxy re-encryption (PRE) allows a proxy to transform a ciphertext intended for Alice (delegator) to another ciphertext intended for Bob (delegatee) without revealing the underlying message. Recently, a new variant of PRE, namely fine-grained PRE (FPRE), was proposed in [Zhou et al., Asiacrypt 2023]. Generally, FPRE is designed for a function family F: each re-encryption key rk_{A→B}^f is associated with a function f ∈ F, and with rk_{A→B}^f, a proxy can transform Alice's ciphertext encrypting m to Bob's ciphertext encrypting f(m). However, their scheme only supports single-hop re-encryption and achieves only CPA security.

In this paper, we formalize multi-hop FPRE (mFPRE) that supports multi-hop re-encryptions in the fine-grained setting, and propose two mFPRE schemes achieving CPA security and stronger HRA security (security against honest re-encryption attacks), respectively. -- For multi-hop FPRE, we formally define its syntax and formalize a set of security notions including CPA security, HRA security, undirectionality and ciphertext unlinkablity. HRA security is stronger and more reasonable than CPA security, and ciphertext unlinkablity blurs the proxy relations among a chain of multi-hop re-encryptions, hence providing better privacy. We establish the relations between these security notions. -- Our mFPRE schemes support fine-grained re-encryptions for bounded linear functions and have security based on the learning-with-errors (LWE) assumption in the standard model. In particular, one of our schemes is HRA secure and enjoys all the aforementioned desirable securities. To achieve CPA security and HRA security for mFPRE, we extend the framework of [Jafargholi et al., Crypto 2017] and the technique of the [Fuchsbauer et al., PKC 2019].

Asymmetric Searchable Encryption (ASE) is a promising cryptographic mechanism that enables a semi-trusted cloud server to perform keyword searches over encrypted data for users. To be useful, an ASE scheme must support expressive search queries, which are expressed as conjunction, disjunction, or any Boolean formulas. In this paper, we propose a fast and expressive ASE scheme that is adaptively secure, called FEASE. It requires only 3 pairing operations for searching any conjunctive set of keywords independent of the set size and has linear complexity for encryption and trapdoor algorithms in the number of keywords.

FEASE is based on a new fast Anonymous Key-Policy Attribute-Based Encryption (A-KP-ABE) scheme as our first proposal, which is of independent interest. To address optional protection against keyword guessing attacks, we extend FEASE into the first expressive Public-Key Authenticated Encryption with Keyword Search (PAEKS) scheme.

We provide implementations and evaluate the performance of all three schemes, while also comparing them with the state of the art. We observe that FEASE outperforms all existing expressive ASE constructions and that our A-KP-ABE scheme offers anonymity with efficiency comparable to the currently fastest yet non-anonymous KP-ABE schemes FAME (ACM CCS 2017) and FABEO (ACM CCS 2022).

All anonymous identity-based encryption (IBE) schemes that are group homomorphic (to the best of our knowledge) require knowledge of the identity to compute the homomorphic operation. This paper is motivated by this open problem, namely to construct an anonymous group-homomorphic IBE scheme that does not sacrifice anonymity to perform homomorphic operations. Note that even when strong assumptions such as indistinguishability obfuscation (iO) are permitted, no schemes are known. We succeed in solving this open problem by assuming iO and the hardness of the DBDH problem over rings (specifically, $Z_{N^2}$ for RSA modulus $N$). We then use the existence of such a scheme to construct an IBE scheme with re-randomizable anonymous encryption keys, which we prove to be IND-ID-RCCA secure. Finally, we use our results to construct identity-based anonymous aggregation protocols.

Higher order differential properties constitute a very insightful tool at the hands of a cryptanalyst allowing for probing a cryptographic primitive from an algebraic perspective. In FSE 2017, Saha et al. reported SymSum (referred to as SymSum_Vec in this paper), a new distinguisher based on higher order vectorial Boolean derivatives of SHA-3, constituting one of the best distinguishers on the latest cryptographic hash standard. SymSum_Vec exploits the difference in the algebraic degree of highest degree monomials in the algebraic normal form of SHA-3 with regards to their dependence on round constants. Later in Africacrypt 2020, Suryawanshi et al. extended SymSum_Vec using linearization techniques and in SSS 2023 also applied it to NIST-LWC finalist Xoodyak. However, a major limitation of SymSum_Vec is the maximum attainable derivative (MAD) which is less than half of the widely studied ZeroSum distinguisher. This is attributed to SymSum_Vec being dependent on m−fold vectorial derivatives while ZeroSum relies on m−fold simple derivatives. In this work we overcome this limitation of SymSum_Vec by developing and validating the theory of computing SymSum_Vec with simple derivatives. This gives us a close to 100% improvement in the MAD that can be computed. The new distinguisher reported in this work can also be combined with one/two-round linearization to penetrate more rounds. Moreover, we identify an issue with the two-round linearization claim made by Suryawanshi et al. which renders it invalid and also furnish an algebraic fix at the cost of some additional constraints.

Combining all results we report SymSum_Sim , a new variant of the SymSum_Vec distinguisher based on m−fold simple derivatives that outperforms ZeroSum by a factor of $2^{257}$, $2^{129}$ for 10-round SHA-3-384 and 9-round SHA-3-512 respectively while enjoying the same MAD as ZeroSum. For every other SHA-3 variant, SymSum_Sim maintains an advantage of factor 2. Combined with one/two-round linearization, SymSum_Sim improves upon all existing ZeroSum and SymSum_Vec distinguishers on both SHA-3 and Xoodyak. As regards Keccak-p, the internal permutation of SHA-3, we report the best 15-round distinguisher with a complexity of $2^{256}$ and the first better than birthday-bound 16-round distinguisher with a complexity of $2^{512}$ (improving upon the 15/16-round results by Guo et al. in Asiacrypt 2016). We also devise the best full-round distinguisher on the Xoodoo internal permutation of Xoodyak with a practically verifiable complexity of $2^{32}$ and furnish the first third-party distinguishers on the Belarushian hash function Bash. All distinguishers furnished in this work have been verified through implementations whenever practically viable. Overall, with the MAD barrier broken, SymSum_Sim emerges as a better distinguisher than ZeroSum on all fronts and adds to the state-of-the-art of cryptanalytic tools investigating non-randomness of crypto primitives.

This technical note presents limits on the security (as a function of the number of plaintext bytes encrypted and the number of forgery attempts made by an adversary) for the main Authenticated Encryption schemes available in TLS 1.2 and the draft of TLS 1.3. These limits are derived from security proofs for the considered schemes available in the literature. Our intention is to provide considered technical input to on-going discussions in the TLS Working Group of the IETF concerning, amongst other things, the necessity of adding a key update feature to the TLS 1.3 specification.

Zero-Knowledge Proofs (ZKPs), a cryptographic tool known for decades, have gained significant attention in recent years due to advancements that have made them practically applicable in real-world scenarios. ZKPs can provide unique attributes, such as succinctness, non-interactivity, and the ability to prove knowledge without revealing the information itself, making them an attractive solution for a range of applications.

This paper aims to critically analyze the applicability of ZKPs in various scenarios. We categorize ZKPs into distinct types: SNARKs (Succinct Non-Interactive Arguments of Knowledge), Commit-then-Prove ZKPs, MPC-in-the-Head, and Sigma Protocols, each offering different trade-offs and benefits. We introduce a flowchart methodology to assist in determining the most suitable ZKP system, given a set of technical application requirements. Next, we conduct an in-depth investigation of three major use cases: Outsourcing Computation, Digital Self-Sovereign Identity, and ZKPs in networking. Additionally, we provide a high-level overview of other applications of ZKPs, exploring their broader implications and opportunities. This paper aims to demystify the decision-making process involved in choosing the right ZKP system, providing clarity on when and how these cryptographic tools can be effectively utilized in various domains — and when they are better to be avoided.

Side-channel analysis based on machine learning, especially neural networks, has gained significant attention in recent years. However, many existing methods still suffer from certain limitations. Despite the inherent capability of neural networks to extract features, there remains a risk of extracting irrelevant information. The heavy reliance on profiled traces makes it challenging to adapt to remote attack scenarios with limited profiled traces. Besides, attack traces also contain critical information that can be used in the training process to assist model learning. In this paper, we propose a side-channel analysis approach based on contrastive learning named CL-SCA to address these issues. We also leverage a stochastic data augmentation technique to assist model to effectively filter out irrelevant information from the profiled traces. Through experiments of different datasets from different platforms, we demonstrate that CL-SCA significantly outperforms various conventional machine learning side-channel analysis techniques. Moreover, by incorporating attack traces into the training process using our approach, known as CL-SCA+, it becomes possible to achieve even greater enhancements. This extension can further improve the effectiveness of key recovery, which is fully verified through experiments on different datasets.

Event date: 26 October 2024
Submission deadline: 31 March 2024

The Cybersecurity (CYS) group at the Faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS) invites applications for full-time doctoral candidates in Computer Security and Applied Cryptography. Successful candidates will tackle exciting and challenging research problems in the area of private computing, privacy-enhancing technologies, secure multiparty computation and generally applied cryptography. Examples include developing attacks against existing cryptosystems by exploiting their information leakage and building new secure and practical schemes. Successful candidates will have the opportunity to work closely with world-class researchers at TU Delft and our research collaborators in Europe and the US.

Requirements:

MSc (or equivalent) degree in Computer Science, Mathematics or a closely related field by the time of the appointment.

Strong ability in at least one programming language: e.g. Python, C/C++

Experience in (at least one of): Cryptography, Privacy, Algorithmic Design

A strong foundation of Mathematics

Some research experience is a plus

Excellent oral and written skills in English

Closing date for applications:

Contact: Lilika Markatou (e.a.markatou@tudelft.nl).

More information: https://www.tudelft.nl/over-tu-delft/werken-bij-tu-delft/vacatures/details?jobId=15653

Requirements: PhD in Computer Science, Information Security, Cryptography, or related fields Strong Analysis and Synthesis Skills Strong Security Analytic Skills Strong Algorithmic Knowledge Information Security Knowledge and Digital Identity Protocols Knowledge of Distributed Ledger and Blockchains Proficiency in one of the major programming languages, such as Python, Node.js, Java, Golang, and Solidity. Knowledge of formal specification and verification would be considered an asset. Keywords: Data Sharing, Zero Knowledge Proof (ZkP), Trust, Formal Modeling and Specification, Smart Contract, Blockchain, DLT Application process: Please send the following documents (in a single PDF file): CV Motivation Lettre List of Publications and Patents Other scientific/technological contributions (if any),

Closing date for applications:

Contact: Prof. Nazim Agoulmine: nazim.agoulmine(at)univ-evry.fr Prof. Djamel Khadraoui: djamel.khadraoui(at)list.lu Dr. Adnan Imeri: adnan.imeri(at)list.lu

More information: https://drive.google.com/file/d/1asWQBNyUKgMPiM-ZU92-kKRPymSY-ru7/view?usp=sharing

We are hiring a research engineer / applied scientist to work out of our Hoboken NJ office. In this position, you will be part of a team developing and implementing analytics and machine learning algorithms using privacy-protected computation. The team includes well-known researchers and is a major contributor to the open-source OpenFHE software library.

The candidate is expected to have a strong research background in implementing complex mathematical operations into efficient processing pipelines. C++ software engineering skills are required, and Python experience is desirable. Experience with privacy-enhancing technologies, such as Fully Homomorphic Encryption (FHE) and Secure Multiparty Computation (SMC), is preferred. Familiarity with modern AI/ML development techniques and frameworks and runtime optimization is preferred.

The candidate is expected to work in the hybrid mode (at least halftime in the Hoboken, NJ office). Initially, the work can be done remotely. More information is available at https://dualitytech.com/careers/research-engineer/.

Closing date for applications:

Contact: Yuriy Polyakov (ypolyakov@dualitytech.com)

More information: https://dualitytech.com/careers/research-engineer/

Differential privacy is a fundamental concept for protecting individual privacy in databases while enabling data analysis. Conceptually, it is assumed that the adversary has no direct access to the database, and therefore, encryption is not necessary. However, with the emergence of cloud computing and the «on-cloud» storage of vast databases potentially contributed by multiple parties, it is becoming increasingly necessary to consider the possibility of the adversary having (at least partial) access to sensitive databases. A consequence is that, to protect the on-line database, it is now necessary to employ encryption. At PoPETs'19, it was the first time that the notion of differential privacy was considered for encrypted databases, but only for a limited type of query, namely histograms. Subsequently, a new type of query, summation, was considered at CODASPY'22. These works achieve statistical differential privacy, by still assuming that the adversary has no access to the encrypted database.

In this paper, we argue that it is essential to assume that the adversary may eventually access the encrypted data, rendering statistical differential privacy inadequate. Therefore, the appropriate privacy notion for encrypted databases that we use is computational differential privacy, which was introduced by Beimel et al. at CRYPTO '08. In our work, we focus on the case of functional encryption, which is an extensively studied primitive permitting some authorized computation over encrypted data. Technically, we show that any randomized functional encryption scheme that satisfies simulation-based security and differential privacy of the output can achieve computational differential privacy for multiple queries to one database. Our work also extends the summation query to a much broader range of queries, specifically linear queries, by utilizing inner-product functional encryption. Hence, we provide an instantiation for inner-product functionalities by proving its simulation soundness and present a concrete randomized inner-product functional encryption with computational differential privacy against multiple queries. In term of efficiency, our protocol is almost as practical as the underlying inner product functional encryption scheme. As evidence, we provide a full benchmark, based on our concrete implementation for databases with up to 1 000 000 entries. Our work can be considered as a step towards achieving privacy-preserving encrypted databases for a wide range of query types and considering the involvement of multiple database owners.

ZK-SNARKs are advanced cryptographic protocols used in private verifiable computation: modern SNARKs allow to encode the invariants of an arithmetic circuit over some large prime field in an appropriate NP language, from which a zero-knowlege short non-interactive argument of knowledge is built. Due to the high cost of proof generation, ZK-SNARKs for large constraint systems are inpractical.

ZK-SNARKs are used in privacy-oriented blockchains such as Filecoin, ZCash and Monero, to verify Merkle tree opening proofs, which in turn requires computing a fixed-input-length (FIL) cryptographic compression function. As classical, bit-oriented hash functions like SHA-2 require huge constraint systems, Arithmetization-Oriented (AO) compression functions have emerged to fill the gap.

Usually, AO compression functions are obtained by applying the Sponge hashing mode on a fixed-key permutation: while this avoids the cost of dynamic key scheduling, AO schedulers are often cheap to compute, making the exploration of AO compression functions based directly on blockciphers a topic of practical interest.

In this work, we first adapt notions related to classical hash functions and their security notions to the AO syntax, and inspired by the classical PGV modes, we propose AO PGV-LC and AO PGV-ELC, two blockcipher-based FIL compression modes with parametrizable input and output sizes. In the ideal cipher model, we prove the collision and preimage resistance of both our modes, and give bounds for collision and opening resistance over Merkle trees of arbitrary arity.

We then experimentally compare the AO PGV-LC mode over the Hades-MiMC blockcipher with its popular Sponge instantiation, Poseidon. The resulting construction, called Poseidon-DM, is $2$-$5\times$ faster than Poseidon in native computations, and $15$-$35\%$ faster in generating Merkle tree proofs over the Groth16 SNARK framework, depending on the tree arity. In particular, proof generation for an $8$-ary tree over Poseidon-DM is $2.5\times$ faster than for a binary tree with the same capacity over Poseidon. Finally, in an effort to further exploit the benefits of wide trees, we propose a new strategy to obtain a compact R1CS constraint system for Merkle trees with arbitrary arity.

The rapid digitization of aviation communication and its dependent critical operations demand secure protocols that address domain-specific security requirements within the unique functional constraints of the aviation industry. These secure protocols must provide sufficient security against current and possible future attackers, given the inherent nature of the aviation community, that is highly complex and averse to frequent upgrades as well as its high safety and cost considerations. In this work we propose a pair of quantum-secure hybrid key exchange protocols (PQAG-KEM and PQAG-SIG) to secure communication between aircrafts in-flight and ground stations. PQAG-KEM leverages post-quantum and classical Key Encapsulation Mechanisms (KEMs) to ensure the hybrid security of the protocol against classical as well as future quantum adversaries. PQAG-SIG, alternatively, uses quantum-safe digital signatures to achieve authentication security. We provide an implementation of both PQAG-KEM and PQAG-SIG, and compare favourably with current state-of- the-art secure avionic protocols. Finally, we provide a formal analysis of our new PQAG protocols in a strong hybrid key exchange framework.

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.