## IACR News

Here you can see all recent updates to the IACR webpage. These updates are also available:

There is currently a problem with the jobs channel, and new jobs listings are not appearing here. Please see the jobs page.

#### 13 November 2019

###### Haidian District, China, 14 September - 17 September 2020

CHES
Event date: 14 September to 17 September 2020

###### Aarhus N, Denmark, 25 May - 28 May 2020

Event Calendar
Event date: 25 May to 28 May 2020

Submission deadline: 11 February 2020

Submission deadline: 11 February 2020

###### Be'er Sheva, Israel, 2 July - 3 July 2020

Event Calendar
Event date: 2 July to 3 July 2020

###### Estosadok, Russia, 8 June - 11 June 2020

Event Calendar
Event date: 8 June to 11 June 2020

Submission deadline: 17 February 2020

Notification: 10 April 2020

Submission deadline: 17 February 2020

Notification: 10 April 2020

#### 11 November 2019

###### Jinming Cui, Huaping Li, Meng Yang

ePrint Report
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.

###### Kaushik Nath, Palash Sarkar

ePrint Report
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$.

###### Wulu Li, Lei Chen, Xin Lai, Xiao Zhang, Jiajun Xin

ePrint Report
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.

###### Máté Horváth, Levente Buttyán, Gábor Székely, Dóra Neubrandt

ePrint Report
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.

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.

###### Dipayan Das, Jeffrey Hoffstein , Jill Pipher, William Whyte , Zhenfei Zhang

ePrint Report
In this paper we revisit the modular lattice signature scheme
and its efficient instantiation known as pqNTRUSign.
First, we show that a modular lattice
signature scheme can be based on a standard lattice problem.
The fundamental problem that needs to be solved by the signer or a potential forger is recovering a lattice vector with a restricted norm, given the least significant bits. We
show that this problem is equivalent to the short integer solution (SIS) problem
over the corresponding lattice.

In addition, we show that by replacing the uniform sampling in pqNTRUSign with a bimodal Gaussian sampling, we can further reduce the size of a signature. An important new contribution, enabled by this Gaussian sampling version of pqNTRUSign, is that we can now perform batch verification of messages signed by the same public key, which allows the verifier to check approximately 24 signatures in a single verification process.

In addition, we show that by replacing the uniform sampling in pqNTRUSign with a bimodal Gaussian sampling, we can further reduce the size of a signature. An important new contribution, enabled by this Gaussian sampling version of pqNTRUSign, is that we can now perform batch verification of messages signed by the same public key, which allows the verifier to check approximately 24 signatures in a single verification process.

###### Dragos Rotaru, Nigel P. Smart, Titouan Tanguy, Frederik Vercauteren, Tim Wood

ePrint Report
We present an actively secure, practical protocol to generate the distributed secret keys needed in the SPDZ offline protocol.
The resulting distribution of the public and secret keys is such that the associated SHE `noise' analysis is the same as
if the distributed keys were generated by a trusted setup. We implemented the presented protocol for distributed BGV key generation within the SCALE-MAMBE framework. Our method makes use of a new method for creating doubly (or even more)
authenticated bits in different MPC engines, which has applications in other areas of MPC-based secure computation.
We were able to generate keys for two parties and a plaintext size of 64 bits in less than ten minutes, and approximately half an hour for a 128 bit prime.

###### Divesh Aggarwal, Maciej Obremski

ePrint Report
Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs in ICS 2010, have emerged in the last few years as a fundamental object at the intersection of cryptography and coding theory. Non-malleable codes provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely "unrelated value''.

The family which received the most attention is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually.

In this work, we give a constant rate non-malleable code from the tampering family containing so called 2-lookahead functions and forgetful functions, and combined with the work of Dodis, Kazana and the authors from STOC 2015, this gives the first constant rate non-malleable code in the split-state model with negligible error.

The family which received the most attention is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually.

In this work, we give a constant rate non-malleable code from the tampering family containing so called 2-lookahead functions and forgetful functions, and combined with the work of Dodis, Kazana and the authors from STOC 2015, this gives the first constant rate non-malleable code in the split-state model with negligible error.

###### Mark Abspoel, Anders Dalskov, Daniel Escudero, Ariel Nof

ePrint Report
MPC over rings like $\mathbb Z_{2^{32}}$ or $\mathbb Z_{2^{64}}$ has received a lot of attention recently due to their potential benefits in implementation and performance.
Several protocols for active security over these rings have been proposed recently, including an implementation in the dishonest majority setting due to Damgård et al. (S&P 2019) and in the popular three-party and one corruption setting. However, to this date, no concretely-efficient protocol for arithmetic computation over rings in the honest majority setting, which works for any number of parties, have been proposed.
In this work, we present a new compiler for MPC over the ring $\mathbb Z_{2^{k}}$ in the honest majority setting, that takes several building blocks, which can be essentially instantiated using semi-honest protocols, and turn them into a maliciously secure protocol. Our compiler follows the framework of Chida et al. (CRYPTO 18) for finite fields, and makes it compatible for rings using techniques from the work of Cramer et al. (CRYPTO 18), with only small additional overhead. Per multiplication gate, our compiler requires only two invocations of a semi-honest multiplication protocol over the larger ring $\mathbb Z_{2^{k+s}}$, where $s$ is the statistical security parameter. As with previous works
in this area aiming to achieve high efficiency, our protocol is secure with abort and does not achieve fairness, meaning that the adversary may receive output while the honest parties do not.

We provide two efficient instantiations for our compiler. The first instantiation is for the three-party case and is based on replicated secret sharing, where the resulting protocol requires each party to send just $2(k+s)$ bits per multiplication gate. To the best of our knowledge, this is the most efficient three-party protocol for large rings to this date. Our second instantiation is for any number of parties. In this case we manage to instantiate our compiler with a variant of Shamir secret sharing that was recently proposed by Abspoel et al. (TCC 2019). We show that the theoretical constructions from Abspoel et al. (TCC 2019) can be instantiated efficiently and prove that they satisfy the properties required by our building blocks. The resulting protocol requires each party to send just $14(k+s) \log n$ bits per multiplication gate. To the best of our knowledge, this is the first concretely-efficient protocol for MPC over rings with an honest majority that works for any number of parties. We implemented our two protocols, run extensive experiments to measure their performance and report their efficiency. Our results prove that efficient honest-majority MPC over rings is possible.

We provide two efficient instantiations for our compiler. The first instantiation is for the three-party case and is based on replicated secret sharing, where the resulting protocol requires each party to send just $2(k+s)$ bits per multiplication gate. To the best of our knowledge, this is the most efficient three-party protocol for large rings to this date. Our second instantiation is for any number of parties. In this case we manage to instantiate our compiler with a variant of Shamir secret sharing that was recently proposed by Abspoel et al. (TCC 2019). We show that the theoretical constructions from Abspoel et al. (TCC 2019) can be instantiated efficiently and prove that they satisfy the properties required by our building blocks. The resulting protocol requires each party to send just $14(k+s) \log n$ bits per multiplication gate. To the best of our knowledge, this is the first concretely-efficient protocol for MPC over rings with an honest majority that works for any number of parties. We implemented our two protocols, run extensive experiments to measure their performance and report their efficiency. Our results prove that efficient honest-majority MPC over rings is possible.

###### Hamid Nejatollahi, Sina Shahhosseini, Rosario Cammarota, Nikil Dutt

ePrint Report
Quantum computers threaten to compromise public-key cryptography schemes such as DSA and ECDSA in polynomial time, which poses an imminent threat to secure signal processing. The cryptography community has responded with the
development and standardization of post-quantum cryptography (PQC) algorithms, a class of public-key algorithms based on hard problems that no known quantum algorithms can solve in polynomial time. Ring learning with error (RLWE) lattice-
based cryptographic (LBC) protocols are one of the most promising families of PQC schemes in terms of efficiency and versatility. Two common methods to compute polynomial multiplication, the most compute-intensive routine in the
RLWE schemes are convolutions and Number Theoretic Transform (NTT).
In this work, we explore the energy efficiency of polynomial multiplier using systolic architecture for the first time. As an early exploration, we design two high-throughput systolic array polynomial multipliers, including NTT-based and convolution-based, and compare them to our low-cost sequential (non-systolic) NTT-based multiplier. Our sequential NTT-based multiplier achieves more than 3x speedup over the state-of-the-art FGPA implementation of the polynomial multiplier in the NewHope-Simple key exchange mechanism on a low-cost Artix7 FPGA.
When synthesized on a Zynq UltraScale+ FPGA, the NTT-based systolic and convolution-based systolic designs achieve on average 1.7x and 7.5x speedup over our sequential NTT-based multiplier respectively, which can lead to generating over
2x more signatures per second by CRYSTALS-Dilithium, a PQC digital signature scheme. These explorations will help designers select the right PQC implementations for making future signal processing applications quantum-
resistant.

###### Mathias Hall-Andersen

ePrint Report
FastSwap is a simple and concretely efficient contingent payment scheme for complex predicates, inspired by FairSwap.
FastSwap only relies on symmetric primitives (in particular symmetric encryption and cryptographic hash functions) and avoids `heavy-weight' primitives such as general ZKP systems.
FastSwap is particularly well-suited for applications where the witness or predicate is large (on the order of MBs / GBs) or expensive to calculate.
Additionally FastSwap allows predicates to be implemented using virtually any computational model (including branching execution), which e.g. enables practitioners to express the predicate in smart contract languages already familiar to them, without an expensive transformation to satisfiability of arithmetic circuits.
The cost of this efficiency during honest execution is a logarithmic number of rounds during
a dispute resolution in the presence of a corrupted party (compared to constant round complexity for existing schemes). Let the witness be of size $|w|$ and the predicate of size $|P|$, where computing $P(w)$ takes $n$ steps. In the honest case the off-chain communication complexity is $|w| + |P| + c$ for a small constant $c$, the on-chain communication complexity is $c'$ for a small constant $c'$. In the malicious case the on-chain communication complexity is $O(\log n)$ with small constants. Concretely with suitable optimizations the number of rounds (on-chain transactions) for a computation of $2^{30}$ steps can be brought to $2$ in the honest case with an estimated cost of $\approx 2$ USD on the Ethereum blockchain and to $14$ rounds with an estimated cost of $\approx 4$ USD in case of a dispute.

###### Borja Gómez

ePrint Report
Conventional asymmetric key exchange protocols rely on computing elements in commutative groups, where the employed trapdoor-permutation function is commutative, allowing Alice and Bob to compute the same element in $G$ as changing the orders of the variables or elements doesn't alter the output. The research found in this paper is focused on the analysis of key exchange protocols found in non-commutative cryptography, sometimes called group-based cryptography. Variations of these schemes made by the author are also included. Concretely, four schemes are presented using matrices over finite fields and permutation groups containing all the theory to break these schemes along with its pseudo-code and implementations in Mathematica.

#### 07 November 2019

###### Dmitrii Koshelev

ePrint Report
This article generalizes the simplified Shallue--van de Woestijne--Ulas (SWU) method of deterministic finite field mapping $\mathbb{F}_{\!q} \to E(\mathbb{F}_{\!q})$ to the case of any elliptic $\mathbb{F}_{\!q}$-curve $E$ of $j$-invariant $1728$. More precisely, we obtain a rational $\mathbb{F}_{\!q}$-curve $C$ (and its explicit quite simple proper $\mathbb{F}_{\!q}$-parametrization $par\!: \mathbb{P}^1 \to C$) on the Kummer surface $K$ associated with the direct product $E \!\times\! E^\prime$, where $E^\prime$ is the quadratic $\mathbb{F}_{\!q}$-twist of $E$. The SWU method consists in computing the direct image of $par$ and a subsequent inverse image $(P,Q)$ of the natural two-sheeted covering $\rho\!: E \!\times\! E^\prime \to K$. Denoting by $\sigma\!:E^\prime \to E$ the corresponding $\mathbb{F}_{\!q^2}$-isomorphism, it is easily seen that $P \in E(\mathbb{F}_{\!q})$ or $\sigma(Q) \in E(\mathbb{F}_{\!q})$. We produce the curve $C$ as one of two absolutely irreducible $\mathbb{F}_{\!q}$-components of $pr^{{-}1}(C_8)$ for some rational $\mathbb{F}_{\!q}$-curve $C_8$ of bidegree $(8,8)$ with $42$ singular points, where $pr\!: K \to \mathbb{P}^1 \!\times\! \mathbb{P}^1$ is the two-sheeted projection to $x$-coordinates of $E$ and $E^\prime$.

###### Chi-Gon Jung, JongHyeok Lee, Youngjin Ju, Yong-Been Kwon, Seong-Woo Kim, Yunheung Paek

ePrint Report
The RLWE family algorithms submitted to the NIST post-quantum cryptography standardization process have each merit in terms of security, correctness, performance, and bandwidth. However, there is no splendid algorithm in all respects. Besides, various recent studies have been published that affect security and correctness, such as side-channel attacks and error dependencies. To date, though, no algorithm has fully considered all the aspects. We propose a novel Key Encapsulation Mechanism scheme called LizarMong, which is based on RLizard. LizarMong combines the merit of each algorithm and state-of-the-art studies. As a result, it achieves up to 85% smaller bandwidth and 3.3 times faster performance compared to RLizard. Compared to the NIST's candidate algorithms with a similar security, the bandwidth is about 5-42% smaller, and the performance is about 1.2-4.1 times faster. Also, our scheme resists the known side-channel attacks.

###### Sarvar Patel, Giuseppe Persiano, Kevin Yeo, Moti Yung

ePrint Report
Volume leakage has recently been identified as a major threat to the security of cryptographic cloud-based data structures by Kellaris et al. [CCS’16] (see also the attacks in Grubbs et al. [CCS’18] and Lacharité et al. [S&P’18]). In this work, we focus on volume-hiding implementations of encrypted multi-maps as first considered by Kamara and Moataz [Eurocrypt’19]. Encrypted multi-maps consist of outsourcing the storage of a multi-map to an untrusted server, such as a cloud storage system, while maintaining the ability to perform private queries. Volume-hiding encrypted multi-maps ensure that the number of responses (volume) for any query remains hidden from the adversarial server. As a result, volume-hiding schemes can prevent leakage attacks that leverage the adversary’s knowledge of the number of query responses to compromise privacy.

We present both conceptual and algorithmic contributions towards volume-hiding encrypted multi-maps. We introduce the first formal definition of volume-hiding leakage functions. In terms of design, we present the first volume-hiding encrypted multi-map dprfMM whose storage and query complexity are both asymptotically optimal. Furthermore, we experimentally show that our construction is practically efficient. Our server storage is smaller than the best previous construction while we improve query complexity by a factor of 10-16x.

In addition, we introduce the notion of differentially private volume-hiding leakage functions which strikes a better, tunable balance between privacy and efficiency. To accompany our new notion, we present a differentially private volume-hiding encrypted multi-map dpMM whose query complexity is the volume of the queried key plus an additional logarithmic factor. This is a significant improvement compared to all previous volume-hiding schemes whose query overhead was the maximum volume of any key. In natural settings, our construction improves the average query overhead by a factor of 150-240x over the previous best volume-hiding construction even when considering small privacy budget of $\epsilon = 0.2$.

We present both conceptual and algorithmic contributions towards volume-hiding encrypted multi-maps. We introduce the first formal definition of volume-hiding leakage functions. In terms of design, we present the first volume-hiding encrypted multi-map dprfMM whose storage and query complexity are both asymptotically optimal. Furthermore, we experimentally show that our construction is practically efficient. Our server storage is smaller than the best previous construction while we improve query complexity by a factor of 10-16x.

In addition, we introduce the notion of differentially private volume-hiding leakage functions which strikes a better, tunable balance between privacy and efficiency. To accompany our new notion, we present a differentially private volume-hiding encrypted multi-map dpMM whose query complexity is the volume of the queried key plus an additional logarithmic factor. This is a significant improvement compared to all previous volume-hiding schemes whose query overhead was the maximum volume of any key. In natural settings, our construction improves the average query overhead by a factor of 150-240x over the previous best volume-hiding construction even when considering small privacy budget of $\epsilon = 0.2$.

###### Cyprien Delpech de Saint Guilhem, Péter Kutas, Christophe Petit, Javier Silva

ePrint Report
We present SÉTA, a new family of public-key encryption schemes with post-quantum security based on isogenies of supersingular elliptic curves. We first define a family of trapdoor one-way functions for which the computation of the inverse is based on an attack by Petit (ASIACRYPT 2017) on the problem of computing an isogeny between two supersingular elliptic curves, given the images of torsion points by this isogeny. We use this method as a decryption mechanism to build first a OW-CPA scheme, then we make use of generic transformations to obtain IND-CCA security in the quantum random oracle model, both for a PKE scheme and a KEM. Compared to alternative schemes based on SIDH, our protocols have the advantage of relying on arguably harder problems.

###### Péter Kutas, Christophe Petit, Javier Silva

ePrint Report
Trapdoor DDH groups are an appealing cryptographic primitive where DDH instances are hard to solve unless provided with additional information (i.e., a trapdoor). In this paper, we introduce a new trapdoor DDH group construction
using pairings and isogenies of supersingular elliptic curves. The construction solves all shortcomings of previous constructions as identified by Seurin (RSA 2013). We also present partial attacks on a previous construction due to Dent--Galbraith, and we provide a formal security definition of the related notion of ``trapdoor pairings''.