International Association
for Cryptologic Research

University of Surrey, Guildford, United Kingdom This PhD position is funded for EU and UK students, and the application deadline is on the 24th of January 2021. Overseas applicants are welcome to apply but will have to cover the difference in Overseas Tuition Fees.

The aim of the PhD is to design and analyse electronic-voting systems that can be deployed in real-life, by looking at combinations between desirable e-voting guarantees (e.g. privacy, receipt-freeness, collusion resistance, verifiability, accountability, etc) and techniques of executing protocols on untrusted platforms. A secondary aim is to certify the security of these systems using formal-analysis tools. The position is under the supervision of Dr. Catalin Dragan and Prof. Steve Schneider.

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

Closing date for applications:

Contact: Catalin Dragan c.dragan@surrey.ac.uk

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

We are hiring protocol and backend engineers to help us to build privacy preserving payment and decentralized exchange on Polkadot. The engineer will be working with world class cryptographers to bring privacy preserving solutions to blockchains using zero-knowledge proof.

Below are good to have skills:

• System level programming using Rust or C/C++
• Familiar with low level system internals and network stack
• Basic knowledge of Cryptographic primitives, such as public key encryption
• Knowledge on distributed system and consensus algorithms
• Familiar with database and storage system

Location

• Boston
• remote

For more information, please contact: Shumo@manta.network

Closing date for applications:

Contact: Shumo Chu

More information: https://manta.network/

Founded by cryptography pioneer Silvio Micali, Algorand fulfills the promise of blockchain through a first-of-its-kind transaction platform that solves the “blockchain trilemma” by offering true decentralization, scalability, and security.

We are looking for a Postdoctoral Cryptography Researcher. This is an opportunity for someone who is excited by new technologies to influence the design and implementation of advanced cryptographic systems and protocols.The Researcher will design cryptographic protocols and partner with the team to develop prototypes. Researchers are also internal subject matter experts, providing guidance to our extended staff, and are also responsible for publishing meaningful research.

Overseen by Chris Peikert, this opportunity is for one (1) year with the possibility for extension.

Core Responsibilities

• Theoretical Focus: Design advanced cryptographic systems and protocols
• Applied Focus: Prototype/build and optimize cryptographic systems and protocols
• Partner with the larger organization on implementations
• Publish meaningful research, both individually and with staff members
• Be part of an inclusive environment that fosters collaboration and creativity both internally and externally

Requirements

• PhD in Cryptography, Computer Science, or related field
• Experience in the following: cryptographic primitives, protocols, and proof systems; post-quantum cryptography preferred
• Publication in top cryptography or security venues
• Open source library contribution or cutting edge implementation experience for applied-focused applicants
• Appreciation for considerations beyond cryptography, such as networking, systems, and performance
• Good written communication and ability to communicate technical information with wide variety of audiences
• Experience in participating in the implementation of complex systems designs preferred
• Enthusiasm for working in a highly collaborative, fast-paced, and dynamic environment

Postdocs receive competitive salary and benefits, as well as a WFH technology package (computer and home

Closing date for applications:

Contact: Regina OBrien

More information: https://jobapply.page.link/TNVg

The Faculty of Mathematics, Informatics and Mechanics at University of Warsaw (MIM UW) invites applications for positions of an assistant professor (“adiunkt” in Polish) in Computer Science, starting on 1st October 2021 (or 1st Feb 2022).

MIM UW is one of the strongest computer science faculties in Europe. It is known for talented students (e.g., two wins and 14 times in top ten at the ACM International Collegiate Programming Contest) and strong research teams, especially in algorithms, logic and automata and computational biology. There is also a growing number of successful smaller groups in areas like cryptography, game theory, distributed systems, machine learning and others. There are five ERC grants in computer science running at MIM UW at the moment.

In the current call, the position is offered in two variants (follow the links for details):

1. a standard position
2. a position with reduced teaching load (120hrs/year) and increased salary

Deadline for applications: 12th February, 2021.

More details, including application procedure can be found under the following links:

1. https://www.mimuw.edu.pl/sites/default/files/konkursy/wmim_1210_ek_03_2021_en.pdf
2. https://www.mimuw.edu.pl/sites/default/files/konkursy/wmim_1210_ek_01_2021_en.pdf

Closing date for applications:

Contact: Prof. Łukasz Kowalik (kowalik@mimuw.edu.pl)

More information: https://www.mimuw.edu.pl/sites/default/files/konkursy/wmim_1210_ek_03_2021_en.pdf

Metadata from voice calls, such as the knowledge of who is communicating with whom, contains rich information about people’s lives. Indeed, it is a prime target for powerful adversaries such as nation states. Existing systems that hide voice call metadata either require trusted intermediaries in the network or scale to only tens of users. This paper describes the design, implementation, and evaluation of Aloha, the first system for voice communication that hides metadata over fully untrusted infrastructure and scales to tens of thousands of users. At a high level, Aloha follows a template in which callers and callees deposit and retrieve messages from private mailboxes hosted at an untrusted server. However, Aloha improves message latency in this architecture, which is a key performance metric for voice calls. First, it enables a caller to push a message to a callee in two hops, using a new way of assigning mailboxes to users that resembles how a post office assigns PO boxes to its customers. Second, it innovates on the underlying cryptographic machinery and constructs a new private information retrieval (PIR) scheme, QuickPIR, that reduces the time to process oblivious access requests for mailboxes. An evaluation of Aloha on a cluster of eighty machines on AWS demonstrates that it can serve 32K users with a 99-th percentile message latency of 726 ms—a 7× improvement over prior work in the same threat model.

In this paper, we show how to apply Montgomery multiplication to the tag tracing variant of the Pollard's rho algorithm applied to prime order fields. This combines the advantages of tag tracing with those of Montgomery multiplication. In particular, compared to the previous version of tag tracing, the use of Montgomery multiplication entirely eliminates costly modular reductions and replaces these with much more efficient divisions by a suitable power of two.

The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes.

We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a small fraction of inputs—into an object that is indifferentiable from a random function, even if the adversary is made aware of all randomness used in the transformation. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., those permitting adversaries that subvert or replace basic cryptographic algorithms) to use random oracles as a trusted black box.

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. This would jeopardize IT security as we know it. In this work, we investigate two quantum-safe, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use in secure boot. We evaluate various parameter sets for the use-case in question and we prove that post-quantum signatures with less than one second signing and less than 10ms verification would not have material impact (less than1‰) on secure boot. We evaluate the hierarchical design of these signatures in hardware-based and virtual secure boot. In addition, we develop Hardware Description Language code and show that the code footprint is just a few kilobytes in size which would fit easily in almost all modern FPGAs. We also analyze and evaluate potential challenges for integration in existing technologies and we discuss considerations for vendors embarking on a journey of image signing with hash-based signatures.

Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain ~\cite{grigoriev2014tropical,grigoriev2018tropical} as a promising platform for the implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: ``Given that $A=V\otimes F^{\otimes t}$ for a unique $t$ and matrices $A$, $V$, $F$ of appropriate dimensions, find this $t$.'' We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

We give secure parameter suggestions to use sparse secret vectors in LWE based encryption schemes. This should replace existing security parameters, because homomorphic encryption(HE) schemes use quite different variables from the existing parameters. In particular HE schemes using sparse secrets should be supported by experimental analysis, here we summarize existing attacks to be considered and security levels for each attacks. Based on the analysis and experiments, we compute optimal scaling factors for CKKS.

We describe the binary numeral tree—a type of binary tree uniquely suited to processing unbounded streams of data—and present a number of algorithms for efficiently constructing and verifying Merkle proofs within such trees. Specifically, we present existence proofs for single leaves, for a contiguous range of leaves, and for multiple disjoint ranges. We also introduce Merkle "diff" proofs, which assert that an arbitrary modification was correctly applied to an existing tree. Each algorithm, operating on a tree with $n$ leaves and $k$ disjoint proof ranges, requires $\mathcal{O}(\log_2(n))$ space and $\mathcal{O}(n)$ time, and yields proofs of size $\mathcal{O}(k\log_2 (n))$. Furthermore, each algorithm operates in streaming fashion, requiring only a single in-order pass over the leaf data.

Being based on a sound theoretical basis, masking schemes are commonly applied to protect cryptographic implementations against Side-Channel Analysis (SCA) attacks. Constructing SCA-protected AES, as the most widely deployed block cipher, has been naturally the focus of several research projects, with a direct application in industry. The majority of SCA-secure AES implementations introduced to the community opted for low area and latency overheads considering Application-Specific Integrated Circuit (ASIC) platforms. Albeit a few, those which particularly targeted Field Programmable Gate Arrays (FPGAs) as the implementation platform yield either a low throughput or a not-highly secure design. In this work, we fill this gap by introducing first-order glitch-extended probing secure masked AES implementations highly optimized for FPGAs, which support both encryption and decryption. Compared to the state of the art, our designs efficiently map the critical non-linear parts of the masked S-box into the built-in Block RAMs (BRAMs). The most performant variant of our constructions accomplishes five first-order secure AES encryptions/decryptions simultaneously in 50 clock cycles. Compared to the equivalent state-of-the-art designs, this leads to at least 70% reduction in utilization of FPGA resources (slices) at the cost of occupying BRAMs. Last but not least, we provide a wide range of such secure and efficient implementations supporting a large set of applications, ranging from low-area to high-throughput.

The modern financial world has seen a significant rise in the use of cryptocurrencies in recent years, partly due to the convincing lures of anonymity promised by these schemes. Bitcoin, despite being considered as the most widespread among all, is claimed to have significant lapses in relation to its anonymity. Unfortunately, studies have shown that many cryptocurrency transactions can be traced back to their corresponding participants through the analysis of publicly available data, to which the cryptographic community has responded by proposing new constructions with improved anonymity claims. Nevertheless, the absence of a common metric for evaluating the level of anonymity achieved by these schemes has led to a number of disparate ad hoc anonymity definitions, making comparisons difficult. The multitude of these notions also hints at the surprising complexity of the overall anonymity landscape.

In this study, we introduce such a common framework to evaluate the nature and extent of anonymity in (crypto)currencies and distributed transaction systems, irrespective of their implementation. As such, our work lays the foundation for formalising security models and terminology across a wide range of anonymity notions referenced in the literature, while showing how ``anonymity'' itself is a surprisingly nuanced concept.

Blockchains suffer from a critical scalability problem where traditionally each network node maintains all network state, including records since the establishment of the blockchain. Sketches are popular hash-based data structures used to represent a large amount of data while supporting particular queries such as on set membership, cardinality estimation and identification of large elements. Often, to achieve time and memory savings, sketches allow potential inaccuracies in answers to the queries. The design of popular blockchain networks such as Bitcoin and Ethereum makes use of sketches for various tasks such as summarization of transaction blocks or declaring the interests of light nodes. Similarly, they seem natural to deal with the size of the state in blockchains. In this paper, we study existing and potential future applications of sketches in blockchains. We first summarize current blockchain use cases of sketches. Likewise, we explore how this coupling can be generalized to a wider range of sketches and additional functionalities. In particular, we explain how sketches can detect anomalies based on efficient an summary of the state or traffic.

In a two-party Circuit-based Private Set Intersection (PSI), $P_{0}$ and $P_{1}$ hold sets $X$ and $Y$ respectively and wish to securely compute a function $f$ over the set $X \cap Y$ (e.g., cardinality, sum over associated attributes, and threshold intersection). Following a long line of work, Pinkas et al. ($\mathsf{PSTY}$, Eurocrypt 2019) showed how to construct such a Circuit-PSI protocol with linear communication complexity. However, their protocol has super-linear computational complexity.

In this work, we construct Circuit-PSI protocols with linear computational and communication cost. Further, our protocols are concretely more efficient than $\mathsf{PSTY}$ -- we are $\approx 2.3\times$ more communication efficient and are up to $2.8\times$ faster in LAN and WAN network settings. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions ($\mathsf{RB\text{-}OPPRF}$) that can be seen as a strict generalization of Batch $\mathsf{OPPRF}$s in $\mathsf{PSTY}$. While using Batch $\mathsf{OPPRF}$s, in the context of Circuit-PSI results, in protocols with super-linear computational complexity, we construct $\mathsf{RB\text{-}OPPRF}$s that can be used to build linear cost and concretely efficient Circuit-PSI protocols. We believe that the $\mathsf{RB\text{-}OPPRF}$ primitive could be of independent interest. As another contribution, we provide more communication efficient protocols (than prior works) for the task of private set membership -- a primitive used in many PSI protocols including ours.

Identity-based encryption (IBE), introduced by Shamir in 1984, eliminates the need for public-key infrastructure. The sender can simply encrypt a message by using the recipient's identity (such as their email or IP address) without needing to look up the public key. In particular, when ciphertexts of an IBE scheme do not reveal the identity of the recipient, this scheme is known as an anonymous IBE scheme. Recently, Blazy et al. (ARES'19) analyzed the trade-off between public safety and unconditional privacy in anonymous IBE and introduced a new notion that incorporates traceability into anonymous IBE, called anonymous IBE with traceable identities (AIBET). However, their construction is based on the discrete logarithm assumption, which is insecure in the quantum era. In this paper, we first formalize the consistency of tracing key of the AIBET scheme to ensure that no adversary can obtain information with the use of wrong tracing keys. Subsequently, we present a generic formulation concept that can be used to transform structure-specific lattice-based anonymous IBE schemes into an AIBET scheme. Finally, we apply this concept to Katsumata and Yamada's compact anonymous IBE scheme (Asiacrypt'16) to obtain the first quantum-resistant AIBET scheme that is secure under the ring learning with errors assumption.

Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable, for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank’s security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all. In this work, we report the experimental realisation of such a zero-knowledge protocol involving two separated verifier-prover pairs. Security is enforced via the physical principle of special relativity, and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances (400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain-based applications such as cryptocurrencies or smart contracts.

Key distribution protocols deal with generating, exchanging, and storing information (especially shared keys). In this paper, we compare three different types of protocols: classical, quantum key distribution, and blockchain-based protocols, with examples from each category, presenting the particularities and challenges of each one, including solutions and the impact of these protocols.

This paper studies zero-knowledge SNARKs for NP, where the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. We observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 20) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan (CRYPTO 20), yields linear-time SNARKs for R1CS. Specifically, for security parameter $\lambda$, and for an $N$-sized R1CS instance over a field of size $\exp(\lambda)$ and fixed $\epsilon > 0$, the prover incurs $O(N)$ finite field operations to produce a proof of size $O_\lambda(N^\epsilon)$ that can be verified in $O_\lambda(N^\epsilon)$---after a one-time preprocessing step, which requires $O(N)$ finite field operations. This reestablishes the main result of BCG. Arguably, our approach is conceptually simpler and more direct. Additionally, the polynomial commitment scheme that we distill from BCG is of independent interest; it improves over the prior state of the art by offering the first scheme where the time to commit and to prove an evaluation of a committed polynomial are both $O(N)$ finite field operations for an $N$-sized polynomial.

We further observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time to polylogarithmic---while maintaining a linear-time prover---by outsourcing the verifier's work via one layer of proof composition with an existing zkSNARK as the ``outer'' proof system. A similar result was recently obtained by Bootle, Chiesa, and Liu (ePrint 2020/1527).

Nowadays, genomic sequencing has become much more affordable for many people and, thus, many people own their genomic data in a digital format. Having paid for genomic sequencing, they want to make use of their data for different tasks that are possible only using genomics, and they share their data with third parties to achieve these tasks, e.g., to find their relatives in a genomic database. As a consequence, more genomic data get collected worldwide. The upside of the data collection is that unique analyses on these data become possible. However, this raises privacy concerns because the genomic data uniquely identify their owner, contain sensitive data about his/her risk for getting particular diseases, and even sensitive information about his/her family members.

In this paper, we introduce EPISODE - a highly efficient privacy-preserving protocol for Similar Sequence Queries (SSQs), which can be used for finding genetically similar individuals in an outsourced genomic database, i.e., securely aggregated from data of multiple institutions. Our SSQ protocol is based on the edit distance approximation by Asharov et al. (PETS'18), which we further optimize and extend to the outsourcing scenario. We improve their protocol by using more efficient building blocks and achieve a 5-6x run-time improvement compared to their work in the same two-party scenario.

Recently, Cheng et al. (ASIACCS'18) introduced protocols for outsourced SSQs that rely on homomorphic encryption. Our new protocol outperforms theirs by more than factor 24000x in terms of run-time in the same setting and guarantees the same level of security. In addition, we show that our algorithm scales for practical database sizes by querying a database that contains up to a million short sequences within a few minutes, and a database with hundreds of whole-genome sequences containing 75 million alleles each within a few hours.