International Association
for Cryptologic Research

Privacy-preserving machine learning (PPML) techniques have gained significant popularity in the past years. Those protocols have been widely adopted in many real-world security-sensitive machine learning scenarios, e.g., medical care and finance. In this work, we introduce $\mathsf{Aegis}$~-- a high-performance PPML platform built on top of a maliciously secure 3-PC framework over ring $\mathbb{Z}_{2^\ell}$. In particular, we propose a novel 2-round secure comparison (a.k.a., sign bit extraction) protocol in the preprocessing model. The communication of its semi-honest version is only 25% of the state-of-the-art (SOTA) constant-round semi-honest comparison protocol by Zhou et al.(S&P 2023); both communication and round complexity of its malicious version are approximately 50% of the SOTA (BLAZE) by Patra and Suresh (NDSS 2020), for $\ell=64$. Moreover, the communication of our maliciously secure inner product protocol is merely $3\ell$ bits, reducing 50% from the SOTA (Swift) by Koti et al. (USENIX 2021). Finally, the resulting ReLU and MaxPool PPML protocols outperform the SOTA by $4\times$ in the semi-honest setting and $10\times$ in the malicious setting, respectively.

Hiding countermeasures are the most widely utilized techniques for thwarting side-channel attacks, and their significance has been further emphasized with the advent of Post Quantum Cryptography (PQC) algorithms, owing to the extensive use of vector operations. Commonly, the Fisher-Yates algorithm is adopted in hiding countermeasures with permuted operation for its security and efficiency in implementation, yet the inherently sequential nature of the algorithm imposes limitations on hardware acceleration. In this work, we propose a novel method named Addition Round Rotation ARR, which can introduce a time-area trade-off with block-based permutation. Our findings indicate that this approach can achieve a permutation complexity level commensurate with or exceeding $2^{128}$ in a single clock cycle while maintaining substantial resistance against second-order analysis. To substantiate the security of our proposed method, we introduce a new validation technique --Identity Verification. This technique allows theoretical validation of the proposed algorithm's security and is consistent with the experimental results. Finally, we introduce an actual hardware design and provide the implementation results on Application-Specific Integrated Circuit (ASIC). The measured performance demonstrates that our proposal fully supports the practical applicability.

Recent advances in SNARK recursion and incrementally-verifiable computation are vast, but most of the efforts seem to be focused on a particular design goal - proving the result of a large computation known completely in advance.

There are other possible applications, requiring different design tradeoffs. Particularly interesting direction is a case with a swarm of collaborating provers, communicating over a peer-to-peer network - which requires to also optimize the amount of data exchanged between the participants of the swarm.

One notable such application is Ethereum's consensus, which requires to aggregate millions of signatures of individual validators.

In this technical note, we propose an informal notion of an end-to-end IVC scheme, which means that the amount of data that the prover needs exchange with the previous prover to continue the computation is small.

We explore the existing design space from this point of view, and suggest an approach to constructing such a scheme by combining the PlonK proof systemwith the recent Cyclefold construction.

A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on distributed randomness beacons suffer from at least one of the following drawbacks: (i) security only against a static/non-adaptive adversary, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as Proof-of-Work (PoW) or Verifiable Delay Functions (VDF). In this paper, we introduce $\mathsf{GRandLine}$, the first adaptively secure randomness beacon protocol that overcomes all these limitations while preserving simplicity and optimal resilience in the synchronous network setting. We achieve our result in two steps. First, we design a novel distributed key generation (DKG) protocol $\mathsf{GRand}$ that runs in $\mathcal{O}(\lambda n^2\log{n})$ bits of communication but, unlike most conventional DKG protocols, outputs both secret and public keys as group elements. Second, following termination of $\mathsf{GRand}$, parties can use their keys to derive a sequence of randomness beacon values, where each random value costs only a single asynchronous round and $\mathcal{O}(\lambda n^2)$ bits of communication. We implement $\mathsf{GRandLine}$ and evaluate it using a network of up to 64 parties running in geographically distributed AWS instances. Our evaluation shows that $\mathsf{GRandLine}$ can produce about 2 beacon outputs per second in a network of 64 parties. We compare our protocol to the state-of-the-art randomness beacon protocols in the same setting and observe that it vastly outperforms them.

This paper presents Reef, a system for generating publicly verifiable succinct non-interactive zero-knowledge proofs that a committed document matches or does not match a regular expression. We describe applications such as proving the strength of passwords, the provenance of email despite redactions, the validity of oblivious DNS queries, and the existence of mutations in DNA. Reef supports the Perl Compatible Regular Expression syntax, including wildcards, alternation, ranges, capture groups, Kleene star, negations, and lookarounds. Reef introduces a new type of automata Skipping Alternating Finite Automata (SAFA) that skips irrelevant parts of a document when producing proofs without undermining soundness, and instantiates SAFA with a lookup argument. Our experimental evaluation confirms that Reef can generate proofs for documents with 32M characters; the proofs are small and cheap to verify (under a second).

Falcon is one out of three post-quantum signature schemes which have been selected for standardization by NIST in July 2022. To the best of our knowledge, Falcon is the only selected algorithm that does not yet have a publicly reported hardware description that performs signing or key generation. The reason might be that the Falcon signature and key generation algorithms do not fit well in hardware due to the use of floating-point numbers and recursive functions. This publication describes the first hardware implementation for Falcon signing and key generation. To overcome the complexity of the Falcon algorithms, High-Level Synthesis (HLS) was preferred over a hardware description language like Verilog or VHDL. Our HLS code is based on the C reference implementation available at NIST. We describe the required modifications in order to be compliant with HLS, such as rewriting recursive functions into iterative versions. The hardware core at security level 5 requires 45,223 LUTs, 41,370 FFs, 182 DSPs, and 37 BRAMs to calculate one signature in 8.7 ms on a Zynq UltraScale+ FPGA. Security level 5 key generation takes 320.3 ms and requires 100,649 LUTs, 91,029 FFs, 1,215 DSPs, and 69 BRAMs.

Multi-signatures allow to combine individual signatures from different signers on the same message into a short aggregated signature. Newer schemes further allow to aggregate the individual public keys, such that the combined signature gets verified against a short aggregated key. This makes them a versatile alternative to threshold or distributed signatures: the aggregated key can serve as group key, and signatures under that key can only be computed with the help of all signers. What makes multi-signatures even more attractive is their simple key management, as users can re-use the same secret key in several and ad-hoc formed groups. In that context, it will be desirable to not sacrifice privacy as soon as keys get re-used and ensure that users are not linkable across groups. In fact, when multi-signatures with key aggregation were proposed, it was claimed that aggregated keys hide the signers' identities or even the fact that it is a combined key at all. In our work, we show that none of the existing multi-signature schemes provide these privacy guarantees when keys get re-used in multiple groups. This is due to the fact that all known schemes deploy deterministic key aggregation. To overcome this limitation, we propose a new variant of multi-signatures with probabilistic yet verifiable key aggregation. We formally define the desirable privacy and unforgeability properties in the presence of key re-use. This also requires to adapt the unforgeability model to the group setting, and ensure that key-reuse does not weaken the expected guarantees. We present a simple BLS-based scheme that securely realizes our strong privacy and security guarantees. We also formalize and investigate the privacy that is possible by deterministic schemes, and prove that existing schemes provide the advertised privacy features as long as one public key remains secret.

Encrypted search schemes have been proposed to address growing privacy concerns. However, several leakage-abuse attacks have highlighted the shortcomings of these schemes. The literature remains vague about the consequences of these attacks for real-world applications: are these attacks dangerous in practice? Is it safe to use these schemes? Do we even need countermeasures?

This paper introduces a novel mathematical model for attackers' knowledge using statistical estimators. Our model reveals that any attacker's knowledge is inherently noisy, which limits attack effectiveness. This inherent noise can be considered a security guarantee, a natural attack mitigation. Capitalizing on this insight, we develop a risk assessment protocol to guide real-world deployments. Our findings demonstrate that limiting the index size is an efficient leverage to bound attack accuracy. Finally, we employ similar statistical methods to enhance attack analysis methodology. Hence, our work offers a fresh perspective on SSE attacks and provides practitioners and researchers with novel methodological tools.

Digital signatures is a cryptographic protocol that can provide the added assurances of identity, status, proof of origin of an electronic document, and can acknowledge informed consent by the signer. Lattice based assumptions have seen a certain rush in recent years to fulfil the desire to expand the hardness assumption beyond factoring or discrete logarithm problem on which digital signatures can rely. In this article, we cover the recent progress made in digital signatures based on lattice assumptions. The article briefly discusses the working of each signature scheme, then investigates the progress made in recent years and compare them with different aspects of security and efficiency. Besides, it provides some future direction which can be helpful in future work in this area.

Electronic voting has occupied a large part of the cryptographic protocols literature. The recent reality of blockchains---in particular their need for online governance mechanisms---has put new parameters and requirements to the problem. We identify the key requirements of a blockchain governance mechanism, namely correctness (including eliminative double votes), voter anonymity, and traceability, and investigate mechanisms that can achieve them with minimal interaction and under assumptions that fit the blockchain setting.

First, we define a signature-like primitive, which we term sharp anonymous multisignatures (in short, #AMS) that tightly meets the needs of blockchain governance. In a nutshell, #AMSs allow any set of parties to generate a signature, e.g., on a proposal to be voted-upon, which if posted on the blockchain hides the identities of the signers/voters, but reveals their number. This can be seen as a (strict) generalization of threshold ring signatures (TRS).

We next turn to constructing such #AMSs and using them in various governance scenarios---e.g., single vs. multiple vote per voter. To this direction, we observe that although the definition of TRS does not imply #AMS, one can compile some of the existing TRS constructions into #AMS. This raises the question: What is the TRS structure that allows such a compilation? To answer the above, we devise templates for TRSs. Our templates encapsulate and abstract the structure that allows for the above compilation---most of the TRS schemes that can be compiled into #AMS are, in fact, instantiations of our template. This abstraction makes our template generic for instantiating TRSs and #AMSs from different cryptographic assumptions (e.g., DDH, LWE, etc). One of our templates is based on chameleon hashing and we explore a framework of lossy chameleon hashes to fully understand its nature.

Finally, we turn to how #AMS schemes can be used in our applications. We provide fast (in some cases non-interactive) #AMS-based blockchain governance mechanisms for a wide spectrum of assumptions on the honesty (semi-honest vs malicious) and availability of voters and proposers.

This note describes a total break of the sequentiality assumption (and broad generalizations thereof) underlying the candidate lattice-based proof of sequential work (PoSW) recently proposed by Lai and Malavolta at CRYPTO 2023. Specifically, for sequentiality parameter $T$ and SIS parameters $n,q,m = n \log q$, the attack computes a solution of norm $(m+1)^{\log_{k} T}$ (or norm $O(\sqrt{m})^{\log_{k} T}$ with high probability) in depth $\tilde{O}_{n,q}(k \log_{k} T)$, where the integer $k \leq T$ may be freely chosen. (The $\tilde{O}$ notation hides polylogarithmic factors in the variables appearing in its subscript.)

In particular, with the typical parameterization $\log q = \tilde{O}_{n,T}(1)$, for $k=2$ the attack finds a solution of quasipolynomial norm $O(\sqrt{m})^{\log T}$ in only *polylogarithmic* $\tilde{O}_{n,T}(1)$ depth; this strongly falsifies the assumption that finding such a solution requires depth *linear* in $T$. Alternatively, setting $k = T^{\varepsilon}$, the attack finds a solution of polynomial norm $O(\sqrt{m})^{1/\varepsilon}$ in depth $\tilde{O}_{n,T}(T^{\varepsilon})$, for any constant $\epsilon > 0$.

We stress that the attack breaks the *assumption* underlying the proposed PoSW, but not the *PoSW itself* as originally defined. However, the attack does break a *slight modification* of the original PoSW, which has an essentially identical security proof (under the same kind of falsified assumption). This suggests that whatever security the original PoSW may have is fragile, and further motivates the search for a PoSW based on a sound lattice-based assumption.

Let $\mathcal{X}$ and $\mathcal{Y}$ be two sets and suppose that a set of participants $P=\{P_1,P_2,\dots,P_n\}$ would like to calculate the keyed hash value of some message $m\in\mathcal{X}$ known to a single participant in $P$ called the data owner. Also, suppose that each participant $P_i$ knows a secret value $x_i\in\mathcal{X}$. In this paper, we will propose a protocol that enables the participants in this setup to calculate the value $y=H(m,x_1,x_2,\dots ,x_n)$ of a hash function $H:\mathcal{X}^{n+1}\rightarrow\mathcal{Y}$ such that: - The function $H$ is a one-way function. - Participants in $P\backslash\{P_i\}$ cannot obtain $x_i$. - Participants other than the data owner cannot obtain $m$. - The hash value $y=H(m,x_1,x_2,\dots ,x_n)$ remains the same regardless the order of the secret $x_i$ values.

Public-key cryptography is widely deployed for encrypting stored files. This paper uses microbenchmarks and purchase costs to predict the performance of various post-quantum KEMs in this application, in particular concluding that Classic McEliece is (1) the most efficient option and (2) easily affordable.

In 2019, Essaid et al. introduced a chaotic map-based encryption scheme for color images. Their approach employs three improved chaotic maps to dynamically generate the key bytes and matrix required by the cryptosystem. It should be noted that these parameters are dependent on the size of the source image. According to the authors, their method offers adequate security (i.e. $279$ bits) for transmitting color images over unsecured channels. However, we show in this paper that this is not the case. Specifically, we present two cryptanalytic attacks that undermine the security of Essaid et al.'s encryption scheme. In the case of the chosen plaintext attack, we require only two chosen plaintexts to completely break the scheme. The second attack is a a chosen ciphertext attack, which requires two chosen ciphertexts and compared to the first one has a rough complexity of $2^{24}$. The attacks are feasible due to the fact that the key bits and matrix generated by the algorithm remain unaltered for distinct plaintext images.

Counter-strategies are key components of coercion-resistant voting schemes, allowing voters to submit votes that represent their own intentions in an environment controlled by a coercer. By deploying a counter-strategy a voter can prevent the coercer from learning if the voter followed the coercer’s instructions or not. Two effective counter-strategies have been proposed in the literature, one based on fake credentials and another on revoting. While fake-credential schemes assume that voters hide cryptographic keys away from the coercer, revoting schemes assume that voters can revote after being coerced. In this work, we present a new counter-strategy technique that enables flexible vote updating, that is, a revoting approach that provides protection against coercion even if the adversary is able to coerce a voter at the very last minute of the voting phase. We demonstrate that our technique is effective by implementing it in Loki, an Internet-based coercion-resistant voting scheme that allows revoting. We prove that Loki satisfies a game-based definition of coercion-resistance that accounts for flexible vote updating. To the best of our knowledge, we provide the first technique that enables deniable coercion- resistant voting and that can evade last-minute voter coercion.

Recently the notion of blockwise error in a context of rank based cryptography has been introduced by Sont et al. at AsiaCrypt 2023 . This notion of error, very close to the notion sum-rank metric, permits, by decreasing the weight of the decoded error, to greatly improve parameters for the LRPC and RQC cryptographic schemes. A little before the multi-syndromes approach introduced for LRPC and RQC schemes had also allowed to considerably decrease parameters sizes for LRPC and RQC schemes, through in particular the introduction of Augmented Gabidulin codes.

In the present paper we show that the two previous approaches (blockwise errors and multi-syndromes) can be combined in a unique approach which leads to very efficient generalized RQC and LRPC schemes. In order to do so, we introduce a new problem, the Blockwise Rank Support Learning problem, which consists of guessing the support of the errors when several syndromes are given in input, with blockwise structured errors. The new schemes we introduce have very interesting features since for 128 bits security they permit to obtain generalized schemes for which the sum of public key and ciphertext is only 1.4 kB for the generalized RQC scheme and 1.7 kB for the generalized LRPC scheme. The new approach proposed in this paper permits to reach a 40 % gain in terms of parameters size when compared to previous results, obtaining even better results in terms of size than for the KYBER scheme whose total sum is 1.5 kB.

Besides the description of theses new schemes the paper provides new attacks for the l-RD problem introduced in the paper by Song et al. of AsiaCrypt 2023, in particular these new attacks permit to cryptanalyze all blockwise LRPC parameters they proposed (with an improvement of more than 40bits in the case of structural attacks). We also describe combinatorial attacks and algebraic attacks, for the new Blockwise Rank Support Learning problem we introduce.

In 2023, Mfungo et al. introduce an image encryption scheme that employs the Kronecker xor product, the Hill cipher and a chaotic map. Their proposal uses the chaotic map to dynamically generate two out of the three secret keys employed by their scheme. Note that both keys are dependent on the size of the original image, while the Hill key is static. Despite the authors' assertion that their proposal offers sufficient security ($149$ bits) for transmitting color images over unsecured channels, we found that this is not accurate. To support our claim, we present a chosen plaintext attack that requires $2$ oracle queries and has a worse case complexity of $\mathcal O(2^{32})$. Note that in this case Mfungo et al.'s scheme has a complexity of $\mathcal O(2^{33})$, and thus our attack is two times faster than an encryption. The reason why this attack is viable is that the two keys remain unchanged for different plaintext images of the same size, while the Hill key remains unaltered for all images.

Transport Layer Security (TLS) is the backbone security protocol of the Internet. As this fundamental protocol is at risk from future quantum attackers, many proposals have been made to protect TLS against this threat by implementing post-quantum cryptography (PQC). The widespread interest in post-quantum TLS has given rise to a large number of solutions over the last decade. These proposals differ in many aspects, including the security properties they seek to protect, the efficiency and trustworthiness of their post-quantum building blocks, and the application scenarios they consider, to name a few.

Based on an extensive literature review, we classify existing solutions according to their general approaches, analyze their individual contributions, and present the results of our extensive performance experiments. Based on these insights, we identify the most reasonable candidates for post-quantum TLS, which research problems in this area have already been solved, and which are still open. Overall, our work provides a well-founded reference point for researching post-quantum TLS and preparing TLS in practice for the quantum age.

In recent years, symmetric primitives that focus on arithmetic metrics over large finite fields, characterized as arithmetization-oriented (\texttt{AO}) ciphers, are widely used in advanced protocols such as secure multi-party computations (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK). To ensure good performance in protocols, these \texttt{AO} ciphers are commonly designed with a small number of multiplications over finite fields and low multiplicative depths. This feature makes \texttt{AO} ciphers vulnerable to algebraic attacks, especially integral attacks. While a far-developed analysis for integral attacks on traditional block ciphers defined over $\mathbb{F}_2$ exists, there is still a lack of research on this kind of attacks over large finite fields. Previous integral attacks over large finite fields are primarily higher-order differential attacks, which construct distinguishers by simply utilizing algebraic degrees without fully exploiting other algebraic properties of finite fields.

In this paper, we propose a new concept called \textit{integral multiset}, which provides a clear characterization of the integral property of multiset over the finite field $\mathbb{F}_{p^n}$. Based on multiplicative subgroups of finite fields, we present a new class of integral multisets that exhibits completely different integral property compared to the previously studied multisets based on vector subspaces over the finite field $\mathbb{F}_2$. In addition, we also present a method for merging existing integral multisets to create a new one with better integral property. Furthermore, combining with monomial detection techniques, we propose a framework for searching for integral distinguishers based on integral multisets.

We apply our new framework to some competitive \texttt{AO} ciphers, including \textsf{MiMC} and \textsf{Chaghri}. For all these ciphers, we successfully find integral distinguishers with lower time and data complexity. Especially for \textsf{MiMC}, the complexity of some distinguishers we find is only a half or a quarter of the previous best one. Due to the specific algebraic structure, all of our results could not be obtained by higher-order differential attacks. Furthermore, our framework perfectly adapts to various monomial detection techniques like general monomial prediction proposed by Cui et al. at ASIACRYPT 2022 and coefficient grouping invented by Liu et al. at EUROCRYPT 2023. We believe that our work will provide new insight into integral attacks over large finite fields.

Modern computing systems predominantly operate on the binary number system that accepts only ‘0’ or ‘1’ as logical values leading to computational homogeneity. But this helps in creating leakage patterns that can be exploited by adversaries to carry out hardware and software-level attacks. Recent research has shown that ternary systems, operating on three logical values (‘0′, ‘1', and ‘z') can surpass binary systems in terms of performance and security. In this paper, we first propose a novel approach that assigns logical values based on the direction of current flow within a conducting element, rather than relying on the voltage scale. Furthermore, we also present the mathematical models for each ternary gate.