International Association
for Cryptologic Research

Fully homomorphic encryption (FHE) is an encryption scheme which enables computation on encrypted data without revealing the underlying data. While there have been many advances in the field of FHE, developing programs using FHE still requires expertise in cryptography. In this white paper, we present a fully homomorphic encryption transpiler that allows developers to convert high-level code (e.g., C++) that works on unencrypted data into high-level code that operates on encrypted data. Thus, our transpiler makes transformations possible on encrypted data.

Our transpiler builds on Google's open-source XLS SDK (https://github.com/google/xls) and uses an off-the-shelf FHE library, TFHE (https://tfhe.github.io/tfhe/), to perform low-level FHE operations. The transpiler design is modular, which means the underlying FHE library as well as the high-level input and output languages can vary. This modularity will help accelerate FHE research by providing an easy way to compare arbitrary programs in different FHE schemes side-by-side. We hope this lays the groundwork for eventual easy adoption of FHE by software developers. As a proof-of-concept, we are releasing an experimental transpiler (https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler) as open-source software.

Though recent breakthroughs have greatly improved the efficiency of asynchronous Byzantine agreement protocols, they mainly focused on the setting with private setups, e.g., assuming a trusted dealer to establish non-interactive threshold cryptosystems. Challenges remain to reduce the large communication complexities in the absence of private setups, for example: (i) for asynchronous binary agreement ($\ABA$) with optimal resilience, prior private-setup free protocols (Cachin et al., CCS' 2002; Kokoris-Kogias et al., CCS' 2020) have to incur $\mathcal{O}(\lambda n^4)$ bits and $\mathcal{O}(n^3)$ messages; (ii) for asynchronous multi-valued agreement with external validity ($\VBA$), Abraham et al. [2] very recently gave the first elegant construction with $\mathcal{O}(n^3)$ messages, relying on only public key infrastructure (PKI), but the design still costs $\mathcal{O}(\lambda n^3 \log n)$ bits. Here $n$ is the number of participating parties and $\lambda$ is the cryptographic security parameter.

We for the first time close the remaining efficiency gap between the communication complexity and the message complexity of private-setup free asynchronous Byzantine agreements, i.e., reducing their communication cost to only $\mathcal{O}(\lambda n^3)$ bits on average. At the core of our design, we give a systematic treatment of reasonably fair common randomness, and proceed as follows:

- We construct a reasonably fair common coin (Canetti and Rabin, STOC' 1993) in the asynchronous setting with PKI instead of private setup, using only $\mathcal{O}(\lambda n^3)$ bit and constant asynchronous rounds. The common coin protocol ensures that with at least $1/3$ probability, all honest parties can output a common bit that is as if uniformly sampled, rendering a more efficient private-setup free $\ABA$ with expected $\mathcal{O}(\lambda n^3)$ bit communication and constant running time.

-More interestingly, we lift our reasonably fair common coin protocol to attain perfect agreement without incurring any extra factor in the asymptotic complexities, resulting in an efficient reasonably fair leader election primitive pluggable in all existing $\VBA$ protocols (including Cachin et al., CRYPTO' 2001; Abraham et al., PODC' 2019; Lu et al., PODC' 2020), thus reducing the communication of private-setup free $\VBA$ to expected $\mathcal{O}(\lambda n^3)$ bits while preserving expected constant running time. This leader election primitive and its construction might be of independent interest.

- Along the way, we also improve an important building block, asynchronous verifiable secret sharing (Canetti and Rabin, STOC' 1993) by presenting a private-setup free implementation costing only $\mathcal{O}(\lambda n^2)$ bits in the PKI setting. By contrast, prior art having the same communication complexity (Backes et al., CT-RSA' 2013) has to rely on a private setup.

Clustering is a popular unsupervised machine learning technique that groups similar input elements into clusters. It is used in many areas ranging from business analysis to health care. In many of these applications, sensitive information is clustered that should not be leaked. Moreover, nowadays it is often required to combine data from multiple sources to increase the quality of the analysis as well as to outsource complex computation to powerful cloud servers. This calls for efficient privacy-preserving clustering. In this work, we systematically analyze the state-of-the-art in privacy-preserving clustering. We implement and benchmark today's four most efficient fully private clustering protocols by Cheon et al. (SAC'19), Meng et al. (ArXiv'19), Mohassel et al. (PETS'20), and Bozdemir et al. (ASIACCS'21) with respect to communication, computation, and clustering quality. We compare them, assess their limitations for a practical use in real-world applications, and conclude with open challenges.

We provide the first construction of a succinct non-interactive argument (SNARG) for *all* polynomial time deterministic computations based on standard assumptions. For $T$ steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in $T$. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC'21].

Along the way, we also provide the first construction of non-interactive batch arguments for $\mathsf{NP}$ based solely on the LWE assumption. The size of the proof and CRS for a batch of $k$ statements grows only with the size of a *single* witness.

We study the problem of designing *non-interactive batch arguments* for $\mathsf{NP}$. Such an argument system allows an efficient prover to prove multiple $\mathsf{NP}$ statements, with size smaller than the combined witness length.

We provide the first construction of such an argument system for $\mathsf{NP}$ in the common reference string model based on standard cryptographic assumptions. Prior works either require non-standard assumptions (or the random oracle model) or can only support private verification.

At the heart of our result is a new *dual mode* interactive batch argument system for $\mathsf{NP}$. We show how to apply the correlation-intractability framework for Fiat-Shamir -- that has primarily been applied to proof systems -- to such interactive arguments.

Existing blind signature schemes that are secure for polynomially many concurrent executions of the signing protocol are either inefficient or rely on non-standard assumptions (even in the random-oracle model). We show the first efficient blind signature schemes achieving this level of security based on the RSA, factoring, or discrete logarithm assumptions (in the random-oracle model). Our core technique involves an extension and generalization of a transform due to Pointcheval (Eurocrypt '98) that allows us to convert certain blind signature schemes that are secure for (concurrently) issuing logarithmically many signatures into ones secure for (concurrently) issuing polynomially many signatures.

Nakamoto proof-of-work ledger consensus currently underlies the majority of deployed cryptocurrencies and smart-contract blockchains, especially when measured in carried value. While a long and fruitful line of work studying the provable security guarantees of this mechanism has succeeded to identify its exact security region---the set of parametrizations under which it possesses asymptotic security---the existing understanding falls short of providing practical settlement-time guarantees backed by this theory. This gap is most noticable for blockchains that are parametrized to maximize throughput by selecting block-creation time commesurate with network delays.

In this work we provide a new approach for obtaining such settlement-time guarantees. Our results give a rigorous framework for analyzing consistency that yields an efficient computational method for computing explicit bounds on settlement time as a function of honest and adversarial computational power and a bound on network delays. Our framework simultaneously provides upper and lower bounds on settlement times, which permits an immediate evaluation of the strength of the bounds. We implement this computational method and provide example results for several settings of interest. For Bitcoin, for example, the explicit upper and lower bounds are within 100 seconds of each other with 1 hour of settlement delay, 10 second networking delays, and a 20% adversary.

Nath and Sarkar propose algorithms to improve the efficiency of Diffie-Hellman key agreement using Curve448. In this note an error in the proof of correctness of the subtraction algorithm is described. An alternative argument is offered to fix this error without changing the algorithm or statement of correctness.

This post [1] represents an exciting opportunity to join the group as part of the SIPP [2] project: as part of the EPSRC center-to-center programme, SIPP is a collaborative effort between the 5 UK-based core project partners within the NCSC-supported Research Institute in Hardware Security & Embedded Systems (RISE) [3] and partners in Singapore. The project has a range of high- and low-level goals, spread over a number of work packages, which revolve around development and use of a secure, IoT-based hardware platform.

Given the project goals, a strong background and interest in at least one of the following research fields is desirable: 1) micro-processor design and implementation, 2) implementation (e.g., side-channel) attacks on cryptography, 3) energy efficiency and energy efficient technologies (spanning both hardware and software, and design-time and run-time).

Although you will have at least a first degree and preferably a PhD in Computer Science, Electrical Engineering, or closely related discipline, we view relevant industrial experience as extremely valuable and therefore equally encourage applicants of this type.

[1] https://www.bristol.ac.uk/jobs/find/details/?jobId=233994
[2] https://gow.epsrc.ukri.org/NGBOViewGrant.aspx?GrantRef=EP/S030867/1
[3] https://www.ukrise.org

Closing date for applications:

Contact: Daniel Page (Daniel.Page@bristol.ac.uk)

More information: https://www.bristol.ac.uk/jobs/find/details/?jobId=233994

This post [1] represents an exciting opportunity to join the group as part of the SCARV [2] project, which in turn forms part of the NCSC-supported Research Institute in Hardware Security & Embedded Systems (RISE) [3]. You will work in collaboration with industrial (i.e., Cerberus Security Labs. and Thales) and academic partners, to deliver more efficient, more secure platforms based on RISC-V.

Given the project goals, a strong background and interest in at least one of the following research fields is desirable: 1) micro-processor design and implementation, 2) implementation (e.g., side-channel) attacks on cryptography, including leakage modelling and simulation, 3) high-assurance hardware or software implementation, e.g., formal specification of and verification with respect to security properties.

Although you will have at least a first degree and preferably a PhD in Computer Science, Electrical Engineering, or closely related discipline, we view relevant industrial experience as extremely valuable and therefore equally encourage applicants of this type.

[1] https://www.bristol.ac.uk/jobs/find/details/?jobId=233794
[2] https://gow.epsrc.ukri.org/NGBOViewGrant.aspx?GrantRef=EP/R012288/1, https://www.scarv.org, https://github.com/scarv
[3] https://www.ukrise.org

Closing date for applications:

Contact: Daniel Page (Daniel.Page@bristol.ac.uk)

More information: https://www.bristol.ac.uk/jobs/find/details/?jobId=233794

The Program Chairs of Eurocrypt 2021, Anne Canteaut and François-Xavier Standaert, publish a detailed report on the Eurocrypt 2021 review process.

The report starts with a list of high-level goals pursued by the PC Chairs, and provides a description of the strategies implemented to try ensuring the goals, for the different steps of the review process. They finally discuss the advantages of these strategies and the challenges they raise (as they perceived them), with suggestions for future PC chairs.

The EC'21 PC Chairs hope this document can also help authors understand how their paper was evaluated.

The full text of the report can be found here: https://iacr.org/docs/EC21_report.pdf

Event date: 18 June 2021

Clearmatics is a protocol engineering company who are building a new financial market architecture that is more open, fair, and resilient than the legacy systems that are in use today.

We are looking for a cryptography engineer, who loves challenges and has a research-oriented mindset. You cultivate an adversarial attitude, always thinking ahead and trying to exploit the code you write and protocols you design. You always look forward to making your code more efficient without compromising on readability and robustness. Code quality and consistency mean everything to you.

Above all, you are a truth seeker and an outstanding communicator/listener not afraid of challenging (and being challenged by) your peers. Unconditional lover of simplicity and robustness, you never miss an opportunity to learn and extend your knowledge basis.

RESPONSIBILITIES

- Assist in the design of cryptographic protocols.

- Collaborate with your colleagues on the implementation of cryptographic primitives and protocols.

- Produce technical design specifications.

- Produce externally facing artefacts (e.g. blog posts, papers, documentation excerpts etc.)

- Support research colleagues in conducting their research.

- Interface with the Engineering team to ease the transition of the research pieces of code into robust production software fully integrated with our stack.

- Keep up with new research in the space.

REQUIREMENTS​

- Fluency in English (written and spoken).

- Background in applied Computer Science.

- Experience with system programming (C/C++/Rust).

- Strong applied cryptography skills (experience implementing robust elliptic curve cryptography).

- Outstanding algorithmic thinking.

- Strong focus on code quality/documentation and simplicity.

Nice to haves

- Knowledge of Unix and bash.

- Experience with constant time cryptography.

- Experience with cryptography on embedded systems.

- Experience with Ethereum or other blockchain projects.

- Experience contributing to open-source cryptography libraries.

- Experience with Pyt

Closing date for applications:

Contact: Stephanie Hawkes - stephanie.hawkes@clearmatics.com Or apply via: https://boards.greenhouse.io/clearmatics/jobs/5326634002

More information: https://boards.greenhouse.io/clearmatics/jobs/5326634002

The Institute of Information Security at University of Stuttgart offers a

fully-funded Postdoc position.

The successful candidate is expected to work on tool-supported formal analysis of cryptographic protocols and web applications building, among others, on our work published at EuroS&P 2021, S&P 2019, CSF 2017, CCS 2016, CCS 2015, ESORICS 2015, and S&P 2014. One goal is to provide tool-supported security analysis based on DY* for our web infrastructure model (WIM).

The position is available immediately with an internationally competitive salary (German public salary scale TV-L E13 or TV-L E14, depending on the candidate's qualification).

The Institute of Information Security offers a creative international environment for top-level international research in Germany's high-tech region.

The successful candidate should have a Ph.D. (or should be very close to completion thereof) in Computer Science, Mathematics, Information Security, or a related field. We value strong analytical skills. Knowledge in one or more of the following fields is an asset:

• Formal Methods (Verification, Theorem Proving, F*, Type Checking, etc.)
• Cryptographic Protocol Analysis
• Web Security

Knowledge of German is not required.

The deadline for applications is

July 4th, 2021.

Late applications will be considered until the position is filled. See the official job offering for details of how to apply.

Closing date for applications:

Contact: Prof. Dr. Ralf Küsters
Institute of Information Security
University of Stuttgart
Germany
https://sec.uni-stuttgart.de

More information: https://www.sec.uni-stuttgart.de/institute/job-openings/

Li and Micciancio (Eurocrypto 2021) shattered a widespread misconception regarding the security of protocols based on cpa-secure homomorphic encryption (HE). They showed an attack breaking security of HE-based protocols provided that the protocol employs an HE scheme for approximate numbers, like CKKS, and the adversary sees decrypted ciphertexts. However, their attack fails when employing exact HE schemes, like BGV, or denying access to decrypted data.

We show that the Li-Micciancio attack is only the tip of the iceberg: 1)We exhibit an input-recovery attack completely breaking the privacy of a wide and natural family of HE-based protocols, including protocols using only exact HE-schemes and with an adversary exposed solely to encrypted data. This proves that cpa-security is insufficient to ensure privacy in a much broader context than previously known. 2)To address the threat exhibited by our attack we introduce sufficient conditions, on either the encryption scheme or the protocol, that do guarantee privacy: (a) Every HE scheme with a sanitization algorithm (e.g., BGV and FHEW) can be transformed into a ``sanitized" scheme so that protocols instantiated with it preserve privacy against malicious adversaries. (b) Moreover, we characterize a natural sub-family of these protocols for which cpa-security does suffice to guarantee privacy, albeit against semi-honest adversaries.

To prove (2a) we define a notion of circuit-privacy+ that lies between semi-honest and malicious circuit-privacy and realize it from existing schemes; this may be of independent interest.

Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Shamir and Blakely in the 70s. It allows to strike a meaningful balance between availability and confidentiality of secret information. It has a host of applications most notably in threshold cryptography and multi-party computation. All known constructions of secret sharing (with the exception of those with a pathological choice of parameters) require access to uniform randomness. In practice, it is extremely challenging to generate a source of uniform randomness. This has led to a large body of research devoted to designing randomized algorithms and cryptographic primitives from imperfect sources of randomness.

Motivated by this, 15 years ago, Bosley and Dodis asked whether it is even possible to build 2-out-of-2 secret sharing without access to uniform randomness. In this work, we make progress towards resolving this question.

We answer this question for secret sharing schemes with important additional properties, i.e., either leakage-resilience or non-malleability. We prove that, unfortunately, for not too small secrets, it is impossible to construct any of 2-out-of-2 leakage-resilient secret sharing or 2-out-of-2 non-malleable secret sharing without access to uniform randomness.

Given that the problem whether 2-out-of-2 secret sharing requires uniform randomness has been open for a long time, it is reasonable to consider intermediate problems towards resolving the open question. In a spirit similar to NP-completeness, we study how the existence of a t-out-of-n secret sharing without access to uniform randomness is related to the existence of a t'-out-of-n' secret sharing without access to uniform randomness for a different choice of the parameters t,n,t',n'.

We introduce and construct memory-hard puzzles. Intuitively, a puzzle is memory-hard if it cannot be solved by any parallel random access machine (PRAM) algorithm with small (amortized) area-time complexity $t^{2-\varepsilon}$. The puzzles should also be easy to generate and should be solvable by a sequential PRAM algorithm running in total time $t$ and area-time complexity at most $t^2$. We construct memory-hard puzzles in the standard model using succinct randomized encodings (Bitansky et al., STOC 2015) under the minimal assumption that a memory-hard language exists. Intuitively, a language is memory-hard if it is undecidable by any PRAM algorithm with small (amortized) area-time complexity $t^{2 - \varepsilon}$ while the language can be decided in time $t$ and with area-time complexity at most $t^2$.

We give two applications which highlight the utility of memory-hard puzzles. For our first application, we give a construction of a (one-time) memory-hard function (MHF) in the standard model, using our memory-hard puzzles and additionally assuming indistinguishability obfuscation. Our construction is the first provable MHF in the standard model --- prior MHF constructions require idealized models (e.g., random oracle model) to prove security. For our second application, we show any cryptographic puzzle (e.g., memory-hard, time-lock) can be used to construct resource-bounded locally decodable codes (LDC) in the standard model, answering an open question of Blocki, Kulkarni, and Zhou (ITC 2020). Prior constructions required idealized primitives like random oracles and assuming that the encoding algorithm efficiency was not resource-constrained like the channel. In particular, assuming time-lock puzzles or memory-hard puzzles, we construct resource-bounded LDCs which are secure against low-depth channels or channels with small (amortized) area-time complexity, respectively.

Time-locked encryption can encrypt a message to a future time such that it can only be decrypted after that time. Potential applications include sealed bid auctions, scheduled confidential transactions, and digital time capsules.

Prior practical schemes for time-locked encryption rely on a clock-equipped trusted server, who periodically publishes a time-specific decryption key based on a long-term secret. Their main idea is to model time periods as identities in an identity-based encryption scheme. While such schemes allow encryption to a future time periods, they offer limited support for decryption of past ciphertexts. In particular, they force a client to be online when the key is published, or interact with the server to re-generate the key.

This paper proposes a new notion of time-locked encryption where an aggregated decryption key can be used to decrypt any ciphertext locked to a prior time. Furthermore, we decentralize the trust amongst a number of servers, such that it can tolerate up to a threshold number of (malicious) corruptions. We call our notion threshold aggregated time-locked encryption (TATLE). We propose a practical construction that supports compact decryption keys as well as compact ciphertexts (both logarithmic in the total lifetime). Our construction is based on bilinear pairing and adapts ideas from Canetti et al.'s binary tree encryption [Eurocypt 2003] and Naor et al.'s distributed pseudorandom functions [Eurocrypt 1999].

Since its invention in 1982, the LLL lattice reduction algorithm (Lenstra, Lenstra, Lovasz 1982) has found countless applications. In cryptanalysis, the two most prominent applications of LLL and its generalisations --e.g. Slide, BKZ and SD-BKZ-- are factoring RSA keys with extra information on the secret key via Coppersmith's method and the cryptanalysis of lattice-based schemes.

After almost 40 years of cryptanalytic applications, predicting and optimising lattice reduction algorithms remains an active area of research. While we do have theorems bounding the worst-case performance of these algorithms, those bounds are asymptotic and not necessarily tight when applied to practical or even cryptographic instances. Reasoning about the behaviour of those algorithms relies on heuristics and approximations, some of which are known to fail for relevant corner cases.

Decades after Lenstra, Lenstra, and Lovász gave birth to this fascinating and lively research area, this state of affairs became a more pressing issue recently. Motivated by post-quantum security, standardisation bodies, governments and industry started to move towards deploying lattice-based cryptographic algorithms. This spurred the refinement of those heuristics and approximations, leading to a better understanding of the behaviour of these algorithms over the last few years.

Lattice reduction algorithms, such as LLL and BKZ, proceed with repeated local improvements to the lattice basis, and each such local improvement means solving the short(est) vector problem in a lattice of a smaller dimension. Therefore, two questions arise: how costly is it to find those local improvements and what is the global behaviour as those improvements are applied.

While those two questions may not be perfectly independent, we will, in this survey, focus on the second one, namely, the global behaviour of such algorithms, given oracle access for finding local improvements. Our focus on the global behaviour is motivated by our intent to draw more of the community's attention to this aspect. We will take a particular interest in the behaviour of such algorithms on a specific class of lattices, underlying the most popular lattice problems to build cryptographic primitives, namely the LWE problem and the NTRU problem. We will emphasise on the approximations that have been made, their progressive refinements and highlight open problems to be addressed.

We present probabilistic dynamic I/O automata, a framework to model dynamic probabilistic systems. Our work extends dynamic I/O Automata formalism [1] to probabilistic setting. The original dynamic I/O Automata formalism included operators for parallel composition, action hiding, action renaming, automaton creation, and behavioral sub-typing by means of trace inclusion. They can model mobility by using signature modification. They are also hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. Our work extends to probabilistic settings all these features. Furthermore, we prove necessary and sufficient conditions to obtain the implementation monotonicity with respect to automata creation and destruction. Our work lays down the premises for extending composable secure-emulation [3] to dynamic settings, an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, secure distributed computation, cybersecure distributed protocols etc).