International Association
for Cryptologic Research

This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time $2^{40}$ GEA-1 evaluations and using 44.5 GiB of memory. The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design.

In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time $2^{45.1}$ GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.

In this work, we study Certificate Transparency (CT), an important standardized extension of classical Web-PKI, deployed and integrated into major browsers. We evaluate the properties of the published design of CT-v1 (RFC 6962), and identify five major concerns, which persist in drafts for CT-v2. Most significantly, CT-v1 fails to achieve the main goal of the original CT publications, namely security with No Trusted Third Party (NTTP) and it does not ensure transparency for revocation status. Several recent works address some of these issues but at the cost of significant, non-evolutionary deviation from the existing standards and ecosystem.

In response, we present CTng, a redesign of CT. CTng achieves security, including transparency of certificate and of revocation status, with No Trusted Third Party, while preserving client’s privacy, allowing offline client validation of certificates, and facilitating resiliency to DoS. CTng is efficient and practical, and provides a possible next step in the evolution of PKI standards. We present a security analysis and an evaluation of our experimental open source prototype shows that CTng imposes acceptable communication and storage overhead.

In this note, we describe an attack against the ANSSI Side-Channel Analysis Database (ASCAD), which recovers the full key using the leakage of a single masked block cipher execution. The attack uses a new open-source Side-Channel Analysis Library (SCALib), which allows running the leakage profiling and attacking in less than 5 minutes. It exploits well-known techniques, yet improves significantly over the best known attacks against ASCAD. We conclude by questioning the impact of these experimental findings for side-channel security evaluations.

We study the problem of privacy-preserving approximate kNN search in an outsourced environment — the client sends the encrypted data to an untrusted server and later can perform secure approximate kNN search and updates. We design a security model and propose a generic construction based on locality-sensitive hashing, symmetric encryption, and an oblivious map. The construction provides very strong security guarantees, not only hiding the information about the data, but also the access, query, and volume patterns. We implement, evaluate efficiency, and compare the performance of two concrete schemes based on an oblivious AVL tree and an oblivious BSkiplist.

Improved attacks on generic small-domain Feistel ciphers with alternating round tweaks are obtained using linear cryptanalysis. This results in practical distinguishing and message-recovery attacks on the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. The data-complexity of the proposed attacks on FF3-1 and FEA-1 is $O(N^{r/2 - 1.5})$, where $N^2$ is the domain size and $r$ is the number of rounds. For example, FF3-1 with $N = 10^3$ can be distinguished from an ideal tweakable block cipher with advantage $\ge 1/10$ using $2^{23}$ encryption queries. Recovering the left half of a message with similar advantage requires $2^{24}$ data. The analysis of FF3-1 serves as an interesting real-world application of (generalized) linear cryptanalysis over the group $\mathbb{Z}/N\mathbb{Z}$.

Minimizing the round complexity of Byzantine Agreement (BA) protocols is a fundamental problem in distributed computing. The typical approach to achieve round efficient (randomized) BA is to have a weak form of BA, called graded consensus (GC), followed by a distributed coin, and to repeat this process until some termination condition is met---as introduced by Feldman and Micali (STOC'88).

In this work, we revisit the question of building BA from GC, or, more precisely, from generalizations of GC. Concretely, for Monte Carlo style BA, where the protocol is run for a fixed number of rounds in function of the security parameter (in contrast to protocols with probabilistic termination), we demonstrate that this generalization helps to considerably reduce the round complexity of BA.

In particular, assuming a setup for threshold signatures among the parties and corruption threshold $t<n/3$, we improve over the round complexity of the best known protocol by a factor of $1/2$, asymptotically; this is achieved by applying one single Feldman-Micali iteration consisting of one (generalized) GC instance and one round of coin tossing.

Our technique also applies to the dishonest-minority case ($t<n/2$), yielding an improvement by a factor of $1/4$ (asymptotically) over the round complexity of the best known fixed-round protocol.

Intelligent Composed Algorithms (ICA) have been developed as a mechanism for introducing new cryptographic algorithms into applications and PKIs. Using ICAs, known cryptographic algorithms (Component-Algorithms) can be combined in order to obtain a stronger mix of cryptographic algorithms or primitives. Using ICAs it is also possible to use known Component-Algorithms as mutual alternatives. Furthermore, the combined and alternative use of Component-Algorithms as ICAs shall enable agile use of cryptographic algorithms without having to change standards as X.509 or CMS. An Intelligent Composed Algorithm is a flexible group of cryptographic algorithms together with the corresponding rules for their combination. The rules for the combination of Component-Algorithms are defined as algorithms (Controlling-Algorithms) themselves. In applications, ICAs are used as conventional algorithms, described by an algorithm identifier (an OID) and matching parameters. The chosen Component-Algorithms are defined by parameters of the Controlling-Algorithm. The use of ICAs impose no need to modify higher-order standards for applications and protocols, as X.509, RFC 5280, RFC 6960, RFC 2986, RFC 4210, and RFC 5652.

Ridesharing is revolutionizing the transportation industry in many countries. Yet, the state of the art is based on heavily centralized services and platforms, where the service providers have full possession of the users’ location data. Recently, researchers have started addressing the challenge of enabling privacy-preserving ridesharing. The initial proposals, however, have shortcomings, as some rely on a central party, some incur high performance penalties, and most do not consider time preferences for ridesharing. TOPPool encompasses ridesharing based on the proximity of end-points of a ride as well as partial itinerary overlaps. To achieve the latter, we propose a simple yet powerful reduction to a private set intersection on trips represented as sets of consecutive road segments. We show that TOPPool includes time preferences while preserving privacy and without relying on a third party. We evaluate our approach on real-world data from the New York’s Taxi & Limousine Commission. Our experiments demonstrate that TOPPool is superior in performance over the prior work: our intersection-based itinerary matching runs in less than 0.3 seconds for reasonable trip length, in contrast, on the same set of trips prior work takes up to 10 hours.

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