International Association
for Cryptologic Research

Event date: 5 October to 8 October 2021
Submission deadline: 15 May 2021
Notification: 24 June 2021

Event date: 7 December to 11 December 2021
Submission deadline: 30 April 2021
Notification: 25 July 2021

Event date: 14 December to 17 December 2021
Submission deadline: 16 July 2021

Event date: 11 November to 12 November 2021
Submission deadline: 25 June 2021
Notification: 30 August 2021

Updatable Encryption (UE), as originally defined by Boneh et al. in 2013, addresses the problem of key rotation on outsourced data while maintaining the communication complexity as low as possible. The security definitions for UE schemes have been constantly updated since then. However, the security notion that is best suited for a particular application remains unclear.

To solve this problem in the ciphertext-independent setting, we use the Constructive Cryptography (CC) framework defined by Maurer et al. in 2011. We define and construct a resource that we call Updatable Server-Memory Resource (USMR), and study the confidentiality guarantees it achieves when equipped with a UE protocol, that we also model in this framework. With this methodology, we are able to construct resources tailored for each security notion. In particular, we prove that IND-UE-RCCA is the right security notion for many practical UE schemes.

As a consequence, we notably rectify a claim made by Boyd et al., namely that their IND-UE security notion is better than the IND-ENC+UPD notions, in that it hides the age of ciphertexts. We show that this is only true when ciphertexts can leak at most one time per epoch.

We stress that UE security is thought of in the context of adaptive adversaries, and UE schemes should thus bring post-compromise confidentiality guarantees to the client. To handle such adversaries, we use an extension of CC due to Jost et al. and give a clear, simple and composable description of the post-compromise security guarantees of UE schemes. We also model semi-honest adversaries in CC.

Our adaption of the CC framework to UE is generic enough to model other interactive protocols in the outsourced storage setting.

Distributed ledger technologies like blockchain have gained great attention in both academia and industry. Blockchain as a potentially disruptive technology can advance many different fields, e.g., cryptocurrencies, supply chains, and the industrial Internet of Things. The next-generation blockchain ecosystem is expected to consist of various homogeneous and heterogeneous distributed ledgers. These ledger systems will inevitably require a certain level of proper cooperation of multiple blockchains to enrich advanced functionalities and enhance interoperable capabilities for future applications. The interoperability among blockchains will definitely revolutionize current blockchain design principles, like the emergence of Internet. The development of cross-blockchain applications involves much complexity regarding the variety of underlying cross-blockchain communication. The way to effectively enable interoperability across multiple blockchains is thus essential and expecting to confront various unprecedented challenges. For instance, due to different transaction structures, ensuring the properties of ACID (Atomicity, Consistency, Isolation, Durability) in transactions processing and verification processes across diverse blockchain systems remains a challenging task in both academia and industry. This paper provides a systematic and comprehensive review of the current progress of blockchain interoperability. We explore both general principles and practical schemes to achieve interoperable blockchain systems. We then survey and compare the state-of-the-art solutions to deal with the interoperability of blockchains in detail. Finally, we discuss several critical challenges and some potential research directions to advance the research on exploring blockchain interoperability.

Lattice-based structures offer considerable possibilities for post-quantum cryptography. Recently, many algorithms have been built on hard lattice problems. The three of the remaining four in the final round of the post-quantum cryptography standardization process use lattice-based methods. Especially in embedded systems, these algorithms should be operated effectively. In this study, the potential of transport triggered architecture is examined in this sense. We try to compare open source RISC-V processors with our transport triggered architecture processors under fair conditions. Thus, we aim to provide a base architecture for developing application specific processors for post-quantum cryptography, which is becoming an increasingly urgent research area. The tests performed are implemented on the same FPGA and evaluated as performance, resource utilization, average power and total energy consumption. Regardless of the algorithm, our design exhibit better results than RISC-V processors for all tests. It seems to be 2x - 3x faster, 2x - 2.5x smaller and consumes 2.5x - 5x less energy than RISC-V competitors. We also share how the results vary for many different configurations of our processor that can be easily converted. The obtained findings show that the transport triggered architecture is a promising option on developing application-specific processors for lattice-based post-quantum cryptography applications.

Liu and Pass (FOCS'20) recently demonstrated an equivalence between the existence of one-way functions (OWFs) and mild average-case hardness of the time-bounded Kolmogorov complexity problem. In this work, we establish a similar equivalence but to a different form of time-bounded Kolmogorov Complexity---namely, Levin's notion of Kolmogorov Complexity---whose hardness is closely related to the problem of whether $\EXP \neq \BPP$. In more detail, let $Kt(x)$ denote the Levin-Kolmogorov Complexity of the string $x$; that is, $Kt(x) = \min_{\desc \in \bitset^*, t \in \N}\{|\desc| + \lceil \log t \rceil: U(\desc, 1^t) = x\}$, where $U$ is a universal Turing machine, and $U(\desc,1^t)$ denotes the output of the program $\Pi$ after $t$ steps, and let $\mktp$ denote the language of pairs $(x,k)$ having the property that $Kt(x) \leq k$. We demonstrate that: - $\mktp \notin \HeurpBPP$ (i.e., $\mktp$ is infinitely-often \emph{two-sided error} mildly average-case hard) iff infinititely-often OWFs exist. - $\mktp \notin \AvgpBPP$ (i.e., $\mktp$ is infinitely-often \emph{errorless} mildly average-case hard) iff $\EXP \neq \BPP$. Thus, the only ``gap'' towards getting (infinitely-often) OWFs from the assumption that $\EXP \neq \BPP$ is the seemingly ``minor'' technical gap between two-sided error and errorless average-case hardness of the $\mktp$ problem. As a corollary of this result, we additionally demonstrate that any reduction from errorless to two-sided error average-case hardness for $\mktp$ implies (unconditionally) that $\NP \neq \P$.

We finally consider other alternative notions of Kolmogorov complexity---including space-bounded Kolmogorov complexity and conditional Kolmogorov complexity---and show how average-case hardness of problems related to them characterize log-space computable OWFs, or OWFs in $\NC^0$.

A splitting BIBD is a type of combinatorial design that can be used to construct splitting authentication codes with good properties. In this paper we show that a design-theoretic approach is useful in the analysis of more general splitting authentication codes. Motivated by the study of algebraic manipulation detection (AMD) codes, we define the concept of a group generated splitting authentication code. We show that all group-generated authentication codes have perfect secrecy, which allows us to demonstrate that algebraic manipulation detection codes can be considered to be a special case of an authentication code with perfect secrecy.

We also investigate splitting BIBDs that can be "equitably ordered". These splitting BIBDs yield authentication codes with splitting that also have perfect secrecy. We show that, while group generated BIBDs are inherently equitably ordered, the concept is applicable to more general splitting BIBDs. For various pairs $(k,c)$, we determine necessary and sufficient (or almost sufficient) conditions for the existence of $(v, k \times c,1)$-splitting BIBDs that can be equitably ordered. The pairs for which we can solve this problem are $(k,c) = (3,2), (4,2), (3,3)$ and $(3,4)$, as well as all cases with $k = 2$.

We introduce CryptGPU, a system for privacy-preserving machine learning that implements all operations on the GPU (graphics processing unit). Just as GPUs played a pivotal role in the success of modern deep learning, they are also essential for realizing scalable privacy-preserving deep learning. In this work, we start by introducing a new interface to losslessly embed cryptographic operations over secret-shared values (in a discrete domain) into floating-point operations that can be processed by highly-optimized CUDA kernels for linear algebra. We then identify a sequence of "GPU-friendly" cryptographic protocols to enable privacy-preserving evaluation of both linear and non-linear operations on the GPU. Our microbenchmarks indicate that our private GPU-based convolution protocol is over 150x faster than the analogous CPU-based protocol; for non-linear operations like the ReLU activation function, our GPU-based protocol is around 10x faster than its CPU analog.

With CryptGPU, we support private inference and private training on convolutional neural networks with over 60 million parameters as well as handle large datasets like ImageNet. Compared to the previous state-of-the-art, when considering large models and datasets, our protocols achieve a 2x to 8x improvement in private inference and a 6x to 36x improvement for private training. Our work not only showcases the viability of performing secure multiparty computation (MPC) entirely on the GPU to enable fast privacy-preserving machine learning, but also highlights the importance of designing new MPC primitives that can take full advantage of the GPU's computing capabilities.

We present the first Cortex-M4 implementation of the NISTPQC signature finalist Rainbow. We target the Giant Gecko EFM32GG11B which comes with 512 kB of RAM which can easily accommodate the keys of RainbowI. We present fast constant-time bitsliced F_16 multiplication allowing multiplication of 32 field elements in 32 clock cycles. Additionally, we introduce a new way of computing the public map P in the verification procedure allowing vastly faster signature verification. Both the signing and verification procedures of our implementation are by far the fastest among the NISTPQC signature finalists. Signing of rainbowIclassic requires roughly 957 000 clock cycles which 4× faster than the state of the art Dilithium2 implementation and 45× faster than Falcon-512. Verification needs about 239 000 cycles which is 5× and 2× faster respectively. The cost of signing can be further decreased by 20% when storing the secret key in a bitsliced representation.

Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). Until recently, it was widely believed that a GC proportional to the entire program, including parts of the program that are entirely discarded due to conditional branching, must be transmitted over a network. Recent work shows that this belief is false, and that communication proportional only to the longest program execution path suffices (Heath and Kolesnikov, CRYPTO 20, [HK20a]). Although this recent work reduces needed communication, it increases computation. For a conditional with $b$ branches, the players use $O(b^2)$ computation (traditional GC uses only $O(b)$).

Our scheme LogStack reduces stacked garbling computation from $O(b^2)$ to $O(b \log b)$ with no increase in communication over [HK20a]. The cause of [HK20a]'s increased computation is the oblivious collection of garbage labels that emerge during the evaluation of inactive branches. Garbage is collected by a multiplexer that is costly to generate. At a high level, we redesign stacking and garbage collection to avoid quadratic scaling.

Our construction is also more space efficient: [HK20a] algorithms require $O(b)$ space, while ours use only $O(\log b)$ space. This space efficiency allows even modest setups to handle large numbers of branches.

[HK20a] assumes a random oracle (RO). We track the source of this need, formalize a simple and natural added assumption on the base garbling scheme, and remove reliance on RO: LogStack is secure in the standard model. Nevertheless, LogStack can be instantiated with typical GC tricks based on non-standard assumptions, such as free XOR and half-gates, and hence can be implemented with high efficiency.

We implemented LogStack (in the RO model, based on half-gates garbling) and report performance. In terms of wall-clock time and for fewer than $16$ branches, our performance is comparable to [HK20a]'s; for larger branching factors, our approach clearly outperforms [HK20a]. For example, given $1024$ branches, our approach is $31\times$ faster.

While side-channel leakage is traditionally evaluated from a fabricated chip, it is more time-efficient and cost-effective to do so during the design phase of the chip. We present Pre-silicon Architecture Correlation Analysis (PACA), a hardware design analysis methodology to help designer locate and mitigate the vulnerabilities in the design at an early design stage. PACA first ranks the individual cells in a design netlist according to their contribution to the estimated side-channel leakage and points out the leaky cells. Next, we further reduce the side-channel leakage by selective replacement of the highest-leaking cells in the design with a side-channel protection version. We demonstrate that PACA’s selective replacement can significantly reduce the overhead of the countermeasure, since traditionally countermeasures are applied to the whole design. We first use a simple circuit to introduce and demonstrate the effectiveness of PACA. Then we further demonstrate that PACA can also handle complex designs by applying the overall methodology of PACA on an AES coprocessor, a PRESENT hardware cipher, and on a complex SoC. We demonstrate it is an achievable goal in the modern IC design flow to locate and mitigate the leakage source with low cost.

We present and implement SnarkPack, an argument for aggregating $n$ Groth16 zkSNARKs with a $O(\log n)$ proof size and verifier time. Our techniques are inspired from the inner pairing product argument introduced by Bünz et al. with the difference that our final scheme does not require a different trusted setup, but it reuses the one from the pairing-based SNARK that it aggregates.

The key tool for our SnarkPack construction is a new commitment scheme that allows us to instantiate the inner product pairing argument of Bünz et al. by using existing powers of tau ceremony transcripts. We also describe a scheme that merge together a multi-exponentiation argument and an inner pairing product argument for some common randomness vector with minimal overhead. We further apply some optimisations to our protocol and illustrate it's efficiency by implementing it. SnarkPack can aggregate 1024 proofs in 2s and verify them in 33ms, including un-serialization time, yielding a verification mechanism that is exponentially faster than batching.

Buldas, Laanoja, and Truu designed a family of server-assisted digital signature schemes (BLT signatures) built around cryptographic timestamping and forward-resistant tag systems. The original constructions had either expensive key generation phase or stateful client-side computations.

In this paper, we construct a stateless tag system with efficient key generation from one-time signature schemes. We prove that the proposed tag system is forward-resistant and when combined with cryptographic timestamping, it induces a secure (existentially unforgeable) multiple-time signature scheme. Our constructions are developed and verified using the EasyCrypt framework.

Shor's quantum algorithm for integer factorization and discrete logarithm is one of the fundamental approaches in modern cryptology. The application of Shor's algorithm requires a general-purpose quantum computer. On the other hand, there are known methods of transformation of factorization problem to the QUBO problem and then solving it using quantum annealing computing with approximately $\frac{n^2}{4}$ logical qubits, for example, using D-Wave computer. It is believed that this approach also may be helpful, primarily until large general-purpose quantum computers will exist. Until now algorithm of similar efficiency for computing discrete logarithm over prime fields was unknown. In this paper, we present a method of reducing discrete logarithm problem to the QUBO problem, which requires approximately $\frac{n^3}{2}$ logical qubits. We also show how to apply quantum annealing to compute discrete logarithm modulo composite numbers, where a quantum annealing factorization algorithm may be used to reduce discrete logarithm modulo composite to several discrete logarithm problems modulo prime number.

Deep learning represents a powerful set of techniques for profiling side-channel analysis. The results in the last few years show that neural network architectures like multilayer perceptron and convolutional neural networks give strong attack performance where it is possible to break targets protected with various countermeasures. Considering that deep learning techniques commonly have a plethora of hyperparameters to tune, it is clear that such top attack results can come with a high price in preparing the attack. This is especially problematic as the side-channel community commonly uses random search or grid search techniques to look for the best hyperparameters.

In this paper, we propose to use reinforcement learning to tune the convolutional neural network hyperparameters. In our framework, we investigate the Q-Learning paradigm and develop two reward functions that use side-channel metrics. We mount an investigation on three commonly used datasets and two leakage models where the results show that reinforcement learning can find convolutional neural networks exhibiting top performance while having small numbers of trainable parameters. We note that our approach is automated and can be easily adapted to different datasets. Several of our newly developed architectures outperform the current state-of-the-art results. Finally, we make our source code publicly available.

In recent years, the advent of deep neural networks opened new perspectives for security evaluations with side-channel analysis. Specifically, profiling attacks now benefit from capabilities offered by convolutional neural networks, such as dimensionality reduction, the absence of manual feature selection, and the inherent ability to reduce trace desynchronization effects. These neural networks contain at least three types of layers: convolutional, pooling, and dense layers. Although the definition of pooling layers causes a large impact on neural network performance, a study on pooling hyperparameters effect on side-channel analysis is still not provided in the academic community.

This paper provides extensive experimental results to demonstrate how pooling layer types and pooling stride and size affect the profiling attack performance with convolutional neural networks. Additionally, we demonstrate that pooling hyperparameters can be larger than usually used in related works and still keep good performance for profiling attacks on specific datasets. Finally, with a larger pooling stride and size, a neural network can be reduced in size, favoring training performance.

Functional encryption (FE) is a new paradigm of public key encryption that can control the exposed information of plaintexts by supporting computation on encrypted data. In this paper, we propose efficient multi-client FE (MCFE) schemes that compute the set intersection of ciphertexts generated by two clients. First, we propose an MCFE scheme that calculates the set intersection cardinality (MCFE-SIC) and prove its static security under dynamic assumptions. Next, we extend our MCFE-SIC scheme to an MCFE scheme for set intersection (MCFE-SI) and prove its static security under dynamic assumptions. The decryption algorithm of our MCFE-SI scheme is more efficient than the existing MCFE-SI scheme because it requires fewer pairing operations to calculate the intersection of two clients. Finally, we propose a decentralized MCFE scheme for set intersection (DMCFE-SI) that decentralizes the generation of function keys. Our MCFE schemes can be effectively applied to a privacy-preserving contact tracing system to prevent the spread of recent infectious diseases.

Real-world random number generators (RNGs) cannot afford to use (slow) cryptographic hashing every time they refresh their state $R$ with a new entropic input $X$. Instead, they use ``superefficient'' simple entropy-accumulation procedures, such as $$R \leftarrow \mathsf{rot}_{\alpha, n}(R) \oplus X,$$ where $\mathsf{rot}_{\alpha,n}$ rotates an $n$-bit state $R$ by some fixed number $\alpha$. For example, Microsoft's RNG uses $\alpha=5$ for $n=32$ and $\alpha=19$ for $n=64$. Where do these numbers come from? Are they good choices? Should rotation be replaced by a better permutation $\pi$ of the input bits?

In this work we initiate a rigorous study of these pragmatic questions, by modeling the sequence of successive entropic inputs $X_1,X_2,\ldots$ as independent (but otherwise adversarial) samples from some natural distribution family ${\mathcal D}$. Our contribution is as follows.

* We define $2$-monotone distributions as a rich family ${\mathcal D}$ that includes relevant real-world distributions (Gaussian, exponential, etc.), but avoids trivial impossibility results.

* For any $\alpha$ with $\gcd(\alpha,n)=1$, we show that rotation accumulates $\Omega(n)$ bits of entropy from $n$ independent samples $X_1,\ldots,X_n$ from any (unknown) $2$-monotone distribution with entropy $k > 1$.

* However, we also show that some choices of $\alpha$ perform much better than others for a given $n$. E.g., we show $\alpha=19$ is one of the best choices for $n=64$; in contrast, $\alpha=5$ is good, but generally worse than $\alpha=7$, for $n=32$.

* More generally, given a permutation $\pi$ and $k\ge 1$, we define a simple parameter, the covering number $C_{\pi,k}$, and show that it characterizes the number of steps before the rule $$(R_1,\ldots,R_n)\leftarrow (R_{\pi(1)},\ldots, R_{\pi(n)})\oplus X$$ accumulates nearly $n$ bits of entropy from independent, $2$-monotone samples of min-entropy $k$ each.

* We build a simple permutation $\pi^*$, which achieves nearly optimal $C_{\pi^*,k}\approx n/k$ for all values of $k$ simultaneously, and experimentally validate that it compares favorably with all rotations $\mathsf{rot}_{\alpha,n}$.