International Association
for Cryptologic Research

SQISign is an isogeny-based signature scheme that has short keys and signatures and is expected to be a post-quantum scheme. Its security depends on the hardness of the problem to find an isogeny between given two elliptic curves over $\mathbb{F}_{p^2}$, where $p$ is a large prime. For efficiency reasons, a public key in SQISign is taken from a set of supersingular elliptic curves with a particular property. In this paper, we investigate the security related to public keys in SQISign. First, we show some properties of the set of public keys. Next, we show that a key generation procedure used in implementing SQISign could not generate all public keys and propose a modification for the procedure. In addition, we confirm the latter result through an experiment.

In this paper, we propose CryptMed, a system framework that enables medical service providers to offer secure, lightweight, and accurate medical diagnostic service to their customers via an execution of neural network inference in the ciphertext domain. CryptMed ensures the privacy of both parties with cryptographic guarantees. Our technical contributions include: 1) presenting a secret sharing based inference protocol that can well cope with the commonly-used linear and non-linear NN layers; 2) devising an optimized secure comparison function that can efficiently support comparison-based activation functions in NN architectures; 3) constructing a suite of secure smooth functions built on precise approximation approaches for accurate medical diagnoses. We evaluate CryptMed on 6 neural network architectures across a wide range of non-linear activation functions over two benchmark and four real-world medical datasets. We comprehensively compare our system with prior art in terms of end-to-end service workload and prediction accuracy. Our empirical results demonstrate that CryptMed achieves up to respectively $413\times$, $19\times$, and $43\times$ bandwidth savings for MNIST, CIFAR-10, and medical applications compared with prior art. For the smooth activation based inference, the best choice of our proposed approximations preserve the precision of original functions, with less than 1.2\% accuracy loss and could enhance the precision due to the newly introduced activation function family.

A distributed network has Mempool Privacy if transactions remain en- crypted until their inclusion is finalized, and inclusion guarantees decryption and execution. Mempool Privacy is highly desirable to prevent transaction censorship and a broad class of MEV attacks. We present Ferveo, a fast protocol for Mempool Privacy on BFT consensus blockchains, such as those based on Tendermint. Blockchain validators use new Distributed Key Generation and Threshold Public Key Encryption schemes to decrypt transactions encrypted to a threshold public key, closely aligning security assumptions with Tendermint and providing concrete scalability up to thousands of transactions per block. The blockchain security and efficiency models are quite different than typically studied in the academic literature, requiring several new ideas for both the abstract scheme and implementation.

In this paper we resolve the question of whether or not constrained pseudorandom functions (CPRFs) can be built directly from pseudorandom synthesizers. In particular, we demonstrate that the generic PRF construction from pseudorandom synthesizers due to Naor and Reingold can be used to construct CPRFs with bit-fixed predicates using the "direct-line'' approach. We further introduce a property of CPRFs that may be of independent interest.

Event date: 7 November 2022
Submission deadline: 16 July 2022
Notification: 31 August 2022

Event date: 19 June to 22 June 2023
Submission deadline: 8 September 2022
Notification: 10 November 2022

We define new families of Tillich-Zémor hash functions, using higher dimensional special linear groups over finite fields as platforms. The Cayley graphs of these groups combine fast mixing properties and high girth, which together give rise to good preimage and collision resistance of the corresponding hash functions. We justify the claim that the resulting hash functions are post-quantum secure.

A blind signature scheme is a digital signature scheme that allows the signature recipient to obtain a digital signature on a message of her choice without revealing anything about the message or the resulting signature to the signer. Blind signature schemes have recently found applications for privacy-preserving web browsing and ad ecosystems, and as such, are ripe for standardization.

Recently, Denis, Jacobs and Wood [18, 17] submitted an IETF draft for a standard for a blind version of RSA-PSS. Here, we show that this proposed standard constitutes a one-more unforgeable blind signature scheme in the random-oracle model under the one-more-RSA assumption. Further, we show that the blind version of RSA-FDH proposed and analyzed by Bellare, Namprempre, Pointcheval and Semanko does not satisfy blindness when the public key (N,e) is chosen maliciously, but satisfies a weaker notion of a blind token.

Encrypted database draws much attention as it provides privacy-protection services for sensitive data outsourced to a third party. Recent studies show that the security guarantee of encrypted databases are challenged by several leakage-abuse attacks on its search module, and corresponding countermeasures are also proposed. Most of these studies focus on static databases, yet the case for dynamic has not been well investigated. To fill this gap, in this paper, we focus on exploring privacy risks in dynamic encrypted databases and devising effective mitigation techniques. To begin with, we systematically study the exploitable information disclosed during the database querying process, and consider two types of attacks that can recover encrypted queries. The first active attack works by injecting encoded files and correlating file volume information. The second passive attack works by identifying queries’ unique relational characteristics across updates, assuming certain background knowledge of plaintext databases. To mitigate these attacks, we propose a two-layer encrypted database hardening approach, which obfuscates both search indexes and files in a continuous way. As a result, the unique characteristics emerging after data updates can be eliminated constantly. We conduct a series of experiments to confirm the severity of our attacks and the effectiveness of our countermeasures.

NJS is a cryptographic protection algorithm for relational databases with non-deterministic symmetric encryption, making it possible to search data with almost the same speed as a clear text search (depending on the parameterization). The algorithm has the characteristic of performing a fast encryption on the data and a slightly slower decryption that is only performed on the client workstation. The entire process of searching, changing, adding and deleting data is performed on the server with the encrypted data. The NJS cipher is not a form of homomorphic encryption, but it can replace it with some search limitations. One advantage is the fact that noise added to the message does not interfere with its decryption, regardless of the number of operations performed on each record in a database table.

Secure multi-party computation (MPC) is an essential tool for privacy-preserving machine learning (ML). However, secure training of large-scale ML models currently requires a prohibitively long time to complete. Given that large ML inference and training tasks in the plaintext setting are significantly accelerated by Graphical Processing Units (GPUs), this raises the natural question: can secure MPC leverage GPU acceleration? A few recent works have studied this question in the context of accelerating specific components or protocols, but do not provide a general-purpose solution. Consequently, MPC developers must be both experts in cryptographic protocol design and proficient at low-level GPU kernel development to achieve good performance on any new protocol implementation.

We present Piranha, a general-purpose, modular platform for accelerating secret sharing-based MPC protocols using GPUs. Piranha allows the MPC community to easily leverage the benefits of a GPU without requiring GPU expertise. Piranha contributes a three-layer architecture: (1) a device layer that can independently accelerate secret-sharing protocols by providing integer-based kernels absent in current general-purpose GPU libraries, (2) a modular protocol layer that allows developers to maximize utility of limited GPU memory with in-place computation and iterator-based support for non-standard memory access patterns, and (3) an application layer that allows applications to remain completely agnostic to the underlying protocols they use.

To demonstrate the benefits of Piranha, we implement 3 state-of-the-art linear secret sharing MPC protocols for secure NN training: 2-party SecureML (IEEE S&P ’17), 3-party Falcon (PETS ’21), and 4-party FantasticFour (USENIX Security ’21). Compared to their CPU-based implementations, the same protocols implemented on top of Piranha’s protocol-agnostic acceleration exhibit a 16−48× decrease in training time. For the first time, Piranha demonstrates the feasibility of training a realistic neural network (e.g. VGG), end-to-end, using MPC in a little over one day. Piranha is open source and available at https://github.com/ucbrise/piranha.

An integrated circuit is subject to a number of attacks including information leakage, side-channel attacks, fault-injection, malicious change, reverse engineering, and piracy. Majority of these attacks take advantage of physical placement and routing of cells and interconnects. Several measures have already been proposed to deal with security issues of the high level functional design and logic synthesis. However, to ensure end-to-end trustworthy IC design flow, it is necessary to have security sign-off during physical design flow. This paper presents a secure physical design roadmap to enable end-to-end trustworthy IC design flow. The paper also discusses utilization of AI/ML to establish security at the layout level. Major research challenges in obtaining a secure physical design are also discussed.

Side-channel attacks are powerful non-invasive attacks on cryptographic algorithms. Among such attacks, profiling attacks have a prominent place as they assume an attacker with access to a copy of the device under attack. The attacker uses the device's copy to learn as much as possible about the device and then mount the attack on the target device. In the last few years, Machine Learning has been successfully used in profiling attacks, as such techniques proved to be capable of breaking implementations protected with countermeasures.

In the deep learning-based profiling attack, a core problem is finding efficient neural network architectures to evaluate an implementation's security correctly. Unfortunately, this process is time-consuming, and a different neural network configuration usually needs to be defined for every target. Hence, we propose the following process: train a separate autoencoder for each dataset obtained from different cryptographic implementations and devices to receive an encoded version for each one. After that, define a universal model that can break multiple (encoded) datasets. Thus, instead of finding dataset-specific neural network architectures, we reduce the effort to find autoencoders to encode the datasets and a single neural network to break~them.

We investigate the security of succinct arguments against quantum adversaries. Our main result is a proof of knowledge-soundness in the post-quantum setting for a class of multi-round interactive protocols, including those based on the recursive folding technique of Bulletproofs.

To prove this result, we devise a new quantum rewinding strategy, the first that allows for rewinding across many rounds. This technique applies to any protocol satisfying natural multi-round generalizations of special soundness and collapsing. For our main result, we show that recent Bulletproofs-like protocols based on lattices satisfy these properties, and are hence sound against quantum adversaries.

Recently, Chaum et al. (ACNS'21) introduced $\mathcal{S}_{leeve}$, which describes an extra security layer for signature schemes, i.e., ECDSA. This distinctive feature is a new key generation mechanism, allowing users to generate a ''back up key'' securely nested inside the secret key of a signature scheme. Using this novel construction, the ''back up key'', which is secret, can be used to generate a ''proof of ownership'', i.e., only the rightful owner of this secret key can generate such a proof. This design offers a quantum secure fallback, i.e., a brand new quantum resistant signature, ready to be used, nested in the ECDSA secret key. In this work, we rely on the original $\mathcal{S}_{leeve}$ definition to generalize the construction to a modular design based on Tweakable Hash Functions, thus yielding a cleaner design of the primitive. Furthermore, we provide a thorough security analysis taking into account the security of the ECDSA signature scheme, which is lacking in the original work. Finally, we provide an analysis based on formal methods using Verifpal assuring the security guarantees our construction provides.

We give black-box, round-optimal protocol compilers from semi-honest security to malicious security in the Random Oracle Model (ROM) and in the 1-out-of-2 oblivious transfer (OT) correlations model. We use our compilers to obtain the following black-box constructions of general-purpose protocols for secure computation tolerating static, malicious corruptions of all-but-one participants: \begin{itemize} \item A two-round, two-party protocol in the random oracle model, making black-box use of a two-round semi-honest secure protocol. Prior to our work, such a result was not known even for special functionalities such as OT. As an application, we get efficient constructions of two-round malicious OT/OLE in the random oracle model based on a black-box use of two-round semi-honest OT/OLE. \item A three-round multiparty protocol in the random oracle model, making a black-box use of two-round semi-honest OT. This protocol matches a known round complexity lower bound due to Applebaum et al. (ITCS 2020) and is based on a minimal cryptographic primitive.

\item A two-round multiparty protocol in the OT correlations model, making a black-box use of a semi-malicious protocol. This improves over a similar protocol of the authors (Crypto 2021) by eliminating an adaptive security requirement and replacing nonstandard multiparty OT correlations by standard ones. As an application, we get 2-round protocols for arithmetic branching programs that make a black-box use of the underlying field. \end{itemize}

As a contribution of independent interest, we provide a new variant of the IPS compiler (Ishai, Prabhakaran and Sahai, Crypto 2008) in the two-round setting, where we relax requirements on the IPS ``inner protocol'' by strengthening the ``outer protocol''.

Cryptanalysis is to infer the secret key of cryptography algorithm. There are brute-force attack, differential attack, linear attack, and chosen plaintext attack. With the development of artificial intelligence, deep learning-based cryptanalysis has been actively studied. There are works in which known-plaintext attacks against lightweight block ciphers, such as S-DES, have been performed. In this paper, we propose a cryptanalysis method based on the-state-of-art deep learning technologies (e.g. residual connections and gated linear units) for lightweight block ciphers (e.g. S-DES and S-AES). The number of parameters required for training is significantly reduced by 93.16~\% and the average of bit accuracy probability increased by about 5.3~\%, compared with previous work.

We revisit the problem of finding $B$-block-long collisions in Merkle-Damgård Hash Functions in the auxiliary-input random oracle model, in which an attacker gets a piece of $S$-bit advice about the random oracle and makes $T$ oracle queries. Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis, Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for $2\leq B\leq T$ (with respect to a random salt). The attack achieves advantage ${\Omega}(STB/2^n+T^2/2^n)$ where $n$ is the output length of the random oracle. They conjectured that this attack is optimal. However, this so-called STB conjecture was only proved for $B\approx T$ and $B=2$.

Very recently, Ghoshal and Komargodski (CRYPTO 22) confirmed STB conjecture for all constant values of $B$, and provided an ${O}(S^4TB^2/2^n+T^2/2^n)$ bound for all choices of $B$.

In this work, we prove an ${O}((STB/2^n)\cdot\max\{1,ST^2/2^n\}+ T^2/2^n)$ bound for every $2< B < T$. Our bound confirms the STB conjecture for $ST^2\leq 2^n$, and is optimal up to a factor of $S$ for $ST^2>2^n$ (note as $T^2$ is always at most $2^n$, otherwise finding a collision is trivial by the birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters except for $B={O}(1)$ and $ST^2>2^n$.

We obtain our results by adopting and refining the technique of Chung, Guo, Liu, and Qian (FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the limitations of prior techniques.

Along the way, we obtain a considerably simpler and illuminating proof for $B=2$, recovering the main result of Akshima, Cash, Drucker and Wee.

Unclonable encryption, first introduced by Broadbent and Lord (TQC'20), is a one-time encryption scheme with the following security guarantee: any non-local adversary (A, B, C) cannot simultaneously distinguish encryptions of two equal length messages. This notion is termed as unclonable indistinguishability. Prior works focused on achieving a weaker notion of unclonable encryption, where we required that any non-local adversary (A, B, C) cannot simultaneously recover the entire message m. Seemingly innocuous, understanding the feasibility of encryption schemes satisfying unclonable indistinguishability (even for 1-bit messages) has remained elusive.

We make progress towards establishing the feasibility of unclonable encryption.

- We show that encryption schemes satisfying unclonable indistinguishability exist unconditionally in the quantum random oracle model.

- Towards understanding the necessity of oracles, we present a negative result stipulating that a large class of encryption schemes cannot satisfy unclonable indistinguishability.

- Finally, we also establish the feasibility of another closely related primitive: copy-protection for single-bit output point functions. Prior works only established the feasibility of copy-protection for multi-bit output point functions or they achieved constant security error for single-bit output point functions.

Oblivious RAM (ORAM) is a machinery that protects any RAM from leaking information about its secret input by observing only the access pattern. It is known that every ORAM must incur a logarithmic overhead compared to the non-oblivious RAM. In fact, even the seemingly weaker notion of differential obliviousness, which intuitively ``protects'' a single access by guaranteeing that the observed access pattern for every two ``neighboring'' logical access sequences satisfy $(\epsilon,\delta)$-differential privacy, is subject to a logarithmic lower bound.

In this work, we show that any Turing machine computation can be generically compiled into a differentially oblivious one with only doubly logarithmic overhead. More precisely, given a Turing machine that makes $N$ transitions, the compiled Turing machine makes $O(N \cdot \log\log N)$ transitions in total and the physical head movements sequence satisfies $(\epsilon,\delta)$-differential privacy (for a constant $\epsilon$ and a negligible $\delta$). We additionally show that $\Omega(\log\log N)$ overhead is necessary in a natural range of parameters (and in the balls and bins model).

As a corollary, we show that there exist natural data structures such as stack and queues (supporting online operations) on $N$ elements for which there is a differentially oblivious implementation on a Turing machine incurring amortized $O(\log\log N)$ overhead per operation, while it is known that any oblivious implementation must consume $\Omega(\log N)$ operations unconditionally even on a RAM. Therefore, we obtain the first \emph{unconditional} separation between obliviousness and differential obliviousness in the most natural setting of parameters where $\epsilon$ is a constant and $\delta$ is negligible. Before this work, such a separation was only known in the balls and bins model. Note that the lower bound applies in the RAM model while our upper bound is in the Turing machine model, making our separation stronger.