International Association
for Cryptologic Research

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.

Many cryptographic schemes have been proposed from learning with errors problems over some rings (Ring-LWE). Polynomial time quantum reduction from the approximating Shortest Independent Vectors Problem ($\textrm{SIVP}_\gamma$) for fractional ideal lattices in any algebraic number field to the average-case decision Ring-LWE for any modu- lus over the integer ring in this number field was established in the Peikert-Regev-Stephens-Davidowitz STOC 2017 paper. However the hardness of approximating SIVPpoly(n) in quantum computing was only a folklore conjecture. In this paper we prove that decision Ring- LWE for arbitrary number fields can be solved within polynomial time for infinitely many modulus parameters under a suitable bound on widths (with respect to the canonical embedding). We construct some algebraic number fields such that the decision versions of Ring-LWE with parameters in the range of Peikert-Regev-Stephens-Davidowitz K - SIV P to Ring-LWE reduction result can be solved within poly- nomial time. Our results indicate that approximating SIV Ppoly(n) for fractional ideal lattices in these algebraic number fields can be solved by a polynomial time quantum algorithm.

Anonymous communication, that is secure end-to-end and unlinkable, plays a critical role in protecting user privacy by preventing service providers from using message metadata to discover communication links between any two users. Techniques, such as Mix-net, DC-net, time delay, cover traffic, Secure Multiparty Computation and Private Information Retrieval techniques, can be used to achieve anonymous communication. However, the existing solutions are very complex and difficult to implement in practice. More importantly, they do not offer security against malicious adversaries who can arbitrarily deviate from normal protocol execution, e.g., refusing to participate and modifying messages exchanged in the protocol. In this paper, we propose a simple and novel approach to establishing anonymous communication, easily implementable with servers having only communication and storage related capabilities. Our approach offers stronger security guarantee against malicious adversaries without incurring a great deal of extra computation and communication costs. We formally prove the security guarantee of the proposed solution and analyze its pros and cons comparing to the existing work.

Boolean functions, and bent functions in particular, are considered up to so-called EA-equivalence, which is the most general known equivalence relation preserving bentness of functions. However, for a special type of bent functions, so-called Niho bent functions there is a more general equivalence relation called o-equivalence which is induced from the equivalence of o-polynomials. In the present work we study, for a given o-polynomial, a general construction which provides all possible o-equivalent Niho bent functions, and we considerably simplify it to a form which excludes EA-equivalent cases. That is, we identify all cases which can potentially lead to pairwise EA-inequivalent Niho bent functions derived from o-equivalence of any given Niho bent function. Furthermore, we determine all pairwise EA-inequivalent Niho bent functions arising from all known o-polynomials via o-equivalence.