International Association
for Cryptologic Research

We show that every language in NP has an Interactive Oracle Proof (IOP) with inverse polynomial soundness error and small query complexity. This achieves parameters that surpass all previously known PCPs and IOPs. Specifically, we construct an IOP with perfect completeness, soundness error $1/n$, round complexity $O(\log \log n)$, proof length $poly(n)$ over an alphabet of size $O(n)$, and query complexity $O(\log \log n)$. This is a step forward in the quest to establish the sliding-scale conjecture for IOPs (which would additionally require query complexity $O(1)$).

Our main technical contribution is a high-soundness small-query proximity test for the Reed-Solomon code. We construct an IOP of proximity for Reed-Solomon codes, over a field $\mathbb{F}$ with evaluation domain $L$ and degree $d$, with perfect completeness, soundness error (roughly) $\max\{1-\delta , O(\rho^{1/4})\}$ for $\delta$-far functions, round complexity $O(\log \log d)$, proof length $O(|L|/\rho)$ over $\mathbb{F}$, and query complexity $O(\log \log d)$; here $\rho = (d+1)/|L|$ is the code rate. En route, we obtain a new high-soundness proximity test for bivariate Reed-Muller codes.

The IOP for NP is then obtained via a high-soundness reduction from NP to Reed-Solomon proximity testing with rate $\rho = 1/poly(n)$ and distance $\delta = 1-1/poly(n)$ (and applying our proximity test). Our constructions are direct and efficient, and hold the potential for practical realizations that would improve the state-of-the-art in real-world applications of IOPs.

Maximal extractable value (MEV) in the context of blockchains and cryptocurrencies refers to the highest potential profit that an actor, particularly a miner or validator, can achieve through their ability to include, exclude, or re-order transactions within the blocks. MEV has become a topic of concern within the Web3 community as it impacts the fairness and security of the cryptocurrency ecosystem. In this work, we propose and explore techniques that utilize randomized permutations to shuffle the order of transactions of a committed block before they are executed. We also show that existing MEV mitigation approaches using an encrypted mempool can be readily extended by permutation-based techniques, thus providing multi-layer protection. With a focus on BFT consensus, we then propose BlindPerm, a framework enhancing an encrypted mempool with permutation at essentially no additional overheads and present various optimizations. Finally, we demonstrate how to extend our mitigation technique to support PoW longest-chain consensus protocols.

During the pandemic, the limited functionality of existing privacy-preserving contact tracing systems highlights the need for new designs. Wang et al. proposed an environmental-adaptive framework (CSS '21) but failed to formalize the security. The similarity between their framework and attribute-based credentials (ABC) inspires us to reconsider contact tracing from the perspective of ABC schemes. In such schemes, users can obtain credentials on attributes from issuers and prove the credentials anonymously (i.e., hiding sensitive information of both user and issuer). This work first extends ABC schemes with auditability, which enables designated auditing authorities to revoke the anonymity of particular issuers. We show a concrete construction by adding a DDH-based ``auditable public key'' mechanism to the Connolly et al.'s ABC scheme (PKC '22). In this work we present three contributions regarding the auditable ABC: (1) we refine the environmental-adaptive contact tracing framework, (2) present a formal treatment which includes game-based security definition and a detailed protocol construction. Finally, (3) we implement our construction to showcase the practicality of our protocol.

Proof-of-useful-work (PoUW), an alternative to the widely used proof-of-work (PoW), aims to re-purpose the network's computing power. Namely, users evaluate meaningful computational problems, e.g., solving optimization problems, instead of computing numerous hash function values as in PoW. A recent approach utilizes the training process of deep learning as ``useful work''. However, these works lack security analysis when deploying them with blockchain-based protocols, let alone the informal and over-complicated system design. This work proposes a distributed proof-of-deep-learning (D-PoDL) scheme concerning PoUW's requirements. With a novel hash-traininßg-hash structure and model-referencing mechanism, our scheme is the first deep learning-based PoUW scheme that enables achieving better accuracy distributively. Next, we introduce a transformation from the D-PoDL scheme to a generic D-PoDL blockchain protocol which can be instantiated with two chain selection rules, i.e., the longest-chain rule and the weight-based blockchain framework (LatinCrypt' 21). This work is the first to provide formal proofs for deep learning-involved blockchain protocols concerning the robust ledger properties, i.e., chain growth, chain quality, and common prefix. Finally, we implement the D-PoDL scheme to discuss the effectiveness of our design.

An encryption scheme is Key Dependent Message (KDM) secure if it is safe to encrypt messages that can arbitrarily depend on the secret keys themselves. In this work, we show how to upgrade essentially the weakest form of KDM security into the strongest one. In particular, we assume the existence of a symmetric-key bit-encryption that is circular-secure in the $1$-key setting, meaning that it maintains security even if one can encrypt individual bits of a single secret key under itself. We also rely on a standard CPA-secure public-key encryption. We construct a public-key encryption scheme that is KDM secure for general functions (of a-priori bounded circuit size) in the multi-key setting, meaning that it maintains security even if one can encrypt arbitrary functions of arbitrarily many secret keys under each of the public keys. As a special case, the latter guarantees security in the presence of arbitrary length key cycles. Prior work already showed how to amplify $n$-key circular to $n$-key KDM security for general functions. Therefore, the main novelty of our work is to upgrade from $1$-key to $n$-key security for arbitrary $n$.

As an independently interesting feature of our result, our construction does not need to know the actual specification of the underlying 1-key circular secure scheme, and we only rely on the existence of some such scheme in the proof of security. In particular, we present a universal construction of a multi-key KDM-secure encryption that is secure as long as some 1-key circular-secure scheme exists. While this feature is similar in spirit to Levin's universal construction of one-way functions, the way we achieve it is quite different technically, and does not come with the same ``galactic inefficiency''.

In this work, we extend the MPC-in-the-head framework, used in recent efficient zero-knowledge protocols, to work over the ring $\mathbb{Z}_{2^k}$, which is the primary operating domain for modern CPUs. The proposed schemes are compatible with any threshold linear secret sharing scheme and draw inspiration from MPC protocols adapted for ring operations. Additionally, we explore various batching methodologies, leveraging Shamir's secret sharing schemes and Galois ring extensions, and show the applicability of our approach in RAM program verification. Finally, we analyse different options for instantiating the resulting ZK scheme over rings and compare their communication costs.

Public data can be authenticated by obtaining from a trustworthy website with TLS. Private data, such as user profile, are usually restricted from public access. If a user wants to authenticate his private data (e.g., address) provided by a restricted website (e.g., user profile page of a utility company website) to a verifier, he cannot simply give his username and password to the verifier. DECO (CCS 2020) provides a solution for liberating these data without introducing undesirable trust assumption, nor requiring server-side modification. Their implementation is mainly based on TLS 1.2.

In this paper, we propose an optimized solution for TLS 1.3 websites. We tackle a number of open problems, including the support of X25519 key exchange in TLS 1.3, the design of round-optimal three-party key exchange, the architecture of two-party computation of TLS 1.3 key scheduling, and circuit design optimized for two-party computation. We test our implementation with real world website and show that our optimization is necessary to avoid timeout in TLS handshake.

Deep neural networks (DNNs) represent a powerful technique for assessing cryptographic security concerning side-channel analysis (SCA) due to their ability to aggregate leakages automatically, rendering attacks more efficient without preprocessing. Nevertheless, despite their effectiveness, DNNs employed in SCA are predominantly black-box algorithms, posing considerable interpretability challenges. In this paper, we propose a novel technique called Key Guessing Occlusion (KGO) that acquires a minimal set of sample points required by the DNN for key recovery, which we call OccPoIs. These OccPoIs provide information on which areas of the traces are important to the DNN for retrieving the key, enabling evaluators to know where to refine their cryptographic implementation. After obtaining the OccPoIs, we first explore the leakages found in these OccPoIs to understand what the DNN is learning with first-order Correlation Power Analysis (CPA). We show that KGO obtains relevant sample points that have a high correlation with the given leakage model but also acquires sample points that first-order CPA fails to capture. Furthermore, unlike the first-order CPA in the masking setting, KGO obtains these OccPoIs without the knowledge of the shares or mask. Next, we employ the template attack (TA) using the OccPoIs to investigate if KGO could be used as a feature selection tool. We show that using the OccPoIs with TA can recover the key for all the considered synchronized datasets and is consistent as a feature selection tool even on datasets protected by first-order masking. Furthermore, it also allows a more efficient attack than other feature selections on the first-order masking dataset called ASCADf.

This paper studies the quantum computational complexity of the discrete logarithm and related group-theoretic problems in the context of ``generic algorithms''---that is, algorithms that do not exploit any properties of the group encoding.

We establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model, as a quantum analog of its classical counterpart. Shor's algorithm for the discrete logarithm problem and related algorithms can be described in this model. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in this model. More precisely, we prove the following results for a cyclic group $\mathcal G$ of prime order.

(1) Any generic quantum discrete logarithm algorithm must make $\Omega(\log |\mathcal G|)$ depth of group operation queries. This shows that Shor's algorithm that makes $O(\log |\mathcal G|)$ group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms. (2) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We introduce a model for generic hybrid quantum-classical algorithm that captures these variants, and show that these algorithms are almost optimal in this model. Any generic hybrid quantum-classical algorithm for the discrete logarithm problem with a total number of (classical or quantum) group operations $Q$ must make $\Omega(\log |\mathcal G|/\log Q)$ quantum group operations of depth $\Omega(\log\log |\mathcal G| - \log\log Q)$. In particular, if $Q={\rm poly}\log |\mathcal G|$, classical group operations can only save the number of quantum queries by a factor of $O(\log\log |\mathcal G|)$ and the quantum depth remains as $\Omega(\log\log |\mathcal G|)$. (3) When the quantum memory can only store $t$ group elements and use quantum random access memory (qRAM) of $r$ group elements, any generic hybrid quantum-classical algorithm must make either $\Omega(\sqrt{|\mathcal G|})$ group operation queries in total or $\Omega(\log |\mathcal G|/\log (tr))$ quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond $\Omega(\log |\mathcal G|/\log (tr))$.

As a side contribution, we show a multiple discrete logarithm problem admits a better algorithm than solving each instance one by one, refuting a strong form of the quantum annoying property suggested in the context of password-authenticated key exchange protocol.

The majority of secure messengers have single, centralized service providers that relay ciphertexts between users to enable asynchronous communication. However, in some scenarios such as mass protests in censored networks, relying on a centralized provider is fatal. Mesh messengers attempt to solve this problem by building ad hoc networks in which user clients perform the ciphertext-relaying task. Yet, recent analyses of widely deployed mesh messengers discover severe security weaknesses (Albrecht et al. CT-RSA'21 & USENIX Security'22).

To support the design of secure mesh messengers, we provide a new, more complete security model for mesh messaging. Our model captures forward and post-compromise security, as well as forward and post-compromise anonymity, both of which are especially important in this setting. We also identify novel, stronger confidentiality goals that can be achieved due to the special characteristics of mesh networks (e.g., delayed communication, distributed network and adversary).

Finally, we develop a new protocol, called ASMesh, that provably satisfies these security goals. For this, we revisit Signal's Double Ratchet and propose non-trivial enhancements. On top of that, we add a mechanism that provides forward and post-compromise anonymity. Thus, our protocol efficiently provides strong confidentiality and anonymity under past and future user corruptions. Most of our results are also applicable to traditional messaging.

We prove security of our protocols and evaluate their performance in simulated mesh networks. Finally, we develop a proof of concept implementation.

Shor's algorithm solves the discrete logarithm problem (DLP) efficiently by taking advantage of the commutativity structure of the group underlying the problem. To counter Shor's algorithm, Horan et al. propose a DLP analogue in the semidirect product semigroup $G\rtimes \mathrm{End}(G)$, given a (semi)group $G$, to construct a quantum-resistant Diffie-Hellman key exchange based on it. For general (semi)groups, the semidirect product discrete logarithm problem (SPDLP) can be reduced to the hidden shift problem where Kuperberg's subexponential quantum algorithm is applicable. In this paper, we consider a specific case where $G$ is an elliptic curve over a finite field and we show that SPDLP on elliptic curves can be solved efficiently using an adaptation of Shor's algorithm for the standard elliptic curve discrete logarithm problem (ECDLP). This result points out that one should not use elliptic curves as the platforms for the semidirect product key exchange.

Zero-knowledge proof systems are becoming increasingly prevalent and being widely used to secure decentralized financial systems and protect the privacy of users. Given the sensitivity of these applications, zero-knowledge proof systems are a natural target for formal verification methods. We describe methods for checking one such proof system: Halo2. We use abstract interpretation and an SMT solver to check various properties of Halo2 circuits. Using abstract interpretation, we can detect unused gates, unconstrained cells, and unused columns. Using an SMT solver, we can detect under-constrained (in the sense that for the same public input they have two efficiently computable satisfying assignments) circuits. This is the first work we are aware of that applies lightweight formal methods to PLONKish arithmetization and Halo2 circuits.

We construct a succinct non-interactive argument ($\mathsf{SNARG}$) for the class of monotone policy batch $\mathsf{NP}$ languages under the Learning with Errors ($\mathsf{LWE}$) assumption. This class is a subclass of $\mathsf{NP}$ that is associated with a monotone function~$f:\{0,1\}^k\rightarrow\{0,1\}$ and an $\mathsf{NP}$ language $\mathcal L$, and contains instances $(x_1,\ldots,x_k)$ such that $f(b_1,\ldots,b_k)=1$ where $b_j=1$ if and only if $x_j\in \mathcal L$. Our $\mathsf{SNARG}$s are arguments of knowledge in the non-adaptive setting, and satisfy a new notion of somewhere extractability against adaptive adversaries.

This is the first $\mathsf{SNARG}$ under standard hardness assumptions for a sub-class of $\mathsf{NP}$ that is not known to have a (computational) non-signaling $\mathsf{PCP}$ with small locality. Indeed, our approach necessarily departs from the known framework of constructing $\mathsf{SNARG}$s dating back to [Kalai-Raz-Rothblum, STOC '13]

Our construction combines existing quasi-arguments for $\mathsf{NP}$ (based on batch arguments for $\mathsf{NP}$) with a novel ingredient which we call a predicate-extractable hash ($\mathsf{PEH}$) family. This notion generalizes the notion of a somewhere extractable hash. Whereas a somewhere extractable hash allows to extract a single input coordinate, our $\mathsf{PEH}$ extracts a global property of the input. We view this primitive to be of independent interest, and believe that it will find other applications.

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis of a new public-key encryption scheme whose security is based on Goldreich's pseudorandom generator. The scheme is a combination of two proposals of Applebaum, Barak, and Wigderson, and inherits desirable features from both.

Topological Data Analysis (TDA) offers a suite of computational tools that provide quantified shape features in high dimensional data that can be used by modern statistical and predictive machine learning (ML) models. In particular, persistent homology (PH) takes in data (e.g., point clouds, images, time series) and derives compact representations of latent topological structures, known as persistence diagrams (PDs). Because PDs enjoy inherent noise tolerance, are interpretable and provide a solid basis for data analysis, and can be made compatible with the expansive set of well-established ML model architectures, PH has been widely adopted for model development including on sensitive data, such as genomic, cancer, sensor network, and financial data. Thus, TDA should be incorporated into secure end-to-end data analysis pipelines. In this paper, we take the first step to address this challenge and develop a version of the fundamental algorithm to compute PH on encrypted data using homomorphic encryption (HE).

We construct the first tight verifiable delay function (VDF) where the evaluation algorithm only evaluates sequentially the function and hence outputs and empty proof, verification is independent of time parameter $T$ and setup has constant size parameters. Our VDF is based on repeated squaring in hidden order groups, but it requires that coins used to sample a random instance must be kept secret in order to guarantee sequentiality. We denote such a VDF as a private coin verifiable delay function and show that it can be used to obtain multiplicatively homomorphic non-interactive timed commitment with efficient publicly verifiable force decommitment algorithm.

Lattice-based cryptographic schemes such as Crystals-Kyber and Dilithium are post-quantum algorithms selected to be standardized by NIST as they are considered to be secure against quantum computing attacks. The multiplication in polynomial rings is the most time-consuming operation in many lattice-based cryptographic schemes, which is also subject to side-channel attacks. While NTT-based polynomial multiplication is almost a norm in a wide range of implementations, a relatively new method, incomplete-NTT is preferred to accelerate lattice-based cryptography, especially on some computing platforms that feature special instructions. In this paper, we present a novel, efficient and non-profiled power/EM side-channel attack targeting polynomial multiplication based on the incomplete NTT algorithm. We apply the attack on the Crystals-Dilithium signature algorithm and demonstrate that the method accelerates attack run-time when compared to conventional correlation power attacks (CPA). While a conventional CPA tests much larger hypothesis set due to the fact that it needs to predict two coefficients of secret polynomials together, we propose a much faster zero-value filtering attack (ZV-FA), which reduces the size of the hypothesis set by targeting the coefficients individually. We also propose an effective and efficient validation and correction technique to estimate and modify the mis-predicted coefficients. Our experimental results show that we can achieve a speed-up of 128.1× over conventional CPA using a total of 13K traces.

Zero-Knowledge proof systems are widely used as building blocks of different protocols, e.g., such as those supporting blockchains. A core element in Zero-Knowledge proof systems is the underlying PRF, usually modeled as a hash function that needs to be efficient over finite fields of prime order. Such hash functions are part of a newly developed paradigm known as Arithmetization-Oriented designs.

In this paper, we propose two new AO hash functions, XHash8 and XHash12 which are designed based on improving the bottlenecks in RPO [ePrint 2022/1577]. Based on our experiments, XHash8 performs $\approx2.75$ times faster than RPO, and XHash12 performs $\approx2$ times faster than RPO, while at the same time inheriting the security and robustness of the battle-tested Marvellous design strategy.

The problem of designing authenticated key establishment protocols has a rich history. Since 1976 more than a hundred different protocols have been proposed. But the task of comparing and classifying existing protocols is usually complicated by the fact that they are described in different terms and with different levels of detail. This paper contains intermediate results on enumeration and uniform description of AKE protocols. We publish it in order to get feedback on the description principles used. Here we describe 100 AKE protocols (there are much more such protocols, but we found these earlier) in identical terms and the same level of detail. The proposed descriptions are not structured (chronologically only) but classifying of these protocols is future work direction.

In recent years, personal and medical data collected through mobile apps has become a useful data source for researchers. Platforms like Apple ResearchKit try to make it as easy as possible for non-experts to set up such data collection campaigns. However, since the collected data is sensitive, it must be well protected. Methods that provide technical privacy guarantees often limit the usefulness of the data and results. In this paper, we model and analyze mobile data donation to better understand the requirements that must be fulfilled by privacy-preserving approaches. To this end, we give an overview of the functionalities researchers require from data donation apps by analyzing existing apps. We also create a model of the current practice and analyze it using the LINDDUN privacy framework to identify privacy threats.