International Association
for Cryptologic Research

In 2022, a Korean domestic Post Quantum Cryptography contest called KpqC held, and the standard for Post Quantum Cryptography is set to be selected in 2024. In Round 1 of this competition, 16 algorithms have advanced and are competing. Algorithms submitted to KpqC introduce their performance, but direct performance comparison is difficult because all algorithms were measured in different environments. In this paper, we present the benchmark results of all KpqC algorithms in a single environment. To benchmark the algorithms, we removed the external library dependency of each algorithm. By removing dependencies, performance deviations due to external libraries can be eliminated, and source codes that can conveniently operate the KpqC algorithm can be provided to users who have difficulty setting up the environment.

Let $(A,t)$ be an instance of the search-LWE problem, where $A$ is a matrix and $t$ is a vector. This paper constructs an integer programming problem using $A$ and $t$, and shows that it is possible to derive a solution of the instance $(A,t)$ (perhaps with high probability) using its optimal solution or its tentative solution of small norm output by an integer programming solver. In other words, the LWE-search problem can be reduced to an integer programming problem. In the reduction, only basic linear algebra and finite field calculation are required. The computational complexity of the integer programming problem obtained is still unknown.

Subversion-resistant zk-SNARKs allow the provers to verify the Structured Reference String (SRS), via an SRS Verification (SV) algorithm and bypass the need for a Trusted Third Party (TTP). Pairing-based zk-SNARKs with \(updatable\) and \(universal\) SRS are an extension of subversion-resistant ones which additionally allow the verifiers to update the SRS, via an SRS Updating (SU) algorithm, and similarly bypass the need for a TTP. In this paper, we examine the setup of these zk-SNARKs by benchmarking the efficiency of the SV and SU algorithms within the \(\textsf{Arkworks}\) library. The benchmarking covers a range of updatable zk-SNARKs, including Sonic, Plonk, Marlin, Lunar, and Basilisk. Our analysis reveals that relying solely on the standard Algebraic Group Model (AGM) may not be sufficient in practice, and we may need a model with weaker assumptions. Specifically, we find that while Marlin is secure in the AGM, additional elements need to be added to its SRS to formally prove certain security properties in the updatable CRS model. We demonstrate that the SV algorithms become inefficient for mid-sized circuits with over 20,000 multiplication gates and 100 updates. To address this, we introduce Batched SV algorithms (BSV) that leverage standard batching techniques and offer significantly improved performance. As a tool, we propose an efficient verification approach that allows the parties to identify a malicious SRS updater with logarithmic verification in the number of updates. In the case of Basilisk, for a circuit with \(2^{20}\) multiplication gates, a \(1000\)-time updated SRS can be verified in less than 30 sec, a malicious updater can be identified in less than 4 min (improvable by pre-computation), and each update takes less than 6 min.

Research about the theoretical properties of side channel distinguishers revealed the rules by which to maximise the probability of first order success (``optimal distinguishers'') under different assumptions about the leakage model and noise distribution. Simultaneously, research into bounding first order success (as a function of the number of observations) has revealed universal bounds, which suggest that (even optimal) distinguishers are not able to reach theoretically possible success rates. Is this gap a proof artefact (aka the bounds are not tight) or does a distinguisher exist that is more trace efficient than the ``optimal'' one? We show that in the context of an unknown (and not linear) leakage model there is indeed a distinguisher that outperforms the ``optimal'' distinguisher in terms of trace efficiency: it is based on the Kruskal-Wallis test.

As a fundamental operation in fixed-point arithmetic, truncation can bring the product of two fixed-point integers back to the fixed-point representation. In large-scale applications like privacy-preserving machine learning, it is essential to have faithful truncation that accurately eliminates both big and small errors. In this work, we improve and extend the results of the oblivious transfer based faithful truncation protocols initialized by Cryptflow2 (Rathee et al., CCS 2020). Specifically, we propose a new notion of two-bit extraction that is tailored for faithful truncation and demonstrate how it can be used to construct an efficient faithful truncation protocol. Benefiting from our efficient construction for two-bit extraction, our faithful truncation protocol reduces the communication complexity of Cryptflow2 from growing linearly with the fixed-point precision to logarithmic complexity.

This efficiency improvement is due to the fact that we reuse the intermediate results of eliminating the big error to further eliminate the small error. Our reuse strategy is effective, as it shows that while eliminating the big error, it is possible to further eliminate the small error at a minimal cost, e.g., as low as communicating only an additional 160 bits in one round.

Despite active research on secret-sharing schemes for arbitrary access structures for more than 35 years, we do not understand their share size $-$ the best known upper bound for an arbitrary n-party access structure is $2^{O(n)}$ while the best known lower bound is $\Omega(n/\log(n))$. Consistent with our knowledge, the share size can be anywhere between these bounds. To better understand this question, one can study specific families of secret-sharing schemes. For example, linear secret-sharing schemes, in which the sharing and reconstruction are computed by linear mappings, have been studied in many papers, e.g., it is known that they require shares of size at least $2^{0.5n}$. Secret-sharing schemes in which the sharing and/or reconstruction are computed by low-degree polynomials have been recently studied by Paskin-Cherniavsky and Radune [ITC 2020] and by Beimel, Othman, and Peter [CRYPTO 2021]. It was shown that secret-sharing schemes with sharing and reconstruction computed by polynomials of degree 2 are more efficient than linear schemes (i.e., schemes in which the sharing and reconstruction are computed by polynomials of degree one).

Prior to our work, it was not known if using polynomials of higher degree can reduce the share size. We show that this is indeed the case, i.e., we construct secret-sharing schemes with reconstruction by degree-$d$ polynomials, where as the reconstruction degree $d$ increases, the share size for arbitrary access structures decreases. As a step in our construction, we construct conditional disclosure of secrets (CDS) protocols. For example, we construct 2-server CDS protocols for functions $f : [N ] \times [N ] \to \{0, 1\}$ with reconstruction computed by degree-d polynomials with message size $N^{O(\log \log d/ \log d)}$. Combining our results with a lower bound of Beimel et al. [CRYPTO 2021], we show that increasing the degree of the reconstruction function in CDS protocols provably reduces the message size. To construct our schemes, we define sparse matching vectors, show constructions of such vectors, and design CDS protocols and secret-sharing schemes with degree-$d$ reconstruction from sparse matching vectors.

In this paper, we analyze the security of authenticated encryption modes OTR (Minematsu, Eurocrypt 2014) and OPP (Granger, Jovanovic, Mennink, and Neves, Eurocrypt 2016) in a setting where an adversary is allowed to make encryption queries in quantum superposition. Starting with OTR -- or more technically, AES-OTR, a third-round CAESAR candidate -- we extend prior quantum attacks on the mode's unforgeability in the literature to provide the first attacks breaking confidentiality, i.e., IND-qCPA security, of AES-OTR in different settings depending on how the associated data is processed. On a technical level, one of our IND-qCPA attacks involves querying the quantum encryption oracle on a superposition of data with unequal length; to the best of our knowledge, such an attack has never been modelled before in the (post-)quantum cryptographic literature, and we hence believe our technique is of independent interest. Coming to OPP, we present the first key-recovery attack against the scheme which uses only a single quantum encryption query.

We present two zero knowledge protocols that allow one to assert solvency of a financial organization instantly with high throughput. The scheme is enabled by the recent breakthrough in lookup argument, i.e., after a pre-processing step, the prover cost can be independent of the lookup table size for subsequent queries. We extend the cq protocol [EFG22] and develop an aggregated non-membership proof for zero knowledge sets. Based on it, we design two instant proof-of-reserve protocols. One is non- intrusive, which works for crypto-currencies such as BTC where transaction details are public. It has O(n log(n)) prover complexity and O(1) proof size/verifier complexity, where n is the number of transactions assembled in a cycle. The other works for privacy preserving platforms where the blockchain has no knowledge of transaction details. By sacrificing non-intrusiveness, the second protocol achieves O(1) complexity for both the prover and verifier.

The number-theoretic literature has long studied the question of distributions of sequences of quadratic residue symbols modulo a prime number. In this paper, we present an efficient algorithm for generating primes containing chosen sequences of quadratic residue symbols and use it as the basis of a method extending the functionality of additively homomorphic cryptosystems.

We present an algorithm for encoding a chosen Boolean function into the public key and an efficient two-party protocol for evaluating this function on an encrypted sum. We demonstrate concrete parameters for secure function evaluation on encrypted sums up to eight bits at standard key sizes in the integer factorization setting. Although the approach is limited to applications involving small sums, it is a practical way to extend the functionality of existing secure protocols built on partially homomorphic encryption schemes.

The Internet of Things (IoT)-enabled ride sharing is one of the most transforming and innovative technologies in the transportation industry. It has myriads of advantages, but with increasing demands there are security concerns as well. Traditionally, cryptographic methods are used to address the security and privacy concerns in a ride sharing system. Unfortunately, due to the emergence of quantum algorithms, these cryptographic protocols may not remain secure. Hence, there is a necessity for privacy-preserving ride sharing protocols which can resist various attacks against quantum computers. In the domain of privacy preserving ride sharing, a threshold private set intersection (TPSI) can be adopted as a viable solution because it enables the users to determine the intersection of private data sets if the set intersection cardinality is greater than or equal to a threshold value. Although TPSI can help to alleviate privacy concerns, none of the existing TPSI is quantum secure. Furthermore, the existing TPSI faces the issue of long-term security. In contrast to classical and post quantum cryptography, quantum cryptography (QC) provides a more robust solution, where QC is based on the postulates of quantum physics (e.g., Heisenberg uncertainty principle, no cloning theorem, etc.) and it can handle the prevailing issues of quantum threat and long-term security. Herein, we propose the first QC based TPSI protocol which has a direct application in privacy preserving ride sharing. Due to the use of QC, our IoT-enabled ride sharing scheme remains quantum secure and achieves long-term security as well.

Over the last few years, Internet of Medical Things (IoMT) has completely transformed the healthcare industry. It is bringing out the most notable, and unprecedented impacts on human health, and has totally changed the way we look at the healthcare industry. The healthcare sector all around the globe are leapfrogging, and adopting the technology, helping in transforming drastically in a very short span of time. However, as more and more number of medical devices are being connected to IoMT, security issues like ensuring authenticity and integrity of the transmitted data are also on the rise. In view of the context, there is a need of an efficient cryptographic primitive that can address these issues in a viable manner. A signature scheme seems to be the natural choice to mitigate the security concerns. But, traditional signature schemes, both PKI-based and Identity-based have their own disadvantages which makes them unsuitable for IoMT networks. Thus, to address the security issues and problems like certificate management and key escrow, herein, we put forward the {\em first} multivariate based certificateless signature scheme, namely {\sf Mul-CLS}, which is built on top of the intractability of multivariate-quadratic (MQ) problem. The fact that multivariate public key cryptosystem (MPKC) provides fast, post-quantum safe, and efficient primitives, makes it a front runner candidate among the other post-quantum cryptography candidates. Our scheme {\sf Mul-CLS} provides existential unforgeability against chosen message and chosen identity Super Type I and Super Type II adversary if solving the MQ problem is NP-hard. In addition to that, our proposed {\sf Mul-CLS} presents itself as a robust and cost-friendly cryptographic building block for building IoMT networks.

Blockchains enable mutually distrustful parties to perform financial operations in a trustless, decentralized, publicly-verifiable environment. Blockchains typically offer little privacy, and thus motivated the construction of privacy mixers, a solution to make funds untraceable. Privacy mixers concern regulators due to their increasing use by bad actors to illegally conceal the origin of funds. Consequently, Tornado Cash, the largest privacy mixer to date is sanctioned by large portions of the Ethereum network.

In this work, we present Haze, a compliant privacy mixer. Haze guarantees users' privacy together with compliance, i.e., funds can be withdrawn as long as they were deposited from a non-banned address, without revealing any information on the matching deposit. We empirically evaluate our solution in a proof-of-concept system, demonstrating gas consumption for each deposit and withdrawal that is comparable to Tornado Cash for compliant users, and there is an optional feature for non-compliant funds to be released from the mixer to some predetermined entity. To the best of our knowledge, our solution is the first to guarantee compliance and privacy on the blockchain (on-chain) that is implemented via a smart contract. Finally, we introduce an alternative compliant privacy mixer protocol that supports de-anonymization of non-compliant users, at the cost of increased trust in the banned-addresses maintainer, which is realized in the two-server model.

Recently, as quantum computing technology develops, the importance of quantum resistant cryptography technology is increasing. AIMer is a quantum-resistant cryptographic algorithm that was selected as the first candidate in the electronic signature section of the KpqC Contest, and uses symmetric primitive AIM. In this paper, we propose a high-speed implementation technique of symmetric primitive AIM and evaluate the performance of the implementation. The proposed techniques are two methods, a Mer operation optimization technique and a linear layer operation simplification technique, and as a result of performance measurement, it achieved a performance improvement of up to 97.9% compared to the existing reference code. This paper is the first study to optimize the implementation of AIM.

This paper explores the optimization of quantum circuits for Argon2, a memory-hard function used for password hashing and other applications. With the rise of quantum computers, the security of classical cryptographic systems is at risk. It emphasizes the need to accurately measure the quantum security strength of cryptographic schemes using optimized quantum circuits. The proposed method focuses on two perspectives: qubit reduction (qubit optimization) and depth reduction (depth optimization). The qubit-optimized quantum circuit was designed to find a point where an appropriate inverse is possible and reuses the qubit through the inverse to minimize the number of qubits. The start point and end point of the inverse are set by finding a point where qubits can be reused with minimal computation. The depth-optimized quantum circuit reduces the depth by using the minimum number of qubits as necessary without performing an inverse operation. The trade-off between qubit and depth is confirmed by modifying the internal structure of the circuits and the quantum adders. Qubit optimization achieved up to a 12,229 qubit reduction, while depth optimization resulted in approximately 196,741 (approximately 69.02%) depth reduction. In conclusion, this research demonstrates the importance of implementing and analyzing quantum circuits from various optimization perspectives. The results contribute to the post-quantum strength analysis of Argon2 and provide valuable insights for future research on quantum circuit design, considering the appropriate trade-offs of quantum resources in response to advancements in quantum computing technology.

This paper focuses on the GPU implementation of the Pilsung block cipher used in the Red Star 3.0 operating system developed in North Korea. The Pilsung block cipher is designed based on AES. One notable feature of the Pilsung block cipher is that the table calculations required for encryption take longer than the encryption process itself. This paper emphasizes the parallel implementation of the Pilsung block cipher by leveraging the parallel processing capabilities of GPUs and evaluates the performance of the Pilsung block cipher. Techniques for optimization are proposed, including the use of Pinned memory to reduce data transfer time and work distribution between the CPU and GPU. Pinned memory helps optimize data transfer, and work distribution between the CPU and GPU needs to be considered for efficient parallel processing. Performance measurements were performed using the Nvidia GTX 3060 laptop for evaluation, comparing the results of applying Pinned memory usage and work distribution optimization. As a result, optimizing memory transfer costs was found to have a greater impact on performance improvement. When both techniques were applied together, approximately a 1.44 times performance improvement was observed.

Private payments in blockchain-based cryptocurrencies have been a topic of research, both academic and industrial, ever since the advent of Bitcoin. Stealth address payments were proposed as a solution to improve payment privacy for users and are, in fact, deployed in several major cryptocurrencies today. The mechanism lets users receive payments so that none of these payments are linkable to each other or the recipient. Currently known stealth address mechanisms either (1) are insecure in certain reasonable adversarial models, (2) are inefficient in practice or (3) are incompatible with many existing currencies. In this work, we formalize the underlying cryptographic abstraction of this mechanism, namely, stealth signatures with formal game-based definitions. We show a surprising application of our notions to passwordless authentication defined in the Fast IDentity Online (FIDO) standard. We then present SPIRIT, the first efficient post-quantum secure stealth signature construction based on the NIST standardized signature and key-encapsulation schemes, Dilithium and Kyber. The basic form of SPIRIT is only secure in a weak security model, but we provide an efficiency-preserving and generic transform, which boosts the security of SPIRIT to guarantee the strongest security notion defined in this work. Compared to state-of-the-art, there is an approximately 800x improvement in the signature size while keeping signing and verification as efficient as 0.2 ms. We extend SPIRIT with a fuzzy tracking functionality where recipients can outsource the tracking of incoming transactions to a tracking server, satisfying an anonymity notion similar to that of fuzzy message detection (FMD) recently introduced in [CCS 2021]. We also extend SPIRIT with a new fuzzy tracking framework called scalable fuzzy tracking that we introduce in this work. This new framework can be considered as a dual of FMD, in that it reduces the tracking server's computational workload to sublinear in the number of users, as opposed to linear in FMD. Experimental results show that, for millions of users, the server only needs 3.4 ms to filter each incoming message which is a significant improvement upon the state-of-the-art.

ChatGPT is recognized as a significant revolution in the field of artificial intelligence, but it raises serious concerns regarding user privacy, as the data submitted by users may contain sensitive information. Existing solutions for secure inference face significant challenges in supporting GPT-like models due to the enormous number of model parameters and complex activation functions.

In this paper, we develop CipherGPT, the $\mathit{first}$ framework for secure two-party GPT inference, building upon a series of innovative protocols. First, we propose a secure matrix multiplication that is customized for GPT inference, achieving upto 2.5$\times$ speedup and 11.2$\times$ bandwidth reduction over SOTA. We also propose a novel protocol for securely computing GELU, surpassing SOTA by 4.2$\times$ in runtime, 3.4$\times$ in communication and 10.9$\times$ in precision. Furthermore, we come up with the first protocol for top-k sampling.

We provide a full-fledged implementation and comprehensive benchmark for CipherGPT. In particular, we measure the runtime and communication for each individual operation, along with their corresponding proportions. We believe this can serve as a reference for future research in this area.

The Structured Encryption (StE) framework can be used to capture the encryption and querying of complex data structures on an honest-but-curious server. In this work, we introduce a new type of StE called indirectly addressed multimap encryption (IA-MME). We propose two IA-MME schemes: the the layered multimaps approach which extends and generalizes the existing "multimap chaining" approach, and a novel technique called the single multimap approach which has comparable efficiency and strictly better security. We demonstrate that our formalisms simplify and modularize StE solutions for real-world use cases in searchable encryption and SQL databases, and provide simulations demonstrating that our IA-MME constructions lead to tangible efficiency and security gains on realistic data.

We instantiate two random oracle (RO) transformations using Zhandry's extremely lossy function (ELF) technique (Crypto'16).

Firstly, using ELFs and indistinguishabililty obfuscation (iO), we instantiate a modified version of the Fujisaki-Okamoto (FO) transform which upgrades a public-key encryption scheme (PKE) from indistinguishability under chosen plaintext attacks (IND-CPA) to indistinguishability under chosen ciphertext attacks (IND-CCA). We side-step a prior uninstantiability result for FO by Brzuska, Farshim, and Mittelbach (TCC'15) by (1) hiding the randomness from the (potentially ill-designed) IND-CPA encryption scheme and (2) embedding an additional secret related to the hash-function into the secret-key of the IND-CCA-secure PKE, an idea brought forward by Murphy, O’Neill, Zaheri (Asiacrypt 2022) who also instantiate a modified FO variant also under ELFs and iO for the class of lossy PKE. Our transformation applies to all PKE which can be inverted given their randomness.

Secondly, we instantiate the hash-then-evaluate paradigm for pseudorandom functions (PRFs), $\mathsf{PRF}_\mathsf{new}(k,x):=\mathsf{wPRF}(k,\mathsf{RO}(x))$. Our construction replaces $\mathsf{RO}$ by $\mathsf{PRF}_\mathsf{old}(k_\mathsf{pub},\mathsf{elf}(x))$ with a key $k_\mathsf{pub}$, that, unusually, is known to the distinguishing adversary against $\mathsf{PRF}_\mathsf{new}$. We start by observing that several existing weak PRF candidates are plausibly also secure under such distributions of pseudorandom inputs, generated by $\mathsf{PRF}_\mathsf{old}$. Firstly, analogous cryptanalysis applies and/or an attack with such pseudorandom inputs would imply surprising results such as key agreement from the high-noise version of the Learning Parity with Noise (LPN) assumption. Our simple transformation applies to the entire family of PRF-style functions. Specifically, we obtain results for oblivious PRFs, which are a core building block for password-based authenticated key exchange (PAKE) and private set intersection (PSI) protocols, and we also obtain results for pseudorandom correlation functions (PCF), which are a key tool for silent oblivious transfer (OT) extension.

As interest in metadata-hiding communication grows in both research and practice, a need exists for stronger abuse reporting features on metadata-hiding platforms. While message franking has been deployed on major end-to-end encrypted platforms as a lightweight and effective abuse reporting feature, there is no comparable technique for metadata-hiding platforms. Existing efforts to support abuse reporting in this setting, such as asymmetric message franking or the Hecate scheme, require order of magnitude increases in client and server computation or fundamental changes to the architecture of messaging systems. As a result, while metadata-hiding communication inches closer to practice, critical content moderation concerns remain unaddressed.

This paper demonstrates that, for broad classes of metadata-hiding schemes, lightweight abuse reporting can be deployed with minimal changes to the overall architecture of the system. Our insight is that much of the structure needed to support abuse reporting already exists in these schemes. By taking a non-generic approach, we can reuse this structure to achieve abuse reporting with minimal overhead. In particular, we show how to modify schemes based on secret sharing user inputs to support a message franking-style protocol. Compared to prior work, our shared franking technique results in a $50\%$ reduction in the time to prepare a franked message and order of magnitude reductions in server-side message processing times, as well as the time to decrypt a message and verify a report.