International Association
for Cryptologic Research

The security in the quantum setting of a series of message authentication codes (MACs) with provable beyond-birthday-bound (BBB) security is analyzed in this paper, including SUM-ECBC, PolyMAC, PMAC_Plus, 3kf9 and some variants (2K-ECBC_Plus, GCM-SIV2, 1k-PMAC_Plus, 2K-PMAC_Plus, PMAC_TBC3k and 2kf9). All these MACs have a security proof up to $2^{2n/3}$ (even $2^{3n/4}$) queries assuming the block size of the underlying (tweakable) block cipher is $n$ bits. Given that the adversary can make quantum queries, we consider secret state recovery and partial key recovery attacks against these MACs. Both attacks lead to successful forgeries. For the first one, we apply Grover-meet-Simon algorithm to recover some secret states of SUM-ECBC, PolyMAC, PMAC_Plus, 3kf9 and so on. Our research shows this forgery attack costs at most $O(2^{n/2}n)$ quantum queries using at most $O(n^{2})$ qubits. For the second one, we apply Grover's algorithm to recover partial keys of PMAC_Plus, 3kf9, PMAC_TBC3k and so on. Our research shows this forgery attack costs $O(2^{m/2})$ quantum queries and $O(m+n^2)$ qubits assuming the size of one key is $m$ bits. As far as we know, these are the first quantum attacks against BBB MACs. Our results show that in the quantum setting their securities go back to birthday bounds.

We implement bootstrapping of RNS-CKKS on SEAL, a homomorphic encryption library released by Microsoft. And we measure the accuracy of encrypted data after bootstrapping for various parameters, which allows us to do more than thousands of homomorphic operations.

In this work, we present the first post-quantum secure Updatable Public-Key Encryption (UPKE) construction. UPKE has been proposed in the literature as a mechanism to improve the forward-secrecy and post-compromise security of secure messaging protocols, but the hardness of all existing constructions to date rely on discrete logarithm assumptions. We focus our assessment on isogeny-based cryptosystems due to their suitability for performing a potentially unbounded number of update operations, a practical requirement for secure messaging where user conversations can occur over months, if not years.

We begin by formalizing two UPKE variants presented in the literature as Symmetric and Asymmetric UPKE. At a fundamental level, these variants differ in how encryption and decryption keys are updated, and consequently impact the design and security model for quantum-safe constructions.

We demonstrate that Asymmetric UPKE cannot be instantiated using existing isogeny-based constructions. We then describe a SIDH-based Symmetric UPKE construction that is possible in theory but requires improving existing mathematical limitations before a practical implementation is possible. Finally, we present a CSIDH-based Symmetric UPKE construction that can be instantiated using a parameter set in which the class group structure is fully known to ensure efficient uniform sampling and canonical representation to prevent leakage of secret keys. We discuss several open problems which are applicable to any cryptosystem with similar requirements for continuous operations over elements in the secret domain.

Imagine that one or more non-colluding servers each holds a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrieval (PIR) schemes achieve polylogarithmic bandwidth per query, but require the server to perform linear computation per query, which is a deal breaker with respect to practical adoption.

Several recent works have shown, however, that by introducing a one-time, per-client, off-line preprocessing phase, an \emph{unbounded} number of client queries can be subsequently served with sublinear on-line computation time per query (and the cost of the preprocessing can be amortized over the unboundedly many queries). Unfortunately, existing preprocessing PIRs make undesirable tradeoffs to achieve sublinear online computation: they either require $\sqrt{n}$ or more bandwidth per query, which is asymptotically worse than classical PIR schemes, or they require the servers to store a linear amount state per client (or even per query), or require polylogarithmically many non-colluding servers.

We propose a novel 2-server preprocessing PIR scheme that achieves $\widetilde{O}(\sqrt{n})$ online computation per query, while preserving the polylogarithmic online bandwidth of classical PIR schemes. In our construction, each server stores only the original database and nothing extra, and each online query is served within a single round trip. Our construction relies on the standard LWE assumption. As an important stepping stone, we propose new, more generalized definitions for a cryptographic object called a Privately Puncturable Pseudorandom Set, and give novel constructions that depart significantly from prior approaches.

Suppose that $n$ players want to elect a random leader and they communicate by posting messages to a common broadcast channel. This problem is called leader election, and it is fundamental to the distributed systems and cryptography literature. Recently, it has attracted renewed interests due to its promised applications in decentralized environments.

In a game theoretically fair leader election protocol, roughly speaking, we want that even majority coalitions cannot increase its own chance of getting elected, nor hurt the chance of any honest individual. The folklore tournament-tree protocol, which completes in logarithmically many rounds, can easily be shown to satisfy game theoretic security. To the best of our knowledge, no sub-logarithmic round protocol was known in the setting that we consider.

We show that by adopting an appropriate notion of approximate game-theoretic fairness, and under standard cryptographic assumption, we can achieve $(1-1/2^{\Theta(r)})$-fairness in $r$ rounds for $\Theta(\log \log n) \leq r \leq \Theta(\log n)$, where $n$ denotes the number of players. In particular, this means that we can approximately match the fairness of the tournament tree protocol using as few as $O(\log \log n)$ rounds. We also prove a lower bound showing that logarithmically many rounds is necessary if we restrict ourselves to ``perfect'' game-theoretic fairness and protocols that are ``very similar in structure'' to the tournament-tree protocol.

Although leader election is a well-studied problem in other contexts in distributed computing, our work is the first exploration of the round complexity of {\it game-theoretically fair} leader election in the presence of a possibly majority coalition. As a by-product of our exploration, we suggest a new, approximate game-theoretic fairness notion, called ``approximate sequential fairness'', which provides a more desirable solution concept than some previously studied approximate fairness notions.

Looking for a top PhD program in English that you can start after BSc or MSc?

CS@max planck is a highly selective doctoral program that grants admitted students full financial support to pursue research in the broad area of computer and information science, with faculty at Max Planck Institutes and some of the best German universities. The faculty at the Max Planck Institute for Security and Privacy (MPI-SP) is also part of this program.

To qualify for the program, students must hold a Bachelor’s or Master’s degree in computer science (or a related field) and have an outstanding academic record. We especially encourage applications from students who wish to explore research across the CS spectrum before committing to a topic and advisor.

For more information about CS@max planck, see here: https://www.cis.mpg.de/graduate-programs/cs-max-planck

The next upcoming application deadline is 31 December 2020.

Closing date for applications:

Contact: csmaxplanck@cis.mpg.de

More information: https://www.cis.mpg.de/graduate-programs/cs-max-planck

This Ph.D. position is funded for EU and UK students, and the application deadline is on the 24th of January 2021.

In recent years, the use of solvers (SAT, MILP, CP...) to solve cryptanalysis problems has become prominent. The aim of this Ph.D. is to develop a fully automated framework based on these solvers for the cryptanalysis of block ciphers, starting with differential cryptanalysis. In particular, non-trivial modeling strategies are sometimes necessary to improve the resolution and scale up[1]. An important part of the task will be to derive efficient ways to model different types of ciphers, and compare which method (among MILP, CP, SAT) works best for each types of building blocks.

This position is fully funded, with a stipend of 16 000 GBP per year, and successful applicants are expected to start in April 2021.

[1] David Gerault, Pascal Lafourcade, Marine Minier, Christine Solnon: Computing AES related-key differential characteristics with constraint programming. Artificial Intelligence 278 (2020)

Closing date for applications:

Contact: David Gerault (david.gerault@surrey.ac.uk)

More information: https://www.surrey.ac.uk/fees-and-funding/studentships/phd-studentships-computer-science

The Department of Computer Science at New Jersey Institute of Technology (NJIT) seeks candidates to fill a University Lecturer/Senior University Lecturer position. Candidates are expected to teach courses under the umbrella of Cybersecurity, in support of our graduate and undergraduate programs. Applicants must have at least an MS degree in Computer Science or in a related computing area. A PhD degree and prior university teaching experience are an advantage.

Successful candidates must have an expert grasp of knowledge of Cybersecurity at all levels, with an emphasis on hands-on applied cybersecurity skills, either through a demonstrated record of teaching excellence, or through industrial experience. The successful candidate will also be involved in creating course content and materials with a focus on hands-on experiential and project-based learning. Strong written, oral and interpersonal skills are required in order to communicate effectively with students in person and online. The formal education and experience prerequisites may be waived at the university’s discretion if the candidate can demonstrate to the satisfaction of the university an equivalent combination of education and experience specifically preparing the candidate for success in the position.

Interested applicants should submit their CV and at least two references by applying as soon as possible at: https://njit.csod.com/ats/careersite/JobDetails.aspx?site=1&id=2600

Work environment and location: The Computer Science department, part of the Ying Wu College of Computing Sciences, is the largest at NJIT, comprising one tenth of the student population. It is also the largest computer science department among all research universities in the New York metropolitan area.​ Located in Northern New Jersey, within the greater New York Metropolitan area, NJIT is part of a vibrant ecosystem of research universities and corporate research centers.

Closing date for applications:

Contact: reza.curtmola@njit.edu

More information: https://njit.csod.com/ats/careersite/JobDetails.aspx?site=1&id=2600

The position will be part of the Coding Theory and Cryptology (CC) group, within the Discrete Mathematics (DM) cluster. The other group in DM is Discrete Algebra and Geometry. The CC group consists of one full professor (Lange), two associate professors (Schoenmakers and de Weger), and three assistant professors (Ashur, Hülsing and Ravagnani). CC provides undergraduate and graduate courses in cryptology, coding theory, algebra and number theory, as well as service teaching.

CC and the Security (SEC) group of Etalle form the Eindhoven Institute for the Protection of Systems and Information (Ei/ Ψ) which covers the whole technical spectrum of information security. Ei/ Ψ organizes the master's track Information Security Technology within the Computer Science program at TU/e.

The ideal candidate has research experience complementing the existing strengths in CC and SEC but candidates from all areas of cryptology including neighboring fields such as software security, side-channel attacks, reverse engineering, etc. are encouraged to apply.

The assistant professor is expected to

• perform outstanding research in the area of cryptology and security;
• establish research collaborations within the department and nternationally;
• take responsibility in coordinating and updating courses; advise BSc, MSc, and PhD students;
• initiate, acquire and coordinate research projects;
• perform managerial and/or administrative tasks for the cluster or department.

Applications need to be submitted via the URL below. Deadline is 16 Feb 2021.

Closing date for applications:

Contact: Tanja Lange tanja@hyperelliptic.org

More information: https://jobs.tue.nl/en/vacancy/assistant-professor-in-cryptology-868539.html

Random beacon protocols provide a continuous public source of randomness and their applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols in the bounded synchronous model sacrifice either the fault tolerance or the communication complexity for security, or ease of reconfigurability. This work overcomes the challenges with the existing works through a novel communication efficient combination of state machine replication and (publicly) verifiable secret sharing (PVSS/VSS) protocols.

We first design a new Byzantine fault-tolerant state machine replication protocol with $O(\kappa n^2)$ bits communication per consensus decision without using threshold signatures. Next, we design GRandPiper (Good Pipelined Random beacon), a random beacon protocol with bias-resistance and unpredictability, that uses PVSS and has a communication complexity of $O(\kappa n^2)$ always (best and worst cases), for a static adversary. However, GRandPiper allows an adaptive adversary to predict beacon values up to $t+1$ epochs into the future. Therefore, we design BRandPiper (Better RandPiper), that uses VSS and has a communication complexity of $O(\kappa fn^2)$, where $f$ is the actual number of faults, while offering a strong unpredictability with an advantage of only a single round even for an adaptive adversary.

Auxiliary-input idealized models, such as the auxiliary-input random oracle model and the auxiliary-input random permutation model, play a critical role in assessing non-uniform security of symmetric-key and hash-function constructions. However, obtaining security bounds in these models are often much more challenging than in traditional idealized models.

The presampling technique, introduced by Unruh (CRYPTO' 07), generically reduces security proofs in the auxiliary-input models to a much simpler bit-fixing models. This technique has been further optimized by Coretti, Dodis, Guo, Steinberger (EUROCRYPT' 18), and generalized by Coretti, Dodis, Guo (CRYPTO' 18), resulting in powerful tools for proving non-uniform security bounds in various idealized models, including random oracle models (ROM), random permutation models (RPM), ideal cipher models (ICM) and generic group models (GGM). We study the possibility of unifying and leveraging the presampling technique to the quantum world. To this end,

* We show that such leveraging will resolve a major open problem in quantum computing, which is closely related with the famous Aaronson-Ambainis conjecture (ITCS' 11).

* Faced with this barrier, we give a new but equivalent bit-fixing model and a simple proof of presampling techniques for arbitrary oracle distribution and access in the classical setting, including AI-ROM and AI-RPM. Our security loss matches the security loss of the best known presampling technique by Coretti et al. (EUROCRYPT' 18) for both indistinguishability and unpredictability applications. Our new proof unifies previous results by Coretti et al. (EUROCRYPT' 18) and Coretti et al. (CRYPTO' 18).

* We leverage our new classical presampling techniques to a novel ``quantum bit-fixing version'' of presampling. The security loss of our quantum bit-fixing presampling also matches the optimal security loss of the classical presampling. Using our techniques, we give the first post-quantum non-uniform security bounds for salted Merkle-Damgard hash functions.

We introduce the notion of Deniable Fully Homomorphic Encryption and provide constructions based on the circular-secure Learning With Errors polynomial hardness assumption. Deniable fully homomorphic encryption offers a compelling upgrade of deniable public key encryption suitable for the motivating applications of deniability, such as prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption, or storing encrypted data in the cloud, to be processed securely, in a deniable way. Our constructions enjoy deniability compactness, namely both the size of the public key and the size of the ciphertext of our schemes can be bounded by a fixed polynomial, independent of the level of deniability (or faking probability) achieved by the scheme. Additionally, our constructions support large message spaces and are well suited to an online-offline model of encryption, where the bulk of computation is independent of the message and may be performed in an offline pre-processing phase. This leads to a very efficient online phase, whose running time is independent of the faking probability, whereas the offline encryption run-time grows with the inverse of the faking probability.

In contrast, all prior constructions even in the context of deniable public key encryption without homomorphic properties, encoded large messages bit by bit, where the ciphertext for each bit grew inversely with the faking probability. Indeed, all previous constructions from polynomial hardness assumptions have both the public key and ciphertext size that grows with the inverse of the faking probability achieved by the scheme. This limitation dates back to the seminal work of Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) which introduced the notion of deniable encryption, and has been inherited by all subsequent work (excepting one by Sahai and Waters (STOC 2013) which is based on indistinguishability obfuscation. Indeed Canetti et al. argued that this dependence ``seems inherent''. Our constructions imply deniable public key encryption with deniability compactness, showing that this dependence is not inherent. However, the running time of our encryption algorithm does depend on the inverse of the faking probability, thus falling short of achieving simultaneously negligible deniability and polynomial encryption time.

At the heart of our constructions is a new way to use bootstrapping to obliviously generate FHE ciphertexts so that it supports faking under coercion.

We initiate a study, when $F$ is a general APN function, of the Boolean function $\gamma_F$ related to the differential spectrum of $F$ (which is known to be bent if and only if $F$ is almost bent). We first list many open questions about it. We study its algebraic normal form and its bivariate representation. We characterize its linear structures and specify nonexistence cases; we show, for $n$ even, their relation with bent components $v\cdot F$, $v\neq 0_n$, of $F$. We pose three related open problems. We characterize further in terms of $\gamma_F$ the fact that a component function of $F$ is bent and study if the number of bent components can be optimal. We consider in particular two classes, one of which is that of APN power functions. We study more deeply the relation between the Walsh transform of $\gamma_F$ and the Walsh transform of $F$. By applying the Titsworth relation to the Walsh transform $W_{\gamma_F}$, we deduce a very simple new relation satisfied by $W_F^2$. From this latter relation, we deduce, for a sub-class of APN functions, a lower bound on the nonlinearity, that is significantly stronger than $nl(F)>0$ (the only general known bound). This sub-class of APN functions includes all known APN functions. The question (which is another open problem that we state) arises whether this sub-class equals that of all APN functions, but our bound provides at least a beginning of explanation why all known APN functions have non-weak nonlinearity. We finally show how the nonlinearities of $\gamma_F$ and $F$ are related by a simple formula; this leads to a last open problem.

The programming languages community, the cryptography community, and others rely on translating programs in high-level source languages (e.g., C) to logical constraint representations. Unfortunately, building compilers for this task is difficult and time consuming. In this work, we show that all of these communities can build upon a shared compiler infrastructure, because they all share a common abstraction: stateless, non-deterministic computations that we call existentially quantified circuits, or EQCs.

To make our approach concrete we create CirC, an infrastructure for building compilers to EQCs. CirC makes it easy to add support for new EQCs: we build support for two, one used by the PL community and one used by the cryptography community, in $\approx$2000 LOC. It’s also easy to extend CirC to support new source languages: we build a feature complete compiler for a cryptographic language in one week and $\approx$700 LOC, whereas the reference compiler for the same language took years to write, comprises $\approx$24000 LOC, and produces worse-performing output than our compiler. Finally, CirC enables novel applications that combine multiple EQCs. For example, we build the first pipeline that (1) automatically identifies bugs in programs, then (2) automatically constructs cryptographic proofs of the bugs’ existence.

Semi-regular sequences over $\mathbb{F}_2$ are sequences of homogeneous elements of the algebra $ B^{(n)}=\mathbb{F}_2[X_1,...,X_n]/(X_1^2,...,X_n^2) $, which have a given Hilbert series and can be thought of as having as few relations between them as possible. It is believed that most such systems are semi-regular and this property has important consequences for understanding the complexity of Grobner basis algorithms such as F4 and F5 for solving such systems. We investigate the case where the sequence has length two and give an almost complete description of the number of semi-regular sequences for each $n$.

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. All currently used, public-key cryptography algorithms would be deemed insecure in a post-quantum setting. In response, the United States National Institute of Standards and Technology has initiated a process to standardize quantum-resistant cryptographic algorithms, focusing primarily on their security guarantees. Additionally, the Internet Engineering Task Force has published two quantum-secure signature schemes and has been looking into adding quantum-resistant algorithms in protocols. In this work, we investigate two post-quantum, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use in secure boot. We evaluate various parameter sets for the use-cases in question and we prove that post-quantum signatures would not have material impact on image signing. We also study the hierarchical design of these signatures in different scenarios of hardware secure boot.

We propose HERMES, a scalable, secure, and privacy-enhancing system, which allows users to share and access vehicles. HERMES outsources the vehicle access token generation to a set of untrusted servers, utilizing several cryptographic primitives with secure multi-party computation efficiently. It conceals the vehicle secret keys and transaction details from the servers such as vehicle booking details, access token information, and user-vehicle identities. It also provides user accountability in case of disputes. We prove that HERMES meets its security and privacy requirements. Moreover, we demonstrate that HERMES scales for a large number of users and vehicles, making it practical for real-world deployments. To achieve high-performance computations, we evaluate HERMES over two different multiparty computation protocols for Boolean and arithmetic circuits. We provide a detailed comparison of their performance, together with other state-of-the-art access provision protocols. Through a proof-of-concept implementation, our performance analysis demonstrates that HERMES requires only approx 61ms for a single-vehicle access provision. At the same time, it handles 546 and 84 access token generations per second from a single-vehicle owner and large branches of rental companies with over a thousand vehicles, respectively.

Bit permutations are efficient linear functions often used for lightweight cipher designs. However, they have low diffusion effects, compared to word-oriented binary and MDS matrices. Thus, the security of bit permutation-based ciphers is significantly affected by differential and linear branch numbers (DBN and LBN) of nonlinear functions. In this paper, we introduce a widely applicable method for constructing S-boxes with high DBN and LBN. Our method exploits constructions of S-boxes from smaller S-boxes and it derives/proves the required conditions for smaller S-boxes so that the DBN and LBN of the constructed S-boxes are at least 3. These conditions enable us to significantly reduce the search space required to create such S-boxes. In order to make cryptographically good and efficient S-boxes, we propose a unbalanced-Bridge structure that accepts one 3-bit and two 5-bit S-boxes, and produces 8-bit S-boxes. Using the proposed structure, we develop a variety of new lightweight S-boxes that provide not only both DBN and LBN of at least 3 but also efficient bitsliced implementations including at most 11 nonlinear bitwise operations. The new S-boxes are the first that exhibit these characteristics. Moreover, we propose a block cipher PIPO based on one of the new S-boxes, which supports a 64-bit plaintext and a 128 or 256-bit key. Our implementations demonstrate that PIPO outperforms existing block ciphers (for the same block and key lengths) in both side-channel protected and unprotected environments, on an 8-bit AVR. The security of PIPO has been scrutinized with regards to state-of-the-art cryptanalysis.

Recently, Li and Micciancio (ePrint 2020/1533) have proposed a passive attack on the CKKS approximate homomorphic encryption (HE) scheme, which allows an adversary to query decryption on valid ciphertexts. In this paper, we discuss for which applications such attack is applicable, and introduce an extension of the HEaaN library. In addition, we investigate the mitigation strategies of other HE libraries that support the CKKS scheme including HElib, PALISADE, Lattigo and SEAL.

State machine replication protocols have reached a crucial juncture in their widespread deployment. Tokenised state machine replication protocols, which utilise an internal token for rewarding player participation, have brought about major advances in the areas of finance, internet of things, supply chain, legal systems, and data storage, to name but a few. However, the viability of these protocols as replacements for their centralised alternatives requires guarantees of player actions at all times which at present do not exist. Current standards for player characterisation in tokenised state machine replication protocols allow for honest players who will always follow the protocol, regardless of possible token increases for deviating. Given the ever-increasing market capitalisation of these tokenised protocols, honesty is becoming more expensive and more unrealistic. As such, this out-dated player characterisation must be removed to provide true guarantees of safety and liveness in a major stride towards universal trust in state machine replication protocols and a new scale of adoption. As all current state machine replication protocols are built on these legacy standards, it is imperative that a new player model is identified and utilised to reflect the true nature of players in tokenised protocols, now and into the future. To this effect, we propose the ByRa player model for state machine replication protocols. In the ByRa model, players either attempt to maximise their tokenised rewards, or behave adversarially. This merges the fields of game theory and distributed systems, an intersection in which tokenised state machine replication protocols exist, but on which little formalisation has been carried out. In the ByRa model, we identify the properties of strong incentive compatibility in expectation and fairness that all protocols must satisfy in order to achieve state machine replication. We then provide FAIRSICAL, a protocol which provably satisfies these properties, and by doing so, achieves state machine replication in the ByRa model.