International Association
for Cryptologic Research

In this paper we present the first formally verified implementations of Kyber and, to the best of our knowledge, the first such implementations of any post-quantum cryptosystem. We give a (readable) formal specification of Kyber in the EasyCrypt proof assistant, which is syntactically very close to the pseudocode description of the scheme as given in the most recent version of the NIST submission. We present high-assurance open-source implementations of Kyber written in the Jasmin language, along with machine-checked proofs that they are functionally correct with respect to the EasyCrypt specification. We describe a number of improvements to the EasyCrypt and Jasmin frameworks that were needed for this implementation and verification effort, and we present detailed benchmarks of our implementations, showing that our code achieves performance close to existing hand-optimized implementations in C and assembly.

Private Stream Aggregation (PSA) schemes are efficient protocols for distributed data analytics. In a PSA scheme, a set of data producers can encrypt data for a central party so that it learns the sum of all (encrypted) values, but nothing about each individual value. Due to this ability to efficiently enable central data analytics without leaking individual user data, PSA schemes are often used for IoT data analytics scenarios where privacy is important, such as smart metering. However, all known PSA schemes require a trusted party for key generation, which is undesirable from a privacy standpoint. Further, even though the main benefit of PSA schemes over alternative technologies such as Functional Encryption is that they are efficient enough to run on IoT devices, there exists no evaluation of the efficiency of existing PSA schemes on realistic IoT devices.

In this paper, we address both these issues. We first evaluate the efficiency of the state of the art PSA schemes on realistic IoT devices. We then propose, implement and evaluate a DIstributed setup PSA scheme for Use in Constrained Environments (DIPSAUCE). DIPSAUCE is the first PSA scheme that does not rely on a trusted party. Our security and efficiency evaluation shows that it is indeed possible to construct an efficient PSA scheme without a trusted central party. Surprisingly, our results also show that, a side effect, our method for distributing the setup procedure also makes the encryption procedure more efficient than the state of the art PSA schemes which rely on trusted parties.

Deniable Authentication is a highly desirable property for secure messaging protocols: it allows a sender Alice to authentically transmit messages to a designated receiver Bob in such a way that only Bob gets convinced that Alice indeed sent these messages. In particular, it guarantees that even if Bob tries to convince a (non-designated) party Judy that Alice sent some message, and even if Bob gives Judy his own secret key, Judy will not be convinced: as far as Judy knows, Bob could be making it all up!

In this paper we study Deniable Authentication in the setting where Judy can additionally obtain Alice's secret key. Informally, we want that knowledge of Alice's secret key does not help Judy in learning whether Alice sent any messages, even if Bob does not have Alice's secret key and even if Bob cooperates with Judy by giving her his own secret key. This stronger flavor of Deniable Authentication was not considered before and is particularly relevant for Off-The-Record Group Messaging as it gives users stronger deniability guarantees. Our main contribution is a scalable ``MDRS-PKE'' (Multi-Designated Receiver Signed Public Key Encryption) scheme---a technical formalization of Deniable Authentication that is particularly useful for secure messaging for its confidentiality guarantees---that provides this stronger deniability guarantee. At its core lie new MDVS (Multi-Designated Verifier Signature) and PKEBC (Public Key Encryption for Broadcast) scheme constructions: our MDVS is not only secure with respect to the new deniability notions, but it is also the first to be tightly secure under standard assumptions; our PKEBC---which is also of independent interest---is the first with ciphertext sizes and encryption and decryption times that grow only linearly in the number of receivers. This is a significant improvement upon the construction given by Maurer et al. (EUROCRYPT '22), where ciphertext sizes and encryption and decryption times are quadratic in the number of receivers.

The development of Artificial Intelligence (AI) based systems to automatically generate hardware systems has gained an impulse that aims to accelerate the hardware design cycle with no human intervention. Recently, the striking AI-based system ChatGPT from OpenAI has achieved a momentous headline and has gone viral within a short span of time since its launch. This chatbot has the capability to interactively communicate with the designers through a prompt to generate software and hardware code, write logic designs, and synthesize designs for implementation on Field Programmable Gate Array (FPGA) or Application Specific Integrated Circuits (ASIC). However, an unvetted ChatGPT prompt by a designer with an aim to generate hardware code may lead to security vulnerabilities in the generated code. In this work, we systematically investigate the necessary strategies to be adopted by a designer to enable ChatGPT to recommend secure hardware code generation. To perform this analysis, we prompt ChatGPT to generate code scenarios listed in Common Vulnerability Enumerations (CWEs) under the hardware design (CWE-1194) view from MITRE. We first demonstrate how a ChatGPT generates insecure code given the diversity of prompts. Finally, we propose techniques to be adopted by a designer to generate secure hardware code. In total, we create secure hardware code for $10$ noteworthy CWEs under hardware design view listed on MITRE site.

To build an efficient security system in the post-quantum era, it is possible to find the minimum security parameters for defending a fault-tolerant quantum computer by estimating the quantum resources required for an quantum attack. In a fault-tolerant quantum computer, errors must reach an acceptable level through error detection and error correction, which additionally uses quantum resources. As the depth of the quantum circuit increases, the computation time per qubit increases, and errors in quantum computers increases. Therefore, in terms of errors in quantum circuits, it is appropriate to reduce the depth by increasing the number of qubits. This paper proposes an low-depth quantum circuit implementations of SHA3 for fault-tolerant quantum computers to reduce errors. The proposed SHA3 quantum circuit is implemented in the direction of reducing the quantum circuit depth through a trade-off between the number of qubits, quantum gate, and quantum depth in each function. Compared to the-state-of-art works, proposed method decreased T-depth and Full-depth by 30.3\% and 80.05\%, respectively. We expect that this work will contribute to the establishment of minimum security parameters for SHA3 in the quantum era.

A $b$-error-correcting $m$-server Private Information Retrieval (PIR) protocol enables a client to privately retrieve a data item of a database from $m$ servers even in the presence of $b$ malicious servers. List-decodable PIR is a generalization of error-correcting PIR to achieve a smaller number of servers at the cost of giving up unique decoding. Previous constructions of error-correcting and list-decodable PIR have exponential computational complexity in $m$ or cannot achieve sub-polynomial communication complexity $n^{o(1)}$, where $n$ is the database size. Recently, Zhang, Wang and Wang (ASIACCS 2022) presented a non-explicit construction of error-correcting PIR with $n^{o(1)}$ communication and polynomial computational overhead in $m$. However, their protocol requires the number of servers to be larger than the minimum one $m=2b+1$ and they left it as an open problem to reduce it. As for list-decodable PIR, there is no construction with $n^{o(1)}$ communication.

In this paper, we propose new generic constructions of error-correcting and list-decodable PIR from any one-round regular PIR. Our constructions increase computational complexity only by a polynomial factor in $m$ while the previous generic constructions incur $\binom{m}{b}$ multiplicative overheads. Instantiated with the best-known protocols, our construction provides for the first time an explicit error-correcting PIR protocol with $n^{o(1)}$ communication, which reduces the number of servers of the protocol by Zhang, Wang and Wang (ASIACCS 2022). For sufficiently large $b$, we also show the existence of $b$-error-correcting PIR with $n^{o(1)}$ communication achieving the minimum number of servers, by allowing for two rounds of interaction. Furthermore, we show an extension to list-decodable PIR and obtain for the first time a protocol with $n^{o(1)}$ communication. Other instantiations improve the communication complexity of the state-of-the-art $t$-private protocols in which $t$ servers may collude. Along the way, we formalize the notion of \textit{locally surjective map families}, which generalize perfect hash families and may be of independent interest.

Deep learning-based profiling side-channel analysis is widely adopted in academia and industry thanks to the ability to reveal secrets protected with countermeasures. To leverage its capability, the adversary needs to have access to a clone of an attack device to obtain the profiling measurements. Moreover, the adversary needs to know secret information to label these measurements. Non-profiling attacks avoid those constraints by not relying on secret information to label data but rather by trying all key guesses and taking the most successful one. Deep learning approaches also form the basis of several non-profiling attacks. Unfortunately, such approaches suffer from high computational complexity and low generality when applied in practice.

This paper proposes a novel non-profiling deep learning-based side-channel analysis technique. Our approach relies on the fact that there is (commonly) a bijective relationship between known information, such as plaintext and ciphertext, and secret information. We use this fact to label the leakage measurement with the known information and then mount attacks. Our results show that we reach at least $3\times$ better attack performance with negligible computational effort than existing non-profiling methods. Moreover, our non-profiling approach rivals the performance of state-of-the-art deep learning-based profiling attacks.

We present zkTree, a general description of a tree constructed by recursively verifying children's zero-knowledge (zk) proofs (ZKPs) in a parent ZKP node with the ability to fetch a membership proof of user supplied zk proofs. We also describe a construction pipeline such that zkTree can be built and verified on chain with constant gas cost and low data processing pipeline cost. zkTree makes ZKP on-chain verification cost effective by aggregating a large number of user proofs into one root proof. Once the root proof is verified, all user proofs can be verified by providing merkle membership proofs. zkTree can be implemented using Plonky2, the combination of PLONK and FRI, and its root proof is recursively proved in Groth16. We also demonstrate how to utilize zkTree to verify the default signature scheme of Tendermint consensus by verifying ed25519 signatures in a single proof in the Ethereum Virtual Machine (EVM).

In this paper we characterize all $2n$-bit-to-$n$-bit Pseudorandom Functions (PRFs) constructed with the minimum number of calls to $n$-bit-to-$n$-bit PRFs and arbitrary number of linear functions. First, we show that all two-round constructions are either classically insecure, or vulnerable to quantum period-finding attacks. Second, we categorize three-round constructions depending on their vulnerability to these types of attacks. This allows us to identify classes of constructions that could be proven secure. We then proceed to show the security of the following three candidates against any quantum distinguisher that asks at most $ 2^{n/4} $ (possibly superposition) queries \[ \begin{array}{rcl} \mathsf{TNT}(x_1,x_2) &:=& f_3(x_2 \oplus f_2(x_2 \oplus f_1(x_1)))\\ \mathsf{LRQ}(x_1,x_2) &:=& f_2(x_2) \oplus f_3(x_2 \oplus f_1(x_1))\\ \mathsf{LRWQ}(x_1,x_2) &:=& f_3( f_1(x_1) \oplus f_2(x_2)). \end{array} \] Note that the first construction is a classically secure tweakable block cipher due to Bao et al., and the third construction is shown to be quantum secure tweakable block cipher by Hosoyamada and Iwata with similar query limits. Of note is our proof framework, an adaptation of Chung et al.'s rigorous formulation of Zhandry's compressed oracle technique in indistinguishability setup, which could be of independent interests. This framework gives very compact and mostly classical looking proofs as compared to Hosoyamada and Iwata interpretation of Zhandry's compressed oracle.

Secure Two-party Computation (2PC) allows two parties to compute any function on their private inputs without revealing their inputs in the clear to each other. Since 2PC is known to have notoriously high overheads, one of the most popular computation models is that of 2PC with a trusted dealer, where a trusted dealer provides correlated randomness (independent of any input) to both parties during a preprocessing phase. Recent works construct efficient 2PC protocols in this model based on the cryptographic technique of function secret sharing (FSS).

We build an end-to-end system Orca to accelerate the computation of FSS-based 2PC protocols with GPUs. Next, we observe that the main performance bottleneck in such accelerated protocols is in storage (due to the large amount of correlated randomness), and we design new FSS-based 2PC cryptographic protocols for several key functionalities in ML which reduce storage by up to $5\times$. Compared to prior state-of-the-art on secure training accelerated with GPUs in the same computation model (Piranha, Usenix Security 2022), we show that Orca has $4\%$ higher accuracy, $123\times$ lesser communication, and is $19\times$ faster on CIFAR-10.

The production of modern integrated circuit (IC) requires a complex, outsourced supply chain involving computer-aided design (CAD) tools, expert knowledge, and advanced foundries. This complexity has led to various security threats, such as Trojans inserted by adversaries during outsourcing, and physical probing or manipulation of devices at run-time. Our proposed solution, DEFense is an extensible CAD framework for evaluating and proactively mitigating threats to IC at the design-time stage. Our goal with DEFense is to achieve “security closure” at the physical layout level of IC design, prioritizing security alongside traditional power, performance, and area (PPA) objectives. DEFense uses an iterative approach to assess and mitigate vulnerabilities in the IC layout, automating vulnerability assessments and identifying vulnerable active devices and wires. Using the quantified findings, DEFense guides CAD tools to re-arrange placement and routing and use other heuristic means to “DEFend” the layouts. DEFense is independent of back-end CAD tools as it works with the standard DEF format for physical layouts. It is a flexible and extensible scripting framework without the need for modifications to commercial CAD code bases. We are providing the framework to the community and have conducted a thorough experimental investigation into different threats and adversaries at various stages of the IC life-cycle, including Trojan insertion by an untrusted foundry, probing by an untrusted end-user, and intentionally introduced crosstalk by an untrusted foundry.

In Private Information Retrieval (PIR), a client wishes to retrieve the value of an index $i$ from a public database of $N$ values without leaking information about the index $i$. In their recent seminal work, Corrigan-Gibbs and Kogan (EUROCRYPT 2020) introduced the first two-server PIR protocol with sublinear amortized server time and sublinear, $O(\sqrt{N}\log N)$ bandwidth. In a followup work, Shi et al. (CRYPTO 2021) reduced the bandwidth to polylogarithmic by proposing a construction based on privately puncturable pseudorandom functions, a primitive whose only construction known to date is based on heave cryptographic primitives. Partly because of this, their PIR protocol does not achieve concrete efficiency.

In this paper we propose TreePIR, a two-server PIR protocol with sublinear amortized server time and polylogarithmic bandwidth whose security can be based on just the DDH assumption. TreePIR can be partitioned in two phases, both sublinear: The first phase is remarkably simple and only requires pseudorandom generators. The second phase is a single-server PIR protocol on \emph{only} $\sqrt{N}$ indices, for which we can use the protocol by D\"ottling et al. (CRYPTO 2019) based on DDH, or, for practical purposes, the most concretely efficient single-server PIR protocol. Not only does TreePIR achieve better asymptotics than previous approaches while resting on weaker cryptographic assumptions, but it also outperforms existing two-server PIR protocols in practice. The crux of our protocol is a new cryptographic primitive that we call weak privately puncturable pseudorandom functions, which we believe can have further applications.

Zero-knowledge range proofs (ZKRPs) are commonly used to prove the validation of a secret integer lies in an interval to some other party in a secret way. In many ZKRPs, the secret is represented in binary and then committed via a suitable commitment scheme or represented as an appropriate encryption scheme. This paper is an extended version of the conference paper presented in 14th IEEE International Conference on Security of Information and Networks. To this end, we first analyze the proof proposed by Mao in 1998 in both discrete logarithm-setting and elliptic-curve settings. Mao’s proof contains a bit commitment scheme with an OR construction as a sub-protocol. We have extended Mao’s range proof to base-u with a modified OR-proof. We investigate and compare the efficiency of different base approaches on Mao’s range proof. Later, we analyze the range poof proposed by Bootle et al. in both finite fields and elliptic-curve settings. This proof contains polynomial commitment with matrix row operations. We take the number of computations in modulo exponentiation and the cost of the number of exchanged integers between parties. Then, we generalize these costs for u-based construction. We show that compared with the base-2 representation, different base approach provides efficiency in communication cost or computation cost, or both.

In Addition-Rotation-Xor (ARX) ciphers, the large domain size obstructs the application of the boomerang connectivity table. In this paper, we explore the problem of computing this table for a modular addition and the automatic search of boomerang characteristics for ARX ciphers. We provide dynamic programming algorithms to efficiently compute this table and its variants. These algorithms are the most efficient up to now. For the boomerang connectivity table, the execution time is $4^2(n − 1)$ simple operations while the previous algorithm costs $8^2(n − 1)$ simple operations, which generates a smaller model in the searching phase. After rewriting these algorithms with boolean expressions, we construct the corresponding Boolean Satisfiability Problem models. Two automatic search frameworks are also proposed based on these models. This is the first time bringing the SAT-aided automatic search techniques into finding boomerang attacks on ARX ciphers. Finally, under these frameworks, we find out the first verifiable 10-round boomerang trail for SPECK32/64 with probability $2^{-29.15}$ and a 12-round trail for SPECK48/72 with probability $2^{-44.15}$. These are the best distinguishers for them so far. We also perceive that the previous boomerang attacks on LEA are constructed with an incorrect computation of the boomerang connection probability. The result is then fixed by our frameworks.

This note describes a new efficient bit-slice implementation DenseQMC of the Quine-McCluskey algorithm for finding all prime implicants of a Boolean function in the dense case. It is practically feasible for n <= 23 when run on a common laptop or for n <= 27 when run on a server with 1 TiB RAM.

This note also outlines a very common mistake in the implementations of the Quine-McCluskey algorithm, leading to a quadratic slowdown. An optimized corrected implementation of the classic approach is also given (called SparseQMC).

The implementation is freely available at https://github.com/hellman/Quine-McCluskey .

The Shortest Vector Problem (SVP) is at the foundation of lattice-based cryptography. The fastest known method to solve SVP in dimension $d$ is by lattice sieving, which runs in time $2^{td+o(d)}$ with $2^{md+o(d)}$ memory for constants $t,m \in \Theta(1)$. Searching reduced vectors in the sieve is a problem reduced to the configuration problem, \ie searching $k$ vectors satisfying given constraints over their scalar products.

In this work, we present a framework for $k$-sieve algorithms: we filter the input list of lattice vectors using a code structure modified from [BDGL16] to get lists centred around $k$ codewords summing to the null-vector. Then, we solve a simpler instance of the configuration problem in the $k$ filtered lists. Based on this framework, we describe classical sieves for $k=3$ and $4$ that introduce new time-memory trade-offs. We also use the $k$-Lists algorithm [KMPM19] inside our framework, and this improves the time for $k=3$ and gives new trade-offs for $k=4$.

In this paper, we propose the MixFlow model, an approach for analyzing the unobservability and unlinkability of instant messaging in Loopix Mix networks. The MixFlow model utilizes contrastive architectures and loss functions inspired by DNA sequence analysis in bioinformatics to identify semantic relationships between entry and exit flows, even after applying significant transformations such as poisson mixing delay and cover traffic. We use the MixFlow model to evaluate the resistance of Loopix Mix networks against a global passive adversary with the ability to control both ends of the network and infer real messages from cover messages. Our experimental results demonstrate that the MixFlow model is highly effective in linking end-to-end flows with a detection rate of over 90\%, challenging the common belief that adding poisson mixing delay and cover traffic can obscure the metadata patterns and relationships between communicating parties. Our findings have important implications for existing Poisson-mixing techniques and open up new opportunities for analyzing the anonymity and unlinkability of communication protocols.

FSE 2023 will take place in Beijing, China and Kobe, Japan simultaneously, on March 20-24 2023.

The registration site is now open: https://fse.iacr.org/2023/registration.php

Event date: 14 August to 16 August 2023
Submission deadline: 20 March 2023
Notification: 5 May 2023

During CRYPTO’22 in Santa Barbara, a Women in Cryptography Networking Reception was successfully held. The attendees discussed several gender-related points they would like to be addressed by the IACR community. A resume (in bullet form) can be found here (https://hackmd.io/@RUWdi86MSmCiqoMLxEzsKQ/S11cD-U1i).

As a result of this, a discord “Women in Cryptography” and a website (https://www.womenincryptography.com/) have been created.

We invite all people who identify as women to join the discord and the ongoing discussions there. To join, please send email with the subject line “Request to join WIC discord” to contact@womenincryptography.com