International Association
for Cryptologic Research

We present several improvements to the framework of differential-linear attacks with a special focus on ARX ciphers. As a demonstration of their impact, we apply them to Chaskey and ChaCha and we are able to significantly improve upon the best attacks published so far.

A Hashed Time Lock Contract (HTLC) is a central concept in cryptocurrencies where some value can be spent either with the preimage of a public hash by one party (Bob) or after a timelock expires by another party (Alice). We present a bribery attack on HTLC's where Bob's hash-protected transaction is censored by Alice's timelocked transaction. Alice incentivizes miners to censor Bob's transaction by leaving almost all her value to miners in general. Miners follow (or refuse) the bribe if their expected payoff is better (or worse). We explore conditions under which this attack is possible, and how HTLC participants can protect themselves against the attack. Applications like Lightning Network payment channels and Cross-Chain Atomic Swaps use HTLC's as building blocks and are vulnerable to this attack. Our proposed solution uses the hashpower share of the weakest known miner to derive parameters that make these applications robust against this bribing attack.

In both hardware and software, masking can represent an effective means of hardening an implementation against side-channel attacks such as Differential Power Analysis (DPA). Focusing on software, however, the use of masking can present various challenges: specifically, it often 1) requires significant effort to translate any theoretical security properties into practice, and, even then, 2) imposes a significant overhead in terms of efficiency. To address both challenges, this paper explores use of an Instruction Set Extension (ISE) as a means of supporting masking in software-based implementations of symmetric cryptographic algorithms: we design, implement, and evaluate such an ISE using RISC-V as the base architecture.

The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language $L$ into a non-interactive argument system for $L$. Proving security of the Fiat-Shamir transform in the standard model, especially in the context of succinct arguments, is largely an unsolved problem. The work of Canetti et al. (STOC 2019) proved the security of the Fiat-Shamir transform applied to the Goldwasser-Kalai-Rothblum (STOC 2008) succinct interactive proof system under a very strong ``optimal learning with errors'' assumption. Achieving a similar result under standard assumptions remains an important open question.

In this work, we consider the problem of compiling a different succinct interactive proof system: Pietrzak's proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly $2^{\lambda^{\epsilon}}$) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential ($2^{-n^{1-\epsilon}}$)-hardness of the $n$-dimensional learning with errors problem. (The latter follows from the worst-case $2^{n^{1-\epsilon}}$ hardness of lattice problems.) More generally, we extend the ``bad-challenge function'' methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable.

As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class $\mathbf{CLS}\subset \mathbf{PPAD}$ under the $2^{\lambda^\epsilon}$-hardness of the repeated squaring problem and the $2^{-n^{1-\epsilon}}$-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is ``inherently sequential'', we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption.

Can Alice and Bob agree on a uniformly random secret key without having any truly secret randomness to begin with? Here we consider a setting where Eve can get partial leakage on the internal state of both Alice and Bob individually before the protocol starts. They then run a protocol using their states without any additional randomness and need to agree on a shared key that looks uniform to Eve, even after observing the leakage and the protocol transcript. We focus on non-interactive (one round) key exchange (NIKE), where Alice and Bob send one message each without waiting for one another.

We first consider this problem in the symmetric-key setting, where the states of Alice and Bob include a shared secret as well as individual uniform randomness. However, since Eve gets leakage on these states, Alice and Bob need to perform privacy amplification to derive a fresh secret key from them. Prior solutions require Alice and Bob to sample fresh uniform randomness during the protocol, while in our setting all of their randomness was already part of their individual states a priori and was therefore subject to leakage. We show an information-theoretic solution to this problem using a novel primitive that we call a two-seed extractor, which we in turn construct by drawing a connection to communication-complexity lower-bounds in the number-on-forehead (NOF) model.

We then turn to studying this problem in the public-key setting, where the states of Alice and Bob consist of independent uniform randomness. Unfortunately, we give a black-box separation showing that leakage-resilient NIKE in this setting cannot be proven secure via a black-box reduction under any game-based assumption when the leakage is super-logarithmic. This includes virtually all assumptions used in cryptography, and even very strong assumptions such as indistinguishability obfuscation (iO). Nevertheless, we also provide positive results that get around the above separation: - We show that every key exchange protocol (e.g., Diffie-Hellman) is secure when the leakage amount is logarithmic, or potentially even greater if we assume sub-exponential security without leakage. - We notice that the black-box separation does not extend to schemes in the common reference string (CRS) model, or to schemes with preprocessing, where Alice and Bob can individually pre-process their random coins to derive their secret state prior to leakage. We give a solution in the CRS model with preprocessing using bilinear maps. We also give solutions in just the CRS model alone (without preprocessing) or just with preprocessing (without a CRS), using iO and lossy functions.

We study collision-finding against Merkle-Damgård hashing in the random-oracle model by adversaries with an arbitrary $S$-bit auxiliary advice input about the random oracle and $T$ queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage $\Omega(ST^2/2^n)$, where $n$ is the output length, beating the birthday bound by a factor of $S$. These attacks were shown to be optimal. We observe that the collisions produced are very long, on the order $T$ blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find short collisions. We first exhibit a simple attack for finding $B$-block-long collisions achieving advantage $\tilde{\Omega}(STB/2^n)$. We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the $ST^2/2^n$ bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length $1$, length $2$, and unbounded-length collisions. Namely, the optimal attacks achieve (up to logarithmic factors) order of $(S+T)/2^n$, $ST/2^n$ and $ST^2/2^n$ advantage. We also give an upper bound on the advantage of a restricted class of short-collision finding attacks via a new analysis on the growth of trees in random functional graphs that may be of independent interest.

We observe that all previously known lattice-based blind signature schemes contain subtle flaws in their security proofs (e.g., R\"uckert, ASIACRYPT '08) or can be attacked (e.g., BLAZE by Alkadri et al., FC '20). Motivated by this, we revisit the problem of constructing blind signatures from standard lattice assumptions.

We propose a new three-round lattice-based blind signature scheme whose security can be proved, in the random oracle model, from the standard SIS assumption. Our starting point is a modified version of the (insecure) BLAZE scheme, which itself is based Lyubashevsky's three-round identification scheme combined with a new aborting technique to reduce the correctness error. Our proof builds upon and extends the recent modular framework for blind signatures of Hauck, Kiltz, and Loss (EUROCRYPT '19). It also introduces several new techniques to overcome the additional challenges posed by the correctness error which is inherent to all lattice-based constructions.

While our construction is mostly of theoretical interest, we believe it to be an important stepping stone for future works in this area.

We investigate the complexity of problems that admit perfect zero-knowledge interactive protocols and establish new unconditional upper bounds and oracle separation results. We establish our results by investigating certain distribution testing problems: computational problems over high-dimensional distributions represented by succinct Boolean circuits. A relatively less-investigated complexity class SBP emerged as significant in this study. The main results we establish are:

1. A unconditional inclusion that NIPZK is in CoSBP.

2. Construction of a relativized world in which there is a distribution testing problem that lies in NIPZK but not in SBP, thus giving a relativized separation of NIPZK (and hence PZK) from SBP.

3. Construction of a relativized world in which there is a distribution testing problem that lies in PZK but not in CoSBP, thus giving a relativized separation of PZK from CoSBP. These results refine the landscape of perfect zero-knowledge classes in relation to traditional complexity classes.

Recent years have seen a tremendous growth in the interest in secure multiparty computation (MPC) and its applications. While much progress has been made concerning its efficiency, many current, state-of-the-art protocols are vulnerable to Denial of Service attacks, where a cheating party may prevent the honest parties from learning the output of the computation, whilst remaining anonymous. The security model of identifiable abort aims to prevent these attacks, by allowing honest parties to agree upon the identity of a cheating party, who can then be excluded in the future. Several existing MPC protocols offer security with identifiable abort against a dishonest majority of corrupted parties. However, all of these protocols have a round complexity that scales linearly with the depth of the circuit (and are therefore unsuitable for use in high latency networks) or use cryptographic primitives or techniques that have a high computational overhead.

In this work, we present the first efficient MPC protocols with identifiable abort in the dishonest majority setting, which run in a constant number of rounds and make only black-box use of cryptographic primitives. Our main construction is built from highly efficient primitives in a careful way to achieve identifiability at a low cost. In particular, we avoid the use of public-key operations outside of a setup phase, incurring a relatively low overhead on top of the fastest currently known constant-round MPC protocols based on garbled circuits. Our construction also avoids the use of adaptively secure primitives and heavy zero-knowledge machinery, which was inherent in previous works. In addition, we show how to upgrade our protocol to achieve public verifiability using a public bulletin board, allowing any external party to verify correctness of the computation or identify a cheating party.

Performing a comprehensive side-channel analysis evaluation of small embedded devices is a process known for its variability and complexity. In real-world experimental setups, the results are largely influenced by a huge amount of parameters that are not easily adjusted without trial and error and are heavily relying on the experience of professional security analysts. In this paper, we advocate the use of an existing statistical methodology called Six Sigma (6σ) for side-channel analysis optimization for this purpose. This well-known methodology is commonly used in other industrial fields, such as production and quality engineering, to reduce the variability of industrial processes. We propose a customized Six Sigma methodology, which enables even a less-experienced security analysis to select optimal values for the different variables that are critical for the side-channel analysis procedure. Moreover, we show how our methodology helps in improving different phases in the side-channel analysis process.

We provide a new definitional framework capturing the multi-user security of encryption schemes and pseudorandom functions in the face of adversaries that can adaptively compromise users' keys. We provide a sequence of results establishing the security of practical symmetric encryption schemes under adaptive compromise in the random oracle or ideal cipher model. The bulk of analysis complexity for adaptive compromise security is relegated to the analysis of lower-level primitives such as pseudorandom functions.

We apply our framework to give proofs of security for the BurnBox system for privacy in the face of border searches and the in-use searchable symmetric encryption scheme due to Cash et al. In both cases, prior analyses had bugs that our framework helps avoid.

In this work, we study the question of what set of simple-to-state assumptions suffice for constructing functional encryption and indistinguishability obfuscation ($i\mathcal{O}$), supporting all functions describable by polynomial-size circuits. Our work improves over the state-of-the-art work of Jain, Lin, Matt, and Sahai (Eurocrypt 2019) in multiple dimensions.

New Assumption: Previous to our work, all constructions of $i\mathcal{O}$ from simple assumptions required novel pseudorandomness generators involving LWE samples and constant-degree polynomials over the integers, evaluated on the error of the LWE samples. In contrast, Boolean pseudorandom generators (PRGs) computable by constant-degree polynomials have been extensively studied since the work of Goldreich (2000). We show how to replace the novel pseudorandom objects over the integers used in previous works, with appropriate Boolean pseudorandom generators with sufficient stretch, when combined with LWE with binary error over suitable parameters. Both binary error LWE and constant-degree Goldreich PRGs have been subject to extensive cryptanalysis since much before our work. Thus, we back the plausibility of our assumption with security against algorithms studied in context of cryptanalysis of these objects.

New Techniques: We introduce a number of new techniques: - We introduce a simple new technique for proving leakage resilience when polynomial-size noise is used to hide small secrets (for example, to hide LWE-based FHE decryption errors). - We show how to build partially-hiding \emph{public-key} functional encryption, supporting degree-2 functions in the secret part of the message, and arithmetic $\mathsf{NC}^1$ functions over the public part of the message, assuming only standard assumptions over asymmetric pairing groups. - We construct single-ciphertext secret-key functional encryption for all circuits with {\em linear} key generation, assuming only the LWE assumption.

Simplification: Unlike prior works, our new techniques furthermore let us construct public-key functional encryption for polynomial-sized circuits directly (without invoking any bootstrapping theorem, nor security amplification, nor transformation from secret-key to public-key FE), and based only on the polynomial hardness of underlying assumptions. The functional encryption scheme satisfies a strong notion of efficiency where the size of the ciphertext grows only sublinearly in the output size of the circuit and not its size. Finally, assuming that the underlying assumptions are subexponentially hard, we can bootstrap this construction to achieve $i\mathcal{O}$.

Cap Gemini funds a chair « blockchains and B2B platforms » fostering research and teaching at École Polytechnique. The Departments of Computer Science and Economics at École Polytechnique thus welcome applications for a post-doctoral research position in the blockchain domain.

Depending on her/his profile, the chosen candidate will become a member of the cryptography team («Grace», joint with INRIA) at the Department of Computer Science, or of the Department of Economics. Candidates must hold a Ph.D. in computer science or in Economics, and have demonstrated great ability in research and teaching. Candidates must present a scientific research project in relation to blockchains.

The mission of the accepted candidate will be to develop research, coordinate with PhD students and researchers, and also support the activities of the chair, by outreaching to the blockchain network in the Paris area, but also worldwide, and by supporting the communication and PR of the chair. If she/he wishes to, the candidate will be able to complement his or her activity by doing lectures, labs and student projects about blockchain platforms.

Through a fast and lightweight process the candidate will be hired from Winter 2020 for two years, which could be extended for two more years after a further review process. The complementary teaching activity, if any, may complement the base salary. Successful candidates will work at Ecole Polytechnique located in Palaiseau, Paris area, France.

Deadline for Application: July 23rd, 2020

Closing date for applications:

Contact: Daniel Augot, Senior researcher, INRIA and École polytechnique. Daniel.Augot@inria.fr

More information: https://blockchain-chair.io/

The CryptoLux group of the University of Luxembourg invites applications from Ph.D. holders in the general area of applied cryptography. CryptoLux is a group of cryptographers and security researchers interested in applied cryptography, cryptanalysis, privacy, network security, cryptographic blockchains and is led by Prof. Alex Biryukov. Candidates with interest in the following topics are welcome to apply:

• Design and cryptanalysis of symmetric cryptographic primitives
• Cryptocurrencies, blockchain
• Privacy enhancing technologies, Tor
• Side-channel attacks and countermeasures
• White-box cryptography

Candidates must have a Ph.D. degree in Computer Science, Applied Mathematics or a related field; competitive research record in applied cryptography or information security (at least one paper in top 10 IT security conferences); strong mathematical and algorithmic CS background; fluent written and verbal communication skills in English.

The University offers a two-year employment contract, which may be extended up to five years. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Alex Biryukov before August 1, 2020. The application should contain a brief cover letter explaining the candidate's research interests, CV with photo, a list of publications and the names and contacts of 3 references.

Closing date for applications:

Contact: Prof. Alex Biryukov

More information: https://www.cryptolux.org/index.php/Vacancies

The Department of Computer Science at New Jersey Institute of Technology (NJIT) seeks candidates to fill a University Lecturer/Senior University Lecturer position. Successful candidates must have an MS in Computer Science or a related computing area and will have demonstrated an expert grasp of knowledge of the Cybersecurity field at all levels, either through a demonstrated record of teaching excellence, or through industrial experience.

Candidates are expected to mainly teach courses under the umbrella of Cybersecurity in support of our graduate and undergraduate programs. The successful candidate will also be involved in creating course content and materials with a focus on experiential and project-based learning.

Interested applicants should submit their CV and the names of at least two references by applying as soon as possible at https://njit.csod.com/ats/careersite/JobDetails.aspx?site=1&id=1961. Applications will be reviewed on a rolling basis until the position is filled.

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

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

The Privacy & Security group at University of Luebeck seeks to hire doctoral students for research in the one or more of the following areas:

• enhancing or attacking training-data-privacy in machine learning algorithms
• ensuring or attacking the robustness of machine learning algorithms
• privacy-preserving health applications (including epidemiological applications)
• privacy-preserving Smart Grid, Smart City applications
• anonymous communication

The ideal candidate is enthusiastic and has a strong background and interest in one or more of the following areas:

• information security, differential privacy, or cryptography
• mathematical statistics and probability theory
• machine learning

Candidates with a strong theoretical background in related areas are also encouraged to apply. Formal requirements for doctoral students are a master's or equivalent degree. The doctoral student will be a paid employee of University of Lübeck according to standard collective labour agreement regulations (TV-L E13, 100%), which compared to the local cost of living provides an attractive salary and attractive working conditions.

Applications should include a curriculum vitae, a brief description of research interests, transcripts of grades, 2-3 letters of recommendation from teachers or employers, and, if possible, the Master's or Bachelor's thesis and publications.

• Application deadline: 30 August 2020 (later applications might also be considered)
• Starting date: 1 October 2020 (negotiable)

About our group: The Privacy & Security group at the Institute for IT-security at the University of Lübeck works on researching privacy-preserving and robust methods to perform computations on large datasets such that the system work as expected and privacy of individuals is protected, including privacy-preserving machine learning, and anonymous communication.

Closing date for applications:

Contact: Prof. Dr. Esfandiar Mohammadi
Privacy & Security group
University of Lübeck
https://mohammadi.eu

More information: https://www.its.uni-luebeck.de/fileadmin/files/jobs/privsec_open_positions.pdf

The PhD students will join Prof. Mitrokotsa's group focusing on security and cryptography, working in the area of privacy-preserving biometric authentication and within the Marie Curie ITN project: "TRESPASS-ETN: Training in Secure and Privacy-preserving biometrics". Privacy-preserving biometric authentication focuses on guaranteeing accurate biometric authentication, while at the same time providing strong privacy guarantees (e.g., avoid tracking, profiling of users and leakage of sensitive information). The focus of one of the PhD positions would be to examine how to guarantee privacy-preservation in biometric authentication systems by employing advanced cryptographic methods such as secure multiparty computation (SMPC) primitives (e.g., homomorphic encryption) and verifiable computation (when biometric authentication is applied in a distributed setting). The second PhD position will focus on employing differentially private mechanisms in the biometric authentication process. The goal is to achieve high accuracy in the authentication process, while at the same time avoid any leakage of information. The PhD student will be supervised by Prof. Katerina Mitrokotsa in the area of information security and cryptography.

Closing date for applications:

Contact: Prof. Katerina Mitrokotsa

More information: https://www.chalmers.se/en/about-chalmers/Working-at-Chalmers/Vacancies/Pages/default.aspx?rmpage=job&rmjob=p8404

Shor's quantum algorithm, running in quantum computers, can efficiently solve integer factorization problem and discrete logarithm problem in polynomial time. This poses an urgent and serious threat to long-term security with recent accelerated evolution of quantum computing. However, National Institute of Standards and Technology (NIST) plans to release its standard of post-quantum cryptography between 2022 and 2024. It is crucially important to propose an early solution, which is likely secure against quantum attacks and classical attacks, and likely to comply with the future NIST standard. A robust combiner combines a set of 2 or more cryptography primitives into a new primitive of the same type, and guarantees that if anyone of the ingredient primitive is secure, then the resulting primitive is secure. This work proposes the first construction of robust combiner for Key Encapsulation Mechanism (KEM), with optimal amortized performance. From our robust combiner of KEMs, we construct efficient stateful hybrid Key Exchange Protocol (KEP), which is more suitable for two parties who will communicate with each other frequently.

We present functional encryption schemes for attribute-weighted sums, where encryption takes as input $N$ attribute-value pairs $(x_i,z_i)$ where $x_i$ is public and $z_i$ is private; secret keys are associated with arithmetic branching programs $f$, and decryption returns the weighted sum $\sum_{i=1}^N f(x_i) z_i$ while leaking no additional information about the $z_i$'s. Our main construction achieves

(1) compact public parameters and key sizes that are independent of $N$ and the secret key can decrypt a ciphertext for any a-prior unbounded $N$;

(2) short ciphertexts that grow with $N$ and the size of $z_i$ but not $x_i$;

(3) simulation-based security against unbounded collusions;

(4) relies on the standard $k$-linear assumption in prime-order bilinear groups.

Reputation systems constitute one of the few workable mechanisms for distributed applications in which users can be made accountable for their actions. By collecting user experiences in reputation profiles, participants are encouraged to interact more with well-behaving peers hence better online behavior is motivated.

In this work, we develop a privacy-preserving reputation scheme for collaborative systems such as P2P networks in which peers can represent themselves with different pseudonyms when interacting with others. All these pseudonyms, however, are bound to the same reputation token. This allows honest peers maintain their good record even when switching to a new pseudonym, while preventing malicious peers from making a fresh start. Apart from an initial offline setup phase which is only needed to ensure reputation soundness but not privacy, our system is truly decentralized. Using an append-only distributed ledger such as Bitcoin’s blockchain, we show how participants can make anonymous yet verifiable assertions about their own reputation. Thus the system maintains soundness, peer-pseudonym unlinkability as well as unlinkability among pseudonyms of the same peer. We formally prove these properties, we discuss ways to eliminate the setup phase and we evaluate the efficiency of the various operations.