International Association
for Cryptologic Research

In most post-quantum signature protocols, the verification procedure leaks information about which signature is being verified, and/or which public key is being used to verify the signature, to timing and other side-channel attacks. In some applications, this information leak is a breach of user privacy or system security.

One class of signature protocols, based on the parallel composition of many runs of one or more interactive cut-and-choose protocols, can be modified to enable constant-time verification at low cost by fixing the multiset of challenges which will be chosen at the cut-and-choose step and randomizing only their order based on the hash of the input message. As a side benefit, this technique naturally makes the size and structure of signatures a fixed system parameter, even if the underlying cut-and-choose protocol has different response sizes for each possible challenge at the cut-and-choose step.

When applied to a 5-pass “$q2$” interactive protocol, this technique requires essentially no extra rounds due to how fixed-weight binary vectors interact with the Kales--Zaverucha structural attack. Alternatively, when the data which must be transmitted for one of the two possible challenge values is significantly shorter than the other, or can be made so using standard and/or specialized compression techniques, a longer, lower-weight challenge vector can be used to obtain shorter signatures at the cost of more rounds of the underlying interactive protocol, with a much shallower computation-vs.-size tradeoff than the precomputation tree approach used in Picnic2, MUDFISH, and SUSHSYFISH.

As an example, these techniques reduce MQDSS signatures to under 15 kB and PKP-DSS signatures to under 14 kB with NIST Category 1 security against both secret key recovery and signature forgery. Further improvements in design and parameters allow PKP-DSS signatures under 10 kB with a security level and performance acceptable for almost all interactive authentication.

The asymptotic ROM proof of security published with MQDSS remains applicable to the optimized system, but the QROM proofs by Don et al. turn out to be invalid even for unmodified MQDSS.

We present a novel lattice-based zero-knowledge proof system for showing that (arbitrary-sized) committed integers satisfy additive and multiplicative relationships. The proof sizes of our schemes are between two to three orders of magnitude smaller than in the lattice proof system of Libert et al. (CRYPTO 2018) for the same relations. Because the proof sizes of our protocols grow linearly in the integer length, our proofs will eventually be longer than those produced by quantum-safe succinct proof systems for general circuits (e.g. Ligero, Aurora, etc.). But for relations between reasonably-sized integers (e.g. $512$-bit), our proofs still result in the smallest zero-knowledge proof system based on a quantum-safe assumption. Of equal importance, the run-time of our proof system is at least an order of magnitude faster than any other quantum-safe scheme.

The shuffle model of differential privacy [Bittau et al. SOSP 2017; Erlingsson et al. SODA 2019; Cheu et al. EUROCRYPT 2019] was proposed as a viable model for performing distributed differentially private computations. Informally, the model consists of an untrusted analyzer that receives messages sent by participating parties via a shuffle functionality, the latter potentially disassociates messages from their senders. Prior work focused on one-round differentially private shuffle model protocols, demonstrating that functionalities such as addition and histograms can be performed in this model with accuracy levels similar to that of the curator model of differential privacy, where the computation is performed by a fully trusted party. A model closely related to the shuffle model was presented in the seminal work of Ishai et al. on establishing cryptography from anonymous communication [FOCS 2006].

Focusing on the round complexity of the shuffle model, we ask in this work what can be computed in the shuffle model of differential privacy with two rounds. Ishai et al. showed how to use one round of the shuffle to establish secret keys between every two parties. Using this primitive to simulate a general secure multi-party protocol increases its round complexity by one. We show how two parties can use one round of the shuffle to send secret messages without having to first establish a secret key, hence retaining round complexity. Combining this primitive with the two-round semi-honest protocol of Applebaum, Brakerski, and Tsabary [TCC 2018], we obtain that every randomized functionality can be computed in the shuffle model with an honest majority, in merely two rounds. This includes any differentially private computation.

We hence move to examine differentially private computations in the shuffle model that (i) do not require the assumption of an honest majority, or (ii) do not admit one-round protocols, even with an honest majority. For that, we introduce two computational tasks: common element, and nested common element with parameter $\alpha$. For the common element problem we show that for large enough input domains, no one-round differentially private shuffle protocol exists with constant message complexity and negligible $\delta$, whereas a two-round protocol exists where every party sends a single message in every round. For the nested common element we show that no one-round differentially private protocol exists for this problem with adversarial coalition size $\alpha n$. However, we show that it can be privately computed in two rounds against coalitions of size $cn$ for every $c < 1$. This yields a separation between one-round and two-round protocols. We further show a one-round protocol for the nested common element problem that is differentially private with coalitions of size smaller than $c n$ for all $0 < c < \alpha < 1 / 2$.

We present TinyGarble2 – a C++ framework for privacy-preserving computation through the Yao’s Garbled Circuit (GC) protocol in both the honest-but-curious and the malicious security models. TinyGarble2 provides a rich library with arithmetic and logic building blocks for developing GC-based secure applications. The framework offers abstractions among three layers: the C++ program, the GC back-end and the Boolean logic representation of the function being computed. TinyGarble2 thus allowing the most optimized versions of all pertinent components. These abstractions, coupled with secure share transfer among the functions make TinyGarble2 the fastest and most memory-efficient GC framework. In addition, the framework provides a library for Convolutional Neural Networks (CNN). Our evaluations show that TinyGarble2 is the fastest among the current end-to-end GC frameworks while also being scalable in terms of memory footprint. Moreover, it performs 18× faster on the CNN LeNet-5 compared to the existing scalable frameworks.

TLS ensures confidentiality, integrity, and authenticity of communications. However, design, implementation, and cryptographic vulnerabilities can make TLS communication channels insecure. We need mechanisms that allow the channels to be kept secure even when a new vulnerability is discovered. We present MultiTLS, a middleware based on diversity and tunneling mechanisms that allows keeping communication channels secure even when new vulnerabilities are discovered. MultiTLS creates a secure communication channel through the encapsulation of k TLS channels, where each one uses a different cipher suite. We evaluated the performance of MultiTLS and concluded that it has the advantage of being easy to use and maintain since it does not modify any of its dependencies.

Broadcast Encryption with optimal parameters was a long-standing problem, whose first solution was provided in an elegant work by Boneh, Waters and Zhandry [BWZ14]. However, this work relied on multilinear maps of logarithmic degree, which is not considered a standard assumption. Recently, Agrawal and Yamada [AY20] improved this state of affairs by providing the first construction of optimal broadcast encryption from Bilinear Maps and Learning With Errors (LWE). However, their proof of security was in the generic bilinear group model. In this work, we improve upon their result by providing a new construction and proof in the standard model. In more detail, we rely on the Learning With Errors (LWE) assumption and the Knowledge of OrthogonALity Assumption (KOALA) [BW19] on bilinear groups.

Our construction combines three building blocks: a (computational) nearly linear secret sharing scheme with compact shares which we construct from LWE, an inner-product functional encryption scheme with special properties which is constructed from the bilinear Matrix Decision Diffie Hellman (MDDH) assumption, and a certain form of hyperplane obfuscation, which is constructed using the KOALA assumption. While similar to that of Agrawal and Yamada, our construction provides a new understanding of how to decompose the construction into simpler, modular building blocks with concrete and easy-to-understand security requirements for each one. We believe this sheds new light on the requirements for optimal broadcast encryption, which may lead to new constructions in the future.

SIDH and CSIDH are key exchange protocols based on isogenies and conjectured to be quantum-resistant. Since their protocols are similar to the classical Diffie–Hellman, they are vulnerable to the man-in-the-middle attack. A key exchange which is resistant to such an attack is called an authenticated key exchange (AKE), and many isogeny-based AKEs have been proposed. However, none of them are efficient in that they all have relatively large security losses. This is partially because the random self-reducibility of isogeny-based decisional problems has not been proved yet. In this paper, we show that the computational problem and the gap problem of CSIDH are random self-reducible. A gap problem is a computational problem given access to the corresponding decision oracle. Moreover, we propose a CSIDH-based AKE with small security loss, following the construction of Cohn-Gordon et al. at CRYPTO 2019, as an application of the random self-reducibility of the gap problem of CSIDH. Our AKE is proved to be the fastest CSIDH-based AKE when we aim at 110-bit security level.

CRAFT is a lightweight tweakable block cipher proposed at FSE 2019, which allows countermeasures against Differential Fault Attacks to be integrated into the cipher at the algorithmic level with ease. CRAFT employs a lightweight and involutory S-box and linear layer, such that the encryption function can be turned into decryption at a low cost. Besides, the tweakey schedule algorithm of CRAFT is extremely simple, where four 64-bit round tweakeys are generated and repeatedly used. Due to a combination of these features which makes CRAFT exceedingly lightweight, we find that some input difference at a particular position can be preserved through any number of rounds if the input pair follows certain truncated differential trails. Interestingly, in contrast to traditional differential analysis, the validity of this invariant property is affected by the positions where the constant additions take place. We use this property to construct ``weak-tweakey'' truncated differential distinguishes of CRAFT in the single-key model. Subsequently, we show how the tweak additions allow us to convert these weak-tweakey distinguishers into ordinary secret-key distinguishers based on which key-recovery attacks can be performed. Moreover, we show how to construct MILP models to search for truncated differential distinguishers exploiting this invariant property. As a result, we find a 15-round truncated differential distinguisher of CRAFT and extend it to a 19-round key-recovery attack with $2^{60.99}$ data, $2^{68}$ memory, $2^{94.59}$ time complexity, and success probability 80.66%. Also, we find a 14-round distinguisher with probability $2^{-43}$ (experimentally verified), a 16-round distinguisher with probability $2^{-55}$, and a 20-round weak-key distinguisher ($2^{118}$ weak keys) with probability $2^{-63}$. Experiments on round-reduced versions of the distinguishers show that the experimental probabilities are sometimes higher than predicted. Finally, we note that our result is far from threatening the security of the full CRAFT.

The University of St. Gallen in Switzerland and the chair of Cyber Security invites applications from PhD holders in the area of cryptography and information security. The researcher will join a group of researchers focusing in applied and theoretical cryptography, network and information security and privacy-preservation led by Prof. Katerina Mitrokotsa. We are affiliated to the Department of Computer Science (DCS) and the Institute of Computer Science. More precisely, the student shall be working on investigating efficient authentication and verifiable delegation of computation mechanisms that provide: i) provable security guarantees, and ii) rigorous privacy guarantees. The overall aim of the PhD position will be to design and evaluate provably secure cryptographic protocols for privacy-preserving authentication and verifiable delegation of computation protocols. The research shall also consider the case where multiple clients outsource jointly computations to untrusted cloud servers.
Research area: Research areas include but are not limited to:

• Verifiable computation
• Secure Multi Party Computation
• Privacy-preserving authentication
• Cryptographic primitives

Your Profile

• A MsC degree in Computer Science, Applied Mathematics or a relevant field;
• Strong mathematical and algorithmic CS background;
• Good skills in programming is beneficial;
• Excellent written and verbal communication skills in English

Deadline for applications: 30 September
Starting date: Fall 2020 or by mutual agreement

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: https://jobs.unisg.ch/offene-stellen/phd-position-in-information-security-and-cryptography-m-w-d/6366821b-4848-4217-90d2-78e6b1096162

The IMDEA Software Institute invites applications for tenure-track (Assistant Professor) positions. We are primarily interested in excellent candidates in Systems, including Distributed Systems, Embedded Systems, etc.; Data Science, including machine learning; Security and Privacy; Software Engineering>; and Cyber-Physical Systems. Exceptional candidates in other topics within the research areas of the Institute will also be considered. Tenured-level (Associate and Full Professor) applications are also welcome.

The primary mission of the IMDEA Software Institute is to perform research of excellence at the highest international level in the area of software development technologies. It is one of the highest ranked institutions worldwide in its main topic areas.

All positions require a doctoral degree in CS or closely related area, earned by the expected start date. Candidates for tenure-track positions will have shown exceptional promise in research and ability to work independently as well as collaboratively. Candidates for tenured positions must have an outstanding research record, recognized international stature, and demonstrated leadership. Experience in graduate student supervision is also valued at this level.

For full consideration, complete applications must be received by December 1, 2020 but will continue to be accepted until the positions are filled.

The institute is located in the vibrant area of Madrid, Spain. It offers an ideal working environment, combining the best aspects of a research center and a university department. The institute offers institutional funding and also encourages participation in national and international research projects. The working language at the institute is English.

Salaries at the Institute are internationally competitive, established on an individual basis, and include social security provisions, and in particular access to an excellent public health care system.

COVID Note: The Institute continues working and hiring, while strictly adopting all recommended hea

Closing date for applications:

Contact: hiring@software.imdea.org

More information: https://software.imdea.org/open_positions/call_for_faculty.html

We are seeking to recruit a post-doctoral research assistant to work in the area of cryptography. The position is available now until 1 June 2022.

The PDRA will work alongside Dr. Martin Albrecht, Dr. Rachel Player and other cryptographic researchers at Royal Holloway on topics in lattice-based cryptography. This post is part of the EU H2020 PROMETHEUS project (http://prometheuscrypt.gforge.inria.fr) for building privacy preserving systems from advanced lattice primitives. Our research focus within this project is on cryptanalysis and implementations, but applicants with a strong background in other areas such as protocol/primitive design are also encouraged to apply.

Closing date for applications:

Contact: Martin Albrecht

More information: https://martinralbrecht.wordpress.com/2020/06/26/postdoc-at-royal-holloway-on-lattice-based-cryptography-3/

We are looking for talented and motivated Post-docs to work on the ERC AdG project PROCONTRA: Smart-Contract Protocols: Theory for Applications. The project is about theoretical and applied aspects of blockchain and smart contracts.

The ideal candidates should have a PhD degree in cryptography (or related field) from a leading university, and a proven record of publications in top cryptography/security/TCS venues.

We offer competitive salary, a budget for conference travel and research visit, and membership in a young and vibrant team with several international contacts (for more see: www.crypto.edu.pl).

A successful candidate will be given a substantial academic freedom and can work on a variety of research problems related to the main theme of the project.

There is no specific deadline for this call, but we will start looking at the applications from Oct 15th, 2020.

Closing date for applications:

Contact: Stefan Dziembowski

More information: https://www.crypto.edu.pl/positions

What we are always looking for?
CISPA constantly seeks applications from outstanding students regardless of their national origin or citizenship. Currently we are looking for students interested in applied cryptography and topics like:

• privacy-preserving signatures,
• anonymous credentials,
• eID and ePassport security.

Admission to the Computer Science graduate program is highly competitive. A successful Master’s degree from a top-tier, research-oriented institution of higher education in a subject relevant to our research is required. Applicants should have an outstanding academic record, proficiency in spoken and written English, and strong letters of recommendation from their academic advisors.

What we offer?
CISPA maintains an open, international and diverse work environment. Every Ph.D. student is a member of a research group lead by his or her supervisor. Admitted students are as a rule paid employees of CISPA with a full time contract (TV-L E 13). The working language is English.

How to apply?
https://jobs.cispa.saarland/jobs/detail/phd-students-in-all-areas-related-to-cybersecurity-privacy-cryptography-and-machine-learning-1

Closing date for applications:

Contact: Lucjan Hanzlik (hanzlik@cispa.saarland)

More information: https://jobs.cispa.saarland/jobs/detail/phd-students-in-all-areas-related-to-cybersecurity-privacy-cryptography-and-machine-learning-1

The University of St. Gallen in Switzerland and the chair of Cyber Security invites applications from PhD holders in the area of cryptography and information security. The researcher will join a group of researchers focusing in applied and theoretical cryptography, network and information security and privacy-preservation led by Prof. Katerina Mitrokotsa. We are affiliated to the Department of Computer Science (DCS) and the Institute of Computer Science.
The position has an attractive salary and located in beautiful St. Gallen and Switzerland.
Research area: Research areas include but are not limited to:

• Verifiable computation
• Secure Multi Party Computation
• Privacy-preserving authentication
• Cryptographic primitives

Your Profile

• A PhD degree in Cryptography, information security;
• Strong mathematical and algorithmic CS background;
• Strong publication record;
• Good skills in programming is beneficial;
• Excellent written and verbal communication skills in English

Deadline for applications: 30 September
Starting date: Fall 2020 or by mutual agreement
How to apply Submit your application through the online application system

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: https://jobs.unisg.ch/offene-stellen/postdoc-fellow-in-cryptography-information-security/707c8a38-0c75-436e-b1b2-4ee6629d1323

We are looking for Research Fellow (Post-Doc), to join our group. The applicants should have background and be interested in working on different aspects of lattice based cryptography, in particular on:

• security proofs for lattice-based schemes,
• building and implementing lattice-based constructions,
• cryptanalysis and side channels attacks.

The research will take place in the Embedded Security and Cryptography (EMSEC) team, within the IRISA computer science institute located in Rennes, France.
To apply please send us by email your detailed CV (with publication list). The positions has flexible starting date. Review of applications will start immediately until the positions are filled.

Closing date for applications:

Contact: Adeline Roux-Langlois / adeline.roux-langlois@irisa.fr

We seek a Research Project Manager to support and coordinate our research on problems within the field of consensus while assembling a team of world-class researchers. Research at Protocol Labs We’re not an ordinary Research Lab. We’re working hard to build the core protocols of the decentralized web pursuant to our vision for the future of the Internet. As part of our research team, you’ll be enabling outcomes at the forefront of our mission. Our research team is granted both the freedom to develop knowledge by working on novel applications and a responsibility to contribute those skills toward advancing the flagship projects of Protocol Labs and the research endeavors of leading institutions in the field. You’ll feel at home working with us if your knowledge and optimism enable you to craft creative solutions working around evolving needs. What will the ConsensusLab do The goal of ConsensusLab will be to focus on long-term research problems facing Filecoin and other Protocol Labs projects related to secure, scalable consensus mechanisms. As ConsensusLab Lead you will… Coordinate with teammates across the research and project teams to drive progress against the goals we want ConsensusLab to accomplish, driving consensus research to support multiple autonomous projects within the company Track and coordinate the known problems that must be solved to hit those goals, the proposed solutions to those problems, the interactions and constraints that proposed solutions have on each other, and the effects design requirements have on proposed solutions. Assemble a team of researchers to drive progress against these problems. You may be a fit for this role if you have... Strong organizational and project management skills A familiarity with consensus research, in which you explored security or scalability of a system with byzantine or rational actors A love of supporting others in their efforts to learn and push the boundaries of human knowledge Bonus points... You’ve applied game theory, mechanism design, or agent-based modeling to fault tolerant system You’ve previously managed a team of researchers working on novel consensus algorithms

Closing date for applications:

Contact: Ed Burns

More information: https://jobs.lever.co/protocol/45adb8e8-4f5b-4da5-9c25-d1b84f3792e9

Several postdoctoral positions are available in the following areas:

• Post-quantum (including lattice-based) zero-knowledge proofs.
• Fast implementation of fully homomorphic encryption and lattice-based cryptography.
• Adversarial machine learning, broadly defined

Closing date for applications:

Contact: Jonathan Katz

This paper introduces the PoSH Consensus protocol, a novel work-in-progress construction for achieving Sybil-resistant Nakamoto-style probabilistic consensus on the contents of a cryptocurrency ledger in a permissionless decentralized network where parties stake their hardware’s computational power towards participation in leader election. PoSH aims to establish an openly mintable cryptocurrency that eliminates the requirement for block rewards and disincentivizes mining pools.

MPC functionalities are increasingly specified in high-level languages, where control-flow constructions such as conditional statements are extensively used. Today, concretely efficient MPC protocols are circuit-based and must evaluate all conditional branches at high cost to hide the taken branch.

The Goldreich-Micali-Wigderson, or GMW, protocol is a foundational circuit-based technique that realizes MPC for p players and is secure against up to p - 1 semi-honest corruptions. While GMW requires communication rounds proportional to the computed circuit’s depth, it is effective in many natural settings.

Our main contribution is MOTIF (Minimizing OTs for IFs), a novel GMW extension that evaluates conditional branches almost for free by amortizing Oblivious Transfers (OTs) across branches. That is, we simultaneously evaluate multiple independent AND gates, one gate from each mutually exclusive branch, by representing them as a single cheap vector-scalar multiplication (VS) gate.

For 2PC with b branches, we simultaneously evaluate up to b AND gates using only two 1-out-of-2 OTs of b-bit secrets. This is a factor ~b improvement over the state-of-the-art 2b 1-out-of-2 OTs of 1-bit secrets. Our factor b improvement generalizes to the multiparty setting as well: b AND gates consume only p(p - 1) 1-out-of-2 OTs of b-bit secrets.

We implemented our approach and report its performance. For 2PC and a circuit with 16 branches, each comparing two length-65000 bitstrings, MOTIF outperforms standard GMW in terms of communication by ~9.4x. Total wall-clock time is improved by 4.1 - 9.2x depending on network settings.

Our work is in the semi-honest model, tolerating all-but-one corruptions.

Biometric databases collect entire countries worth of citizens' sensitive information with few cryptographic protections. The critical required functionality is proximity search, the ability to search for all records close to a queried value, that is within a bounded distance. Biometrics usually operate in high dimensional space where an exponential number (in the dimension) of values are close.

This work builds searchable encryption that supports proximity queries for the Hamming metric. The Hamming metric is frequently used for the iris biometric. Searchable encryption schemes have leakage, which is information revealed to the database server such as identifiers of records returned which is known as access pattern leakage.

Prior work on proximity searchable encryption falls into two classes: 1) Li et al. (INFOCOM 2010) and Boldyreva and Chenette (FSE 2014) support only a polynomial number of close values, 2) Kim et al. (SCN 2018) leak the distance between the query and all stored records. The first class is not feasible due to the exponential number of close values. The second class allows the server to compute geometry of the space, enabling attacks akin to those on nearest neighbor schemes (Kornaropoulos et al. IEEE S&P 2019, 2020).

We build proximity search out of a new variant of inner product encryption called multi-point inner product encryption (MPIPE). MPIPE is built from function-hiding, secret-key, inner product predicate encryption (Shen, Shi, and Waters, TCC 2009). Our construction leaks access pattern and when two database records are the same distance from the queried point.

In most applications of searchable encryption the data distribution is not known a priori, making it prudent to consider leakage in a variety of settings. However, biometrics' statistics are well studied and static. Frequently in biometric search at most one record is returned. In this setting, access pattern leakage and the additional leakage of distance equality is unlikely to be harmful.

We also introduce a technique for reducing key size of a class of inner product encryption schemes based on dual pairing vector spaces. Our technique splits these vector spaces into multiple, smaller components, yielding keys that are a linear number of group elements instead of quadratic. We instantiate this technique on the scheme of Okamoto and Takashima (Eurocrypt, 2012) and show security under the same assumption (decisional linear).