International Association
for Cryptologic Research

In this paper, we present a new diverse class of post-quantum group-based Digital Signature Schemes (DSS). The approach is significantly different from previous examples of group-based digital signatures and adopts the framework of group action-based cryptography: we show that each finite group defines a group action relative to the semidirect product of the group by its automorphism group, and give security bounds on the resulting signature scheme in terms of the group-theoretic computational problem known as the Semidirect Discrete Logarithm Problem (SDLP). Crucially, we make progress towards being able to efficiently compute the novel group action, and give an example of a parameterised family of groups for which the group action can be computed for any parameters, thereby negating the need for expensive offline computation or inclusion of redundancy required in other schemes of this type.

Of the many families of cryptographic schemes proposed to be post-quantum, a relatively unexplored set of examples comes from group-based cryptography. One of the more central schemes from this area is the so-called Semidirect Product Key Exchange (SDPKE), a generalisation of Diffie-Hellman Key Exchange that is plausibly post-quantum. In this report we survey the state of the literature relating to SDPKE, providing a high-level discussion of security, as well as a comprehensive overview of the proposed platforms and the main cryptanalytic ideas relevant to each.

In today’s interconnected world, data has become a valuable asset, leading to a growing interest in protecting it through techniques such as privacy-preserving computation. Two well-known approaches are multi-party computation and homomorphic encryption with use cases such as privacy-preserving machine learning evaluating or training neural networks. For multi-party computation, one of the fundamental arithmetic operations is the secure multiplication in the malicious security model and by extension the multiplication of matrices which is expensive to compute in the malicious model. Transferring the problem of secure matrix multiplication to the homomorphic domain enables savings in communication complexity, reducing the main bottleneck.

In this work, we implement and optimize the homomorphic generation of matrix triples. We provide an open-source implementation for the leveled BGV (Brakerski Gentry Vaikuntanathan) scheme supporting plaintext moduli of arbitrary size using state-of-the-art implementation techniques. We also provide a new, use-case specific approach to parameter generation for leveled BGV-like schemes heuristically optimizing for computation time and taking into account architecture-specific constraints. Finally, we provide an in-depth analysis of the homomorphic circuit enabling the re-use of key switching keys and eliminating constant multiplications, combining our results in an implementation to generate homomorphic matrix triples for arbitrary plaintext moduli.

Our implementation is publicly available and up to $2.1\times$ faster compared to previous work while also providing new time-memory trade-offs for different computing environments. Furthermore, we implement and evaluate additional, use-case specific optimization opportunities such as matrix slicing for the matrix triple generation.

This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions. The proposed tool, TXRANK, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System. Unlike traditional methods, TXRANK is designed to offer an unrestricted search space and does not rely on predefined rules or patterns, enabling it to detect a broader range of anomalies. We demonstrate the effectiveness of TXRANK through its use as an anomaly detection tool for Ethereum transactions. In our experiments, it effectively identifies abnormal transactions among a dataset of 68M transactions and has a batched throughput of 2284 trans- actions per second on average. Our results show that, TXRANK identifies abnormal transactions by ranking 49 out of 124 attacks among the top-3 most abnormal transactions interacting with their victim contracts. This work makes contributions to the field of blockchain transaction analysis by introducing a custom data encoding compatible with the transformer architecture, a domain-specific tokenization technique, and a tree encoding method specifically crafted for the Ethereum Virtual Machine (EVM) trace representation.

Public-key encryption with keyword search was first proposed by Boneh et al. (EUROCRYPT 2004), achieving the ability to search for ciphertext files. Nevertheless, this scheme is vulnerable to inside keyword guessing attacks (IKGA). Public-key authenticated encryption with keyword search (PAEKS), introduced by Huang et al. (Inf. Sci. 2017), on the other hand, is secure against IKGA. Nonetheless, it is susceptible to quantum computing attacks. Liu et al. and Cheng et al. addressed this problem by reducing to the lattice hardness (AsiaCCS 2022, ESORICS 2022). Furthermore, several scholars pointed out that the threat of secret key exposure delegates a severe and realistic concern, potentially leading to privacy disclosure (EUROCRYPT 2003, Compt. J. 2022). As a result, research focusing on mitigating key exposure and resisting quantum attacks for the PAEKS primitive is significant and far-reaching. In this work, we present the first instantiation of post-quantum PAEKS primitive that is forward-secure and does not require trusted authorities, mitigating the secret key exposure while ensuring quantum-safe properties. We extended the scheme of Liu et al. (AsiaCCS 2022), and proposed a novel post-quantum PAEKS construction, namely FS-PAEKS. To begin with, we introduce the binary tree structure to represent the time periods, along with a lattice basis extension algorithm, and SamplePre algorithm to obtain the post-quantum one-way secret key evolution, allowing users to update their secret keys periodically. Furthermore, our scheme is proven to be IND-CKA, IND-IKGA, and IND-Multi-CKA in the quantum setting. In addition, we also compare the security of our primitive in terms of computational complexity and communication overhead with other top-tier schemes and provide implementation details of the ciphertext generation and test algorithms. The proposed FS-PAEKS is more efficient than the FS-PEKS scheme (IEEE TDSC 2021). Lastly, we demonstrate three potential application scenarios of FS-PAEKS.

Authenticated Encryption (AE) achieves privacy and authenticity with a single scheme. It is possible to obtain an AE scheme gluing together an encryption scheme (privacy secure) and a Message Authentication Code (authenticity secure). This approach is called generic composition and its security has been studied by Namprempre et al. [NRS14]. They looked into all the possible gluings of an encryption scheme with a secure MAC to obtain a nonce-based AE-scheme. The encryption scheme is either IV-based (that is, with an additional random input, the initialization vector [IV]) or nonce-based (with an input to be used once, the nonce). Nampremepre et al. assessed the security/insecurity of all possible composition combinations except for 4 (N4, A10, A11 and A12). Berti et al. [BPP18a] showed that N4 is insecure and that the remaining modes (A10, A11, and A12) are either all secure or insecure. Here, we prove that these modes are all insecure with a counterexample.

The estimation of the computational complexity of hard problems is essential for determining secure parameters for cryptographic systems. To date, those estimations are often performed in an ad-hoc manner. This led to a scattered landscape of available estimation scripts, with multiple scripts for the same problem with varying outputs. Overall, this complicates the task of reaching consensus on the hardness of cryptographic problems. Furthermore, for designers it makes it difficult to gather precise information on the concrete difficulty of the underlying problems. Especially in the light of the still ongoing NIST PQC standardization effort and the upcoming call for post-quantum secure digital signature schemes there is a pressing need for a reliable point of access for concrete security estimates.

In this work we present the first open-source software library entirely dedicated to cryptographic hardness estimation, the $\texttt{CryptographicEstimators}$ library. In contrast to most previous estimators, this library follows a modern object-oriented software architecture, which provides a wide variety of features. Overall the design is optimized to ease extending existing estimators by new algorithms and makes it simple to integrate completely new estimators. In this work we further specify the algorithmic cost model underlying the estimators. In order to provide a starting point for the project, we gathered and integrated estimators for six different hardness assumptions, including the syndrome decoding problem, the multivariate quadratic problem, the code equivalence problem, the permuted kernel problem and different flavors thereof. In our effort of gathering those estimation scripts, we also normalized those estimates to fit into the cost model and to measure the same unit operations.

Wave is a provably EUF-CMA (existential unforgeability under adaptive chosen message attacks) digital signature scheme based on codes \cite{DST19a}. It is an hash-and-sign primitive and its security is built according to a GPV-like framework \cite{GPV08} under two assumptions related to coding theory: (i) the hardness of finding a word of prescribed Hamming weight and prescribed syndrome, and (ii) the pseudo-randomness of ternary generalized $(U|U+V)$ codes. Forgery attacks (i)---or message attacks---consist in solving the ternary decoding problem for large weight \cite{BCDL19}, while, to the best of our knowledge, key attacks (ii) will try to exhibit words that are characteristic of $(U|U+V)$ codes, which are called type-U or type-V codewords in the present paper. In the current state-of-the-art, the best known attacks both reduce to various flavours of Information Set Decoding (ISD) algorithms for different regime of parameters. In this paper we give estimates for the complexities of the best known ISD variants for those regimes. Maximizing the computational effort, thus the security, for both attacks lead to conflicting constraints on the parameters. We provide here a methodology to derive optimal trade-offs for selecting parameters for the Wave signature scheme achieving a given security. We apply this methodology to the current state-of-the-art and propose some effective parameters for Wave. For $\lambda=128$ bits of classical security, the signature is $737$ bytes long, scaling linearly with the security, and the public key size is $3.6$ Mbytes, scaling quadratically with the security.

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. SNARKs with desirable properties such as transparent setup are constructed in the random oracle model. However, using such SNARKs to construct PCD requires heuristically instantiating the oracle and using it in a non-black-box way. Chen, Chiesa and Spooner (EC'22) constructed SNARKs in the low-degree random oracle model, circumventing this issue, but instantiating their model in the real world appears difficult.

In this paper, we introduce a new model: the arithmetized random oracle model (AROM). We provide a plausible standard-model (software-only) instantiation of the AROM, and we construct PCD in the AROM, given only a standard-model collision-resistant hash function. Furthermore, our PCD construction is for arbitrary-depth compliance predicates. We obtain our PCD construction by showing how to construct SNARKs in the AROM for computations that query the oracle, given an accumulation scheme for oracle queries in the AROM. We then construct such an accumulation scheme for the AROM.

We give an efficient "lazy sampling" algorithm (an emulator) for the ARO up to some error. Our emulator enables us to prove the security of cryptographic constructs in the AROM and that zkSNARKs in the ROM also satisfy zero-knowledge in the AROM. The algorithm is non-trivial, and relies on results in algebraic query complexity and the combinatorial nullstellensatz.

VC schemes provide a mechanism for verifying the output of a remotely executed program. These are used to support computing paradigms wherein a computationally restricted client, the Verifier, wishes to delegate work to a more powerful but untrusted server, the Prover. The Verifier wishes to detect any incorrect results, be they accidental or malicious. The current state-of-the-art is only close-to-practical, usually because of a computationally demanding setup which must be amortised across repeat executions. We present a VC scheme for verifying the output of arithmetic circuits with a small one-time setup, KGen, independent of the size of the circuit being verified, and a insignificantly small constant program specific setup, ProbGen. To our knowledge our VC scheme is the first built from the hardness of integer factoring, a standard cryptographic assumption. Our scheme has the added novelty that the proofs are simply the raw output of the target computation, and the Prover is in effect blind to the fact they are taking part in a VC scheme at all. Compared to related work our scheme comes at the cost of a more expensive, but still efficient, verification step. Verification is always practical, and the Prover workload is unchanged from unverified outsourced computation. Although our scheme has worse asymptotic performance than the state-of-the-art it is particularly well suited for verifying one-shot programs and the output of large integer polynomial evaluation.

Consider two participants who wish to each reveal some secret information to each other, but both will only reveal their secret if there is a guarantee that the other will do so too. Conventionally, whoever sends their secret first makes themselves vulnerable to the possibility that the other party will cheat and won’t send their secret in reply. Fair Exchange (FE) protocols are a class of cryptographic construction which allow an exchange like this to occur without either party making themselves vulnerable. It is widely believed that a trusted third party arbitrator is required to intervene in the case of a dispute. We present a FE protocol that allows two parties to exchange secrets, safe in the knowledge that either both secrets will be exchanged, or neither will; without the involvement of a third party. This construction requires that the parties run online interactive processes, with reasonable timeliness requirements on the messages. In this work we provide a scheme for swapping arbitrarily sized secrets with security that reduces to the strength of an underlying symmetric authenticated encryption scheme.

Conflict-free Replicated Data Types (CRDTs) are a very popular class of distributed data structures that strike a compromise between strong and eventual consistency. Ensuring the protection of data stored within a CRDT, however, cannot be done trivially using standard encryption techniques, as secure CRDT protocols would require replica-side computation. This paper proposes an approach to lift general-purpose implementations of CRDTs to secure variants using secure multiparty computation (MPC). Each replica within the system is realized by a group of MPC parties that compute its functionality. Our results include: i) an extension of current formal models used for reasoning over the security of CRDT solutions to the MPC setting; ii) a MPC language and type system to enable the construction of secure versions of CRDTs and; iii) a proof of security that relates the security of CRDT constructions designed under said semantics to the underlying MPC library. We provide an open-source system implementation with an extensive evaluation, which compares different designs with their baseline throughput and latency.

Despite offering numerous advantages, public decentralized cryptocurrencies such as Bitcoin suffer from scalability issues such as high transaction latency and low throughput. The vast array of so-called Layer-2 solutions tackling the scalability problem focus on throughput, and consider latency as a secondary objective. However, in the context of retail payments, instant finality of transactions is arguably a more pressing concern, besides the overarching concern for privacy.

In this paper, we provide an overlay network that allows privacy-friendly low latency payments in a retail market. Our approach follows that of a recent work called Snappy, which achieved low latency but exposed identities of customers and their transaction histories. Our construction ensures this data is kept private, while providing merchants with protection against double-spending attacks. Although our system is still based upon customers registering with a collateral, crucially this collateral is reusable over time.

The technical novelty of our work comes from randomness-reusable threshold encryption (RRTE), a cryptographic primitive we designed specifically for the following features: our construction provably guarantees payments to merchants, preserves the secret identity of honest customers and prevents their transactions from being linked. We also present an implementation of our construction, showing its capacity for fast global payments in a retail setting with a delay of less than 1 second.

The original NTRU cryptosystem from 1998 can be considered the starting point of the great success story of lattice-based cryptography. Modern NTRU versions like NTRU-HPS and NTRU-HRSS are round-3 finalists in NIST's selection process, and also Crystals-Kyber and especially Falcon are heavily influenced by NTRU. Coppersmith and Shamir proposed to attack NTRU via lattice basis reduction, and variations of the Coppersmith-Shamir lattice have been successfully applied to solve official NTRU challenges by Security Innovations, Inc. up to dimension $n=173$. In our work, we provide the tools to attack modern NTRU versions, both by the design of a proper lattice basis, as well as by tuning the modern BKZ with lattice sieving algorithm from the G6K library to NTRU needs. Let $n$ be prime, $\Phi_n := (X^n-1)/(X-1)$, and let $\mathbb{Z}_q[X]/(\Phi_n)$ be the cyclotomic ring. As opposed to the common belief, we show that switching from the Coppersmith-Shamir lattice to a basis for the cyclotomic ring provides benefits. To this end, we slightly enhance the LWE with Hints framework by Dachman-Soled, Ducas, Gong, Rossi with the concept of projections against almost-parallel hints. Using our new lattice bases, we set the first cryptanalysis landmarks for NTRU-HPS with $n \in [101,171]$ and for NTRU-HRSS with $n \in [101,211]$. As a numerical example, we break our largest HPS-171 instance using the cyclotomic ring basis within $83$ core days, whereas the Coppersmith-Shamir basis requires $172$ core days. We also break one more official NTRU challenges by Security Innovation, Inc., originally worth 1000\$, in dimension $n=181$ in $20$ core years.

MQ-Sign is a variant of the UOV singature scheme proposed by Shim et al. It has been suggested as a candidate for the standardization of post-quantum cryptography in Republic of Korea (known as KpqC). However, recently Aulbach et al. proposed a practical key recovery attack against MQ-Sign-RS and MQ-Sign-SS with a simple secret key $\mathcal{S}$. In this paper, we propose another attack that is valid for the case of a general secret key $\mathcal{S}$.

The neural-differential distinguisher proposed by Gohr boosted the development of neural aided differential attack. As another significant cryptanalysis technique, linear attack has not been developing as rapidly in combination with deep learning technology as differential attack. In 2020, Hou et al. proposed the first neural-linear attack with one bit key recovery on 3, 4 and 5-round DES and restricted multiple bits recovery on 4 rounds, where the effective bits in one plain-ciphertext pair are spliced as one data sample. In this paper, we compare the neural-linear cryptanalysis with neural-differential cryptanalysis and propose a new data preprocessing algorithm depending on their similarities and differences. We call the new data structure distribution data. Basing on it, we mount our key recovery on round-reduced DES—first, we raise the accuracy of the neural-linear distinguisher by about 50%. Second, our distinguisher improves the effectiveness of one bit key recovery against 3, 4 and 5-round DES than the former one, and attack 6-round DES with success rate of 60.6% using 2048 plain-ciphertext pairs. Third, we propose a real multiple bit key recovery algorithm, leading neural-linear attack from theory to practice.

In this work we are interested in evaluating the possibility of extracting information from radio-enabled embedded-systems from a long distance. That is, our focus is capturing information from sources in the micrometer to tens of centimeters scale, such as intra- or inter- device busses, board-level routing traces etc. Moreover, we focus on distances in the range of millimeters to tens of centimeters from the (on-chip or on-board) embedded-system Tx Antenna to the signal source. Side-channels denotes presence of information in illegitimate channels. Side-channel analysis (SCA) attacks typically require statistical analysis and many leakage traces, focusing on micrometer level signals (sources) which emanate direct Near-Field information up to centimeters-level distances. In the same context (Near-Field and micrometer-level) simple power analysis (SPA) like attacks typically extract either direct raw information from one or few leakages or utilize statistical analysis on various samples from the same trace, similarly to horizontal attacks. Lately, radio-enabled systems were shown to emanate to a large distance (Far-Field), information from micrometer level sources, such as CPU processing, through the RF Tx Antenna: so far, SCA-like statistical analysis were shown. On the other hand, various reports exist on direct information eavesdropping/ sniffing or data exfiltration, emanated from centimeter to tens of centimeters scale sources, e.g., SATA, USB, Power-lines, Serial interface, Air-Gap systems, Screens and even optical fibers. All these elements are typically being used as a source and a direct Tx Antenna (huge, several to tens of centimeters) of the sensitive information. These antennas typically transmit information to short distances and the decay is very steep (proportional to $r^{-2}$-$r^{-3}$ depending on various factors and models). To the best of our knowledge, we report here for the first time an alarming security challenge: any signal in the embedded system, from serial ports, DMA-controlled memory-access, JTAG and SPI interfaces, on-board signals with galvanic connection to the Tx Antenna-chip and \emph{on-board signals without galvanic connection to the Tx Antenna-chip itself, all leak direct information up to tens of centimeters from source to the Tx Antenna}. This alarming situation induce signal-integrity implications within the embedded system, and significant implications relating to device-isolation and user-isolation, it may also affect standards and specifications for e.g., electromagnetic compatibility (EMC), on-board signal shielding, electromagnetic and RF interference (EMI, RFI), cross-talk, and generally design-for-manufacturing (DFM) guidelines for both intra-IC and PCB board. We demonstrate such direct readout of signals with commercial and low-cost equipment indicating how problematic the situation is. The existence of such leakage is demonstrated both over an ultra-low-cost platform such as the nRF52832(nRF) embedded-system and on a more advanced ESP32-c3-devkitc-02 board which is far more widespread in ISM radio applications and meets certification like FCC and CE (as compared to the nRF device). We have constructed an experiment to demonstrate leakage scenarios from (1) on- and (2) off-chip, on-board or (3) signals without galvanic connection to the RF front-end chip, showing the severity of the leakage, repetitively and systematic nature of the phenomena over various devices. We further demonstrate how sophisticated adversaries can build a code-injection Gadget which can carry sensitive-data and modulate it to be best extracted by the RF-channel. The main observation we push forward is that unless concrete interference and isolation standards appear with security metrics in mind, which are significantly different than ones needed for communication, it would be hard to prevent such leakages.

Distributed Oblivious Random Access Memory (DORAM) is a secure multiparty protocol that allows a group of participants holding a secret-shared array to read and write to secret-shared locations within the array. The efficiency of a DORAM protocol is measured by the amount of communication and computation required per read/write query into the array. DORAM protocols are a necessary ingredient for executing Secure Multiparty Computation (MPC) in the RAM model.

Although DORAM has been widely studied, all existing DORAM protocols have focused on the setting where the DORAM servers are semi-honest. Generic techniques for upgrading a semi-honest DORAM protocol to the malicious model typically increase the asymptotic communication complexity of the DORAM scheme.

In this work, we present a 3-party DORAM protocol which requires $O((\kappa + D)\log N)$ communication and computation per query, for a database of size $N$ with $D$-bit values, where $\kappa$ is the security parameter. Our hidden constants in a big-O nation are small. We show that our protocol is UC-secure in the presence of a malicious, static adversary. This matches the communication and computation complexity of the best semi-honest DORAM protocol, and is the first malicious DORAM protocol with this complexity.

Cryptographic hash functions are used inside many applications that critically rely on their resistance against cryptanalysis attacks and the correctness of their implementations. Nevertheless, vulnerabilities in cryptographic hash function implementations can remain unnoticed for more than a decade, as shown by the recent discovery of a buffer overflow in the implementation of SHA-3 in the eXtended Keccak Code Package (XKCP), impacting Python, PHP, and several other software projects. This paper explains how this buffer overflow vulnerability in XKCP was found. More generally, we explore the application of formal methods to the five finalist submission packages to the NIST SHA-3 competition, allowing us to (re-)discover vulnerabilities in the implementations of Keccak and BLAKE, and also discover a previously undisclosed vulnerability in the implementation of Grøstl. We also show how the same approach rediscovers a vulnerability affecting 11 out of the 12 implemented cryptographic hash functions in Apple's CoreCrypto library. Our approach consists of removing certain lines of code and then using KLEE as a tool to prove functional equivalence. We discuss the advantages and limitations of our approach and hope that our attempt to consolidate some earlier approaches can lead to new insights.

Due to the significant development of the intelligence industry worldwide, various initiatives have increasingly recognized the value of the Internet of Things. IoT systems, however, are often hindered by fundamental challenges, such as the need for a central server to manage them. Decentralizing these systems can be achieved through the use of blockchains. Recently, there has been an increase in the popularity of blockchain in various fields, such as banking, Internet of Things, and intelligence industry, and human societies have taken notice of it. One of the main problems is with the scalability of such systems as the network size grows.

This paper examines how blockchain can assist IoT systems to overcome this challenge. We introduce a lightweight-scalable blockchain as a solution for the sharding nodes. This solution assigns nodes to shards according to their history of activity. As part of this study, an IGDBFT algorithm is introduced within the proposed scheme for intra-shard consensus. A solution to storing blocks and cross-shard transactions has been developed using a global chain containing parent blocks in the cloud layer. Finally, we analyze the security and efficiency of our scheme and compare our sharding-based protocol with previous protocols.