International Association
for Cryptologic Research

We show how to construct new multilinear maps from subexponentially secure indistinguishability obfuscation (iO) and (relatively) standard assumptions. In particular, we show how to construct multilinear maps with arbitrary predetermined degree of multilinearity where each of the following assumptions hold: SXDH, joint-SXDH, exponent-DDH and all other assumptions implied by them (including k-party-DDH, k-Lin and its variants). Our constructions achieve the full functionality of the “dream version” definition of multilinear maps as defined in the initial work of Garg et al. (Eurocrypt’13). Our work substantially extends a previous line of works including that of Albrecht et al. (TCC’16) and Farshim et al. (PKC’18), which showed how to build multilinear maps endowed with weaker assumptions (such as multilinear DDH and other related assumptions) from iO.

A number of recent works have shown how to build iO from multilinear maps endowed with plausible assumptions; one example would be the work of Lin and Tessaro (Crypto’17) which shows how to construct iO from subexponentially secure SXDH-hard multilinear maps and some (subexponentially secure) plausible assumptions. Coupled with any one of these constructions, our results here can be seen as formally proving the equivalence of iO and multilinear maps/graded encodings (modulo subexponential reductions and other plausible assumptions) for the first time.

Cryptographic protections are ubiquitous in information technology, including the emerging Internet of Things (IoT). As a result of technology migration to a resource-challenged landscape and new threats to cryptographic security, governments and industry are exploring new cryptographic algorithms. While new standards will emerge, however, old standards will not disappear for the time being. It is therefore important to explore platforms where multiple cryptographic deployments can be dynamically interchanged and even share resources. In this research we build on the Development Package for the Applications Programming Interface for Hardware Implementations of Lightweight Cryptography (DP API HW LWC). In this construct, developers design hardware implementations of authenticated encryption with associated data (AEAD) inside a cryptographic core (CryptoCore) encapsulated by input/output utilities. While CryptoCore is intended for single register-transfer level (RTL) implementations, we install a custom-designed soft core microprocessor inside CryptoCore to run underlying block ciphers, along with a shell to facilitate AEAD processing. Through dynamic loading and execution of block ciphers on the core, we demonstrate a single LWC deployment on an Artix-7 FPGA, capable of executing 3 NIST LWC Standardization Process Round 2 AEAD candidates (COMET-AES, COMET-CHAM and GIFT-COFB) using only 55% of the combined area of separate RTL implementations of the same ciphers.

The bit-sliding work of Jean et al. (CHES 2017) showed that the smallest-size circuit for SPN based blockciphers such as AES, SKINNY and, PRESENT can be achieved via bit-serial implementations. Their technique decreases the bitsize of the datapath, and it naturally leads to significant loss in latency (as well as the maximum throughput). Their designs complete a single round of the encryption in 168, 168 (for 128-bit blocks), 68 clock cycles (for 64-bit block) respectively. A follow-up work by Banik et al. (FSE 2020) introduced the swap-and-rotate technique that both eliminates this loss in latency and achieves even smaller footprint.

In the paper, we extend these results on bit-serial implementations all the way to three authenticated encryption schemes from NIST LWC. Our first focus is to decrease latency and improve throughput with the use of swap-and-rotate technique. Our blockcipher implementations have the most efficient round operations in the sense that a round function of a $n$-bit blockcipher is computed in exactly $n$ clock cycles. This leads to implementations that are similar in size to the state-of-the-art, but have much lower latency (savings up to 20 percent).

Though these results are promising, blockciphers themselves are not end-user primitives, as they need to used together with a mode of operation. Hence, in the second part of the paper, we use our blockciphers in bit-serial implementations for three active NIST authenticated encryption candidates: SUNDAE-GIFT, Romulus and SAEAES. We provide the smallest blockcipher-based authenticated encryption circuits known in the literature so far.

The selection criteria for NIST's Lightweight Crypto Standardization (LWC) have been slowly shifting towards the lightweight efficiency of designs, given that a large number of candidates already establish their security claims on conservative, well-studied paradigms. The research community has accumulated a decent level of experience on authenticated encryption primitives, thanks mostly to the recently completed CAESAR competition, with the advent of the NIST LWC, the de facto focus is now on evaluating efficiency of the designs with respect to hardware metrics like area, throughput, power and energy.

In this paper, we focus on a less investigated metric under the umbrella term lightweight, i.e. energy consumption. Quantitatively speaking, energy is the sum total electrical work done by a voltage source and thus is a critical metric of lightweight efficiency. Among the thirty-two second round candidates, we give a detailed evaluation of the ten that only make use of a lightweight or semi-lightweight block cipher at their core. We use this pool of candidates to investigate a list of generic implementation choices that have considerable effect on both the size and the energy consumption of modes of operation circuit, which function as an authenticated encryption primitive. Besides providing energy and circuit size metrics of these candidates, our results provide useful insights for designers who wish to understand what particular choices incur significant energy consumption in AEAD schemes. In the second part of the paper we shift our focus to threshold implementations that offer protection against first order power analysis attacks. There has been no study focusing on energy efficiency of such protected implementations and as such the optimizations involved in such circuits are not well established. We explore the simplest possible protected circuit: the one in which only the state path of the underlying block cipher is shared, and we explore how design choices like number of shares, implementation of the masked s-box and the circuit structure of the AEAD scheme affect the energy consumption.

A weak pseudorandom function $F: K \times X \to Y$ is said to be ring key-homomorphic if, given $F(k_1, x)$ and $F(k_2, x)$, there are efficient algorithms to compute $F(k_1 \oplus k_2, x)$ and $F(k_1 \otimes k_2, x)$ where $\oplus$ and $\otimes$ are the addition and multiplication operations in the ring $K$, respectively. In this work, we initiate the study of ring key-homomorphic weak PRFs (RKHwPRFs). In particular, we show that the following primitives can be constructed from any RKHwPRF:

- Multiparty non-interactive key exchange (NIKE) for an arbitrary number of parties.

- Indistinguishability obfuscation for all circuits in NC_1.

Our proofs are in the standard model, and the proof for our iO scheme is program-independent. Our iO scheme can also be bootstrapped to all polynomial-size circuits using standard techniques. We also consider restricted versions of RKHwPRFs that are structurally weaker than a classic RKHwPRF but suffice for all our constructions. We show how to instantiate these restricted RKHwPRFs from various multilinear maps and associated assumptions. Our framework gives several new results, such as:

- The first iO scheme that relies only on SXDH over any asymmetric multilinear map without additional assumptions.

- The first iO scheme that relies only on DLIN (or more generally Matrix-DDH) over any (even symmetric) multilinear map without additional assumptions.

- The first iO scheme that relies on SXDH over the multilinear map presented by Ma and Zhandry (TCC'18) (the authors only presented a NIKE protocol in their paper). To our knowledge, this candidate multilinear map has not been successfully cryptanalyzed, and the SXDH assumption plausibly holds over it.

Our analysis of RKHwPRFs in a sense completes the work initiated by Alamati et al. (EUROCRYPT'19) on building cryptosystems from generic Minicrypt primitives with structure. With our results, almost all of the major known cryptosystems can be built from a weak PRF with either a group or ring homomorphism over either the input space or the key space. Thus, a major contribution of this work is advancing the study of the relationship between structure and cryptography.

This paper introduces LUSA - the Lattice Unified Set of Algorithms library - a C++ library that comprises many high performance, parallel implementations of lattice algorithms, with particular focus on lattice-based cryptanalysis. Currently, LUSA offers algorithms for lattice reduction and the SVP. % and the CVP.

LUSA was designed to be 1) simple to install and use, 2) have no other dependencies, 3) be designed specifically for lattice-based cryptanalysis, including the majority of the most relevant algorithms in this field and 4) offer efficient, parallel and scalable methods for those algorithms.

LUSA explores paralellism mainly at the thread level, being based on OpenMP. However the code is also written to be efficient at the cache and operation level, taking advantage of carefully sorted data structures and data level parallelism.

This paper shows that LUSA delivers these promises, by being simple to use while consistently outperforming its counterparts, such as NTL, plll and fplll, and offering scalable, parallel implementations of the most relevant algorithms to date, which are currently not available in other libraries.

Event date: 27 May 2020

Applications are invited for multiple PhD student positions at the IMDEA Software Institute, Madrid, Spain.

Selected candidates will work under the supervision of Marco Guarnieri on the design, verification, and implementation of countermeasures against CPU micro-architectural attacks.

The specific topic of the research will be determined based on the common interests of the candidate and the supervisor.

The positions are fully funded by a research grant from Intel Corporation.

How to apply?

Applicants interested in the position should submit their application at https://careers.software.imdea.org/ selecting option 5 - PhD Student and reference code 2020-05-phd-uarchsec.

Questions

For any questions about these positions, please contact Marco Guarnieri directly (marco dot guarnieri at imdea dot org).

Closing date for applications:

Contact:

Marco Guarnieri, Assistant Professor @ IMDEA Software

Email: marco dot guarnieri at imdea dot org

Website: https://mguarnieri.github.io

More information: https://software.imdea.org/open_positions/2020-05-phd-uarchsec.html

We have two post-docs posts (Research Fellow and Senior Research Fellow, each for up to 4 years) available in the Department of Computer Science, University of Warwick, as part of a 4-year EPSRC project on "End to End Authentication of Caller ID in Heterogeneous Telephony Systems", working with Professor Feng Hao (PI) and Dr Adrian Von Mühlenen (co-I). The primary aim of this project is to improve security in telecommunication systems, in particular, providing reliable authentication of the caller ID without requiring any PKI, and protecting end-to-end privacy of the call contents.

The candidates will join a dynamic and growing team of security researchers in the Department of Computer Science, University of Warwick. Warwick Computer Science is ranked 1st in research output, 2nd in research impact, and 2nd overall among all computer science departments in the UK based on REF 2014. The candidates will have the flexibility to collaborate with other members in the security team on a wider range of topics, such as key exchange, e-voting, e-auction, PUF, cryptocurrency, mobile security, IoT, web security and e-payment security. Our work has been largely driven by tackling real-world security problems. Candidates who have a strong interest in working on real-world problems for practical impacts are encouraged to apply. Those who have industrial experiences are also most welcome to apply.

1. Research fellow: https://tinyurl.com/y8spmtb5
2. Senior research fellow (equivalent grade as Assistant Professor): https://tinyurl.com/ybjyqzh4

Application deadline: 17 June, 2020. After the deadline, the posts will be vacant until they are filled. Interested candidates are encouraged to contact Prof Feng Hao with an expression of interest as early as possible.

Closing date for applications:

Contact: Professor Feng Hao (feng.hao@warwick.ac.uk)

We offer one 2-year and one 3-year position as postdoctoral researcher in the area of symmetric cryptography.

The positions will be fulfilled within the Digital Security group at Radboud University in Nijmegen in the team led by Joan Daemen and Bart Mennink. Your main tasks will be to perform research and supervise that of the PhD of our ESCADA and SCALAR teams and master students. The research subjects are cryptanalysis and design of primitives, provable security of modes of use, implementation attacks and countermeasures. We concentrate on cryptography based on permutations as in the sponge, duplex and farfalle constructions. As such, we are building an alternative for block cipher based cryptography, both in the lightweight as in the high-performance arena.

There are possibilities for teaching courses within our BSc in Cyber Security program and MSc in Computer Security.

The starting date is negotiable but is preferably not later than October.

The successful candidate should ideally have a PhD in Computer Science, Mathematics, or Electrical engineering and a good publication record in the area.

Applications will be considered until the position is filled.

Closing date for applications:

Contact: Joan Daemen, joan (at) cs.ru.nl and Bart Mennink, b.mennink (at) cs.ru.nl

Oblivious RAM (ORAM) is a technique for compiling any program to an oblivious counterpart, i.e., one whose access patterns do not leak information about the secret inputs. Similarly, Oblivious Parallel RAM (OPRAM) compiles a parallel program to an oblivious counterpart. In this paper, we care about ORAM/OPRAM with perfect security, i.e., the access patterns must identically distributed no matter what the program's memory request sequence is. We show two novel results.

The first result is a new perfectly secure OPRAM scheme with $O(\log^3 N/\log \log N)$ expected overhead. In comparison, the prior literature has been stuck at $O(\log^3 N)$ for more than a decade.

The second result is a new perfectly secure OPRAM scheme with $O(\log^4 N/\log \log N)$ worst-case overhead. To the best of our knowledge, this is the first perfectly secure OPRAM scheme with polylogarithmic worst-case overhead. Prior to our work, the state of the art is a perfectly secure ORAM scheme with more than $\sqrt{N}$ worst-case overhead, and the result does not generalize to a parallel setting. Our work advances the theoretical understanding of the asymptotic complexity of perfectly secure OPRAMs.

We propose a new approach for building efficient, provably secure, and practically hardened assembly implementations of masked algorithms. Our approach is based on a Domain Specific Language in which users can write efficient assembly implementations and fine-grained leakage models. The latter are then used as a basis for formal verification, allowing for the first time formal guarantees for a broad range of leakage effects not addressed by prior work. The practical benefits of our approach are demonstrated through a case study of the PRESENT S-Box: we develop a highly optimized and provably secure masked implementation, and show through practical evaluation based on TVLA that our implementation is practically resilient. Our approach significantly narrows the gap between formal verification of masking and practical security.

Public permutations have been established as valuable primitives since the absence of a key schedule compared to block ciphers alleviates cryptanalysis. While many permutation-based authentication and encryption schemes have been proposed in the past decade, the birthday bound in terms of the primitive's block length n has been mostly accepted as the standard security goal. Thus, remarkably little research has been conducted yet on permutation-based modes with higher security guarantees. Only recently at CRYPTO'19, Chen et al showed two constructions with higher security based on the sum of two public permutation. Their work has sparked increased interest in this direction by the community. However, since their proposals were domain-preserving, the question of encryption schemes with beyond-birthday-bound security was left open. This work tries to address this gap by proposing CENCPP, a nonce-based encryption scheme from public permutations. Our proposal is a variant of Iwata's block-cipher-based mode CENC that we adapt for public permutations, thereby generalizing Chen et al.'s Sum-of-Even-Mansour construction to a mode with variable output lengths. Like CENC, our proposal enjoys a comfortable rate-security trade-off that needs w + 1 calls to the primitive for w primitive outputs. We show a tight security level for up to O(2^(2n/3)/w^2) primitive calls. While w can be arbitrary, two independent keys suffice; moreover, although we propose CENCPP first in a generic setting with w + 1 independent permutations, we show that only log_2(w + 1) bits of the input for domain separation suffice to obtain a single-permutation variant that still maintains a security level of up to O(2^(2n/3)/w^4) queries.

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

In multi-party threshold private set intersection (PSI), $n$ parties each with a private set wish to compute the intersection of their sets if the intersection is sufficiently large. Previously, Ghosh and Simkin (CRYPTO 2019) studied this problem for the two-party case and demonstrated interesting lower and upper bounds on the communication complexity. In this work, we investigate the communication complexity of the multi-party setting $(n \geq 2)$. We consider two functionalities for multi-party threshold PSI. In the first, parties learn the intersection if each of their sets and the intersection differ by at most $T$. In the second functionality, parties learn the intersection if the union of all their sets and the intersection differ by at most $T$.

For both functionalities, we show that any protocol must have communication complexity $\Omega(nT)$. We build protocols with a matching upper bound of $O(nT)$ communication complexity for both functionalities assuming threshold FHE. We also construct a computationally more efficient protocol for the second functionality with communication complexity $\tO(nT^2)$ under a weaker assumption of threshold additive homomorphic encryption.

As a consequence, we achieve the first "regular" multi-party PSI protocol where the communication complexity only grows with the size of the set difference and does not depend on the size of the input sets.

We revisit the problem of two-party private set intersection for aggregate computation which we refer to as private matching for compute. In this problem, two parties want to perform various downstream computation on the intersection of their two datasets according to a previously agreed-upon identifier. We observe that prior solutions to this problem have important limitations. For example, any change or update to the records in either party's dataset triggers a rerun of the private matching component; and it is not clear how to support a streaming arrival of one party's set in small batches without revealing the match rate for each individual batch.

We introduce two new formulations of the private matching for compute problem meeting these requirements, called private-ID and streaming private secret shared set intersection, and design new DDH-based constructions for both. Our implementation shows that when taking advantage of the inherent parallelizability of these solutions, we can execute the matching for datasets of size upto 100 million records within an hour.

In this paper we cryptanalyse the two accumulator variants proposed by Au et al., namely the $a$-based construction and the reference string-based ($RS$-based) construction. We show that if non-membership witnesses are issued according to the $a$-based construction, colluding users can efficiently discover the secret accumulator parameter $a$ and takeover the Accumulator Manager. More precisely, if $p$ is the order of the underlying bilinear group, the knowledge of $O(log(p)loglog(p))$ non-membership witnesses permits to successfully recover $a$. Further optimizations and different attack scenarios allow to reduce the number of required witnesses to $O(log(p))$, together with practical attack complexity. Moreover, we show that accumulator collision resistance can be broken if just one of these non-membership witnesses is known to the attacker.

In the case when non-membership witnesses are issued using the $RS$-based construction (with $RS$ kept secret by the Manager), we show that a group of colluding users can reconstruct the $RS$ and compute witnesses for arbitrary new elements. In particular, if the accumulator is initialized by adding $m$ secret elements, $m$ colluding users that share their non-membership witnesses will succeed in such attack.

In this paper we present a bitstream modification attack on the Trivium cipher, an international standard under ISO/IEC 29192-3. By changing the content of three LUTs in the bitstream, we reduce the non-linear state updating function of Trivium to a linear one. This makes it possible to recover the key from 288 keystream bits using at most $2^{19.41}$ operations. We also propose a countermeasure against bitstream modification attacks which obfuscates the bitstream using dummy and camouflaged LUTs which look legitimate to the attacker. We present an algorithm for injecting dummy LUTs directly into the bitstream without causing any performance or power penalty.

An encryption scheme is called indistinguishable under chosen plaintext attack (short IND-CPA), if an attacker cannot distinguish the encryptions of two messages of his choice. Alternatively there are other variants of this definition, that all turn out to be equivalent in the classical case. However in the quantum case, there is a lack of a comprehensive study of all quantum versions of IND-CPA security notion. We give an overview of these different variants of quantum IND-CPA for symmetric encryption schemes. In total, 57 different notions are valid and achievable. We investigate the relations between these notions and prove various equivalences, implications, non-equivalences, and non-implications between these variants. Some of non-implications are left as conjectures and need further research.

In Time-Specific Encryption (TSE) [Paterson and Quaglia, SCN'10] system, each secret-key (resp. ciphertext) is associated with a time period t s.t. 0<=t<=T-1 (resp. a time interval [L,R] s.t. 0<=L<=R<=T-1. A ciphertext under [L,R] is correctly decrypted by any secret-key for any time t included in the interval, i.e., L<=t<=R. TSE's generic construction from identity-based encryption (IBE) (resp. hierarchical IBE (HIBE)) from which we obtain a concrete TSE scheme with secret-keys of O(log T)|g| (resp. O(log^2 T)|g|) and ciphertexts of size O(log T)|g| (resp. O(1)|g|) has been proposed in [Paterson and Quaglia, SCN'10] (resp. [Kasamatsu et al., SCN'12]), where |g| denotes bit length of an element in a bilinear group G. In this paper, we propose another TSE's generic construction from wildcarded identity-based encryption (WIBE). Differently from the original WIBE ([Abdalla et al., ICALP'06]), we consider WIBE w/o (hierarchical) key-delegatability. By instantiating the TSE's generic construction, we obtain the first concrete scheme with constant-size secret-keys secure under a standard (static) assumption. Specifically, it has secret-keys of size O(1)|g| and ciphertexts of size O(log^2 T)|g|, and achieves security under the decisional bilinear Diffie-Hellman (DBDH) assumption.