International Association
for Cryptologic Research

In this work, we explore the problem of secure and efficient scalar multiplication on binary field using Kummer lines. Gaudry and Lubicz first introduced the idea of Kummer line in [12]. We investigate the possibilities of speedups using Kummer lines compared to binary Edwards curve and Weierstrass curves. Firstly, we propose a binary Kummer line $\mathsf{BKL}251$ on binary field $\mathbb{F}_{2^{251}}$ where the associated elliptic curve satisfies the required security conditions and offers 124.5-bit security which is same as the $\mathsf{BBE251}$ and $\mathsf{CURVE2251}$. $\mathsf{BKL}251$ also has small parameter and small base point. We implement the software of $\mathsf{BKL}251$ using the instruction ${\tt PCLMULQDQ}$ of modern Intel processors. For fair comparison, we also implement the software $\mathsf{BEd}251$ for binary Edwards curve introduced in [4] using the same field arithmetic library of the $\mathsf{BKL}251$ and thus this work also complements the works of [7,4]. In both the implementations, scalar multiplications take constant time which use Montgomery ladder. Binary Kummer line requires $4[\mathsf{M}]+5[\mathsf{S}]+1[\mathsf{C}]+1[\mathsf{B}]$ field operations for each ladder step where ladder step of binary Edwards curve requires $4[\mathsf{M}]+4[\mathsf{S}]+2[\mathsf{C}]+1[\mathsf{B}]$. Our experimental results show that fixed-base scalar multiplication of $\mathsf{BKL}251$ is $8.36\%-9.33\%$ faster than that of $\mathsf{BEd}251$. On the other hand, variable-base scalar multiplications take almost same time for both the curves (variable-base scalar multiplication of $\mathsf{BKL}251$ is $0.25\%-1.55\%$ faster than that of $\mathsf{BEd}251$).

Machine learning has started to be deployed in fields such as healthcare and finance, which involves dealing with a lot of sensitive data. This propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known machine learning algorithms -- Linear Regression, Logistic Regression, Neural Networks, and Convolutional Neural Networks.

Our 4PC protocol tolerating at most one malicious corruption is practically efficient as compared to Gordon et al. (ASIACRYPT 2018) as the 4th party in our protocol is not active in the online phase, except input sharing and output reconstruction stages. Concretely, we reduce the online communication as compared to them by 1 ring element. We use the protocol to build an efficient mixed-world framework (Trident) to switch between the Arithmetic, Boolean, and Garbled worlds. Our framework operates in the offline-online paradigm over rings and is instantiated in an outsourced setting for machine learning, where the data is secretly shared among the servers. Also, we propose conversions especially relevant to privacy-preserving machine learning. With the privilege of having an extra honest party, we outperform the current state-of-the-art ABY3 (for three parties), in terms of both rounds as well as communication complexity.

The highlights of our framework include using a minimal number of expensive circuits overall as compared to ABY3. This can be seen in our technique for truncation, which does not affect the online cost of multiplication and removes the need for any circuits in the offline phase. Our B2A conversion has an improvement of $\mathbf{7} \times$ in rounds and $\mathbf{18} \times$ in the communication complexity. In addition to these, all of the special conversions for machine learning, e.g. Secure Comparison, achieve constant round complexity.

The practicality of our framework is argued through improvements in the benchmarking of the aforementioned algorithms when compared with ABY3. All the protocols are implemented over a 64-bit ring in both LAN and WAN settings. Our improvements go up to $\mathbf{187} \times$ for the training phase and $\mathbf{158} \times$ for the prediction phase when observed over LAN and WAN.

Searchable encryption can provide secure search over encrypted cloud-based data without infringing data confidentiality and data searcher privacy. In this work, we focus on a secure search service providing fine-grained and expressive search functionality, which can be seen as a general extension of searchable encryption and called attribute-based multi-keyword search (ABMKS). In most of the existing ABMKS schemes, the ciphertext size of keyword index (encrypted index) grows linearly with the number of the keyword associated with a file, so that the computation and communication complexity of keyword index is limited to O(m) , where m is the number of the keyword. To address this shortage, we propose the first ABMKS scheme through utilizing keyword dictionary tree and the subset cover, in such a way that the ciphertext size of keyword index is not dependent on the number of underlying keyword in a file. In our design, the complexity of computation and the complexity of the keyword index are at most O ( 2· log (n/2) ) for the worst case, but O(1) for the best case, where n is the number of keyword in a keyword dictionary. We also present the security and the performance analysis to demonstrate that our scheme is both secure and efficient in practice.

We consider the problem of amplifying two-party coin-tossing protocols: given a protocol where it is possible to bias the common output by at most $\rho$, we aim to obtain a new protocol where the output can be biased by at most $\rho^\star<\rho$. We rule out the existence of a natural type of amplifiers called oblivious amplifiers for every $\rho^\star<\rho$. Such amplifiers ignore the way that the underlying $\rho$-bias protocol works and can only invoke an oracle that provides $\rho$-bias bits.

We provide two proofs of this impossibility. The first is by a reduction to the impossibility of deterministic randomness extraction from Santha-Vazirani sources. The second is a direct proof that is more general and also rules outs certain types of asymmetric amplification. In addition, it gives yet another proof for the Santha-Vazirani impossibility.

Historically, fault diagnosis for integrated circuits has singularly dealt with reliability concerns. In contrast, a cryptographic circuit needs to be primarily evaluated concerning information leakage in the presence of maliciously crafted faults. While Differential Fault Attacks (DFAs) on symmetric ciphers have been known for over 20 years, recent developments have tried to structurally classify the attackers’ capabilities as well as the properties of countermeasures. Correct realization of countermeasures should still be manually verified, which is error-prone and infeasible for even moderate-size real-world designs. Here, we introduce the concept of Cryptographic Fault Diagnosis, which revises and shapes the notions of fault diagnosis in reliability testing to the needs of evaluating cryptographic implementations. Additionally, we present VerFI, which materializes the idea of Cryptographic Fault Diagnosis. It is a fully automated, open-source fault detection tool processing the gate-level representation of arbitrary cryptographic implementations. By adjusting the bounds of the underlying adversary model, VerFI allows us to rapidly examine the desired fault detection/correction capabilities of the given implementation. Among several case studies, we demonstrate its application on an implementation of LED cipher with combined countermeasures against side-channel analysis and fault-injection attacks (published at CRYPTO 2016). This experiment revealed general implementation flaws and undetectable faults leading to successful DFA on the protected design with full-key recovery.

The 2019 election has closed and 588 IACR members casted their votes. The results are below, with elected candidates in bold:

Candidates for IACR President:
Michel Abdalla 350
Greg Rose 221

Candidates for IACR Vice-President:
Shai Halevi 523

Candidates for IACR Treasurer:
Brian LaMacchia 527

Candidates for IACR Secretary:
Joppe W. Bos 524

Candidates for IACR Director:
Peter Schwabe 277
Bart Preneel 361
Muthuramakrishnan Venkitasubramaniam 173
Huaxiong Wang 167
Marc Fischlin 234
Jung Hee Cheon 178
Leonie Simpson 149
François-Xavier Standaert 243

Congratulations to all elected members and thank to you all candidates for your contributions to the IACR and willingness to serve.

Election results can be verified at https://vote.heliosvoting.org/helios/e/IACR2019

In public key broadcast encryption, anyone can securely transmit a message to a group of receivers such that privileged users can decrypt it. The three important parameters of the broadcast encryption scheme are the length of the ciphertext, the size of private/public key, and the performance of encryption/decryption. It is suggested to decrease them as much as possible, however, it turns out that decreasing one increases the other in most schemes.

This paper proposes a new broadcast encryption scheme for tiny IoT equipments (BESTIE), minimizing the private key size in each user. In the proposed scheme, the private key size is O(log n), the public key size is O(log n), the encryption time per subset is O(log n), the decryption time is O(log n), and the ciphertext text size is O(r), where n denotes the maximum number of users and r indicates the number of revoked users. The proposed scheme is the first subset difference based broadcast encryption scheme to reduce the private size O(log n) without sacrificing the other parameters. We prove that our proposed scheme is secure under q-Simplified Multi-Exponent Bilinear Diffie-Hellman (q-SMEBDH) in the standard model.

As perfect building blocks for the diffusion layers of many symmetric-key primitives, the construction of MDS matrices with light-weight circuits has received much attention from the symmetric-key community. One promising way of realizing low-cost MDS matrices is based on the iterative construction: a low-cost matrix becomes MDS after rising it to a certain power. To be more specific, if $A^t$ is MDS, then one can implement $A$ instead of $A^t$ to achieve the MDS property at the expense of an increased latency with $t$ clock cycles. In this work, we identify the exact lower bound of the number of nonzero blocks for a $4 \times 4$ block matrix to be potentially iterative-MDS. Subsequently, we show that the theoretically lightest $4 \times 4$ iterative MDS block matrix (whose entries or blocks are $4 \times 4$ binary matrices) with minimal nonzero blocks costs at least 3 XOR gates, and a concrete example achieving the 3-XOR bound is provided. Moreover, we prove that there is no hope for previous constructions (GFS, LFS, DSI, and spares DSI) to beat this bound. Since the circuit latency is another important factor, we also consider the lower bound of the number of iterations for certain iterative MDS matrices. Guided by these bounds and based on the ideas employed to identify them, we explore the design space of lightweight iterative MDS matrices with other dimensions and report on improved results. Whenever we are unable to find better results, we try to determine the bound of the optimal solution. As a result, the optimality of some previous results is proved.

Saber is a module lattice-based CCA-secure key encapsulation mechanism (KEM) which has been shortlisted for the second round of NIST's Post Quantum Cryptography Standardization project. To attain simplicity and efficiency on constrained devices, the Saber algorithm is serial by construction. However, on high-end platforms, such as modern Intel processors with AVX2 instructions, Saber achieves limited speedup using vector processing instructions due to its serial nature.

In this paper we overcome the above-mentioned algorithmic bottleneck and propose a high-throughput software implementation of Saber, which we call `SaberX4', targeting modern Intel processors with AVX2 vector processing support. We apply the batching technique at the highest level of the implementation hierarchy and process four Saber KEM operations simultaneously in parallel using the AVX2 vector processing instructions. Our proof-of-concept software implementation of SaberX4 achieves nearly 1.5 times higher throughput at the cost of latency degradation within acceptable margins, compared to the AVX2-optimized non-batched implementation of Saber by its authors.

We anticipate that both latency and throughput of SaberX4 will improve in the future with improved computer architectures and more optimization efforts.

Cryptosystems based on Learning with Errors or related problems are central topics in recent cryptographic research. One main witness to this is the NIST Post-Quantum Cryptography Standardization effort. Many submitted proposals rely on problems related to Learning with Errors. Such schemes often include the possibility of decryption errors with some very small probability. Some of them have a somewhat larger error probability in each coordinate, but use an error correcting code to get rid of errors. In this paper we propose and discuss an attack for secret key recovery based on generating decryption errors, for schemes using error correcting codes. In particular we show an attack on the scheme {\sf LAC}, a proposal to the NIST Post-Quantum Cryptography Standardization that has advanced to round 2. In a standard setting with CCA security, the attack first consists of a precomputation of special messages and their corresponding error vectors. This set of messages are submitted for decryption and a few decryption errors are observed. In a statistical analysis step, these vectors causing the decryption errors are processed and the result reveals the secret key. The attack only works for a fraction of the secret keys. To be specific, regarding {\sf LAC}256, the version for achieving the 256-bit classical security level, we recover one key among approximately \(2^{64}\) public keys with complexity \(2^{79}\), if the precomputation cost of \(2^{162}\) is excluded. We also show the possibility to attack a more probable key (say with probability \(2^{-16}\)). This attack is verified via extensive simulation.

We further apply this attack to {\sf LAC}256-v2, a new version of {\sf LAC}256 in round 2 of the NIST PQ-project and obtain a multi-target attack with slightly increased precomputation complexity (from \(2^{162}\) to \(2^{171}\)). One can also explain this attack in the single-key setting as an attack with precomputation complexity of \(2^{171}\) and success probability of \(2^{-64}\).

Distributed randomness is very useful for many applications, such as smart contract, the proof-of-stake-based blockchain, elliptic curve generation and lottery. Randomness beacon protocols are proposed, which are aimed at continuously distributed randomness generation. However, a reliable source of distributed randomness is gained with difficulty because of Byzantine behavior which may lead to bias for distributed randomness. These Byzantine behaviors include, but not limited to, the “last actor” problem, DoS attack, and collusion attack. Various cryptography schemes have been used to generate distributed randomness. Current constructions face challenging obstacles due to high communication overheads and collusion problems. Given these barriers, we propose a new protocol that is the first precept to utilize attribute-based encryption for distributed randomness (ABERand). Compared to existing state- of-the-art public distributed randomness protocols, ABERand possesses distinguished scalability, security and efficiency. More specifically, we resolve the “last actor” problem and make ABERand an intensive output randomness beacon with com- munication complexity O(n2), computation complexity O(1), verification complexity O(n), and communication complexity O(n) of nodes adding/removing.

Data, an important asset in digital economy, has fueled the emergence of a new data trading market. Big data market can efficiently promote data trading and further increases the utility of data. However, to realize effective data trading, several challenges needs to be resolved. First, it needs to resolve disputes over data availability in the data trad- ing. Second, atomic exchange and payment fairness between the seller and the buyer are hard to guarantee. Third, data trading platform is the single-point-failure. In this paper, we resolve these challenges by pre- senting a valid blockchain-based data trading ecosystem. The ecosystem constructs a decentralized arbitration mechanism to address the dispute over data availability in data trading. The ecosystem also designs a sale contract and a deterministic public-key encryption algorithm to guaran- tee fairness of data trading between the seller and buyer. The features of blockchain is preventing single-point-failure of data trading platform. We prove the desirable security properties that a secure data trading ecosystem should have. Discussion of the presented ecosystem is given. To demonstrate availability, we implement our proposed data trading ecosystem using smart contract in Solidity and program in Java, and evaluate its performance.

Event date: 14 September to 17 September 2020

Event date: 25 May to 28 May 2020
Submission deadline: 11 February 2020

Event date: 2 July to 3 July 2020

Event date: 8 June to 11 June 2020
Submission deadline: 17 February 2020
Notification: 10 April 2020

Genetic data is an indispensable part of big data, promoting the advancement of life science and biomedicine. Yet, highly private genetic data also brings concerns about privacy risks in data shar- ing. In our work, we adopt the cryptographic prim- itive Secure Function Evaluation (SFE) to address this problem. A secure SFE scheme allows insti- tutions and hospitals to compute a function while preserving the privacy of their input data, and each participant knows nothing but their own input and the final result. In our work, we present privacy-preserving solutions for Human Leukocyte Antigen (HLA) matching and two popular biostatistics tests: Chi-squared test and odds ratio test. We also show that our protocols are compatible with multiple databases simultaneously and could feasibly han- dle larger-scale data up to genome-wide level. This approach may serve as a new way to jointly analyze distributed and restricted genetic data among insti- tutions and hospitals. Meanwhile, it can potentially be extended to other genetic analysis algorithms, allowing individuals to analyze their own genomes without endangering data privacy.

An elliptic curve known as Curve448 over the finite field $\mathbb{F}_p$, where $p=2^{448}-2^{224}-1$ has been proposed as part of the Transport Layer Security (TLS) protocol, version 1.3. Elements of $\mathbb{F}_p$ can be represented using 7 limbs where each limb is a 64-bit quantity. In this paper, we describe efficient algorithms for reduction modulo $p$ that are required for performing field arithmetic in $\mathbb{F}_p$. A key feature of our algorithms is that we provide the relevant proofs of correctness. Based on the proofs of correctness we point out the incompleteness of the reduction methods in the previously known fastest code for implementing arithmetic in $\mathbb{F}_p$.

Traceable and linkable ring signature scheme (TLRS) plays a major role in the construction of regulatable privacy-preserving blockchains, as it empowers the regulator with traceability of signers' identities. A recent work by Li et al. gives a modular construction of TLRS by usage of classic ring signature, one-time signature and zero-knowledge proofs. In this paper, we propose a simpler method to construct TLRS directly from classic ring signature and one-time signature without additional zero-knowledge proofs and verifications for validity of users' public keys. Moreover, the security proof of the new TLRS is also given to achieve anonymity, unforgeability, linkability, nonslanderability and traceability.

Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input $x$ is confidential but certain partial information $g(x)$ of it as well, standard PFE fails to provide meaningful input privacy if $g$ and the function $f$ to be computed fall into the same function class.

Our work investigates the question whether it is possible to achieve a reasonable level of input and function privacy simultaneously even in the above cases. We propose the notion of Controlled PFE (CPFE) with different flavours of security and answer the question affirmatively by showing simple, generic realizations of the new notions. Our main construction, based on functional encryption (FE), also enjoys strong reusability properties enabling, e.g. fast computation of the same function on different inputs. To demonstrate the applicability of our approach, we show a concrete instantiation of the FE-based protocol for inner product computation that enables secure statistical analysis (and more) under the standard Decisional Diffie--Hellman assumption.