International Association
for Cryptologic Research

We propose a novel obfuscation technique that can be used to outsource hard satisfiability (SAT) formulas to the cloud. Servers with large computational power are typically used to solve SAT instances that model real-life problems in task scheduling, AI planning, circuit verification and more. However, outsourcing data to the cloud may lead to privacy and information breaches since satisfying assignments may reveal considerable information about the underlying problem modeled by SAT.

In this work, we develop CENSOR (privaCy prEserviNg obfuScation for Outsourcing foRmulas), a novel SAT obfuscation framework that resembles Indistinguishability Obfuscation. At the core of the framework lies a mechanism that transforms any formula to a random one with the same number of satisfying assignments. As a result, obfuscated formulas are indistinguishable from each other thus preserving the input-output privacy of the original SAT instance. Contrary to prior solutions that are rather adhoc in nature, we formally prove the security of our scheme. Additionally, we show that obfuscated formulas are within a polynomial factor of the original ones thus achieving polynomial slowdown. Finally, the whole process is efficient in practice, allowing solutions to original instances to be easily recovered from obfuscated ones.

A byproduct of our method is that all NP problems can be potentially outsourced to the cloud by means of reducing to SAT.

As an enhancement of quantum collision-resistance, the collapsing property of hash functions proposed by Unruh (EUROCRYPT 2016) emphasizes the hardness for distinguishing a superposition state of a hash value from a collapsed one. The collapsing property trivially implies the quantum collision-resistance. However, it remains to be unknown whether there is a reduction from the collapsing hash functions to the quantum collision-resistant hash functions. In this paper, we further study the relations between these two properties and derive two intriguing results as follows:

Firstly, when the size of preimages of each hash value is bounded by some polynomial, we demonstrate that the collapsing property and the collision-resistance must hold simultaneously. This result is proved via a semi-black-box manner by taking advantage of the invertibility of a unitary quantum circuit.

Next, we further consider the relations between these two properties in the exponential-sized preimages case. By giving a construction of polynomial bounded hash functions, which preserves the quantum collision-resistance, we show the existence of collapsing hash functions is implied by the quantum collision-resistant hash functions when the size of preimages is not too large to the expected value.

Our results indicate that the gap between these two properties is sensitive to the size of preimages. As a corollary, our results also reveal the non-existence of polynomial bounded equivocal collision-resistant hash functions.

Zero-knowledge defines that verifier(s) learns nothing but predefined statement(s); e.g., verifiers learn nothing except the program's path for the respective transaction in a zero-knowledge contract program. Intra-Privacy or insiders' zero-knowledge --- ability to maintain a secret in a multi-party computation --- is an essential security property for smart contracts of Confidential Transactions (CT). Otherwise, the users have to reveal their confidential coin amounts to each other even if it is not a condition of the contract, contradicting the idea of zero-knowledge. For example, in an escrow contract, the escrow should not learn buyers' or sellers' account balances if the escrow has to pay into their accounts. Current private computational platforms, including homomorphic encryption and (ZK-)SNARK, can not be used in CT's smart contracts because homomorphic encryption requires secret key sharing, and (ZK-)SNARK requires a different setup for each computation which has to be stored on the blockchain. Existing private smart contracts are not intra-private even though they are inter-private --- participants can maintain secrets from verifiers but not from other participants, accordingly. To fill this research gap, we introduce the notion of ``Confidential Integer Processing'' (CIP) with two intra-private single-setup zero-knowledge programming protocols, (1) ``CIP-DLP'' from the Discrete Log Problem (DLP) targeting Ring/Aggregable CT like Monero and Mimblewimble, and (2) ``CIP-SIS'' from Approximate (Ring-Modular-) Short Integer Solution Problem (Approx-SIS) aiming at lattice-based Ring/Aggregable CT. To the best of our knowledge, our CIP protocols are the first practical public zero-knowledge contract protocols that are also secure under the Universal Composability (UC) framework without any hardware magic or trusted offline computations.

In this paper, we study the class of those Boolean functions that are coset leaders of first order Reed-Muller codes. We study their properties and try to better understand their structure (which seems complex), by studying operations on Boolean functions that can provide coset leaders (we show that these operations all provide coset leaders when the operands are coset leaders, and that some can even produce coset leaders without the operands being coset leaders). We characterize those coset leaders that belong to the well known classes of direct sums of monomial Boolean functions and Maiorana-McFarland functions. Since all the functions of Hamming weight at most $2^{n-2}$ are automatically coset leaders, we are interested in constructing infinite classes of coset leaders having possibly Hamming weight larger than $2^{n-2}$.

3kf9 is a three-key CBC-type MAC that enhances the standardized integrity algorithm f9 (3GPP-MAC). It has beyond-birthday-bound security and is expected to be a possible candidate in constrained environments when instantiated with lightweight blockciphers. Two variants 2kf9 and 1kf9 were proposed to reduce key size for efficiency, but recently, Leurent et al. (CRYPTO'18) and Shen et al. (CRYPTO'21) pointed out critical flaws on these two variants and invalidated their security proofs with birthday-bound attacks.

In this work, we revisit previous constructions of key-reduced variants of 3kf9 and analyze what went wrong in security analyzes. Interestingly, we find that a single doubling at the end can not only fix 2kf9 to go beyond the birthday bound, but also help 1kf9 to go beyond the birthday bound. We then propose two new key-reduced variants of 3kf9, called n2kf9 and n1kf9. By leveraging previous attempts, we prove that n2kf9 is secure up to 2^{2n/3} queries, and prove that n1kf9 is secure up to 2^{2n/3} queries when the message space is prefix-free. We also provide beyond-birthday analysis of n2kf9 in the multi-user setting. Note that compared to EMAC and CBC-MAC, the additional cost to provide a higher security guarantee is expected to be minimal for n2kf9 and n1kf9. It only requires one additional blockcipher call and one doubling.

Some of the most efficient protocols for Multi-Party Computation (MPC) use a two-phase approach where correlated randomness, in particular Beaver triples, is generated in the offline phase and then used to speed up the online phase. Recently, more complex correlations have been introduced to optimize certain operations even further, such as matrix triples for matrix multiplications. In this paper, our goal is to speed up the evaluation of multivariate polynomials and therewith of whole arithmetic circuits in the online phase. To this end, we introduce a new form of correlated randomness: arithmetic tuples. Arithmetic tuples can be fine tuned in various ways to the constraints of application at hand, in terms of round complexity, bandwidth, and tuple size. We show that for many real-world setups an arithmetic tuples based online phase outperforms state-of-the-art protocols based on Beaver triples.

We describe an efficient algorithm for testing and recovering linear equivalence between a pair of $k$-to-$1$ discrete functions with a specific structure. In particular, for $k = 3$ this applies to many APN functions over fields of even characteristic, and for $k = 2$ this applies to all known planar functions over fields of odd characteristic. Our approach is significantly faster than all known methods for testing equivalence, and allows linear equivalence to be tested in practice for dimensions much higher than what has been possible before (for instance, we can efficiently test equivalence for $n = 12$ or $n = 14$ in the case of 3-to-1 APN functions over $\mathbb{F}_{2^n}$, and for $n = 8$ or $n = 9$ in the case of 2-to-1 planar functions over $\mathbb{F}_{3^n}$ within a few minutes even in the worst case). We also develop supplementary algorithms allowing our approach to be extended to the more general case of EA-equivalence. Classifying 3-to-1 APN functions over $\mathbb{F}_{2^n}$ for dimensions as high as $n = 14$ up to EA-equivalence can be performed in a matter of minutes using the developed framework.

In this paper, we propose a noncommutative-ring based unbalanced oil and vinegar signature scheme with key-randomness alignment: NOVA (Noncommutative Oil and Vinegar with Alignment). Instead of fields or even commutative rings, we show that noncommutative rings can be used for algebraic cryptosystems. At the same or better level of security requirement, NOVA has a much smaller public key than UOV (Unbalanced Oil and Vinegar), which makes NOVA practical in most situations. We use Magma to actually implement and give a detailed security analysis against known major attacks.

Permutation polynomials with low $c$-differential uniformity and boomerang uniformity have wide applications in cryptography. In this paper, by utilizing the Weil sums technique and solving some certain equations over $\mathbb{F}_{2^n}$, we determine the $c$-differential uniformity and boomerang uniformity of these permutation polynomials: (1) $f_1(x)=x+\mathrm{Tr}_1^n(x^{2^{k+1}+1}+x^3+x+ux)$, where $n=2k+1$, $u\in\mathbb{F}_{2^n}$ with $\mathrm{Tr}_1^n(u)=1$; (2) $f_2(x)=x+\mathrm{Tr}_1^n(x^{{2^k}+3}+(x+1)^{2^k+3})$, where $n=2k+1$; (3) $f_3(x)=x^{-1}+\mathrm{Tr}_1^n((x^{-1}+1)^d+x^{-d})$, where $n$ is even and $d$ is a positive integer. The results show that the involutions $f_1(x)$ and $f_2(x)$ are APcN functions for $c\in\mathbb{F}_{2^n}\backslash \{0,1\}$. Moreover, the boomerang uniformity of $f_1(x)$ and $f_2(x)$ can attain $2^n$. Furthermore, we generalize some previous works and derive the upper bounds on the $c$-differential uniformity and boomerang uniformity of $f_3(x)$.

Secure multiparty computation (MPC) has been proposed to allow multiple mutually distrustful data owners to jointly train machine learning (ML) models on their combined data. However, the datasets used for training ML models might be under the control of an adversary mounting a data poisoning attack, and MPC prevents inspecting training sets to detect poisoning. We show that multiple MPC frameworks for private ML training are susceptible to backdoor and targeted poisoning attacks. To mitigate this, we propose SafeNet, a framework for building ensemble models in MPC with formal guarantees of robustness to data poisoning attacks. We extend the security definition of private ML training to account for poisoning and prove that our SafeNet design satisfies the definition. We demonstrate SafeNet's efficiency, accuracy, and resilience to poisoning on several machine learning datasets and models. For instance, SafeNet reduces backdoor attack success from $100\%$ to $0\%$ for a neural network model, while achieving $39\times$ faster training and $36 \times$ less communication than the four-party MPC framework of Dalskov et al.

Many applications that benefit from data offload to cloud services operate on private data. A now-long line of work has shown that, even when data is offloaded in an encrypted form, an adversary can learn sensitive information by analyzing data access patterns. Existing techniques for oblivious data access—that protect against access pattern attacks—require a centralized, stateful and trusted, proxy to orchestrate data accesses from applications to cloud services. We show that, in failure-prone deployments, such a centralized and stateful proxy results in violation of oblivious data access security guarantees and/or system unavailability. Thus, we initiate the study of distributed, fault-tolerant, oblivious data access. We present SHORTSTACK , a distributed proxy architecture for oblivious data access in failure-prone deployments. SHORTSTACK achieves the classical obliviousness guarantee—access patterns observed by the adversary being independent of the input—even under a powerful passive persistent adversary that can force failure of arbitrary (bounded-sized) subset of proxy servers at arbitrary times. We also introduce a security model that enables studying oblivious data access with distributed, failure-prone, servers. We provide a formal proof that SHORTSTACK enables oblivious data access under this model, and show empirically that SHORTSTACK performance scales near-linearly with number of distributed proxy servers.

Recent works to improve privacy and auditability in permissioned blockchains like Hyperledger Fabric rely on Idemix, the only anonymous credential system that has been integrated to date. The current Idemix implementation in Hyperledger Fabric (v2.4) only supports a fixed set of attributes, it does not support revocation features, nor does it support anonymous endorsement of transactions (in Fabric, transactions need to be approved by a subset of peers before consensus). A prototype Idemix extension by Bogatov et al. (CANS, 2021) was proposed to include revocation, auditability, and to gain privacy for users. We explore how to gain efficiency, functionality, and further privacy departing from recent works on anonymous credentials based on Structure-Preserving Signatures on Equivalence Classes. As a result, we propose Protego and Protego Duo, two alternatives for Idemix and its recent extensions. We discuss how they can be used in the permissioned blockchain setting and integrated to Hyperledger Fabric. We also provide a prototype implementation and benchmarks showing that both alternatives are twice as fast as state-of-the-art-approaches.

Random sampling from specified distributions is an important tool with wide applications for analysis of large-scale data. In this paper we study how to randomly sample when the distribution is partitioned among two parties' private inputs. Of course, a trivial solution is to have one party send a (possibly encrypted) description of its weights to the other party who can then sample over the entire distribution (possibly using homomorphic encryption). However, this approach requires communication that is linear in the input size which is prohibitively expensive in many settings. In this paper, we investigate secure 2-party sampling with \emph{sublinear communication} for many standard distributions. We develop protocols for $L_1$, and $L_2$ sampling. Additionally, we investigate the feasibility of sublinear product sampling, showing impossibility for the general problem and showing a protocol for a restricted case of the problem. We additionally show how such product sampling can be used to instantiate a sublinear communication 2-party exponential mechanism for differentially-private data release.

An important theme in research on attribute-based encryption (ABE) is minimizing the sizes of the secret keys and ciphertexts. In this work, we present two new ABE schemes with *constant-size* secret keys, that is, the key size is independent of the sizes of policies or attributes, and dependent only on the security parameter lambda.

* We construct the first key-policy ABE scheme for circuits with constant-size secret keys, |sk_f|=poly(lambda), which concretely consist of only three group elements. The previous state-of-the-art construction by [Boneh et al., Eurocrypt '14] has key size polynomial in the maximum depth d of the policy circuits, |sk_f|=poly(d,lambda). Our new scheme removes this dependency of key size on d while keeping the ciphertext size the same, which grows linearly in the attribute length and polynomially in the maximal depth, |ct|=|x|poly(d,lambda).

* We present the first ciphertext-policy ABE scheme for Boolean formulae that simultaneously has constant-size keys and succinct ciphertexts of size independent of the policy formulae, in particular, |sk_f|=poly(lambda) and |ct_x|=poly(|x|,lambda). Concretely, each secret key consists of only two group elements. Previous ciphertext-policy ABE schemes either have succinct ciphertexts but non constant-size keys [Agrawal--Yamada, Eurocrypt '20; Agrawal--Wichs--Yamada, TCC '20], or constant-size keys but large ciphertexts that grow with the policy size, as well as the attribute length. Our second construction is the first ABE scheme achieving *double succinctness*, where both keys and ciphertexts are smaller than the corresponding attributes and policies tied to them.

Our constructions feature new ways of combining lattices with pairing groups for building ABE and are proven selectively secure based on LWE and in the generic (pairing) group model. We further show that when replacing the LWE assumption with its adaptive variant introduced in [Quach--Wee--Wichs FOCS '18] the constructions become adaptively secure.

We propose a mechanism for generating and manipulating protein polymers to obtain a new type of consumable storage that exhibits intriguing cryptographic "self-destruct" properties, assuming the hardness of certain polymer-sequencing problems. To demonstrate the cryptographic potential of this technology, we first develop a formalism that captures (in a minimalistic way) the functionality and security properties provided by the technology. Next, using this technology, we construct and prove security of two cryptographic applications that are currently obtainable only via trusted hardware that implements logical circuitry (either classical or quantum). The first application is a password-controlled secure vault where the stored data is irrecoverably erased once a threshold of unsuccessful access attempts is reached. The second is (a somewhat relaxed version of) one-time programs, namely a device that allows evaluating a secret function only a limited number of times before self-destructing, where each evaluation is made on a fresh user-chosen input. Finally, while our constructions, modeling, and analysis are designed to capture the proposed polymer-based technology, they are sufficiently general to be of potential independent interest.

Fully Homomorphic Encryption (FHE) allows for secure computation on encrypted data. It enables a variety of theoretical and practical applications, but is still several orders of magnitudes too slow to be practical. We present BASALISC, an architecture family of FHE hardware accelerators that aims to substantially accelerate FHE computations in the cloud. BASALISC implements Brakerski, Gentry, and Vaikuntanathan's (BGV) scheme and supports a range of parameter sets. In contrast to many prior studies, we directly support and implement BGV bootstrapping - the noise removal capability necessary to support arbitrary-depth computation.

BASALISC exploits data representation in residue number systems and number-theoretic transforms to realize massive FHE parallelism. We propose a new generalized version of bootstrapping that can be implemented with optimized Montgomery multipliers that cost 46% less in silicon area and 40% less in power consumption versus traditional approaches. BASALISC is a Reduced Instruction Set Computing (RISC) architecture with a four-layer memory hierarchy, including a two-dimensional conflict-free inner memory layer that enables 32 Tb/s radix-256 number-theoretic transform (NTT) computations without pipeline stalls. Our conflict-resolution data permutation hardware is re-used to compute BGV automorphisms without additional hardware and without throughput penalty. BASALISC additionally includes a custom multiply-accumulate unit familiar in Digital Signal Processing (DSP) architectures, with which we accelerate tight BGV key switching loops. The BASALISC computation units and inner memory layers are designed in asynchronous logic, allowing them to run at different speeds to optimize each function. BASALISC is designed for Application-Specific Integrated Circuit (ASIC) implementation with a 1 GHz operational frequency, and is already underway toward tape-out with a 150mm2 die size in a 12nm Global Foundries process.

The BASALISC toolchain comprises both a custom compiler and a joint performance and correctness simulator. We evaluate BASALISC in multiple ways: we study its physical realizability; we emulate and formally verify its core functional units; and we study its performance on a single iteration of logistic regression training over encrypted data. For this application, comprising from up to 900K high-level BASALISC instructions (including 513 bootstraps) down to 27B low-level instructions, we show a speedup of at least 2,025x over HElib - a popular software FHE library - running on a Xeon-class processor.

We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM). Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM.

On a technical level, we show how to obtain a quantum speedup on the search for Fast Fourier Transform (FFT) coefficients above a given threshold by leveraging the relative sparseness of the FFT and using quantum amplitude estimation. We also discuss the applicability of the Quantum Fourier Transform in this context. Furthermore, we give a more rigorous analysis of the classical and quantum expected complexity of guessing part of the secret vector where coefficients follow a discrete Gaussian (mod \(q\)).

We revisit the question of what should be the definition of bit security, previously answered by Micciancio-Walter (Eurocrypt 2018) and Watanabe-Yasunaga (Asiacrypt 2021). Our new definition is simple, but (i) captures both search and decision primitives in a single framework like Micciancio-Walter, and (ii) has a firm operational meaning like Watanabe-Yasunaga. It also matches intuitive expectations and can be easily well-estimated in terms of Kullback-Leibler divergence. Along the way of defining bit security and justifying our definition, we raise undervalued concepts such as allowing aborts in security games, considering partial adversaries, and verifiability in security games.

Isogeny-based cryptography is a promising approach for post-quantum cryptography.

The best-known protocol following that approach is the supersingular isogeny Diffie-Hellman protocol (SIDH); this protocol was turned into the CCA-secure key encapsulation mechanism SIKE, which was submitted to and remains in the third round of NIST's post-quantum standardization process as an ``alternate'' candidate.

Isogeny-based cryptography generally relies on the conjectured hardness of computing an isogeny between two isogenous elliptic curves, and most cryptanalytic work referenced on SIKE's webpage exclusively focuses on that problem.

Interestingly, the hardness of this problem is sufficient for neither SIDH nor SIKE. In particular, these protocols reveal additional information on the secret isogeny, in the form of images of specific torsion points through the isogeny.

This paper surveys existing cryptanalysis approaches exploiting this often called ``torsion point information'', summarizes their current impact on SIKE and related algorithms, and suggests some research directions that might lead to further impact.

Private set union (PSU) allows two parties to compute the union of their sets without revealing anything except the union and it has found numerous applications in practice. Recently, some computationally efficient PSU protocols have been designed in the balanced case, but a potential limitation with these approaches is the communication complexity, which scales linearly with the size of the larger set. This is of particular concern when performing PSU in the unbalanced case, where one party is a constrained device (cellphone) holding a small set, and another is a large service provider.

In this work, we propose a generic framework of using the leveled fully homomorphic encryption and a newly introduced protocol called permute matrix Private EQuality Test (pm-PEQT) to construct the \emph{unbalanced} PSU that is secure against semi-honest adversaries. By instantiating the pm-PEQT, we obtain fast unbalanced PSU protocols with a small communication overhead. Our protocol has communication complexity \emph{linear in the size of the smaller set, and logarithmic in the larger set}. More precisely, if the set sizes are $|X|\ll |Y|$, our protocol achieves a communication overhead of $O(|X|\log |Y|)$.

Finally, we implement our protocols that can compare with the state-of-the-art PSU. Experiments show that our protocols are more efficient than all previous protocols in the unbalanced case, especially, the larger the difference of two set sizes, the better our protocols perform. Our running-time-optimized benchmarks show that it takes 18.782 seconds of computation and 2.179 MB of communication to compute the union between $2^{10}$ strings and $2^{19}$ strings. Compared to prior secure PSU proposed by Jia et al. (Usenix Security 2022), this is roughly a $300 \times$ reduction in communication and $20 \times$ reduction in computational overhead with a single thread in WAN/LAN settings.