International Association
for Cryptologic Research

We initiate a systematic study of pseudorandom functions (PRFs) that are computable by simple matrix branching programs; we refer to these objects as “matrix PRFs”. Matrix PRFs are attractive due to their simplicity, strong connections to complexity theory and group theory, and recent applications in program obfuscation.

Our main results are:

* We present constructions of matrix PRFs based on the conjectured hardness of some simple computational problems pertaining to matrix products.

* We show that any matrix PRF that is computable by a read-c, width w branching program can be broken in time poly(w^c); this means that any matrix PRF based on constant-width matrices must read each input bit omega(log lambda) times. Along the way, we simplify the “tensor switching lemmas” introduced in previous IO attacks.

* We show that a subclass of the candidate local-PRG proposed by Barak et al. [Eurocrypt 2018] can be broken using simple matrix algebra.

* We show that augmenting the CVW18 IO candidate with a matrix PRF provably immunizes the candidate against all known algebraic and statistical zeroizing attacks, as captured by a new and simple adversarial model.

We investigate concretely efficient protocols for distributed oblivious linear evaluation over vectors (Vector-OLE). Boyle et al. (CCS 2018) proposed a protocol for secure distributed pseudorandom Vector-OLE generation using sublinear communication, but they did not provide an implementation. Their construction is based on a variant of the LPN assumption and assumes a distributed key generation protocol for single-point Function Secret Sharing (FSS), as well as an efficient batching scheme to obtain multi-point FSS. We show that this requirement can be relaxed, resulting in a weaker variant of FSS, for which we give an efficient protocol. This allows us to use efficient probabilistic batch codes that were also recently used for batched PIR by Angel et al. (S&P 2018). We construct a full Vector-OLE generator from our protocols, and compare it experimentally with alternative approaches. Our implementation parallelizes very well, and has low communication overhead in practice. For generating a VOLE of size $2^{20}$, our implementation only takes $0.52$s on 32 cores.

A number of important real-world protocols including the Transport Layer Security (TLS) protocol have the ability to negotiate various security-related choices such as the protocol version and the cryptographic algorithms to be used in a particular session. Furthermore, some insecure application-layer protocols such as the Simple Mail Transfer Protocol (SMTP) negotiate the use of TLS itself on top of the application protocol to secure the communication channel. These protocols are often vulnerable to a class of attacks known as downgrade attacks which targets this negotiation mechanism. In this paper we create the first taxonomy of TLS downgrade attacks. Our taxonomy classifies possible attacks with respect to four different vectors: the protocol element that is targeted, the type of vulnerability that enables the attack, the attack method, and the level of damage that the attack causes. We base our taxonomy on a thorough analysis of fifteen notable published attacks. Our taxonomy highlights clear and concrete aspects that many downgrade attacks have in common, and allows for a common language, classification, and comparison of downgrade attacks. We demonstrate the application of our taxonomy by classifying the surveyed attacks.

Multikey fully homomorphic encryption (MFHE) scheme enables homomorphic computation on data encrypted under different keys. To decrypt a result ciphertext, all the involved secret keys are required. For multi decryptor setting, decryption is a protocol with minimal interaction among parties. However, all prior schemes supporting the protocol are not secure in public channel against a passive external adversary who can see any public information not joining the protocol. Furthermore, the possible adversaries have not been defined clearly.

In this paper, we revisit the security of MFHE and present a secure one-round decryption protocol. We apply it to one of existing schemes and prove the scheme is secure against possible static adversaries. As an application, we construct a two round multiparty computation without common random string.

We propose OCEAN, an alternative miner reward system for blockchains that seeks to discourage pooling by providing a pool's variance mitigation functionality as a blockchain built-in. Our proposal relies on Succinct, Non-interactive Arguments of Knowledge (SNARKs), an advanced modern cryptographic tool that enables anyone to prove complex statements with the proof not growing in size with the complexity of the statement. We expect that blockchains that implement our proposal would see less pooling centralization than what is currently observable in deployed cryptocurrencies.

The Gimli permutation was proposed in CHES 2017 and the hash mode Gimli-Hash is now included in the Round 2 candidate Gimli in NIST's Lightweight Cryptography Standardization process. In the Gimli document, the security of the Gimli permutation has been intensively investigated. However, little is known about the security of Gimli-Hash. The designers of Gimli have claimed $2^{128}$ security against all attacks on Gimli-Hash, whose hash is a 256-bit value. Firstly, we present the trivial generic preimage attack on the structure of Gimli-Hash matching the $2^{128}$ security bound, both, in time and memory complexity. Following such a generic preimage attack framework, we then describe specific preimage attacks on 2/3/4/5 (out of 24) rounds of Gimli-Hash using divide-and-conquer methods. As will be shown, the application of the divide-and-conquer methods much benefits from the properties of the SP-box and the linear layer of Gimli. Therefore, this work can also be viewed to make the first step to exploit specific properties of the SP-box. Finally, the divide-and-conquer method was also applied to a collision attack on up to 5-round Gimli-Hash. As a support of our method, we provide a practical colliding four-block message pair for the full-state collision of 3-round Gimli-Hash. We hope our analysis can advance the understanding of Gimli-Hash.

The Number Theoretic Transform (NTT) technique is widely used in the implementation of the cryptographic schemes based on the Ring Learning With Errors problem(RLWE), since it provides efficient algorithm for multiplication of polynomials over the finite field. However, to employ NTT, the finite field is required to have some special root of unity, such as $n$-th root, which makes the module $q$ in RLWE big since we need $q\equiv 1\mod 2n$ to ensure such root exits. At Inscrypt 2018, Zhou et al. proposed a technique called preprocess-then-NTT to reduce the value of modulus $q$ while the NTT still works, and the time complexity is just a constant ($>1$) multiple of the original NTT algorithm asymptotically. In this paper, we revisit the preprocess-then-NTT technique and point out it can be improved such that its time complexity is as the same as the original NTT algorithm asymptotically. What's more, through experiments we find that even compared with the original NTT our improved algorithm may have some advantages in efficiency.

This work envisions a new encryption primitive for many-to-many paradigms such as group messaging systems. Previously, puncturable encryption (PE) was introduced to provide forward security for asynchronous messaging services. However, existing PE schemes were proposed only for one-to-one communication, and causes a significant overhead for a group messaging system. In fact, the group communication over PE can only be achieved by encrypting a message multiple times for each receiver by the sender's device, which is usually suitable to restricted resources such as mobile phones or sensor devices. Our new suggested scheme enables to re-encrypt ciphertexts of puncturable encryption by a message server (i.e., a proxy) so that computationally heavy operations are delegated to the server who has more powerful processors and a constant power source. We then proposed a new Puncturable Proxy Re-Encryption (PPRE) scheme. The scheme is inspired by unidirectional proxy re-encryption (UPRE), which achieves forward secrecy through fine-grained revocation of decryption capability by integrating the PE scheme. This paper first presents a forward secure PPRE in the group messaging service. Our scheme is IND-CCA secure under 3-weak Decision Bilinear Diffie-Hellman Inversion assumption

We construct the first adaptively secure garbling scheme based on standard public-key assumptions for garbling a circuit $C: \{0, 1\}^n \mapsto \{0, 1\}^m$ that simultaneously achieves a near-optimal online complexity $n + m + \textrm{poly}(\lambda, \log |C|)$ (where $\lambda$ is the security parameter) and \emph{preserves the parallel efficiency} for evaluating the garbled circuit; namely, if the depth of $C$ is $d$, then the garbled circuit can be evaluated in parallel time $d \cdot \textrm{poly}(\log|C|, \lambda)$. In particular, our construction improves over the recent seminal work of Garg et al. (Eurocrypt 2018), which constructs the first adaptively secure garbling scheme with a near-optimal online complexity under the same assumptions, but the garbled circuit can only be evaluated gate by gate in a sequential manner. Our construction combines their novel idea of linearization with several new ideas to achieve parallel efficiency without compromising online complexity.

We take one step further to construct the first adaptively secure garbling scheme for parallel RAM (PRAM) programs under standard assumptions that preserves the parallel efficiency. Previous such constructions we are aware of is from strong assumptions like indistinguishability obfuscation Ananth et al. (TCC 2016). Our construction is based on the work of Garg et al. (Crypto 2018) for adaptively secure garbled RAM, but again introduces several new ideas to handle parallel RAM computation, which may be of independent interests. As an application, this yields the first constant round secure computation protocol for persistent PRAM programs in the malicious settings from standard assumptions.

We present a new methodology to efficiently realize recursive composition of succinct non-interactive arguments of knowledge (SNARKs). Prior to this work, the only known methodology relied on pairing-based SNARKs instantiated on cycles of pairing-friendly elliptic curves, an expensive algebraic object. Our methodology does not rely on any special algebraic objects and, moreover, achieves new desirable properties: it is *post-quantum* and it is *transparent* (the setup is public coin).

We exploit the fact that recursive composition is simpler for SNARKs with *preprocessing*, and the core of our work is obtaining a preprocessing zkSNARK for rank-1 constraint satisfiability (R1CS) that is post-quantum and transparent. We obtain this latter by establishing a connection between holography and preprocessing in the random oracle model, and then constructing a holographic proof for R1CS.

We experimentally validate our methodology, demonstrating feasibility in practice.

We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client's query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Our protocols can provide statistical security in the two-server setting and computational security in the single-server setting. Finally, we prove that our protocols are optimal in terms of the trade-off they achieve between communication and running time.

This work shows all necessary calculations to extend the ``Practical Attribute Based Encryption: Traitor Tracing, Revocation, and Large Universe'' scheme of Liu and Wong with non-monotonic access structures. We ensure that the blackbox tracability property is preserved.

Proving the security of complex protocols is a crucial and very challenging task. A widely used approach for reasoning about such protocols in a modular way is universal composability. A perfect model for universal composability should provide a sound basis for formal proofs and be very flexible in order to allow for modeling a multitude of different protocols. It should also be easy to use, including useful design conventions for repetitive modeling aspects, such as corruption, parties, sessions, and subroutine relationships, such that protocol designers can focus on the core logic of their protocols.

While many models for universal composability exist, including the UC, GNUC, and IITM models, none of them has achieved this ideal goal yet. As a result, protocols cannot be modeled faithfully and/or using these models is a burden rather than a help, often even leading to underspecified protocols and formally incorrect proofs.

Given this dire state of affairs, the goal of this work is to provide a framework for universal composability which combines soundness, flexibility, and usability in an unmatched way. Developing such a security framework is a very difficult and delicate task, as the long history of frameworks for universal composability shows.

We build our framework, called iUC, on top of the IITM model, which already provides soundness and flexibility while lacking sufficient usability. At the core of iUC is a single simple template for specifying essentially arbitrary protocols in a convenient, formally precise, and flexible way. We illustrate the main features of our framework with example functionalities and realizations.

Trapdoor functions (TDFs) are one of the fundamental building blocks in cryptography. Studying the underlying assumptions and the efficiency of the resulting instantiations is therefore of both theoretical and practical interest.

In this work we improve the input-to-image rate of TDFs based on the Diffie-Hellman problem. Specically, we present:

\begin{enumerate}

\item A rate-1 TDF from the computational Diffie-Hellman (CDH) assumption, improving the result of Garg, Gay, and Hajiabadi [EUROCRYPT 2019], which achieved linear-size outputs but with large constants. Our techniques combine non-binary alphabets and high-rate error-correcting codes over large fields.

\item A rate-1 deterministic public-key encryption satisfying block-source security from the decisional Diffie-Hellman (DDH) assumption. While this question was recently settled by Döttling et al. [CRYPTO 2019], our scheme is conceptually simpler and concretely more efficient. We demonstrate this fact by implementing our construction.

\end{enumerate}

Abstract - Research on Side Channel Analysis (SCA) is veryactive and progressing at a fast pace. The idea of usingMachine Learning (ML), and more recently Deep Learning(DL), to help SCA data is explored extensively. One issue facingsecurity researchers interested in contributing to this cause isthe difficulties getting started. While replicating previous workswith open source code is not difficult, taking the next steps fromthere can be daunting. The presented open-source DLSCA toolis created to aid with research on DL-based SCA and to helpnewcomers to DL to get started. It is hoped to contribute toinvestigating the strengths and limitations of ML-based SCA.

Keywords - Machine Learning, Side Channel Attack, Software Tool

We address the problem of speeding up isogeny computation for supersingular elliptic curves over finite fields using untrusted computational resources like third party servers or cloud service providers (CSPs). We first propose new, efficient and secure delegation schemes. This especially enables resource-constrained devices (e.g. smart cards, RFID tags, tiny sensor nodes) to effectively deploy post-quantum isogeny-based cryptographic protocols. To the best of our knowledge, these new schemes are the first attempt to generalize the classical secure delegation schemes for group exponentiations and pairing computation to an isogeny-based post-quantum setting. Then, we apply these secure delegation subroutines to improve the performance of supersingular isogeny-based zero-knowledge proofs of identity. Our experimental results show that, at the 128−bit quantum-security level, the proving party only needs about 3% of the original protocol cost, while the verifying party’s effort is fully reduced to comparison operations. Lastly, we also apply our delegation schemes to decrease the computational cost of the decryption step for the NIST postquantum standardization candidate SIKE.

A private PEZ protocol is a variant of secure multi-party computation performed using a (long) PEZ dispenser. The original paper by Balogh et al. presented a private PEZ protocol for computing an arbitrary function with n inputs. This result is interesting, but no follow-up work has been presented since then, to the best of our knowledge. We show herein that it is possible to shorten the initial string (the sequence of candies filled in a PEZ dispenser) and the number of moves (a player pops out a specified number of candies in each move) drastically if the function is symmetric. Concretely, it turns out that the length of the initial string is reduced from O((2^n)!) for general functions in Balogh et al.'s results to O(n * n!) for symmetric functions, and 2^n moves for general functions are reduced to n^2 moves for symmetric functions. Our main idea is to utilize the recursive structure of symmetric functions to construct the protocol recursively. This idea originates from a new initial string we found for a private PEZ protocol for the three-input majority function, which is different from the one with the same length given by Balogh et al. without describing how they derived it.

Neural Networks have become a much studied approach in the recent literature on profiled side channel attacks: many articles examine their use and performance in profiled single-target DPA style attacks. This paper contributes to this ongoing discourse by taking a slightly different angle: we train networks for many intermediates of a typical AES implementation on an ARM Cortex-M0 processor, and compare their performance with classical profiling methods. Because the cost of finding good hyperparameters for networks is high, we demonstrate how to configure a network with a set of hyperparameters for a specific intermediate (SubBytes) that can also be used for learning the leakage of other intermediates. This is interesting because although we can't beat the no free lunch theorem (i.e. we find that different profiling methods excel on different intermediates), we can still get ``good value for money'' (i.e. reasonable classification results across many intermediates with reasonable profiling effort). To put the trained classifiers into side channel practice we integrate them not only into a standard profiled single-target attack on SubBytes, but we use them as part of a (multi-target) belief-propagation attack.

Middle-product learning with errors (MP-LWE) was recently introduced by Rosca, Sakzad, Steinfeld and Stehlé (CRYPTO 2017) as a way to combine the efficiency of Ring-LWE with the more robust security guarantees of plain LWE. While Ring-LWE is at the heart of efficient lattice-based cryptosystems, it involves the choice of an underlying ring which is essentially arbitrary. In other words, the effect of this choice on the security of Ring-LWE is poorly understood. On the other hand, Rosca et al. showed that a new LWE variant, called MP-LWE, is as secure as Polynomial-LWE (another variant of Ring-LWE) over any of a broad class of number fields. They also demonstrated the usefulness of MP-LWE by constructing an MP-LWE based public-key encryption scheme whose efficiency is comparable to Ring-LWE based public-key encryption. In this work, we take this line of research further by showing how to construct Identity-Based Encryption (IBE) schemes that are secure under a variant of the MP-LWE assumption. Our IBE schemes match the efficiency of Ring-LWE based IBE, including a scheme in the random oracle model with keys and ciphertexts of size $\tilde{O}(n)$ (for $n$-bit identities).

We construct our IBE scheme following the lattice trapdoors paradigm of [Gentry, Peikert, and Vaikuntanathan, STOC'08]; our main technical contributions are introducing a new leftover hash lemma and instantiating a new variant of lattice trapdoors compatible with MP-LWE.

This work demonstrates that the efficiency/security tradeoff gains of MP-LWE can be extended beyond public-key encryption to more complex lattice-based primitives.

With the rapid increase in cloud computing, concerns surrounding data privacy, security, and confidentiality also have been increased significantly. Not only cloud providers are susceptible to internal and external hacks, but also in some scenarios, data owners cannot outsource the computation due to privacy laws such as GDPR, HIPAA, or CCPA. Fully Homomorphic Encryption (FHE) is a groundbreaking invention in cryptography that, unlike traditional cryptosystems, enables computation on encrypted data without ever decrypting it. However, the most critical obstacle in deploying FHE at large-scale is the enormous computation overhead.

In this paper, we present HEAX, a novel hardware architecture for FHE that achieves unprecedented performance improvement. HEAX leverages multiple levels of parallelism, ranging from ciphertext-level to fine-grained modular arithmetic level. Our first contribution is a new highly-parallelizable architecture for number-theoretic transform (NTT) which can be of independent interest as NTT is frequently used in many lattice-based cryptography systems. Building on top of NTT engine, we design a novel architecture for computation on homomorphically encrypted data. We also introduce several techniques to enable an end-to-end, fully pipelined design as well as reducing on-chip memory consumption. Our implementation on reconfigurable hardware demonstrates 164-268× performance improvement for a wide range of FHE parameters.