International Association
for Cryptologic Research

Binary search is one of the most popular algorithms in computer science. Realizing it in the context of secure multiparty computation which demands data-oblivious execution, however, is extremely non-trivial. It has been previously implemented only using oblivious RAM (ORAM) for secure computation and in this work we initiate the study of this topic using conventional secure computation techniques based on secret sharing. We develop a suite of protocols with different properties and of different structure for searching a private dataset of $m$ elements by a private numeric key. Our protocols result in $O(m)$ and $O(\sqrt{m})$ communication using only standard and readily available operations based on secret sharing. We further extend our protocols to support write operations, namely, binary search that obliviously updates the selected element, and realize two variants: updating non-key fields and updating the key field. Our implementation results indicate that even after applying known and our own optimizations to the fastest ORAM constructions, our solutions are faster than optimized ORAM schemes for datasets of up to $2^{30}$ elements and by up to two orders of magnitude. We hope that this work will prompt further interest in seeking efficient realizations of this important problem.

This work presents an approach for compressing regular hash-based signatures using STARKs (Ben-Sasson et. al.'18). We focus on constructing a hash-based t-of-n threshold signature scheme, as well as an aggregate signature scheme. In both constructions, an aggregator collects individual one-time hash-based signatures and outputs a STARK proof attesting that the signatures are valid and meet the required thresholds. This proof then serves the role of the aggregate or threshold signature. We demonstrate the concrete performance of such constructions, having implemented the algebraic intermediate representations (AIR) for them, along with an experimental evaluation over our implementation of the STARK protocol.

We find that, even when we aggregate thousands of signatures, the final aggregated size ranges between 100KB and 200KB, making our schemes attractive when there exist at least 50 one-or-few-times hash-based signatures. We also observe that for STARK-based signature aggregation, the size of individual signatures is less important than the number of hash invocations and the complexity of the signature verification algorithm. This implies that simple hash-based signature variants (e.g. Lamport, HORST, BPQS) are well-suited for aggregation, as their large individual signatures serve only as witnesses to the ZKP circuit and are not needed for aggregate signature verification.

Our constructions are directly applicable as scalable solutions for post-quantum secure blockchains which typically employ blocks of hundreds or thousands of signed transactions. Moreover, stateful hash-based one-or-few-times signatures are already used in some PQ-ready blockchains, as address reuse is typically discouraged for privacy reasons.

In this paper, a method for searching correlations between the binary stream of LFSR and the keystream of SNOW-V and SNOW-Vi is presented based on the techniques of composite function. With the aid of the linear relationship between the four taps of LFSR inputting to FSM at three consecutive clocks, we present an automatic search model based on the SAT/SMT technique and search out a binary linear approximation with a correlation 2^{-49.54}. Applying such approximation, we provide a correlation attack on SNOW-V with an expected time complexity 2^{248.81}, a memory complexity 2^{240} and 2^{240} keystream words generated by the same key and IV. For SNOW-Vi, we provide a binary linear approximation with the same correlation and mount a correlation attack with the same complexity as that of SNOW-V. The results indicate that neither of SNOW-V and SNOW-Vi can guarantee the 256-bit security level if the design constraint that the maximum of keystream length for a single pair of key and IV is less than 2^{64} is ignored.

At PQCrypto 2021, Smith-Tone proposed a new modifier, called ``Q'', to construct a fast multivariate signature scheme from a known scheme. In the present paper, we propose an idea to weaken the security of this modifier.

There have been several works on solving an under-defined system of multivariate quadratic equations over a finite field, e.g. Kipnis et al. (Eurocrypt'98), Courtois et al. (PKC'02), Tomae-Wolf (PKC'12), Miura et al. (PQC'13), Cheng et al. (PQC'14) and Furue et al. (PQC'21). This paper presents two minor improvements of Furue's aproach.

In 2019, Tao proposed a new variant of UOV with small keys, called Hufu-UOV. This paper studies its security.

This paper introduces Brakedown, the first built system that provides linear-time SNARKs for NP, meaning the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. Brakedown’s prover is faster, both concretely and asymptotically, than prior SNARK implementations. Brakedown does not require a trusted setup and is plausibly post-quantum secure. Furthermore, it is compatible with arbitrary finite fields of sufficient size; this property is new amongst implemented arguments with sublinear proof sizes.

To design Brakedown, we observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 2020) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan (CRYPTO 2020), yields linear-time IOPs and SNARKs for R1CS (a similar theoretical result was previously established by BCG, but our approach is conceptually simpler, and crucial for achieving high-speed SNARKs). A core ingredient in the polynomial commitment scheme that we distill from BCG is a linear-time encodable code. Existing constructions of such codes are believed to be impractical. Nonetheless, we design and engineer a new one that is practical in our context.

We also implement a variant of Brakedown that uses Reed-Solomon codes instead of our linear-time encodable codes; we refer to this variant as Shockwave. Shockwave is not a linear-time SNARK, but it provides shorter proofs and lower verification times than Brakedown (it also provides a faster prover than prior plausibly post-quantum SNARKs).

As a modest additional contribution, we observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time from $O(\sqrt{N})$ to $polylog(N)$---while maintaining a linear-time prover---by outsourcing the verifier’s work via one layer of proof composition with an existing zkSNARK as the "outer" proof system.

At ITCS 2010, Dziembowski, Pietrzak and Wichs introduced Non-malleable Codes (NMCs). Non-malleability is one of the strongest and most challenging notions of security considered in cryptography and protects against tampering attacks. In the context of coding schemes, non-malleability requires that it be infeasible to tamper the codeword of a message into the codeword of a related message. A natural and well-studied model of tampering is the 2-split-state model where the codeword consists of two independently tamperable states. As with standard error-correcting codes, it is of great importance to build codes with high rates. Cheraghchi and Guruswami (ITCS 2014) showed that one cannot obtain NMCs in the 2-split state model with rate better than 1/2. Since its inception, this area has witnessed huge strides leading to the construction of a constant-rate NMC in the 2-split state model due to Aggarwal and Obremski (FOCS 2020). However, the rate of this construction -- roughly 1/1,500,000 -- is nowhere close to the best achievable rate of 1/2! In this work, we dramatically improve this status quo by building a rate booster that converts any augmented non-malleable code into an augmented non-malleable code with a rate of 1/3. Using similar, but simpler techniques we also obtain rate boosters that convert any unbalanced (with sources of unequal length) non-malleable 2-source extractor into an unbalanced non-malleable 2-source extractor with rate 1/2. The beauty of our construction lies in its simplicity. In particular, if we apply our rate booster to the non-malleable code construction by Aggarwal, Dodis and Lovett (STOC 2014), then all we need is one instance of the inner-product extractor, one instance of a seeded extractor, and an affine-evasive function for the construction to work.

Multiplicative complexity is a relevant complexity measure for many advanced cryptographic protocols such as multi-party computation, fully homomorphic encryption, and zero-knowledge proofs, where processing AND gates is more expensive than processing XOR gates. For Boolean functions, multiplicative complexity is defined as the minimum number of AND gates that are sufficient to implement a function with a circuit over the basis (AND, XOR, NOT). In this paper, we study the multiplicative complexity of cubic Boolean functions. We propose a method to implement a cubic Boolean function with a small number of AND gates and provide upper bounds on the multiplicative complexity that are better than the known generic bounds.

The increasing adoption of machine learning inference in applications has led to a corresponding increase in concerns surrounding the privacy guarantees offered by existing mechanisms for inference. Such concerns have motivated the construction of efficient secure inference protocols that allow parties to perform inference without revealing their sensitive information. Recently, there has been a proliferation of such proposals, rapidly improving efficiency. However, most of these protocols assume that the client is semi-honest, that is, the client does not deviate from the protocol; yet in practice, clients are many, have varying incentives, and can behave arbitrarily. To demonstrate that a malicious client can completely break the security of semi-honest protocols, we first develop a new model-extraction attack against many state-of-the-art secure inference protocols. Our attack enables a malicious client to learn model weights with 22x-312x fewer queries than the best black-box model-extraction attack and scales to much deeper networks.

Motivated by the severity of our attack, we design and implement MUSE, an efficient two-party secure inference protocol resilient to malicious clients. MUSE introduces a novel cryptographic protocol for conditional disclosure of secrets to switch between authenticated additive secret shares and garbled circuit labels, and an improved Beaver's triple generation procedure which is 8x-12.5x faster than existing techniques.

These protocols allow MUSE to push a majority of its cryptographic overhead into a preprocessing phase: compared to the equivalent semi-honest protocol (which is close to state-of-the-art), MUSE's online phase is only 1.7x-2.2x slower and uses 1.4x more communication. Overall, MUSE is 13.4x-21x faster and uses 2x-3.6x less communication than existing secure inference protocols which defend against malicious clients.

Leakage detection tests have become an indispensable tool for testing implementations featuring side channel countermeasures such as masking. Whilst moment-based techniques such as the Welch’s t-test are universally powerful if there is leakage in a central moment, they naturally fail if this is not the case. Distribution-based techniques such as the χ2-test then come to the rescue, but they have shown not to be robust with regards to noise. In this paper, we propose a novel leakage detection technique based on Neyman’s smoothness test. We find that our new test is robust with respect to noise (similar to the merit of Welch’s t-test), and can pick up on leakage that is not located in central moments (similar to the merit of the χ2-test). We also find that there is a sweet-spot where Neyman’s test outperforms both the t-test and the χ2-test. Realistic measurements confirm that such a sweet-spot is relevant in practice for detecting implementation flaws.

We propose a new hash function Reinforced Concrete for the proof systems that support lookup tables, concretely Plookup based on KZG commitments or FRI. It has two solid advantages over predecessors: (a) Table lookups instead of (big) modular reductions are much faster both in ZK and plain computations thus making verifiable computation protocols based on recursive proofs (current trend) much more efficient; (b) the security is no longer solely based on (high) algebraic degree but rather on more traditional AES-like components inheriting decades of public scrutiny. Our design also employs a novel and fast field-to-tables conversion, which is of independent interest and can be used in other Plookup-friendly constructions. The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.

In cryptography, the private simultaneous messages (PSM) and conditional disclosure of secrets (CDS) are closely related fundamental primitives. We consider $k$-party PSM and CDS protocols for a function $f$ with a $\rho$-bit common random string, where each party $P_i$ generates an $\lambda_i$-bit message ($i\in[k]$), and sends it to a referee $P_0$.

We consider bounds for the optimal length $\rho$ of the common random string among $k$ parties (or, {\it randomness complexity}) in PSM and CDS protocols with perfect and statistical privacy through combinatorial and entropic arguments. ($i$) We provide general connections from the optimal total length $\lambda = \sum_{i\in[k]}\lambda_i$ of the messages (or, {\it communication complexity}) to the randomness complexity $\rho$. ($ii$) We also prove randomness lower bounds in PSM and CDS protocols for general functions. ($iii$) We further prove randomness lower bounds for several important explicit functions. They contain the following results: For PSM protocols with perfect privacy, we prove $\rho\ge \lambda-1$ and $\rho\le \lambda$ as the general connection. To prove the upper bound, we provide a new technique for randomness sparsification for {\it perfect}\/ privacy, which would be of independent interest. From the general connection, we prove $\rho\ge 2^{(k-1)n}-1$ for a general function $f:(\{0,1\}^n)^k\rightarrow\{0,1\}$ under universal reconstruction, in which $P_0$ is independent of $f$. This implies that the Feige-Killian-Naor protocol for a general function [Proc.~STOC '94, pp.554--563]\ is optimal with respect to randomness complexity. We also provide a randomness lower bound $\rho> kn-2$ for a generalized inner product function. This implies the optimality of the $2$-party PSM protocol for the inner-product function of Liu, Vaikuntanathan, and Wee [Proc.~CRYPTO 2017, pp.758--790]. For CDS protocols with perfect privacy, we show $\rho\ge\lambda-\sigma$ and $\rho\le\lambda$ as the general connection by similar arguments to those for PSM protocols, where $\sigma$ is the length of secrets. We also obtain randomness lower bounds $\rho\ge (k-1)\sigma$ for XOR, AND, and generalized inner product functions. These imply the optimality of Applebaum and Arkis's $k$-party CDS protocol for a general function [Proc. TCC 2018, pp.317--344]\ up to a constant factor in a large $k$.

This article presents Lelantus-CLA, an adaptation of Lelantus for use with the Mimblewimble protocol and confidential assets. Whereas Mimblewimble achieves a limited amount of privacy by merging transactions that occur in the same block, Lelantus uses a logarithmic-size proof of membership to effectively enable merging across different blocks. At a high level, this allows value to be added to a common pool and then spent privately, but only once. We explain how to adapt this construction to Mimblewimble, while at the same time simplifying the protocol where possible.

Confidential assets is a mechanism that allows multiple currencies to co-exist in the same ledger and (optionally) enables transactions to be conducted without disclosing the currency.

Finally, we also describe how we can use Bulletproof “coloring” to enable offline payments, thus addressing one of the original shortcomings of Mimblewimble.

An encrypted search algorithm (ESA) allows a user to encrypt its data while preserving the ability to search over it. As all practical solutions leak some information, cryptanalysis plays an important role in the area of encrypted search. Starting with the work by Islam et al. (NDSS'12), many attacks have been proposed that exploit different leakage profiles under various assumptions. While they aim to improve our common understanding of leakage, it is difficult to draw definite conclusions about their practical risk. This uncertainty stems from many limitations including a lack of reproducibility due to closed-source implementations, empirical evaluations conducted on small and/or unrealistic data, and reliance on very strong assumptions that can significantly affect accuracy. Particularly, assumptions made about the query distribution do not have any empirical basis because datasets containing users' queries are hard to find.

In this work, we address the main limitations of leakage cryptanalysis. First, we design and implement an open-source framework called LEAKER that can evaluate the major leakage attacks against a given dataset and can serve as a common leakage analysis reference for the community. We identify new real-world datasets that capture different use cases for ESAs and, for the first time, include real-world user queries. Finally, we use LEAKER to evaluate known attacks on our datasets to assess their practical risks and gain insights about the properties that increase or diminish their accuracy.

This article provides new constant-time encodings $\mathbb{F}_{\!q}^* \to E(\mathbb{F}_{\!q})$ to ordinary elliptic $\mathbb{F}_{\!q}$-curves $E$ of $j$-invariants $0$, $1728$ having a small prime divisor of the Frobenius trace. Therefore all curves of $j = 1728$ are covered. This is also true for the Barreto--Naehrig curves BN512, BN638 from the international cryptographic standards ISO/IEC 15946-5, TCG Algorithm Registry, and FIDO ECDAA Algorithm. Many $j = 1728$ curves as well as BN512, BN638 do not have $\mathbb{F}_{\!q}$-isogenies of small degree from other elliptic curves. So, in fact, only universal SW (Shallue--van de Woestijne) encoding was previously applicable to them. However this encoding (in contrast to ours) can not be computed at the cost of one exponentiation in the field $\mathbb{F}_{\!q}$.

We formally define polynomial packing methods and initiate a unified study of related concepts in various contexts of cryptography. This includes homomorphic encryption (HE) packing and reverse multiplication-friendly embedding (RMFE) in information-theoretically secure multi-party computation (MPC). We prove several upper bounds or impossibility results on packing methods for $\mathbb{Z}_{p^k}$ or $\mathbb{F}_{p^k}$-messages into $\mathbb{Z}_{p^t}[x]/f(x)$ regarding (i) packing density, (ii) level-consistency, and (iii) surjectivity. These results have implications on recent development of HE-based MPC over $\mathbb{Z}_{2^k}$ secure against actively corrupted majority and provide new proofs for upper bounds on RMFE.

This paper presents AdVeil, a privacy-preserving advertising ecosystem with formal guarantees for end users. AdVeil is built around an untrusted advertising network which is responsible for brokering the display of advertisement to users. This ad network targets relevant ads to users without learning any of the users' personal information in the process. Our targeting protocol combines private information retrieval with standard, locality-sensitive hashing based techniques for nearest neighbor search. By running ad targeting in this way, users of AdVeil have full control over and transparency into the contents of their targeting profile.

AdVeil additionally supports private metrics for ad interactions, allowing the ad network to correctly charge advertisers and pay websites for publishing ads. This is done without the ad network learning which user interacted with an ad, only that some honest user did. AdVeil achieves this using an anonymizing proxy (e.g., Tor) to transit batched user reports along with unlinkable anonymous tokens with metadata to certify the authenticity of each report.

We build a prototype implementation of AdVeil which we evaluate on a range of parameters to demonstrate the applicability of AdVeil to a real-world deployment. Our evaluation shows that AdVeil scales to ad networks with millions of ads, using state-of-the-art single-server private information retrieval. A selection of ads from a database of 1 million ads can be targeted to a user in approximately 10 seconds with a single 32-core server, and can be parallelized further with more servers. Targeting is performed out-of-band (e.g., on a weekly basis) while ad delivery happens in real time as users browse the web. Verifying report validity (for fraud prevention) requires less than 300 microseconds of server computation per report.

In this work we present two commitment schemes based on hardness assumptions arising from supersingular elliptic curve isogeny graphs, which possess strong security properties. The first is based on the CGL hash function while the second is based on the SIDH framework, both of which require a trusted third party for the setup phrase. The proofs of security of these protocols depend on properties of non-backtracking random walks on regular graphs. The optimal efficiency of these protocols depends on the size of a certain constant, defined in the paper, related to relevant isogeny graphs, which we give conjectural upper bounds for.

ChaCha is a high-throughput stream cipher designed with the aim of ensuring high-security margins while achieving high performance on software platforms. RISC-V, an emerging, free, and open Instruction Set Architecture (ISA) is being developed with many instruction set extensions (ISE). ISEs are a native concept in RISC-V to support a relatively small RISC-V ISA to suit different use-cases including cryptographic acceleration via either standard or custom ISEs. This paper proposes a lightweight ISE to support ChaCha on RISC-V architectures. This approach targets embedded computing systems such as IoT edge devices that don't support a vector engine. The proposed ISE is designed to accelerate the computation of the ChaCha block function and align with the RISC-V design principles. We show that our proposed ISEs help to improve the efficiency of the ChaCha block function. The ISE-assisted implementation of ChaCha encryption speeds up at least $5.4\times$ and $3.4\times$ compared to the OpenSSL baseline and ISA-based optimised implementation, respectively. For encrypting short messages, the ISE-assisted implementation gains a comparative performance compared to the implementations using very high area overhead vector extensions.