International Association
for Cryptologic Research

Homomorphic encryption (HE) is a useful variant of public key encryption (PKE), but it has a drawback that HE cannot fully achieve IND-CCA2 security, which is a standard security notion for PKE. Beyond existing HE schemes achieving weaker IND-CCA1 security, Emura et al.\ (PKC 2013) proposed the notion of \lq\lq keyed\rq\rq{} version of HE, called KH-PKE, which introduces an evaluation key controlling the functionality of homomorphic operations and achieves security stronger than IND-CCA1 and as close to IND-CCA2 as possible. After Emura et al.'s scheme which can evaluate linear polynomials only, Lai et al.\ (PKC 2016) proposed a fully homomorphic KH-PKE, but it requires indistinguishability obfuscation and hence has a drawback in practical feasibility. In this paper, we propose a \lq\lq two-level\rq\rq{} KH-PKE scheme for evaluating degree-two polynomials, by cleverly combining Emura et al.'s generic framework with a recent efficient two-level HE by Attrapadung et al.\ (ASIACCS 2018). Our scheme is the first KH-PKE that can handle non-linear polynomials while keeping practical efficiency.

For a hyperelliptic curve defined over a finite field $\bbbf_{q^n}$ with $n>1$, the discrete logarithm problem is subject to index calculus attacks. We exploit the endomorphism of the curve to reduce the size of the factorization basis and hence improve the complexity of the index calculus attack for certain families of ordinary elliptic curves and genus 2 hyperelliptic Jacobians defined over finite fields. This approach adds an extra cost when performing operation on the factor basis, but the experiences show that reducing the size of the factor basis allows to have a gain on the total complexity of index calculus algorithm with respect to the generic attacks.

In recent years machine learning has become increasingly mainstream across industries. Additionally, Graphical Processing Unit (GPU) accelerators are widely deployed in various neural network (NN) applications, including image recognition for autonomous vehicles and natural language processing, among others. Since training a powerful network requires expensive data collection and computing power, its design and parameters are often considered a secret intellectual property of their manufacturers. However, hardware accelerators can leak crucial information about the secret neural network designs through side-channels, like Electro-Magnetic (EM) emanations, power consumption, or timing.

We propose and evaluate non-invasive and passive reverse engineering methods to recover NN designs deployed on GPUs through EM side-channel analysis. We employ a well-known technique of simple EM analysis and timing analysis of NN layers execution. We consider commonly used NN architectures, namely Multilayer Perceptron and Convolutional Neural Networks. We show how to recover the number of layers and neurons as well as the types of activation functions. Our experimental results are obtained on a setup that is as close as possible to a real-world device in order to properly assess the applicability and extendability of our methods.

We analyze the NN execution of a PyTorch python framework implementation running on Nvidia Jetson Nano, a module computer embedding a Tegra X1 SoC that combines an ARM Cortex-A57 CPU and a 128-core GPU within a Maxwell architecture. Our results show the importance of side-channel protections for NN accelerators in real-world applications.

In CRYPTO 2019, Gohr introduced deep learning into cryptanalysis, and for the first time successfully applied it to key recovery attacks on Speck32/64 reduced to 11 and 12 rounds, with complexities comparable with traditional differential cryptanalysis. In this paper, we introduce the technique of generalized neutral bits into Gohr's framework, and successfully mount the first practical key recovery attacks against 13-round Speck32/64 with time $2^{48}$ and data $2^{29}$ for a success rate of 0.21. Compared against the best differential attacks in literature with time $2^{51}$ for 12 rounds or impractical time $2^{57}$ on a single GPU for 13 rounds, the full implementation of our 13-round attack is able to complete execution within 3 days. We also extend the framework to Simon32/64, and reduce the data complexity for the practical 16-round attack from 1/6 of the codebook to $2^{21}$. This is arguably the first time to witness deep learning based cryptanalysis having a considerable advantage over traditional methods.

In this work, we propose novel side-channel assisted chosen-ciphertext attacks applicable to IND-CCA secure NTRU-based PKE/KEMs. In particular, we propose two types of chosen-ciphertext attacks on Streamlined NTRU Prime which instantiate respectively, a plaintext-checking oracle and decryption-failure oracle to perform full key recovery. We propose efficient strategies to construct chosen ciphertexts to instantiate the aforementioned oracles to perform full key recovery. We perform experimental validation of our attacks on the optimized implementation of Streamlined NTRU Prime KEM obtained from the pqm4 public library, a testing and benchmarking framework for post quantum cryptographic schemes on the ARM Cortex-M4 microcontroller. We positively confirm that both the PC and DF oracle- based attacks result in full key recovery in a few thousand traces with 100% success rate. Masking serves as a concrete countermeasure against our proposed attacks and thus our work stresses on the need for concrete masking countermeasures for the NTRU-based PKE/KEMs to protect against similar chosen-ciphertext based side-channel attacks.

Deep learning-based side-channel analysis represents a powerful option for profiling attacks on power and electromagnetic leakages as it breaks targets protected with countermeasures. While most of the papers report successful results, it is not difficult to find cases where deep learning works better or worse, especially concerning various countermeasures. Current approaches concentrate on various data augmentations or hyperparameter tuning options to make the attacks more powerful. At the same time, understanding what makes an attack difficult has received very little attention. This paper proposes a side-channel analysis methodology based on the ablation paradigm to explain how neural networks process countermeasures. Our results show that an ablation is a powerful tool as it allows to understand 1) in which layers various countermeasures are processed, 2) whether it is possible to use smaller neural network architectures without performance penalties, and 3) how to redesign neural networks to improve the attack performance when the results indicate that the target cannot be broken. By using the ablation-based approach, we manage to mount more powerful attacks or use simpler neural networks without any attack performance penalties. We hope this is just the first of the works in the direction of countermeasure explainability for deep learning-based side-channel analysis.

Searchable Symmetric Encryption (SSE) enables a client to outsource a database to an untrusted server, while retaining the ability to securely search the data. The performance bottleneck of classic SSE schemes typically does not come from their fast, symmetric cryptographic operations, but rather from the cost of memory accesses. To address this issue, many works in the literature have considered the notion of locality, a simple design criterion that helps capture the cost of memory accesses in traditional storage media, such as Hard Disk Drives. A common thread among many SSE schemes aiming to improve locality is that they are built on top of new memory allocation schemes, which form the technical core of the constructions. The starting observation of this work is that for newer storage media such as Solid State Drives (SSDs), which have become increasingly common, locality is not a good predictor of practical performance. Instead, SSD performance mainly depends on page efficiency, that is, reading as few pages as possible. We define this notion, and identify a simple memory allocation problem, Data-Independent Packing (DIP), that captures the main technical challenge required to build page-efficient SSE. As our main result, we build a page-efficient and storage-efficient data-independent packing scheme, and deduce the Tethys SSE scheme, the first SSE scheme to achieve at once O(1) page efficiency and O(1) storage efficiency. The technical core of the result is a new generalization of cuckoo hashing to items of variable size. Practical experiments show that this new approach achieves excellent performance.

We put forth a keyless wallet, a cryptocurrency wallet in which money can be spent using a password alone, and no private keys are required. It requires a smart contract blockchain. We propose two schemes. In the first, the user sets a short wallet password and can spend their money at a prespecified maturity date using the password alone. Using this as a stepping stone, we propose a second scheme, in which the user uses an OTP authenticator seed to generate a long series of time-based OTP passwords for the foreseeable future. These are encrypted and organized in a Merkle tree whose root is stored in a smart contract. The user can spend funds at any time by simply visually providing the current OTP password from an air gapped device. These OTPs can be relatively short: Just $6$ alphanumeric characters suffice. Our OTP scheme can work in proof-of-stake as well as static and variable difficulty proof-of-work blockchains. The low-entropy in the passwords and OTPs in our scheme is protected from brute force attempts by requiring that an adversary accompany any brute force attempt by a transaction on the chain. This quickly incurs enormous economic costs for the adversary. Thus, we develop the first decentralized rate limiting scheme. We use Witness Encryption (WE) to construct a timelock encryption scheme in which passwords are encrypted from past into future blocks by leveraging the NP-language expressing proof-of-work or proof-of-stake performed as the witness. Witness Encryption is a currently impractical cryptographic primitive, but our scheme may become practical as these primitives are further developed.

Abstract—CARiMoL is a novel run-time Configurable Hardware Accelerator for Ring and Module Lattice-based postquantum cryptography. It’s flexible design can be configured to key-pair generation, encapsulation, and decapsulation for NewHope and CRYSTALS-Kyber schemes using same hardware. CARiMoL offers run-time configurability for multiple security levels of NewHope and CRYSTALS-Kyber schemes, supporting both Chosen-Plaintext Attack (CPA) and Chosen-Ciphertext Attack (CCA) secure implementations. To the best of our knowledge, it is the first systematically designed full scale hardware accelerator for CCA-complaint multiple LBC schemes that supports run-time reconfigurability without the use of processor such as ARM Cortex series or soft core such as popular RISC-V processors. CARiMol performs logic sequencing on runtime and eliminates the cycle overhead associated with fetch and decode instructions. For the simultaneous use of Ring-LWE and Module-LWE, CARiMoL’s single hardware accelerator has 7x less area overhead as compared to combined standalone design of these schemes. CARiMoL exploits parallelism and extensive resource sharing among the different LBC schemes to achieve high performance and efficiency. Despite its reconfigurability, CARiMoL offers substantial speedup compared to the state-ofthe- art, i.e., 9x over NewHope-1024, 10x over NewHope-512, 17x over CRYSTALS-Kyber-1024, and 18x over CRYSTALSKyber-512.

Many interesting applications of pattern matching (e.g. deep-packet inspection or medical data analysis) target very sensitive data. In particular, spotting illegal behaviour in internet traffic conflicts with legitimate privacy requirements, which usually forces users (e.g. children, employees) to blindly trust an entity that fully decrypts their traffic in the name of security.

The compromise between traffic analysis and privacy can be achieved through searchable encryption. However, as the traffic data is a stream and as the patterns to search are bound to evolve over time (e.g. new virus signatures), these applications require a kind of searchable encryption that provides more flexibility than the classical schemes. We indeed need to be able to search for patterns of variable sizes in an arbitrary long stream that has potentially been encrypted prior to pattern identification. To stress these specificities, we call such a scheme a stream encryption supporting pattern matching.

Recent papers use bilinear groups to provide public key constructions supporting these features. These solutions are lighter than more generic ones (e.g. fully homomorphic encryption) while retaining the adequate expressivity to support pattern matching without harming privacy more than needed. However, all existing solutions in this family have weaknesses with respect to efficiency and security that need to be addressed. Regarding efficiency, their public key has a size linear in the size of the alphabet, which can be quite large, in particular for applications that naturally process data as bytestrings. Regarding security, they all rely on a very strong computational assumption that is both interactive and specially tailored for this kind of scheme.

In this paper, we tackle these problems by providing two new constructions using bilinear groups to support pattern matching on encrypted streams. Our first construction shares the same strong assumption but dramatically reduces the size of the public key by removing the dependency on the size of the alphabet, while nearly halving the size of the ciphertext. On a typical application with large patterns, our public key is two order of magnitude smaller that the one of previous schemes, which demonstrates the practicality of our approach. Our second construction manages to retain most of the good features of the first one while exclusively relying on a simple (static) variant of DDH, which solves the security problem of previous works.

Event date: 19 November 2021
Submission deadline: 25 June 2021
Notification: 13 August 2021

Applications are invited for the MS position in Information Security at the Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan. The successful candidate will work under the guidance of Arijit Karati (https://sites.google.com/site/oryjyt/home?authuser=0) on the diverse topics in Applied Cryptology.

Responsibilities: Apart from academic work, student must involve in several activities in a group or individually, such as (not limited to):

Design and implementation of security protocol.

Assesment of the security and performance metric.

Meeting with the supervisor.

Requirements: Apart from the university's basic admission policies (https://cse.nsysu.edu.tw/?Lang=en), students are desired to have following key requirements:

Strong motivation on information security.

Knowledge of modern technology.

Knowledge of Basic mathematics for cryptography.

Knowledge of at least two programming languages, such as Python/Java/C/C++.

Scholarship:

Under the university policy.

Project funding (based on availability for master students).

What students can expect:

Cooperation from the supervisor and labmates.

The rich culture in research and related activities.

Flexibility in communication, e.g., English.

What the supervisor can expect: Apart from academic and research works, students are expected to have

Good moral character.

Hardworking and dedication.

Closing date for applications:

Contact: Arijit Karati (arijit.karati@mail.cse.nsysu.edu.tw)

More information: https://cse.nsysu.edu.tw/?Lang=en

Your Tasks:
• Specification of innovative and disruptive crypto & security solutions
• Definition of crypto & security algorithms and related IP architectures
• Definition of advanced crypto protocols
• Definition of crypto & security mechanisms in hardware, firmware, etc.
• Specification and review of crypto & security architectures
• Detailed attack modeling and security mechanism specification for hardware and software blocks
• Advising and training the product and IP teams on design, implementation and test
• Root cause analysis of security defects
• Technical interface to customers, evaluation labs and to the product development team
• Certification support and technical interface with evaluator and certifier

Your Profile:
• Have a PhD/Master in Cryptography, Security or Mathematics
• Very good knowledge of cryptography (incl. symmetric and asymmetric crypto)
• Very good knowledge of discrete mathematics, algebra and number theory
• Good knowledge of SoCs and/or Secure Element products
• Good knowledge of crypto hardware implementation
• Strong security background
• Have >5 years of experience in embedded security
• Used to an independent working style
• Be willing to listen and to adapt
• Very good communication skills
• Be willing to travel

Closing date for applications:

Contact: Sebastian Stappert (sebastian.stappert@nxp.com) or Joppe Bos (joppe.bos@nxp.com)

The IMDEA Software Institute invites applications for a Software Engineer with a specialization in Cryptography. The successful candidate will collaborate closely with researchers to work on implementing and experimenting novel cryptographic protocols, including zkSNARKs, verifiable computation and homomorphic encryption schemes, and randomness generation protocols.

The ideal candidate should have:

• MS or PhD in computer science, mathematics, or a related discipline
• In-depth knowledge of cryptography (e.g., has taken a university courses)
• Solid background in math (number theory, abstract algebra) and algorithms
• Programming experience in one or more of the following languages: C, C++, Rust
• Prior experience with implementation of cryptographic protocols Familiarity with the UNIX command line and developer tools (e.g., git, svn)
• Familiarity with reading cryptography research papers will be considered positively

The position is based in Madrid, Spain, where the IMDEA Software Institute is situated. The institute provides for travel expenses and an internationally competitive salary. The working language at the institute is English. The starting date is flexible from September 2021.

How to apply? The application requires a CV and possibly the names of 2-3 persons that can provide references about you and your work. Applicants interested in the position should submit their application at https://careers.software.imdea.org/. Review of applications will start immediately and close when positions are filled or on July 2nd, 2021. We do encourage to submit applications as early as possible.

Closing date for applications:

Contact: Ignacio Cascudo (ignacio.cascudo (at) imdea.org), Dario Fiore (dario.fiore (at) imdea.org)

More information: https://software.imdea.org//open_positions/2021-05-programmer-zk.html

Differential Fault Analysis (DFA) is a well known cryptanalytic technique that exploits faulty outputs of an encryption device. Despite its popularity and similarity with the classical Differential Analysis (DA), a thorough analysis explaining DFA from a designer's point of view is missing in the literature. To the best of our knowledge, no DFA immune cipher at an algorithmic level has been proposed so far. Furthermore, all known DFA countermeasures somehow depend on the device/protocol or on the implementation such as duplication/comparison. As all of these are outside the scope of the cipher designer, we focus on designing a primitive which can protect from DFA on its own. We present the first concept of cipher level DFA resistance which does not rely on any device/protocol related assumption, nor does it depend on any form of duplication. Our construction is simple, software/hardware friendly and DFA security scales up with the state size. It can be plugged before and/or after (almost) any symmetric key cipher and will ensure a non-trivial search complexity against DFA. One key component in our DFA protection layer is an SBox with linear structures. Such SBoxes have never been used in cipher design as they generally perform poorly against differential attacks. We argue that they in fact represent an interesting trade-off between good cryptographic properties and DFA resistance. As a proof of concept, we construct a DFA protecting layer, named DEFAULT-LAYER, as well as a full-fledged block cipher DEFAULT. Our solutions compare favourably to the state-of-the-art, offering advantages over the sophisticated duplication based solutions like impeccable circuits/CRAFT or infective countermeasures.

Lattice-based schemes are promising candidates to replace the current public-key cryptographic infrastructure in wake of the looming threat of quantum computers. One of the Round 3 candidates of the ongoing NIST post-quantum standardization effort is FrodoKEM. It was designed to provide conservative security, which comes with the caveat that implementations are often bigger and slower compared to alternative schemes. In particular, the most time-consuming arithmetic operation of FrodoKEM is the multiplication of matrices with entries in Z_q. In this work, we investigate the performance of different matrix multiplication approaches in the specific setting of FrodoKEM. We consider both optimized “naïve” matrix multiplication with cubic complexity, as well as the Strassen multiplication algorithm which has a lower asymptotic run-time complexity. Our results show that for the proposed parameter sets of FrodoKEM we can improve over the state-of-the-art implementation with a row-wise blocking and packing approach, denoted as RWCF in the following. For the matrix multiplication in FrodoKEM, this results in a factor two speed-up. The impact of these improvements on the full decapsulation operation is up to 22 percent. We additionally show that for batching use-cases, where many inputs are processed at once, the Strassen approach can be the best choice from batch size 8 upwards. For a practically-relevant batch size of 128 inputs the observed speed-up is in the range of 5 to 11 percent over using the efficient RWCF approach and this speed-up grows with the batch size.

The construction of zkSNARKs involves designing a Polynomial IOP that matches with the constraint system for which it proves membership. Designing this Polynomial IOP is a challenging task because the constraint system is typically not expressed in terms of polynomials but in terms of matrices and vectors. To mitigate mismatch, we propose a new methodology for the first step in SNARK construction, that first designs a matching Vector Oracle protocol before compiling it into a Polynomial IOP. The native first-class citizens of the Vector Oracle protocol are vectors; and by virtue of matching with the language of the arithmetic constraint system, Vector Oracle protocols are more intuitive to design and analyze. The Vector-Oracle-to-PIOP compilation procedure is protocol-independent, allowing us to present and optimize it as a standalone component, leading to the discovery of a series of acceleration techniques.

We apply our methodology to construct three zkSNARKs, each targeting a constraint system: the Rank-1 Constaint System (R1CS), the Hadamard Product Relation (HPR), and a modified PLONK circuit. All three zkSNARKs achieve shorter proofs and/or smaller verification costs compared to the state-of-the-art constructions targeting the same constraint systems. Specifically, VCProof/R1CS defeats Marlin in proof size, with a slightly higher verification cost; VCProof/HPR and VCProof/POV outperform Sonic and PLONK, respectively, in both proof sizes and verification costs. In particular, the proof of VCProof/POV has only two field elements and six group elements, thus becoming the shortest among all existing universal-setup zkSNARKs.

We give an attribute-based encryption system for Turing Machines that is provably secure assuming only the existence of identity-based encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search Diffie-Hellman assumption, and the Learning with Errors assumption. Our core construction provides security against an attacker that makes a single key query for a machine $T$ before declaring a challenge string $w^∗$ that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova, and Wichs; however, to prove security we need to introduce a new notion of security called iterated simulation security. We then show how to transform our core construction into one that is secure for an a-priori bounded number $q = q(\lambda)$ of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of non-committing encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this non-committing encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from single-key adaptive security to $q$-key adaptive security.

A core goal of the NIST PQC competition is to produce public-key encryption (PKE) schemes which, even if attacked with a large-scale quantum computer, maintain the security guarantees needed by applications. The main security focus in the NIST PQC context has been IND-CCA security, but other applications demand that PKE schemes provide anonymity (Bellare et al., ASIACRYPT 2001), and robustness (Abdalla et al., TCC 2010). Examples of such applications include anonymous communications systems, cryptocurrencies, anonymous credential systems, searchable encryption, and auction protocols. Almost nothing is known about how to build post-quantum PKE schemes offering these security properties. In particular, the status of the NIST PQC finalists with respect to anonymity and robustness is unknown.

This paper offers a systematic study of anonymity and robustness for post-quantum PKE schemes. We focus on two theoretical aspects. Firstly, we study the crucial role of implicit/explicit rejection for the KEM used in the standard KEM-DEM paradigm and how it affects anonymity and robustness of the resulting PKE scheme. Secondly, we examine how the Fujisaki-Okamoto (FO) transforms (Fujisaki and Okamtoto, Journal of Cryptology 2013) confer robustness and enhance weak anonymity of a base PKE scheme to strong anonymity for the resulting KEM.

We then leverage our theoretical results to study the anonymity and robustness of the four NIST finalists: Classic McEliece, Kyber, NTRU and Saber. We exhibit a striking property of the PKE scheme obtained from the Classic McEliece KEM using the standard KEM-DEM construction: for any message 'm', we can construct a single hybrid ciphertext 'c' which decrypts to the chosen 'm' under any Classic McEliece private key. This highlights that Classic McEliece does not lead to a robust PKE scheme and presents a barrier to using our proof techniques to establish the anonymity of Classic McEliece. As a side-result of our treatment, we identify (and repair) technical gaps in the IND-CCA security claims for Saber; we also provide positive anonymity and robustness results for Saber. Similarly, we identify issues with the IND-CCA security claims for Kyber; these also act as a barrier to proving its anonymity. Finally, we describe technical barriers to applying our techniques to NTRU.

Our work, as well as being of theoretical interest, directly contributes to the broad-spectrum evaluation of NIST candidate algorithms.

The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article, we overcome this difficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area, a high-dimensional sphere, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time, despite the larger dimension of the search space, and even when considering a larger target, as demonstrated by a record computation we performed in a 521-bit finite field GF(p^6). The target finite field is of the same form than finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.