International Association
for Cryptologic Research

Building expressive encrypted databases that can scale to large volumes of data while enjoying formal security guarantees has been one of the holy grails of security and cryptography research. Searchable Encryption (SE) is considered to be an attractive implementation choice for this goal: It naturally supports basic database queries such as point, join and range, and is very practical at the expense of well-defined leakage such as search and access pattern. Nevertheless, recent attacks have exploited these leakages to recover the plaintext database or the posed queries, casting doubt to the usefulness of SE in encrypted systems. Defenses against such leakage-abuse attacks typically require the use of Oblivious RAM or worst-case padding---such countermeasures are however quite impractical. In order to efficiently defend against leakage-abuse attacks on SE-based systems, we propose SEAL, a family of new SE schemes with adjustable leakage. In SEAL, the amount of privacy loss is expressed in leaked bits of search or access pattern and can be defined at setup. As our experiments show, when protecting only a few bits of leakage (e.g., three to four bits of access pattern), enough for existing and even new more aggressive attacks to fail, SEAL query execution time is within the realm of practical for real-world applications (a little over one order of magnitude slowdown compared to traditional SE-based encrypted databases). Our findings therefore show that SEAL could be a promising approach for building efficient and robust encrypted databases.

In an article from CHES 2015, which appears in extended form in the Journal of Cryptology in 2019, Bernard, Haddad, Fischer, and Nicolai modeled the physical behavior of a transient effect ring oscillator (TERO), thereby providing a means to certify its operation as a true random number generator (TRNG). In this work, we disprove the physical assumption on which the whole model is based. Moreover, we show that the convenient use of tractable, closed-form equations stems from a mathematical error. On a more constructive note, we are the first to point out that TEROs and Bistable Ring physically unclonable functions (PUFs) are closely related, thereby not only laying the foundations of a more accurate physical model but also revealing a new design trade-off between throughput, entropy, and reliability. Furthermore, we demonstrate that most TERO implementations in the literature are prone to counter value corruptions, and propose a solution to this problem. Measurements performed on a field-programmable gate array (FPGA) substantiate our claims.

Many cryptographers have focused on lightweight cryptography, and a huge number of lightweight block ciphers have been proposed. On the other hand, designing lightweight stream ciphers is a challenging task due to the well-known security criteria, i.e., the state size of stream ciphers must be at least twice the key size. The designers of Sprout addressed this issue by involving the secret key not only in the initialization but also in the keystream generation, and the state size of such stream ciphers can be smaller than twice the key size. After the seminal work, some small-state stream ciphers have been proposed such as Fruit, Plantlet, and LIZARD. Unlike conventional stream ciphers, these small-state stream ciphers have the limitation of keystream bits that can be generated from the same key and IV pair. In this paper, our motivation is to show whether the data limitation claimed by the designers is proper or not. The correlation attack is one of the attack methods exploiting many keystream bits generated from the same key and IV pair, and we apply it to Fruit-80 and Plantlet. As a result, we can break the full Fruit-80, i.e., the designers' data limitation is not sufficient. We can also recover the secret key of Plantlet if it allows about $2^{53}$ keystream bits from the same key and IV pair.

We construct a 2-message publicly verifiable witness indistinguishable argument system for NP assuming that the Learning with Errors (LWE) problem is subexponentially hard. Moreover, the protocol is ``delayed input''; that is, the verifier message in this protocol does not depend on the instance. This means that a single verifier message can be reused many times.

We construct two variants of this argument system: one variant is adaptively sound, while the other is public-coin (but only non-adaptively sound).

We obtain our result via a generic transformation showing that the correlation intractable hash families constructed by Canetti et al. (STOC 2019) and Peikert and Shiehian (CRYPTO 2019) suffice to construct such 2-message WI arguments when combined with an appropriately chosen ``trapdoor Sigma-protocol.'' Our construction can be seen as an adaptation of the Dwork-Naor ``reverse randomization'' paradigm (FOCS '00) for constructing ZAPs to the setting of computational soundness rather than statistical soundness. Our adaptation of the Dwork-Naor transformation crucially relies on complexity leveraging to prove that soundness is preserved.

In this work we apply the systematic approach of game-based security specifications and proofs by reductions, to the design and evaluation of public key infrastructure (PKI) schemes. The importance of rigorous definitions and reduction based proofs for cryptographic primitives is well-recognized, but this approach has not yet been applied to PKI schemes, despite their importance and pervasive use. This is most problematic in case of the advanced PKI properties such as transparency, revocation transparency and non-equivocation, which are nontrivial to define, analyze and prove. In response, we propose the first Public Identity Infrastructure (PII) framework that offers rigorous yet flexible game-based security for PKI schemes. We show the feasibility of the PII framework by presenting United-$\Large \pi$, a simple, efficient and provably secure ‘proof of concept’ PKI scheme, that provably achieves all security properties we define.

Rapid advances in Internet technologies have fostered the emergence of the “software as a service” model for enterprise computing. The “Database as a Service” model provides users with the power to create, store, modify, and retrieve data from any location, as long as they have access to the Internet. As more and more datasets (including those containing private and sensitive data) are outsourced to remote / cloud storage providers, the data owner, firstly, needs to be certain of the security of data against thefts by outsiders and, secondly, the data owner needs to secure the data not only against external threats but also from untrusted service providers. The same is true for distributed applications with complex microservice architectures. However, the use of standard encryption schemes for data protection also effectively eliminates the search capability of the database service which, in turn, severely constrains the ability of the service to manage large volumes of data.

Searchable encryption (SE) is a class of cryptographic techniques that addresses these issues. SE allows a user to write encrypted data to an untrusted storage provider while retaining the ability to perform queries without decrypting the data. This can be achieved by either encrypting the data in a special way that enables queries to be executed directly on the ciphertext or by introducing a searchable encrypted index which is stored together with the encrypted data on the storage provider.

All reasonably efficient SE schemes have a common problem. They leak the search pattern that reveals whether two search queries were performed for the same keyword or not. Hence, the search pattern provides the information on the frequency of occurrence for each query. This information can be further exploited by statistical analysis, allowing an adversary to gain full knowledge about the plaintext keywords, which significantly decreases the security benefits of encrypting the data. There is no single best publicly known secure search system or a set of such techniques. The design of SE schemes is a balancing act between security, functionality, performance, and usability. This is especially true since different users will want different database architecture (SQL, NoSQL, NewSQL).

Most progress in the area of SE has been made in the setting of keyword search on encrypted documents. While this has many practical applications (i.e. email, desktop search engines, cloud document storage), much of the data produced and consumed is stored and processed in relational databases queried using SQL.

In this paper, we propose Acra Searchable Encryption (Acra SE) – a solution for secure search in an encrypted SQL database based on the blind indexing approach developing and evolving the original idea of the CipherSweet project.

Data minimization has become a paradigm to address privacy concerns when collecting and storing personal data. In this paper we present two new approaches, RSTxFM and RRTxFM, to estimate the cardinality of a dataset while ensuring differential privacy. We argue that privacy-preserving cardinality estimators are able to realize strong privacy requirements. Both approaches are based on a probabilistic counting algorithm which has a logarithmic space complexity. We combine this with a randomization technique to provide differential privacy. In our analysis, we detail the privacy and utility guarantees and expose the impact of the various parameters. Moreover, we discuss workforce analytics as application area where strong privacy is paramount.

For enabling post-quantum cryptanalytic experiments on a meaningful scale, there is a strong need for low-memory algorithms. We show that the combination of techniques from representations, multiple collision finding, and the Schroeppel-Shamir algorithm leeds to improved low-memory algorithms. For random subset sum instances $(a_1, \ldots, a_n,t)$ defined modulo $2^n$, our algorithms improve over the Dissection technique for small memory $M < 2^{0.02n}$ and in the mid-memory regime $2^{0.13n} < M < 2^{0.2n}$. An application of our technique to LPN of dimension $k$ and constant error $p$ yields significant time complexity improvements over the Dissection-BKW algorithm from Crypto 2018 for all memory parameters $M< 2^{0.35 \frac{k}{\log k}}$.

The side-channel community has recently investigated a new approach, based on deep learning, to significantly improve profiled attacks against embedded systems. Previous works have shown the benefit of using Convolutional Neural Networks (CNN) to limit the effect of some countermeasures such as desynchronization. In comparison to Template Attacks, deep learning techniques can deal with traces misalignment and the high dimensionality of the data. The pre-processing phases are no longer mandatory. However, the performance of attacks highly depend on the choice of each hyperparameters that compose a CNN architecture. Hence, we cannot perfectly harness the potential of deep neural networks without a clear comprehension of the networks inner-workings. In order to reduce this gap, we propose to clearly explain the role of each hyperparameters during the feature selection phase by using some specific visualization techniques such as Weight Visualization, Gradient Visualization and Heatmap. By highlighting which features are retained by filters, Heatmaps come in handy when a security evaluator tries to interpret and understand the efficiency of CNN. We propose a methodology for building efficient CNN architectures in terms of attack efficiency and network complexity, even in the presence of desynchronization. We evaluate our methodology on public datasets with and without desynchronization. In each case, we outperform the previous state-of-the-art CNN models while significantly reducing the network complexity. Our networks are up to 25 times more efficient than previous state-of-the-art while their complexity is up to 31810 times smaller. Our results show that CNN networks do not need to be too complex for getting good performance in the side-channel context.

In this paper we consider various methods and techniques to find the smallest circuit realizing a given linear transformation on $n$ input signals and $m$ output signals, with a constraint of a maximum depth, $maxD$, of the circuit. Additional requirements may include that input signals can arrive to the circuit with different delays, and output signals may be requested to be ready at a different depth. We apply these methods and also improve previous results in order to find hardware circuits for forward, inverse, and combined AES SBoxes, and for each of them we provide the fastest and smallest combinatorial circuits. Additionally, we propose a novel technique with ``floating multiplexers'' to minimize the circuit for the combined SBox, where we have two different linear matrices (forward and inverse) combined with multiplexers. The resulting AES SBox solutions are the fastest and smallest to our knowledge.

SAE (Simultaneous Authentication of Equals), is a password authenticated key exchange protocol, which is designed to replace the WPA2-PSK based authentication. The SAE Authentication Protocol supports the peer to peer (P2P) authentication, and is a major authentication mechanism of the Authentication and Key Management Suite (AKM). The SAE key exchange protocol and its variants, i.e, the Dragonfly key exchange protocol, have previously received some cryptanalysis, in which the authors pointed out Dragonfly protocol is vulnerable to the sub-group attack. This paper investigates some further vulnerabilities using impersonation attacks and suggests some protocol amendments for protection. It is recommended that SAE implementations should be upgraded to ensure protection against these attacks.

We give a 4-list algorithm for solving the Elliptic Curve Discrete Logarithm (ECDLP) over some quadratic field $\mathbb{F}_{p^2}$. Using the representation technique, we reduce ECDLP to a multivariate polynomial zero testing problem. Our solution of this problem using bivariate polynomial multi-evaluation yields a $p^{1.314}$-algorithm for ECDLP. While this is inferior to Pollard's Rho algorithm with square root (in the field size) complexity $\mathcal{O}(p)$, it still has the potential to open a path to an $o(p)$-algorithm for ECDLP, since all involved lists are of size as small as $p^{\frac 3 4}$, only their computation is yet too costly.

Physical Unclonable Functions (PUFs) and, in particular, XOR Arbiter PUFs have gained much research interest as an authentication mechanism for embedded systems. One of the biggest problems of (strong) PUFs is their vulnerability to so called machine learning attacks. In this paper we take a closer look at one aspect of machine learning attacks that has not yet gained the needed attention: the generation of the sub-challenges in XOR Arbiter PUFs fed to the individual Arbiter PUFs. Specifically, we look at one of the most popular ways to generate sub-challenges based on a combination of permutations and XORs as it has been described for the "Lightweight Secure PUF". Previous research suggested that using such a sub-challenge generation increases the machine learning resistance significantly.

Our contribution in the field of sub-challenge generation is three-fold: First, drastically improving attack results by Rührmair et al., we describe a novel attack that can break the Lightweight Secure PUF in time roughly equivalent to an XOR Arbiter PUF without transformation of the challenge input. Second, we give a mathematical model that gives insight into the weakness of the Lightweight Secure PUF and provides a way to study generation of sub-challenges in general. Third, we propose a new, efficient, and cost-effective way for sub-challenge generation that mitigates the attack strategy we used and outperforms the Lightweight Secure PUF in both machine learning resistance and resource overhead.

To deal with dynamically changing user's credentials in identity-based encryption (IBE), providing an efficient key revocation method is a very important issue. Recently, Ma and Lin proposed a generic method of designing a revocable IBE (RIBE) scheme that uses the complete subtree (CS) method by combining IBE and hierarchical IBE (HIBE) schemes. In this paper, we propose a new generic method for designing an RIBE scheme that uses the subset difference (SD) method instead of using the CS method. In order to use the SD method, we generically design an RIBE scheme by combining IBE, identity-based revocation (IBR), and two-level HIBE schemes. If the underlying IBE, IBR, and HIBE schemes are adaptively (or selectively) secure, then our RIBE scheme is also adaptively (or selectively) secure. In addition, we show that the layered SD (LSD) method can be applied to our RIBE scheme and a chosen-ciphertext secure RIBE scheme also can be designed generically.

In the last few years, post-quantum cryptography has received much attention. NIST is running a competition to select some post-quantum schemes as standard. As a consequence, implementations of post-quantum schemes have become important and with them side-channel attacks. In this paper, we show a timing attack on a code-based scheme which was submitted to the NIST competition. This timing attack recovers secret information because of a timing variance in finding roots in a polynomial. We present four algorithms to find roots that are protected against remote timing exploitation.

With continuously shrinking feature sizes of integrated circuits, the vast majority of semiconductor companies have become fabless, i.e., chip manufacturing has been outsourced to foundries across the globe. However, by outsourcing critical stages of IC fabrication, the design house puts trust in entities which may have malicious intents. This exposes the design industry to a number of threats, including piracy via unauthorized overproduction and subsequent reselling on the black market. One alleged solution for this problem is logic locking, also known as logic encryption, where the genuine functionality of a chip is ``locked'' using a key only known to the designer. If a correct key is provided, the design works as intended but with an incorrect key, the circuit produces faulty outputs. As the keys are inserted by the designer after production, an adversarial foundry should not be able to unlock overproduced chips.

In this work, we highlight major shortcomings of proposed logic locking schemes. They are primarily due to the absence of a well-defined and realistic attacker model in the current literature. To this end, we characterize physical capabilities of a malicious foundry, especially with respect to invasive attacks. This allows us to derive an attacker model that matches reality, yielding attacks against the foundations of locking schemes beyond the usually employed SAT-based attacks. Our analysis shows that no previously proposed logic locking scheme is able to achieve the intended protection goals against piracy in real-world scenarios. As an important conclusion, we argue that there are strong indications that logic locking will most likely never be secure against a determined malicious foundry.

Single-trace side-channel attacks are a considerable threat to implementations of classic public-key schemes. For lattice-based cryptography, however, this class of attacks is much less understood, and only a small number of previous works show attacks. Primas et al., for instance, present a single-trace attack on the Number Theoretic Transform (NTT), which is at the heart of many efficient lattice-based schemes.

They, however, attack a variable-time implementation and also require a rather powerful side-channel adversary capable of creating close to a million multivariate templates. Thus, it was an open question if such an attack can be made practical while also targeting state-of-the-art constant-time implementations.

In this paper, we answer this question positively. First, we introduce several improvements to the usage of belief propagation, which underlies the attack. And second, we change the target to encryption instead of decryption; this limits attacks to the recovery of the transmitted symmetric key, but in turn, increases attack performance. All this then allows successful attacks even when switching to univariate Hamming-weight templates. We evaluate the performance and noise resistance of our attack using simulations, but also target a real device. Concretely, we successfully attack an assembly-optimized constant-time Kyber implementation running on an ARM Cortex M4 microcontroller while requiring the construction of only 213 templates.

RISC-V is a promising free and open-source instruction set architecture. Most of the instruction set has been standardized and several hardware implementations are commercially available. In this paper we highlight features of RISC-V that are interesting for optimizing implementations of cryptographic primitives. We provide the first optimized assembly implementations of table-based AES, bitsliced AES, ChaCha, and the Keccak-$f$[1600] permutation for the RV32I instruction set. With respect to public-key cryptography, we study the performance of arbitrary-precision integer arithmetic without a carry flag. We then estimate the improvement that can be gained by several RISC-V extensions. These performance studies also serve to aid design choices for future RISC-V extensions and implementations.

We study a question whether the currently known families of quadratic APN polynomials are pairwise different up to CCZ-equivalence. We reduce the list of these families to those CCZ-inequivalent to each other. In particular, we prove that the families of APN trinomials (constructed by Budaghyan and Carlet in 2008) and multinomials (constructed by Bracken et al. 2008) are CCZ-equivalent to the APN hexanomial family introduced by Budaghyan and Carlet in 2008. We also prove that a generalization of these trinomial and multinomial families given by Duan et al. (2014) is CCZ-equivalent to the family of hexanomials as well.

Currently, a lightweight blockchain client cannot verify a transaction directly. Rather, it generally considers a transaction to be valid and finalized if there are six confirmations on this transaction. This is not desired for micro-payments where payees may opt for zero-confirmation. When a payee chooses to accept zero-confirmation transactions, it needs to verify the validity of the transaction. In particular, one of the steps is to verify that the input of the transaction is not previously spent. This requires the payee to either trust some full nodes to perform the verification, or download the entire blockchain in order to perform the verification locally. The former is less secure as anyone can be a full node, it cannot be blindly trusted; the latter is not desired since a blockchain is large in size and is ever growing. We propose TICK, a Tiny Client for blockchains, to solve this problem. TICK advances blockchain client in the following aspects. First, TICK allows a mobile device to efficiently and cryptographically verify whether an input of a transaction is previously spent or not. Second, TICK can be adapted without changing the current implementation of the blockchain, such as Bitcoin. Rather, it only requires miners to put an extra hash value in the free field of a block. Last, as a side effect, rather than requiring new miners to download the entire blockchain to performmining,theTICKdesignallowsnewminerstodownload only a small portion of data to start mining. We implement TICK for Bitcoin, and provide an experimental evaluation on its performance by using the current Bitcoin blockchain data. Our result shows that the proof for verifying whether an input of a transaction is spent or not is only less than 2KB. The verification is very fast – a mobile client only needs to compute a few dozens of hash values. In addition, to start mining, new miners only need to download a few GB data, rather than downloading over 200 GB data.