IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
28 April 2023
Alexander Maximov, Mats Näslund
This paper analyses the security of the so-called Milenage construction, developed by ETSI SAGE, when it is based on a non-one-to-one pseudo-random function (PRF) rather than a one-to-one pseudo-random permutation (PRP). It is shown that Milenage based on an $n$-bit random function and producing $t$ $n$-bit outputs, is indistinguishable from a random $tn$-bit function up to $q = O(2^{n/2}/ t)$ queries. We also extend the existing security proof for PRP-based Milenage due to Gilbert by incorporating also the Milenage message authentication function in the proof.
Hyeokdong Kwon, Minjoo Sim, Gyeongju Song, Minwoo Lee, Hwajeong Seo
ChatGPT, which emerged at the end of 2022, has gained significant attention as a highly advanced conversational artificial intelligence service. Developed by OpenAI, ChatGPT is a natural language processing model. There are instances where individuals might want to attempt programming using ChatGPT. In this paper, we utilized the ChatGPT to implement a cryptographic algorithms. Despite numerous trial and error efforts, it was possible to implement cryptography through ChatGPT. This implies that even without extensive coding skill or programming knowledge, one can implement cryptography through ChatGPT if they understand the cryptographic structure. However, the ability to analyze the source code is essential, as it is necessary to identify incorrect parts within the implemented code.
Apostolos Tzinas, Dionysis Zindros
Proof-of-stake systems require stakers to lock up their funds in order to participate in consensus validation. This leads to capital inefficiency, as locked capital cannot be invested in Decentralized Finance (DeFi). Liquid staking rewards stakers with fungible tokens in return for staking their assets. These fungible tokens can in turn be reused in the DeFi economy. However, liquid staking introduces unexpected risks, as all delegated stake is now fungible. This exacerbates the already existing Principal–Agent problem faced during any delegation, in which the interests of the delegator (the Principal) are not aligned with the interests of the validator (the Agent). In this paper, we study the Principal–Agent problem in the context of liquid staking. We highlight the dilemma between the choice of proportional representation (having one's stake delegated to one's validator of choice) and fair punishment (being economically affected only when one's choice is misinformed). We put forth an attack illustrating that these two notions are fundamentally incompatible in an adversarial setting. We then describe the mechanism of exempt delegations, used by some staking systems today, and devise a precise formula for quantifying the correct choice of exempt delegation which allows balancing the two conflicting virtues in the rational model.
Vincent Hwang
This paper implements a vectorization–friendly polynomial multiplication for the NTRU Prime parameter sets ntrulpr761/sntrup761 with AVX2 based on the recently released work [Chen, Chung, Hwang, Liu, and Yang, Cryptology ePrint Archive, 2023/541]. Our big-by-big polynomial multiplication is 1.77 times faster than the state-of-the-art optimized implementation by [Bernstein, Brumley, Chen, and Tuveri, USENIX Security 2022] on Haswell with AVX2.
Marc Joye
This note introduces a public-key variant of TFHE. The output ciphertexts are of LWE type. Interestingly, the public key is shorter and the resulting ciphertexts are less noisy. The security of the scheme holds under the standard RLWE assumption. Several variations and extensions are also described.
Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat, LaKyah Tyner
We propose a secure multiparty signing protocol for the BBS+ signature scheme; in other words, an anonymous credential scheme with threshold issuance. We prove that due to the structure of the BBS+ signature, simply verifying the signature produced by an otherwise semi-honest protocol is sufficient to achieve composable security against a malicious adversary. Consequently, our protocol is extremely simple and efficient: it involves a single request from the client (who requires a signature) to the signing parties, two exchanges of messages among the signing parties, and finally a response to the client; in some deployment scenarios the concrete cost bottleneck may be the client's local verification of the signature that it receives. Furthermore, our protocol can be extended to support the strongest form of blind signing and to serve as a distributed evaluation protocol for the Dodis-Yampolskiy Oblivious VRF. We validate our efficiency claims by implementing and benchmarking our protocol.
George Teseleanu
In this paper we introduce a novel version of the Joye-Libert cryptosystem that allows users to decrypt without knowing the factorisation of the composite modulus. Then we use our construction as a building block for a threshold decryption protocol of the homomorphic Joye-Libert encryption scheme. Finally, we present several extensions of the threshold cryptosystem.
Beatrice Biasioli, Chiara Marcolla, Marco Calderini, Johannes Mono
Fully homomorphic encryption is a revolutionary technology that allows arbitrary computations on encrypted data, providing privacy and security. State-of-the-art schemes such as the Fan-Vercauteren (FV) scheme are based on the Learning with Errors assumption and its variants. Thus, each ciphertext has an error that increases with each homomorphic operation. To maintain correctness, the error must be kept below a certain threshold, which requires a balance between security and computational efficiency. Therefore, choosing optimal, secure, and efficient parameters can be a challenging task, even for experts in a particular scheme.
In this paper, we present two major contributions to improve the parameter selection in the FV scheme. We perform the first average case analysis to estimate the error growth. Our method significantly improves on previous work in terms of accuracy and tightness of bounds. For a circuit with a multiplicative depth of only 3, our bounds are within 1.2 bits of the experimentally observed values while being up to 19 bits tighter than previous analyses.
In addition, we take advantage of our theoretical advances and propose the first parameter generation tool for the FV scheme. Here we add support for arbitrary but use-case-specific circuits, as well as the ability to generate easy-to-use code snippets, making our theoretical work accessible to both researchers and practitioners.
In this paper, we present two major contributions to improve the parameter selection in the FV scheme. We perform the first average case analysis to estimate the error growth. Our method significantly improves on previous work in terms of accuracy and tightness of bounds. For a circuit with a multiplicative depth of only 3, our bounds are within 1.2 bits of the experimentally observed values while being up to 19 bits tighter than previous analyses.
In addition, we take advantage of our theoretical advances and propose the first parameter generation tool for the FV scheme. Here we add support for arbitrary but use-case-specific circuits, as well as the ability to generate easy-to-use code snippets, making our theoretical work accessible to both researchers and practitioners.
George Teseleanu
In this paper we formally introduce a novel mode of operation based on the cipher block chaining mode. The main idea of this mode is to use a stateful block cipher instead of a stateless one. Afterwards, we show how to implement our proposal and present a performance analysis of our mode. Next, we provide a concrete security analysis by computing a tight bound on the success of adversaries based on their resources. The results of our performance and security analyses are that this novel mode is more secure than the cipher block chaining mode for large files, but the encryption/decryption time doubles/triples. Therefore, our novel mode is suitable for encrypting large files, when higher security is required, but speed is not paramount. Note that the changes required to transform the software implementations of the cipher block chaining mode into this new mode are minimal, and therefore transitioning to this new mode is straightforward.
Sourav Das, Philippe Camacho, Zhuolun Xiang, Javier Nieto, Benedikt Bunz, Ling Ren
Threshold signatures protect the signing key by sharing it among a group of signers so that an adversary must corrupt a threshold number of signers to be able to forge signatures. Existing threshold signatures with succinct signatures and constant verification times do not work if signers have different weights. Such weighted settings are seeing increasing importance in decentralized systems, especially in the Proof-of-Stake blockchains. This paper presents a new paradigm for threshold signatures for pairing- and discrete logarithm-based cryptosystems. Our scheme has a compact verification key consisting of only 7 group elements, and a signature consisting of 8 group elements. Verifying the signature requires 1 exponentiation and 13 bilinear pairings. Our scheme supports arbitrary weight distributions among signers and arbitrary thresholds. It requires non-interactive preprocessing after a universal powers-of-tau setup. We prove the security of our scheme in the Algebraic Group Model and implement it using golang. Our evaluation shows that our scheme achieves a comparable signature size and verification time to a standard (unweighted) threshold signature. Compared to existing multisignature schemes, our scheme has a much smaller public verification key.
Songze Li, Duanyi Yao, Jin Liu
In a vertical federated learning (VFL) system consisting of a central server and many distributed clients, the training data are vertically partitioned such that different features are privately stored on different clients. The problem of split VFL is to train a model split between the server and the clients. This paper aims to address two major challenges in split VFL: 1) performance degradation due to straggling clients during training; and 2) data and model privacy leakage from clients’ uploaded data embeddings. We propose FedVS to simultaneously address these two challenges. The key idea of FedVS is to design secret sharing schemes for the local data and models, such that information-theoretical privacy against colluding clients and curious server is guaranteed, and the aggregation of all clients’ embeddings is reconstructed losslessly, via decrypting computation shares from the non- straggling clients. Extensive experiments on various types of VFL datasets (including tabular, CV, and multi-view) demonstrate the universal advantages of FedVS in straggler mitigation and privacy protection over baseline protocols.
Shenghui Su, Ping Luo
Modular arithmetic used for cryptography includes modular adding, modular subtracting, modular multiplying, modular inverting, modular exponentiating etc. In this paper, the authors well analyze the bit complexity of a bitwise modular operation and the time complexity of a non-bitwise modular operation. Besides discuss the clock cycles for one bytewise modular operation utilizing directives from the ATmel 8-bit AVR instruction set. Last, reveal that the ratio of derivate numbers of clock cycles for two modular operations under different modulus lengths is almost a constant.
Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, Siamak F. Shahandashti
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.
Christopher Battarbee, Delaram Kahrobaei, Siamak F. Shahandashti
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.
Johannes Mono, Tim Güneysu
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.
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.
Yu Gai, Liyi Zhou, Kaihua Qin, Dawn Song, Arthur Gervais
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.
Shiyuan Xu, Yibo Cao, Xue Chen, Siu-Ming Yiu, Yanmin Zhao
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.
Francesco Berti
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.
Andre Esser, Javier Verbel, Floyd Zweydinger, Emanuele Bellini
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.
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.
Nicolas Sendrier
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.