International Association
for Cryptologic Research

Private set intersection and related functionalities are among the most prominent real-world applications of secure multiparty computation. While such protocols have attracted significant attention from the research community, other functionalities are often required to support a PSI application in practice. For example, in order for two parties to run a PSI over the unique users contained in their databases, they might first invoke on a support functionality to agree on the primary keys to represent their users. This paper studies a secure approach to agreeing on primary keys. We introduce and realize a functionality that computes a common set of identifiers based on incomplete information held by two parties, which we refer to as private identity agreement. We explain the subtleties in designing such a functionality that arise from privacy requirements when intending to compose securely with PSI protocols. We also argue that the cost of invoking this functionality can be amortized over a large number of PSI sessions, and that for applications that require many repeated PSI executions, this represents an improvement over a PSI protocol that directly uses incomplete or fuzzy matches.

We study the security of $\mathsf{CTR\text{-}DRBG}$, one of NIST's recommended Pseudorandom Number Generator (PRNG) designs. Recently, Woodage and Shumow (Eurocrypt' 19), and then Cohney et al. (S&P' 20) point out some potential vulnerabilities in both NIST specification and common implementations of $\mathsf{CTR\text{-}DRBG}$. While these researchers do suggest counter-measures, the security of the patched $\mathsf{CTR\text{-}DRBG}$ is still questionable. Our work fills this gap, proving that $\mathsf{CTR\text{-}DRBG}$ satisfies the robustness notion of Dodis et al. (CCS'13), the standard security goal for PRNGs.

Threshold encryption is encryption to a group of n intended recipients in such a way that any t+1 out of the n recipients together can decrypt, but t or fewer learn nothing about the message. Ad hoc threshold encryption (ATE) is threshold encryption with no trusted setup beyond a PKI (that is, all keys are generated independently). The techniques known in the ad hoc setting suffer either from ciphertexts linear in (n-t) (Daza et. al), or from reliance on cumbersome primitives like indistinguishability obfuscation (Reyzin et. al).

In this paper, we set out to determine whether we can get ATE with short ciphertexts from standard primitives. We therefore work in a model where we limit reliance on computational assumptions. We do this by demanding information theoretic security given black-box access to limited cryptographic tools such as non-interactive key exchange and pseudorandom generators.

We show that, with access only to idealized two-party key exchange, any secure ATE scheme must produce ciphertexts of size at least (n-t-1)l (where l is the length of the message). If access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes k(n-t)/2 + l (where k is the length of the input to the PRG).

If idealized q-party key exchange for q > 2 is availabe, then we can achieve a constant-size ciphertext, at the cost of invoking the key exchange an exponential number of times. We also prove that, if the size of the ciphertext is optimal (that is, equal to the size of the message), the exponential overhead is unavoidable. Finally, we give some alternative constructions demonstrating that the overhead can be reduced at the cost of slightly larger ciphertext size.

A proof of replication system is a cryptographic primitive that allows a server (or group of servers) to prove to a client that it is dedicated to storing multiple copies or replicas of a file. Until recently, all such protocols required fined-grained timing assumptions on the amount of time it takes for a server to produce such replicas.

Damg{\aa}rd, Ganesh, and Orlandi (CRYPTO' 19) proposed a novel notion that we will call proof of replication with client setup. Here, a client first operates with secret coins to generate the replicas for a file. Such systems do not inherently have to require fine-grained timing assumptions. At the core of their solution to building proofs of replication with client setup is an abstraction called replica encodings. Briefly, these comprise a private coin scheme where a client algorithm given a file $m$ can produce an encoding $\sigma$. The encodings have the property that, given any encoding $\sigma$, one can decode and retrieve the original file $m$. Secondly, if a server has significantly less than $n \cdot |m|$ bit of storage, it cannot reproduce $n$ encodings. The authors give a construction of encodings from ideal permutations and trapdoor functions.

In this work, we make three central contributions: 1) Our first contribution is that we discover and demonstrate that the security argument put forth by DGO19 is fundamentally flawed. Briefly, the security argument makes assumptions on the attacker's storage behavior that does not capture general attacker strategies. We demonstrate this issue by constructing a trapdoor permutation which is secure assuming indistinguishability obfuscation, serves as a counterexample to their claim (for the parameterization stated). 2) In our second contribution we show that the DGO19 construction is actually secure in the ideal permutation model from any trapdoor permutation when parameterized correctly. In particular, when the number of rounds in the construction is equal to $\lambda \cdot n \cdot b$ where $\lambda$ is the security parameter, $n$ is the number of replicas and $b$ is the number of blocks. To do so we build up a proof approach from the ground up that accounts for general attacker storage behavior where we create an analysis technique that we call ``sequence-then-switch''. 3) Finally, we show a new construction that is provably secure in the random oracle (or random function) model. Thus requiring less structure on the ideal function.

Identity-based encryption (IBE) is a generalization of public-key encryption (PKE) by allowing encryptions to be made to user identities. In this work, we seek to obtain IBE schemes that achieve key-dependent-message (KDM) security with respect to messages that depend on the master secret key. Previous KDM-secure schemes only achieved KDM security in simpler settings, in which messages may only depend on user secret keys. An important motivation behind studying master-KDM security is the application of this notion in obtaining generic constructions of KDM-CCA secure PKE, a primitive notoriously difficult to realize. We give the first IBE that achieves master-KDM security from standard assumptions in pairing groups. Our construction is modular and combines techniques from KDM-secure PKE based from hash-proof systems, together with IBE that admits a tight security proof in the multi-challenge setting, which happens to be unexpectedly relevant in the context of KDM security. In fact, to the best of our knowledge, this is the first setting where techniques developed in the context of realizing tightly secure cryptosystems have led to a new feasibility result. As a byproduct, our KDM-secure IBE, and thus the resulting KDM-CCA-secure PKE both enjoy a tight security reduction, independent of the number of challenge ciphertexts, which was not achieved before.

Although it is one of the most popular signature schemes today, ECDSA presents a number of implementation pitfalls, in particular due to the very sensitive nature of the random value (known as the nonce) generated as part of the signing algorithm. It is known that any small amount of nonce exposure or nonce bias can in principle lead to a full key recovery: the key recovery is then a particular instance of Boneh and Venkatesan's hidden number problem (HNP). That observation has been practically exploited in many attacks in the literature, taking advantage of implementation defects or side-channel vulnerabilities in various concrete ECDSA implementations. However, most of the attacks so far have relied on at least 2 bits of nonce bias (except for the special case of curves at the $80$-bit security level, for which attacks against $1$-bit biases are known, albeit with a very high number of required signatures).

In this paper, we uncover LadderLeak, a novel class of side-channel vulnerabilities in implementations of the Montgomery ladder used in ECDSA scalar multiplication. The vulnerability is in particular present in several recent versions of OpenSSL. However, it leaks less than $1$ bit of information about the nonce, in the sense that it reveals the most significant bit of the nonce, but with probability $<1$. Exploiting such a mild leakage would be intractable using techniques present in the literature so far. However, we present a number of theoretical improvements of the Fourier analysis approach to solving the HNP (an approach originally due to Bleichenbacher), and this lets us practically break LadderLeak-vulnerable ECDSA implementations instantiated over the sect163r1 and NIST P-192 elliptic curves. In so doing, we achieve several significant computational records in practical attacks against the HNP.

Electronic cash (e-cash) was introduced 40 years ago as the digital analogue of traditional cash. It allows users to withdraw electronic coins that can be spent anonymously with merchants. As advocated by Camenisch et al. (Eurocrypt 2005), it should be possible to store the withdrawn coins compactly (i.e., with logarithmic cost in the total number of coins), which has led to the notion of compact e-cash. Many solutions were proposed for this problem but the security proofs of most of them were invalidated by a very recent paper by Bourse et al. (Asiacrypt 2019). The same paper describes a generic way of fixing existing constructions/proofs but concrete instantiations of this patch are currently unknown in some settings. In particular, compact e-cash is no longer known to exist under quantum-safe assumptions. In this work, we resolve this problem by proposing the first secure compact e-cash system based on lattices following the result from Bourse et al. Contrarily to the latter work, our construction is not only generic, but we describe two concrete instantiations. We depart from previous frameworks of e-cash systems by leveraging lossy trapdoor functions to construct our coins. The indistinguishability of lossy and injective keys allows us to avoid the very strong requirements on the involved pseudo-random functions that were necessary to instantiate the generic patch proposed by Bourse et al.

We propose two new supersingular isogeny-based public key encryptions: SiGamal and C-SiGamal. These public key encryptions are developed by giving an additional point of the order $2^r$ to CSIDH. SiGamal seems similar to ElGamal encryption, while C-SiGamal is a compressed version of SiGamal. We prove that SiGamal and C-SiGamal obtain IND-CPA security without using hash functions under a new assumption: the P-CSSDDH assumption. This assumption comes from the expectation that no efficient algorithm can distinguish between a random point and a point that is the image of a public point under a hidden isogeny.

Next, we propose a Naor-Reingold type pseudo random function based on SiGamal. If the P-CSSDDH assumption and the CSSDDH$^*$ assumption, which guarantees the security of CSIDH that uses a prime $p$ in the setting of SiGamal, hold, then our proposed function is a pseudo random function. Moreover, we estimate computational costs of group actions to compute our proposed PRF are about $\sqrt{\frac{8T}{3\pi}}$ times than that of the group action in CSIDH, where $T$ is the Hamming weight of input of the PRF.

Finally, we experimented group actions in SiGamal and C-SiGamal. In our experimentation, the computational costs of group actions in SiGamal-512 with a $256$-bit plaintext message space are about $2.62$ times that of a group action in CSIDH-512.

A popular cryptographic option to implement Hierarchical Access Control in organizations is to combine a key assignment scheme with a symmetric encryption scheme. In brief, key assignment associates with each object in the hierarchy a unique symmetric key, and provides all higher-ranked authorized subjects with a method to recover it. This setup allows for encrypting the payloads associated with the objects so that they can be accessed by the authorized and remain inaccessible for the unauthorized. Both key assignment and symmetric encryption have been researched for roughly four decades now, and a plethora of efficient constructions have been the result. Surprisingly, a treatment of the joint primitive (key assignment combined with encryption, as used in practice) in the framework of provable security was conducted only very recently, leading to a publication in ToSC 2018(4). We first carefully revisit this publication. We then argue that there are actually two standard use cases for the combined primitive, which also require individual treatment. We correspondingly propose a fresh set of security models and provably secure constructions for each of them. Perhaps surprisingly, the two constructions call for different symmetric encryption primitives: While standard AEAD is the right tool for the one, we identify a less common tool called Encryptment as best fitting the other.

New primes were proposed for Supersingular Isogeny Key Encapsulation (SIKE) in NIST standardization process of Round 2 after further cryptanalysis research showed that the security levels of the initial primes chosen were over-estimated. In this paper, we develop a highly optimized $\mathbb{F}_{p}$ Montgomery multiplication algorithm and architecture that further utilizes the special form of SIKE prime compared to previous implementations available in the literature. We then implement SIKE for all Round 2 NIST security levels (SIKEp434 for NIST security level 1, SIKEp503 for NIST security level 2, SIKEp610 for NIST security level 3, and SIKEp751 for NIST security level 5) on Xilinx Virtex 7 using the proposed multiplier. Our best implementation (NIST security level 1) runs 29\% faster and occupies 30\% less hardware resources in comparison to the leading counterpart available in the literature and implementations for other security levels achieved similar improvement.

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