International Association
for Cryptologic Research

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.

Pairings are a powerful tool to build advanced cryptographic schemes. The most efficient way to instantiate a pairing scheme is through Pairing-Friendly Elliptic Curves.

Because a randomly picked elliptic curve will not support an efficient pairing (the embedding degree will usually be too large to make any computation practical), a pairing-friendly curve has to be carefully constructed. This has led to famous curves, e.g. Barreto-Naehrig curves.

However, the computation of the discrete logarithm problem on the finite-field side has received much interest and its complexity has recently decreased. Hence the need to propose new curves has emerged.

In this work, we give one new curve that is specifically tailored to be fast over the first pairing-group, which is well suited for several cryptographic schemes, such as group signatures and their variants (EPID, anonymous attestation, etc) or accumulators.

We provide a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions. Our construction is black box and assumes no special properties (e.g. ``lossy'', ``correlated product secure'') of the trapdoor function.

This article describes recent progress in realizing verifiable state machines, a primitive that enables untrusted services to provide cryptographic proofs that they operate correctly. Applications of this primitive range from proving the correct operation of distributed and concurrent cloud services to reducing blockchain transaction costs by leveraging inexpensive off-chain computation without trust.

The use of deep learning in side-channel analysis has been more and more prominent recently. In particular, Convolution Neural Networks (CNN) are very efficient tools to extract the secret information from side-channel traces. Previous work regarding the use of CNN in side-channel has been mostly proposed through practical results. Zaid et al. have proposed a theoretical methodology in order to better understand the convolutional part of CNN and to understand how to construct an efficient CNN in the side-channel context [ZBHV19]. The proposal of Zaid et al. has been recently questioned by [WAGP20]. However this revisit is based on wrong assumptions and misinterpretations. Hence, many of the claims of [WAGP20] are unfounded regarding [ZBHV19]. In this paper, we clear out the potential misunderstandings brought by [WAGP20] and explain more thoroughly the contributions of [ZBHV19].

We carry out the first provable security analysis of the new FIDO2 protocols, the promising FIDO Alliance’s proposal for a standard for passwordless user authentication. Our analysis covers the core components of FIDO2: the new Client-to-Authenticator Protocol (CTAP2) and the Web Authentication (WebAuthn) specification.

Our analysis is modular. For CTAP2 and WebAuthn, in turn, we propose appropriate security models that aim to capture their intended security goals and use the models to analyze security. We identify a series of shortcomings and propose stronger protocols designed to withstand stronger yet realistic adversaries. Next, we prove the security guarantees FIDO2 provides based on the security of its components.

We expect that our models and provable security results will help clarify the security guarantees of the FIDO2 protocols. In addition, our proposed constructions should pave the way towards the design and deployment of more secure passwordless user authentication protocols.

Time-release cryptography requires problems that take a long time to solve and take just as long even with significant computational resources. While time-release cryptography originated with the seminal paper of Rivest, Shamir and Wagner ('96), it has gained special visibility recently due to new time-release primitives, like verifiable delay functions (VDFs) and sequential proofs of work, and their novel blockchain applications. In spite of this recent progress, security definitions remain inconsistent and fragile, and foundational treatment of these primitives is scarce. Relationships between the various time-release primitives are elusive, with few connections to standard cryptographic assumptions.

We systematically address these drawbacks. We define formal notions of sequential functions, the building blocks of time-release cryptography. The new definitions are robust against change of machine models, making them more amenable to complexity theoretic treatment. We demonstrate the equivalence of various types of sequential functions under standard cryptographic assumptions. The time-release primitives in the literature (such as those defined by Bitansky et al. (ITCS '16)) imply that these primitives exist, as well as the converse.

However, showing that a given construction is a sequential function is a hard circuit lower bound problem. To our knowledge, no results show that standard cryptographic assumptions imply any sequentiality. For example, repeated squaring over RSA groups is assumed to be sequential, but nothing connects this conjecture to standard hardness assumptions. To circumvent this, we construct a function that we prove is sequential if there exists any sequential function, without needing any specific knowledge of this hypothetical function. Our techniques use universal circuits and fully homomorphic encryption and generalize some of the elegant techniques of the recent work on lattice NIZKs (Canetti et al., STOC '19).

Using our reductions and sequential function constructions, we build VDFs and sequential proofs of work from fully homomorphic encryption, incremental verifiable computation, and the existence of a sequential function. Though our constructions are theoretical in nature and not competitive with existing techniques, they are built from much weaker assumptions than known constructions.

Existing approaches to secure multiparty computation (MPC) require all the participants to commit to the entire duration of the protocol. As interest in MPC continues to grow, it is inevitable that there will be a desire to use it to evaluate increasingly complex functionalities on massive datasets, resulting in computations spanning several hours or days. Such scenarios call for a dynamic participation model for MPC where participants have the flexibility to go offline as needed and (re)join when they have available computational resources. Such a model would also democratize access to privacy-preserving computation by facilitating an ``MPC-as-a-service'' paradigm --- the deployment of MPC in volunteer-operated networks that perform computation on behalf of clients.

In this work, we initiate the study of ``fluid MPC'', where parties can dynamically join and leave the computation. The minimum commitment required from each participant is referred to as ``fluidity'', measured in the number of rounds of communication that it must stay online. Our contributions are threefold:

1) We provide a formal treatment of fluid MPC, exploring various possible modeling choices.

2) We construct information-theoretic fluid MPC protocols in the honest-majority setting. Our protocols achieve ``maximal fluidity'', meaning that a party can exit the computation after receiving and sending messages in one round.

3) We implement our protocol and test it in multiple network settings.