International Association
for Cryptologic Research

In this paper, we initiate a study of asymmetric all-or-nothing transforms (or asymmetric AONTs). A (symmetric) $t$-all-or-nothing transform is a bijective mapping defined on the set of $s$-tuples over a specified finite alphabet. It is required that knowledge of all but $t$ outputs leaves any $t$ inputs completely undetermined. There have been numerous papers developing the theory of AONTs as well as presenting various applications of AONTs in cryptography and information security.

In this paper, we replace the parameter $t$ by two parameters $t_o$ and $t_i$, where $t_i \leq t_o$. The requirement is that knowledge of all but $t_o$ outputs leaves any $t_i$ inputs completely undetermined. When $t_i < t_o$, we refer to the AONT as asymmetric.

We give several constructions and bounds for various classes of asymmetric AONTs, especially those with $t_i = 1$ or $t_i = 2$. We pay particular attention to linear transforms, where the alphabet is a finite field $F_q$ and the mapping is linear.

The recent KEMTLS protocol (Schwabe, Stebila and Wiggers, CCS’20) is a promising design for a quantum-safe TLS handshake protocol. Focused on the web setting, wherein clients learn server public-key certificates only during connection establishment, a drawback compared to TLS 1.3 in terms of latency is that KEMTLS introduces an additional round trip before the server can send data. In many scenarios, including IoT and embedded settings, client devices may however have the targeted server certificate pre-loaded, so that such performance penalty seems unnecessarily restrictive.

This work proposes a variant of KEMTLS tailored to such scenarios. The protocol leverages the fact that clients know the server public keys in advance to decrease handshake latency while protecting client identities. It combines medium-lived with long-term server public keys to enable a delayed form of forward secrecy even from the first data flow on, and full forward secrecy upon the first round trip. The protocol is proved to achieve strong security guarantees, based on the security of the underlying building blocks, in a new model for multi-stage key exchange with medium-lived keys.

Established in 2020, Dfns is a cybersecurity startup operating within decentralized finance (DeFi). From our office in Paris, we are building an API for digital asset security. More specifically, Xkey provides safe, cloud-native custody as a service to help companies secure cryptos & tokens. Dfns is also a stellar team incubated at Station F (the world's biggest startup campus), the Garage (#1 blockchain ecosystem in Europe), and Techstars Future of Finance in collaboration with ABN AMRO.

We are looking for a highly motivated candidate to fill a cryptography researcher position at Dfns. Topics include:

Secure multi-party computation

Threshold Signature

Anonymity and privacy

Cryptocurrencies

Blockchain-based cryptography

Closing date for applications:

Contact: Houda Ferradi: Houda@dfns.io

More information: https://www.dfns.co/

A candidate will work in the area of post-quantum cryptography. A candidate will conduct research on code-based, lattice-based cryptography in term of design, its security and performance analysis; and possibly its applications, etc. The work requires to carry out some simulations.

Applicants are expected to have a PhD degree in Mathematics/Computer Science and a strong background in algebra, linear algebra, algebraic number theory or algebraic coding theory.

Preferred candidates are expected to be proficient in Magma software or SAGEMATH software, a team worker and able to conduct independent research.

Interested candidates will kindly include their full CV and transcripts in their applications and send to Dr Chik How Tan, tsltch@nus.edu.sg.

Only shortlisted applicants will be notified. Review of applicants will start immediately.

Closing date for applications:

Contact: Dr Chik How Tan (tsltch@nus.edu.sg)

Event date: 9 November to 11 November 2021
Submission deadline: 1 July 2021
Notification: 15 August 2021

Event date: 6 October to 8 October 2021
Submission deadline: 7 July 2021
Notification: 10 August 2021

TU Wien is Austria's largest institution of research and higher education in the fields of technology and natural sciences. The Security and Privacy research unit at the Institute of Logic and Computation at TU Wien is offering a 4-year PhD student position in symmetric cryptography.

A successful candidate should have an excellent academic record from a completed master or diploma curriculum in Mathematics, Computer Science, or related fields. Previous knowledge or experience in the area of cryptography or security is a plus.

The Security and Privacy research unit at TU Wien is internationally renowned with its expertise in the fields of cryptography, security and privacy. Our working language is English.

Formal applications must be submitted via https://jobs.tuwien.ac.at/Job/153314. We look forward to receiving your application until 29.07.2021.

Closing date for applications:

Contact: Inquiries about the position and process to Asst. Prof. Elena Andreeva elena[dot]andreeva[at]tuwien[dot]ac[dot]at

More information: https://jobs.tuwien.ac.at/Job/153314

In distributed computations and cryptography, it is desirable to record events on a public ledger, such that later alterations are computationally infeasible. An implementation of this idea is called blockchain, which is a distributed protocol that allows the creation of an immutable ledger. While such an idea is very appealing, the ledger may be contaminated with incorrect, illegal, or even dangerous data, and everyone running the blockchain protocol has no option but to store and propagate the unwanted data. The ledger is bloated over time, and it is not possible to remove redundant information. Finally, missing data cannot be inserted later. Redactable blockchains were invented to allow the ledger to be mutated in a controlled manner. To date, redactable blockchains support at most two types of redactions: block modification and removal. The next logical step is to support block insertions. However, we show that this seemingly innocuous enhancement renders all previous constructs insecure. We put forward a model for blockchains supporting all three redaction operations, and construct a blockchain that is provably secure under this formal definition.

Abstract: Side-channel attacks exploit information from the physical implementation of cryptographic systems, rather than from theoretical weaknesses. In recent years, cache attacks have made significant progress in their ability to recover secret information by combining observations of the victim's cache access and knowledge of the internal structure of the cipher. So far, cache attacks have been implemented for most Feistel-structured and SPN-structured block cipher algorithms, but the security of algorithms for special structures has little attention. In this paper, the Flush+Reload attack is performed on the implementation of MISTY1. Unlike Feistel and SPN structures, MISTY1 is a class of the block cipher with a recursive structure. The FL function is performed before the plaintext input S-box and after the ciphertext output S-box, making it difficult to attack the first and last rounds. However, we find that the key scheduling part of MISTY1 leaks many bits of key, which, together with the leakage of partial bits of the round key during encryption, was sufficient to recover the key of the MISTY1 algorithm. We design the algorithm that only needs to observe one time encryption to recover the MISTY1 128-bit key and use leakage during encryption to reduce the complexity of the algorithm. We experiment on 32-byte cache line and 64-byte cache line environment, respectively. In the 32-byte cache line environment, an adversary only needs to observe five times encryption to recover the all 128-bit key of the MISTY1 in 0.035 seconds; in the 64-byte cache line environment, an adversary needs to observe 10 times encryption to recover the entire 128-bit key in 2.1 hours.

Keywords: Side Channel, Cache attack, Flush+Reload, MISTY1, Key Scheduling Part

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