International Association
for Cryptologic Research

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.

Physical characteristics of electronic devices, leaking secret and sensitive information to an adversary with physical access, pose a long-known threat to cryptographic hardware implementations. Among a variety of proposed countermeasures against such Side-Channel Analysis attacks, masking has emerged as a promising, but often costly, candidate. Furthermore, the manual realization of masked implementations has proven error-prone and often introduces flaws, possibly resulting in insecure circuits. In the context of automatic masking, a new line of research emerged, aiming to replace each physical gate with a secure gadget that fulfills well-defined properties, guaranteeing security when interconnected to a large circuit. Unfortunately, those gadgets introduce a significant amount of additional overhead into the design, in terms of area, latency, and randomness requirements. In this work, we present a novel approach to reduce the demands for randomness in such gadget-composed circuits by reusing randomness across gadgets while maintaining security in the probing adversary model. To this end, we embedded the corresponding optimization passes into an Electronic Design Automation toolchain, able to construct, optimize, and implement masked circuits, starting from an unprotected design. As such, our security-aware optimization offers an additional building block for existing or new Electronic Design Automation frameworks, where security is considered a first-class design constraint

Public-key cryptography (PKC), including conventional cryptosystems (e.g., RSA, ECC) and post-quantum cryptography, involves computation-intensive workloads. With noticing the extraordinary computing power of AI accelerators, in this paper, we further explore the feasibility to introduce AI accelerators into high-performance cryptographic computing. Since AI accelerators are dedicated to machine learning or neural networks, the biggest challenge is how to transform cryptographic workloads into their operations, while ensuring the correctness of the results and bringing convincing performance gains.

After investigating and analysing the workload of the commercial off-the-shelf AI accelerators, we utilize NVIDIA's AI accelerator, Tensor Core, to accelerate the polynomial multiplication, usually the most time-consuming part in lattice-based cryptography. A series of measures are taken, such as accommodating the matrix-multiply-and-add mode of Tensor Core and making a trade-off between precision and performance, to leverage Tensor Core as a high-performance NTT box performing NTT/INTT through CUDA C++ WMMA API. Meanwhile, we take CRYSTALS-Kyber, one of the NIST PQC 3rd round candidates, as a case study on RTX 3080 with the Ampere Tensor Core. The empirical results show that the defined NTT of polynomial vector ($n=256,k=4$) with our NTT box obtains a speedup of around 6.47x that of the state-of-the-art implementation on the same platform.

Many public-key cryptographic protocols, notably non-interactive key exchange (NIKE), require incoming public keys to be validated to mitigate some adaptive attacks. In CSIDH, an isogeny-based post-quantum NIKE, a key is deemed legitimate if the given Montgomery coefficient specifies a supersingular elliptic curve over the prime field. In this work, we survey the current supersingularity tests used for CSIDH key validation, and implement and measure two new alternative algorithms. Our implementation shows that we can determine supersingularity substantially faster, and using less memory, than the state-of-the-art.

Modular polynomial multiplication is a core and costly operation of ideal lattice-based schemes. In the context of embedded devices, previous works transform the polynomial multiplication to an integer one using Kronecker substitution. Then thanks to this transformation, existing coprocessors which handle large-integer operations can be re-purposed to speed-up lattice-based cryptography. In a nutshell, the Kronecker substitution transforms by evaluation the polynomials to integers, multiplies it with an integer multiplication and gets back to a polynomial result using a radix conversion. The previous work focused on optimization of the integer multiplication using coprocessor instructions. In this work, we pursue the seminal research by optimizing the evaluation, radix conversion and the modular reductions modulo q with today's RSA/ECC coprocessor. In particular we show that with a RSA/ECC coprocessor that can compute addition/subtraction, (modular) multiplication, shift and logical AND on integers, we can compute the whole modular polynomial multiplication using coprocessor instructions. The efficiency of our modular polynomial multiplication depends on the component specification and on the cryptosystem parameters set. Hence, we assess our algorithm on a chip for several lattice-based schemes, which are finalists of the NIST standardization. Moreover, we compare our modular polynomial multiplication with other polynomial multiplication techniques.

Frequently, users on the web need to show that they are, for example, not a robot, old enough to access an age restricted video, or eligible to download an ebook from their local public library without being tracked. Anonymous credentials were developed to address these concerns. However, existing schemes do not handle the realities of deployment or the complexities of real world identity. Instead, they make (often incorrect) assumptions, e.g., that the local department of motor vehicles will issue sophisticated cryptographic tokens to show users are over 18. In reality, there are multiple trust sources for a given identity attribute, their credentials have distinctively different formats, and many, if not all, issuers are unwilling to adopt new protocols.

We present and build $\texttt{zk-creds}$, a protocol that uses general-purpose zero-knowledge proofs to 1) remove the need for credential issuers to hold signing keys: credentials can be issued via a transparency log, Byzantine system, or even a blockchain; 2) convert existing identity documents into anonymous credentials without modifying documents or coordinating with their issuing authority; 3) allow for flexible, composable, and complex identity statements over multiple credentials. Concretely, identity assertions using $\texttt{zk-creds}$ take less than 300ms in a real-world scenario of using a passport to anonymously access age-restricted videos.

The re-encryption mix-net (RMN) is a basic cryptographic tool that is widely used in the privacy protection domain and requires anonymity support; for example, it is used in electronic voting, web browsing, and location systems. To protect information about the relationship between senders and messages, a number of mix servers in RMNs shuffle and forward a list of input ciphertexts in a cascading manner. The output of the last mix server is decrypted to yield the set of original messages. The main downside of this approach is that the mixing process requires a number of rounds that is linear in the number of mix servers. This implies that a long round delay would cause network latency, which can dominate local computational latencies. To minimize the effect of network latency, RMN protocols with constant round complexity are more desirable. In this work, we propose a new RMN protocol that runs in $O(1)$ rounds in the number of mix servers and that UC-realizes a hybrid model with access to some functionalities for secure communication and zero-knowledge proof (ZKP). Interestingly, because our protocol does not require a ZKP protocol for a verifiable shuffle, we also achieve a considerable efficiency gain in terms of computation cost. Our main tools are secret sharing and an ElGamal encryption that is extended in the sense that it works on a multiplicative group under field extension. Importantly, this extended ElGamal encryption scheme acquires a new capability: it can efficiently decompose a decrypted message into unique values. We provide a detailed report on the theoretical performance and security analysis of this method.

The current state of the art in watermarked public-key encryption schemes under standard cryptographic assumptions suggests that extracting the embedded message requires either linear time in the number of marked keys or the a-priori knowledge of the marked key employed in the decoder.

We present the first scheme that obviates these restrictions in the secret-key marking model, i.e., the setting where extraction is performed using a private extraction key. Our construction offers constant time extraction complexity with constant size keys and ciphertexts and is secure under standard assumptions, namely the Decisional Composite Residuosity Assumption [Eurocrypt '99] and the Decisional Diffie Hellman in prime order subgroups of  square higher order residues.