International Association
for Cryptologic Research

This paper constructs unbounded simulation sound proofs for boolean circuit satisfiability under standard assumptions with proof size O(n+d) bilinear group elements, where d is the depth and n is the input size of the circuit. Our technical contribution is to add unbounded simulation soundness to a recent NIZK of González and Ràfols (ASIACRYPT'19) with very small overhead. We give two different constructions: the first one is more efficient but not tight, and the second one is tight. Our new scheme can be used to construct Signatures of Knowledge based on standard assumptions that also can be composed universally with other cryptographic protocols/primitives. As an independent contribution we also detail a simple formula to encode Boolean circuits as Quadratic Arithmetic Programs.

Isogeny-based assumptions have emerged as a viable option for quantum-secure cryptography. Recent works have shown how to build efficient (public-key) primitives from isogeny-based assumptions such as CSIDH and CSI-FiSh. However, in its present form, the landscape of isogenies does not seem very amenable to realizing new cryptographic applications. Isogeny-based assumptions often have unique efficiency and security properties, which makes building new cryptographic applications from them a potentially tedious and time-consuming task.

In this work, we propose a new framework based on group actions that enables the easy usage of a variety of isogeny-based assumptions. Our framework generalizes the works of Brassard and Yung (Crypto’90) and Couveignes (Eprint’06). We provide new definitions for group actions endowed with natural hardness assumptions that model isogeny-based constructions amenable to group actions such as CSIDH and CSI-FiSh.

We demonstrate the utility of our new framework by leveraging it to construct several primitives that were not previously known from isogeny-based assumptions. These include smooth projective hashing, dual-mode PKE, two-message statistically sender-private OT, and Naor-Reingold style PRF. These primitives are useful building blocks for a wide range of cryptographic applications.

We introduce a new assumption over group actions called Linear Hidden Shift (LHS) assumption. We then present some discussions on the security of the LHS assumption and we show that it implies symmetric KDM-secure encryption, which in turn enables many other primitives that were not previously known from isogeny-based assumptions.

This paper makes three contributions. First, we present a simple theory of random systems. The main idea is to think of a probabilistic system as an equivalence class of distributions over deterministic systems. Second, we demonstrate how in this new theory, the optimal information-theoretic distinguishing advantage between two systems can be characterized merely in terms of the statistical distance of probability distributions, providing a more elementary understanding of the distance of systems. In particular, two systems that are $\epsilon$-close in terms of the best distinguishing advantage can be understood as being equal with probability 1-$\epsilon$, a property that holds statically, without even considering a distinguisher, let alone its interaction with the systems. Finally, we exploit this new characterization of the distinguishing advantage to prove that any threshold combiner is an amplifier for indistinguishability in the information-theoretic setting, generalizing and simplifying results from Maurer, Pietrzak, and Renner (CRYPTO 2007).

Non-committing encryption (NCE) is a type of public key encryption which comes with the ability to equivocate ciphertexts to encryptions of arbitrary messages, i.e., it allows one to find coins for key generation and encryption which ``explain'' a given ciphertext as an encryption of any message. NCE is the cornerstone to construct adaptively secure multiparty computation [Canetti et al. STOC'96] and can be seen as the quintessential notion of security for public key encryption to realize ideal communication channels. A large body of literature investigates what is the best message-to-ciphertext ratio (i.e., the rate) that one can hope to achieve for NCE. In this work we propose a near complete resolution to this question and we show how to construct NCE with constant rate in the plain model from a variety of assumptions, such as the hardness of the learning with errors (LWE), the decisional Diffie-Hellman (DDH), or the quadratic residuosity (QR) problem. Prior to our work, constructing NCE with constant rate required a trusted setup and indistinguishability obfuscation [Canetti et al. ASIACRYPT'17].

The hardness of the Ring Learning with Errors problem (RLWE) is a central building block for efficiency-oriented lattice-based cryptography. Many applications use an ``entropic'' variant of the problem where the so-called ``secret'' is not distributed uniformly as prescribed but instead comes from some distribution with sufficient min-entropy. However, the hardness of the entropic variant has not been substantiated thus far.

For standard LWE (not over rings) entropic results are known, using a ``lossiness approach'' but it was not known how to adapt this approach to the ring setting. In this work we present the first such results, where entropic security is established either under RLWE or under the Decisional Small Polynomial Ratio (DSPR) assumption which is a mild variant of the NTRU assumption.

In the context of general entropic distributions, our results in the ring setting essentially match the known lower bounds (Bolboceanu et al., Asiacrypt 2019; Brakerski and Döttling, Eurocrypt 2020).

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