International Association
for Cryptologic Research

The recent development of machine learning and cloud computing arises a new privacy problem; how can one outsource computation on confidential data? Homomorphic encryption (HE) is a solution for that as it allows computation on encrypted data without decryption. The Cheon-Kim-Kim-Song (CKKS) scheme (Asiacrypt '17) is one of the highlighted fully homomorphic encryption (FHE) schemes as it is efficient to deal with encrypted real numbers, which are the usual data type for many applications such as machine learning. This paper proposes a generally applicable method to achieve high-precision approximate FHE using the following two techniques. First, we apply the concept of signal-to-noise ratio (SNR) and propose a method of maximizing the SNR of encrypted data by reordering homomorphic operations in the CKKS scheme. For that, the error variance is minimized instead of the upper bound of error when we deal with encrypted data. Second, we propose a novel polynomial approximation method for the CKKS scheme from the same perspective of minimizing error variance. We especially apply the approximation method to the bootstrapping of the CKKS scheme, where we achieve the smaller error variance in the bootstrapping compared to the prior arts. The performance improvement of the proposed methods for the CKKS scheme is verified by implementation over HE libraries: HEAAN and SEAL. The implementation results show that the message precision of the CKKS scheme is improved by reordering homomorphic operations and using the proposed polynomial approximation. Specifically, the proposed method uses only depth 8, although the bootstrapping precision is increased by 1 bit compared to that of the previous method using depth 11. We also suggest a loose lower bound of bootstrapping error in the CKKS scheme and show that the proposed method’s bootstrapping error is only 2.8 bits on average larger than the lower bound. Therefore, various applications’ quality of services using the proposed CKKS scheme, such as privacy-preserving machine learning, can be improved without compromising performance and security.

Public-key encryption (PKE) schemes or key-encapsulation mechanisms (KEMs) are fundamental cryptographic building blocks to realize secure communication protocols. There are several known transformations that generically turn weakly secure schemes into strongly (i.e., IND-CCA) secure ones. While most of these transformations require the weakly secure scheme to provide perfect correctness, Hofheinz, Hövelmanns, and Kiltz (HHK) (TCC 2017) have recently shown that variants of the Fujisaki-Okamoto (FO) transform can work with schemes that have negligible correctness error in the (quantum) random oracle model (QROM). Many recent schemes in the NIST post-quantum competition (PQC) use variants of these transformations. Some of their CPA-secure versions even have a non-negligible correctness error and so the techniques of HHK cannot be applied.

In this work, we study the setting of generically transforming PKE schemes with potentially large, i.e., non-negligible, correctness error to ones having negligible correctness error. While there have been previous treatments in an asymptotic setting by Dwork, Naor, and Reingold (EUROCRYPT 2004), our goal is to come up with practically efficient compilers in a concrete setting and apply them in two different contexts. Firstly, we show how to generically transform weakly secure deterministic or randomized PKEs into CCA-secure KEMs in the (Q)ROM using variants of HHK. This applies to essentially all candidates to the NIST PQC based on lattices and codes with non-negligible error for which we provide an extensive analysis. We thereby show that it improves some of the code-based candidates. Secondly, we study puncturable KEMs in terms of the Bloom Filter KEM (BFKEM) proposed by Derler et al. (EUROCRYPT 2018) which inherently have a non-negligible correctness error. BFKEMs are a building block to construct fully forward-secret zero round-trip time (0-RTT) key-exchange protocols. In particular, we show the first approach towards post-quantum secure BFKEMs generically from lattices and codes by applying our techniques to identity-based encryption (IBE) schemes with (non-)negligible correctness error.

Distributed ORAM (DORAM) is a multi-server variant of Oblivious RAM. Originally proposed to lower bandwidth, DORAM has recently been of great interest due to its applicability to secure computation in the RAM model, where circuit complexity and rounds of communication are equally important metrics of efficiency.

In this work, we construct the first DORAM schemes in the 2-server, semi-honest setting that simultaneously achieve sublinear server computation and constant rounds of communication.

We provide two constant-round constructions, one based on square root ORAM that has $O(\sqrt{N}\log N)$ local computation and another based on secure computation of a doubly efficient PIR that achieves local computation of $O(N^\epsilon)$ for any $\epsilon > 0$ but that allows the servers to distinguish between reads and writes. As a building block in the latter construction, we provide secure computation protocols for evaluation and interpolation of multivariate polynomials based on the Fast Fourier Transform, which may be of independent interest.

Modeling the spread of COVID-19 is crucial for any effort to manage the pandemic. However, detailed epidemiological simulations suffer from a scarcity of relevant empirical data, such as social contact graphs, because such data is inherently privacy-critical. Thus, there is an urgent need for a method to perform powerful epidemiological simulations on real-world contact graphs without disclosing privacy-critical information. In this work, we propose a practical framework for privacy-preserving epidemiological modeling (PEM) on contact information stored on mobile phones, like the ones collected by already deployed contact tracing apps. Unlike those apps, PEM allows for meaningful epidemiological simulations. This is enabled by a novel Threshold-PIR-SUM protocol to privately retrieve the sum of a fixed number of distinct values without revealing individual values. PEM protects the privacy of the users by not revealing sensitive data to the system operator or other participants, while enabling detailed predictive models of pandemic spread.

In this article, we discuss basic strategies that can be used to implement block ciphers in both software and hardware environments. As models for discussion, we use substitution-permutation networks which form the basis for many practical block cipher structures. For software implementation, we discuss approaches such as table lookups and bit-slicing, while for hardware implementation, we examine a broad range of architectures from high speed structures like pipelining, to compact structures based on serialization. To illustrate different implementation concepts, we present example data associated with specific methods and discuss sample designs that can be employed to realize different implementation strategies. We expect that the article will be of particular interest to researchers, scientists, and engineers that are new to the field of cryptographic implementation.

A single-sign-on (SSO) is an authentication system that allows a user to log in with a single identity and password to any of several related, yet independent, server applications. SSO solutions eliminate the need for users to repeatedly prove their identities to different applications and hold different credentials for each application. Token-based authentication is commonly used to enable an SSO experience on the web, and on enterprise networks. A large body of work considers distributed token generation which can protect the long-term keys against a subset of breached servers. A recent work (CCS'18) introduced the notion of Password-based Threshold Authentication (PbTA) with the goal of making password-based token generation for SSO secure against server breaches that could compromise both long-term keys and user credentials. They also introduced a generic framework called PASTA that can instantiate a PbTA system.

The existing SSO systems built on distributed token generation techniques, including the PASTA framework, do not admit password-update functionality. In this work, we address this issue by proposing a password-update functionality into the PASTA framework. We call the modified framework PAS-TA-U.

As a concrete application, we instantiate PAS-TA-U to implement in Python a distributed SSH key manager for enterprise networks (ESKM) that also admits a password-update functionality for its clients. Our experiments show that the overhead of protecting secrets and credentials against breaches in our system compared to a traditional single server setup is low (average 119 ms in a 10-out-of-10 server setting on Internet with 80 ms round trip latency).

Contact tracing is an important mitigation tool for national health services to fight epidemics such as COVID-19. While many of the existing approaches for automated contact tracing focus on privacy-preserving decentralized solutions, the use of blockchain in these applications is often suggested for the transparency and immutability of the data being collected.

We present CovidBloc, a contact tracing system that implements the COVID 19 exposure database on Hyperledger Fabric Blockchain Network. Like most decentralized contact tracing application, the participants of the CovidBloc are: (1) a mobile application running on a bluetooth-equipped smartphone, (2) a web dashboard for health officials, and (3) a backend server acting as a repository for data being collected. We have implemented all components of CovidBloc to make it a fully functional contact tracing application. It is hosted at https://anonymous.4open.science/r/c6caad6d-62a4-463c-8301-472e421b931f/.

The mobile application for CovidBloc is developed for Android. The exposure notification system in our mobile application is implemented as per the recently released draft documentation by Google and Apple. The exposure notification API from Google and Apple is only available to a limited number of teams per country.

The backend server is an important component of any automated contact tracing system which acts as a repository for exposure data to be pushed by smartphones upon authorization by the health staff. Since adding or removing information on the server has privacy consequences, it is required that the server should not be trusted. The backend server for CovidBloc is implemented on Hyperledger Fabric Blockchain network.

In the current world of the Internet-of-things and edge computing, computations are increasingly performed locally on small connected systems. As such, those devices are often vulnerable to adversarial physical access, enabling a plethora of physical attacks which is a challenge even if such devices are built for security.

As cryptography is one of the cornerstones of secure communication among devices, the pertinence of fault attacks is becoming increasingly apparent in a setting where a device can be easily accessed in a physical manner. In particular, two recently proposed fault attacks, Statistical Ineffective Fault Attack (SIFA) and the Fault Template Attack (FTA) are shown to be formidable due to their capability to bypass the common duplication based countermeasures. Duplication based countermeasures, deployed to counter the Differential Fault Attack (DFA), work by duplicating the execution of the cipher followed by a comparison to sense the presence of any effective fault, followed by an appropriate recovery procedure. While a handful of countermeasures are proposed against SIFA, no such countermeasure is known to thwart FTA to date.

In this work, we propose a novel countermeasure based on duplication, which can protect against both SIFA and FTA. The proposal is also lightweight with only a marginally additional cost over simple duplication based countermeasures. Our countermeasure further protects against all known variants of DFA, including Selmke, Heyszl, Sigl’s attack from FDTC 2016. It does not inherently leak side-channel information and is easily adaptable for any symmetric key primitive. The validation of our countermeasure has been done through gate-level fault simulation.

Private Set Intersection (PSI) is a specified protocol of secure Multi-Party Computation (MPC). PSI allows two parties to obtain the intersection of their private sets while nothing else is revealed. In contrast to the great demand for PSI in real-world applications, there is still no evaluation results of different general practical PSI framework. Most existing PSI implmentations are based on C/C++, which also makes them hard to compute in parallel. %We focus on OT-based PSI in this work. Oblivious transfer (OT) allows a party to obliviously choose messages from others. Lots of PSI protocols have been proposed in recent years, which achieve good performance and are regarded as one of the most potential PSI species. In this paper, we propose a generic Java-based PSI framework and implement all up-to-date OT-based PSI protocols within the framework until now. We evaluate these OT-based PSI protocols and the dependent cryptographic primitives and provide the best combination of primitives for constructing a best-performed OT-based PSI from the ground up. Additional optimizations are also applied to the protocols in our framework, including both generic and custom-tailored ones. We adopt filters to significantly reduce the communication of OT-based PSI protocols. The implementations in our framework support concurrence by using the natural feature of Java, which avoids to manurally allocate threads when using C/C++. We believe that our framework benefits a lot for future MPC and PSI researches and helps the promotion of PSI-based applications.

Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short.

We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these problems. We apply our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and demonstrate that our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches. We carried out extensive experiments using our estimation and solving framework, which we also make available with this work.

We discuss the setting of information-theoretically secure channel protocols where confidentiality of transmitted data should hold against unbounded adversaries. We argue that there are two possible scenarios: One is that the adversary is currently bounded, but stores today's communication and tries to break confidentiality later when obtaining more computational power or time. We call channel protocols protecting against such attacks future-secure. The other scenario is that the adversary already has extremely strong computational powers and may try to use that power to break current executions. We call channels withstanding such stronger attacks unconditionally-secure.

We discuss how to instantiate both future-secure and unconditionally-secure channels. To this end we first establish according confidentiality and integrity notions, then prove the well-known composition theorem to also hold in the information-theoretic setting: Chosen-plaintext security of the channel protocol, together with ciphertext integrity, implies the stronger chosen-ciphertext notion. We discuss how to build future-secure channel protocols by combining computational message authentication schemes like HMAC with one-time pad encryption. Chosen-ciphertext security follows easily from the generalized composition theorem. We also show that using one-time pad encryption with the unconditionally-secure Carter-Wegman MACs we obtain an unconditionally-secure channel protocol.

Semi-regular sequences over $\mathbb{F}_2$ are sequences of homogeneous elements of the algebra $ B^{(n)}=\mathbb{F}_2[X_1,...,X_n]/(X_1^2,...,X_n^2)$, which have as few relations between them as possible. It is believed that most such systems are semi-regular and this property has important consequences for understanding the complexity of Grobner basis algorithms such as F4 and F5 for solving such systems. In fact even in one of the simplest and most important cases, that of quadratic sequences of length $n$ in $n$ variables, the question of the existence of semi-regular sequences for all $n$ remains open. In this paper we present a new framework for the concept of semiregularity which we hope will allow the use of ideas and machinery from homological algebra to be applied to this interesting and important open question. First we introduce an analog of the Koszul complex and show that $\mathbb{F}_2$-semi-regularity can be characterized by the exactness of this complex. We show how the well known formula for the Hilbert series of a semiregular sequence can be deduced from the Koszul complex. Finally we show that the concept of first fall degree also has a natural description in terms of the Koszul complex.

Aggregate signcryption combines the functionalities of aggregate signature and encryption. Very recently, Zia & Ali [1] (Wireless Personal Communications, https://doi.org/10.1007/s11277-020-07637-z) proposed an elliptic curve cryptography (ECC) based multi-recipient aggregate signcryption scheme. The authors claimed that their scheme is correct, efficient, and secure against known attacks. However, by this comment, we show that their scheme is incorrect and the receiver(s) is unable to unsigncrypt the message.

A polynomial commitment scheme (PCS) provides the ability to commit to a polynomial over a finite field and prove its evaluation at points. A succinct PCS has commitment and evaluation proof size sublinear in the degree of the polynomial. An efficient PCS has sublinear proof verification. Recently, it has been shown that any efficient and succinct PCS can be used to construct a SNARK with similar security and efficiency characteristics. We define an additive PCS to capture a ``homomorphic" property of commitments over a computational group $\mathbb{G}$ of bounded size. All existing examples of additive schemes (e.g., Bulletproofs, KZG, DARK, Dory) are also what we call $m$-spanning, meaning that commitments to the monomials of degree less than $m$ generate $\mathbb{G}$. Our first technical result is a black-box transformation of any $m$-spanning additive PCS into a hiding PCS with a zero-knowledge evaluation proof. Our second technical result is that every additive succinct PCS supports efficient proof aggregation.

PCS proof aggregation reduces the task of proving evaluations of multiple commitments at multiple independent points to the task of proving the evaluation of a single ``aggregate" commitment at a single point. We present two flavors of aggregation: private and public. In private aggregation the prover has a private witness consisting of openings of the input commitments. In public aggregation, the prover/verifier share the same inputs, which includes non-interactive evaluation proofs for each input commitment. Our public aggregation protocol applies to any additive succinct PCS. Our private aggregation protocol applies more broadly to any succinct PCS that supports an efficient $\textit{linear combination scheme}$: a protocol for verifiably aggregating commitments into a new commitment to their linear combination. This includes non-additive schemes such as the post-quantum FRI-based PCS.

We apply these results to the Halo proof carrying data (PCD) system. Halo was originally built using the Bulletproofs inner-product argument as the underlying PCS, and was recently generalized to work with the KZG PCS. We show that Halo can be instantiated with any PCS that supports efficient PCS aggregation, private or public. Thus, our results show that efficient (zero-knowledge) SNARKs and PCD can be constructed from any succinct PCS that has an efficient linear combination scheme, even if the PCS itself is inefficient. These results yield new Halo-like PCD systems from PCS constructions beyond Bulletproofs and KZG, including DARK, FRI, and Dory. The post-quantum Halo instantiation from FRI is particularly surprising as FRI is not additive.

Prime integers are the backbone of most public key cryptosystems. Attacks often go after the primes themselves, as in the case of all factoring and index calculus algorithms. Primes are time sensitive cryptographic material and should be periodically changed. Unfortunately many systems use fixed primes for a variety of reasons, including the difficulty of generating trusted, random, cryptographically secure primes. This is particularly concerning in the case of discrete log based cryptosystems. This paper describes a variant of provable prime generation, intended for discrete logarithm based cryptography, based off Pocklington's theorem with improved efficiency, flexibility and security.

Recently, as the number of IoT (Internet of Things) devices has increased, the use of lightweight cryptographic algorithms that are suitable for environments with scarce resources has also increased. Consequently, the safety of such cryptographic algorithms is becoming increasingly important. Among them, side-channel analysis methods are very realistic threats. In this paper, we propose a novel differential fault attack method on the Lightweight Encryption Algorithm (LEA) cipher which became the ISO/IEC international standard lightweight cryptographic algorithm in 2019. Previously proposed differential fault attack methods on the LEA used the Single Bit Flip model, making it difficult to apply to real devices. The proposed attack method uses a more realistic attacker assumption, the Random Word Error model. We demonstrate that the proposed attack method can be implemented on real devices using an electromagnetic fault injection setup. Our attack method has the weakest attacker assumption among attack methods proposed to date. In addition, the number of required fault-injected ciphertexts and the number of key candidates for which exhaustive search is performed are the least among all existing methods. Therefore, when implementing the LEA cipher on IoT deivces, designers must apply appropriate countermeasures against fault injection attacks.

Event date: 10 December to 15 June 2021
Submission deadline: 15 June 2021

Event date: 6 July to 8 July 2021
Submission deadline: 16 February 2021
Notification: 15 April 2021

Event date: 7 July to

Project Title: Social and Societal Foundations of Cryptography: The Case of Large-Scale Protests. The Centre for Doctoral Training in Cyber Security for the Everyday at Royal Holloway seeks to recruit PhD students who will explore the social and societal foundations of cryptography. Cryptography is a field that actively interrogates its foundations. These foundations are, unsurprisingly and sensibly, understood to be of the complexity-theoretic and mathematical variety. However, cryptographic security notions -- and everything that depends on them -- do not exist in a vacuum, they have reasons to be. While the immediate objects of cryptography are not social relations, it presumes and models them. This fact is readily acknowledged in the introductions of cryptographic papers which illustrate the utility of the work by reference to some social situation where several parties have conflicting ends but a need or desire to interact. Yet, this part of the definitional work has not received the same rigour from the cryptographic community as complexity-theoretic and mathematical questions. This project aims to take first steps towards remedying this situation by grounding cryptographic security notions in findings emerging from ethnographic fieldwork in adversarial situations. In particular, it considers protesters in large-scale protests and aims to understand their security needs, practices and the technologies they rely upon. The project then also analyses these technologies, i.e. attempts to break their security, and proposes new solutions based on the findings from fieldwork. By bringing cryptographic security notions to *the field*, the project provokes a series of security questions about, for example, confidentiality and anonymity in online and offline networks, trust relations and how to establish them, onboarding and authentication practices. We seek applicants with either a background in mathematics and/or computer science or related disciplines or a background in ethnography or experience using related qualitative social science methods

Closing date for applications:

Contact: The studentship includes * Tuition fees: * Maintenance: £21,285 for each academic year. The CDT in Cyber Security for the Everyday can offer up to ten studentships per year, three of which can be awarded to international students (which includes EU and EEA.) contact Prof Martin Albrecht