## IACR News

Updates on the COVID-19 situation are on the
Announcement channel.

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

#### 05 January 2021

###### Isla Vista, USA, 15 August - 19 August 2021

CRYPTO
Event date: 15 August to 19 August 2021

Submission deadline: 24 February 2021

Submission deadline: 24 February 2021

###### Munich, Germany, 21 June - 22 June 2021

Event Calendar
Event date: 21 June to 22 June 2021

Submission deadline: 12 March 2021

Notification: 16 April 2021

Submission deadline: 12 March 2021

Notification: 16 April 2021

###### IRISA, Rennes, France

Job Posting
Context: This position is funded by the French ANR project IDROMEL, which aims at investigating and preventing power side-channel leakages induced by micro-architectural design choices. (Partners: Arm France, CEA, IRISA, LAAS, Sorbonne University),

Group: EMSEC (https://www.irisa.fr/emsec/)

Duration: 20 month

Starting: Beginning of 2021. Understanding and modeling power leakages due to micro-architectural features.

Test vector definition to trigger side-channel leakage caused by some micro-architectural features.

Side-channel measurements on different Arm platforms using our lab equipment.

Side-channel exploitation analysis.

Exchange and collaborate with other partners in the project.

Publications in top-rated conferences/journal.
embedded devices / micro-architecture, and/or
side-channel analysis, and/or
statistics, machine learning, deep learning.

Group: EMSEC (https://www.irisa.fr/emsec/)

Duration: 20 month

Starting: Beginning of 2021.

Main Objectives:

Prerequisites:

We are looking for team players who are motivated and able to drive top-quality
research. The area of research lies between several fields and we expect at least competences in one
of them:

**Closing date for applications:**

**Contact:** Annelie Heuser, annelie.heuser@irisa.fr

#### 02 January 2021

###### Dorokhovo, Russia, 1 June - 3 June 2021

Event Calendar
Event date: 1 June to 3 June 2021

Submission deadline: 14 February 2021

Notification: 9 April 2021

Submission deadline: 14 February 2021

Notification: 9 April 2021

###### M. R. Mirzaee Shamsabad, S. M. Dehnavi

ePrint Report
Nonlinear diffusion layers are less studied in cryptographic literature, up to now. In 2018, Liu, Rijmen and Leander studied nonlinear non-MDS diffusion layers and mentioned some advantages of them. As they stated, nonlinear diffusion layers could make symmetric ciphers more resistant against statistical and algebraic cryptanalysis. In this paper, with the aid of some special maps over the finite field $\mathbb{F}_{2^n}$, we examine nonlinear MDS mappings and present a family of $4 \times 4$ nonlinear MDS diffusion layers. Next, we determine the Walsh and differential spectrum as well as the algebraic degree of the proposed diffusion layers.

###### Zi-Yuan Liu, Yi-Fan Tseng, Raylin Tso, Cheng-Yi Lee

ePrint Report
Zhang et al. recently proposed a lattice-based proxy-oriented identity-based encryption with keyword search (PO-IBEKS) at Information Sciences in 2019. They claimed that their scheme can resist insider keyword guessing attacks by preventing cloud server from generating ciphertext. In this note, we provide a cryptanalysis of their PO-IBEKS and demonstrate that their scheme cannot resist outsider/insider keyword guessing attacks, even though they satisfy unforgeability requirement. Furthermore, we uncover the root cause of the attack and provide a possible solution for Zhang et al.'s scheme to aid future designs of secure PO-IBEKS schemes.

###### Wyatt Howe, Andrei Lapets

ePrint Report
Many web-based and mobile applications and services allow users to indicate their preferences regarding whether and how their personal information can be used or reused by the application itself, by the service provider, and/or by third parties. The number of possible configurations that constitute a user's preference profile can be overwhelming to a typical user. This report describes a practical, privacy-preserving technique for reducing the burden users face when specifying their preferences by offering users data-driven recommendations for fully-specified preference profiles based on their inputs for just a few settings. The feasibility of the approach is demonstrated by a browser-based prototype application that relies on secure multi-party computation and uses the web-compatible JIFF library as the backbone for managing communications between the client application and the recommendation service. The principal algorithms used for generating proposed preference profiles are $k$-means clustering (for privacy-preserving analysis of preference profile data across multiple users) and $k$-nearest neighbors (for selecting a proposed preference profile to recommend to the user).

###### Kobi Gurkan, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, Alin Tomescu

ePrint Report
In this paper, we introduce a distributed key generation (DKG) protocol with aggregatable and publicly-verifiable transcripts.
Compared with prior publicly-verifiable approaches, our DKG reduces the size of the final transcript and the time to verify it from $O(n^2)$ to $O(n log(n))$, where $n$ denotes the number of parties.
As compared with prior non-publicly-verifiable approaches, our DKG leverages gossip rather than all-to-all communication to reduce verification and communication complexity.
We also revisit existing DKG security definitions, which are quite strong, and propose new and natural relaxations.
As a result, we can prove the security of our aggregatable DKG as well as that of several existing DKGs, including the popular Pedersen variant.
We show that, under these new definitions, these existing DKGs can be used to yield secure threshold variants of popular cryptosystems such as El-Gamal encryption and BLS signatures.
We also prove that our DKG can be securely combined with a new efficient verifiable unpredictable function (VUF), whose security we prove in the random oracle model.
%
Finally, we experimentally evaluate our DKG and show that the per-party overheads scale linearly and are practical.
For $64$ parties, it takes $71$ms to share and $359$ms to verify the overall transcript, while for $8192$ parties, it takes $8$s and $42.2$s respectively.

###### Ismail San

ePrint Report
This study presents a method to perform low-latency modular multiplication operation based on both Montgomery and Ozturk methods. The design space exploration of the proposed method on a latest FPGA device is also given. Through series of experiments on the FPGA using an high-level synthesis tool, optimal parameter selection of the proposed method for the low-latency constraint is also presented for the proposed technique.

###### Mahdi Mahdavi Oliaee, Zahra Ahmadian

ePrint Report
We present the first Ciphertext Policy Attribute Based Encryption (CP-ABE) scheme where access policies are expressed as arithmetic circuits. The idea is first introduced as a basic design based on the multilinear map. Then, two improved versions of that, with or without the property of hidden attributes, are introduced. We also define the concept of Hidden Result Attribute Based Encryption (HR-ABE) which means that the result of the arithmetic function is hidden from the users. We prove that the proposed schemes have adaptive security, under the assumption of the hardness of the (k-1)-Distance Decisional Diffie-
Hellman problem.

###### Dingfeng Ye

ePrint Report
Existing lattice signature schemes are much less efficient than encryption schemes due to the rejection sampling paradigm. We give a construction of comparable efficiency with lattice encryption that avoids sampling using structured secrets together with temporary keys. Structured secrets (and randoms) also improve existing lattice encryption schemes to nearly the same extreme efficiency. Our signature scheme allows the same parameters of any encryption schemes (a variation of the basic form is
needed when the modulus is as small as 1-byte) and has comparable efficiency with our extreme encryption efficiency. For lightweight implementation, our techniques allow integrating of public-key encryption and signature in a simple circuit which only needs to do small integer additions as the main part of the computation.

##### 2-Step Multi-Client Quadratic Functional Encryption from Decentralized Function-Hiding Inner-Product

###### Michel Abdalla, David Pointcheval, Azam Soleimanian

ePrint Report
In this paper, we present a multi-client quadratic functional encryption (MCQFE) scheme from function-hiding inner-product (FHIP). The main challenge in such construction is that all the clients require the access to the master secret key of the underlying FHIP scheme, which clearly breaches the security.

To overcome this challenge, we present an efficient decentralized version of FHIP scheme of Lin (Crypto 16). This leads to a 2-step MCQFE (2-MCQFE) scheme. In a 2-step MCQFE scheme, the encryption phase is a (non-interactive) protocol among clients and a set of honest-but-curious authorities. More precisely, clients are the owner of messages and the master secret-key of the underlying FHIP is shared among authorities. In the first step, the client publishes a pre-ciphertext ``pct'' associated with its message. Then in the second step, each authority generates its share ``ct_i'' extracted from the pre-ciphertext. The public aggregation of these shares ``ct_i'' will generate the target ciphertext ``ct'' which then would be applied on the functional key ``sk_F'' to compute the quadratic functionality. The security model is strong enough to consider no trust among clients and authorities, and also the revelation of some secret keys (of clients or authorities) through corruptions. We instantiate our 2-MCQFE scheme and prove its security in the random-oracle model based on the SXDH assumption. Moreover, we show that its security holds as long as at least one of the authorities is not corrupted.

To overcome this challenge, we present an efficient decentralized version of FHIP scheme of Lin (Crypto 16). This leads to a 2-step MCQFE (2-MCQFE) scheme. In a 2-step MCQFE scheme, the encryption phase is a (non-interactive) protocol among clients and a set of honest-but-curious authorities. More precisely, clients are the owner of messages and the master secret-key of the underlying FHIP is shared among authorities. In the first step, the client publishes a pre-ciphertext ``pct'' associated with its message. Then in the second step, each authority generates its share ``ct_i'' extracted from the pre-ciphertext. The public aggregation of these shares ``ct_i'' will generate the target ciphertext ``ct'' which then would be applied on the functional key ``sk_F'' to compute the quadratic functionality. The security model is strong enough to consider no trust among clients and authorities, and also the revelation of some secret keys (of clients or authorities) through corruptions. We instantiate our 2-MCQFE scheme and prove its security in the random-oracle model based on the SXDH assumption. Moreover, we show that its security holds as long as at least one of the authorities is not corrupted.

#### 31 December 2020

###### Yi Chen, Hongbo Yu

ePrint Report
Gohr improved attacks on 11-round Speck32/64 using deep
learning [17] at Crypto 2019, which is the first work of neural aided
cryptanalysis. But we find that the key recovery attack model proposed
by Gohr is limited by several properties.
It relies heavily on the neutral bit which doesn’t always exist in the attacked cipher.
Besides, the data complexity, computation complexity, and success rate can only be
estimated through the practical attack.

In this paper, we propose a neural aided statistical attack that can be as generic as the differential cryptanalysis. It has no special requirements about the attacked cipher and allows us to estimate the theoretical complexities and success rate. For reducing the key space to be searched, we propose a Bit Sensitivity Test to identify which ciphertext bit is informative. Then specific key bits can be recovered by building neural distinguishers on related ciphertext bits. Applications to round reduced Speck32/64, Speck48/72, Speck48/96, DES prove the correctness and superiorities of our neural aided statistical attack.

In this paper, we propose a neural aided statistical attack that can be as generic as the differential cryptanalysis. It has no special requirements about the attacked cipher and allows us to estimate the theoretical complexities and success rate. For reducing the key space to be searched, we propose a Bit Sensitivity Test to identify which ciphertext bit is informative. Then specific key bits can be recovered by building neural distinguishers on related ciphertext bits. Applications to round reduced Speck32/64, Speck48/72, Speck48/96, DES prove the correctness and superiorities of our neural aided statistical attack.

###### Paul Kirchner, Pierre-Alain Fouque

ePrint Report
We revisit some well-known cryptographic problems in a black box modular ring model of computation. This model allows us to compute with black box access to the ring $\mathbb{Z}/m\mathbb{Z}$. We develop new generic ring algorithms to recover $m$ even if it is unknown. At the end, Maurer's generic algorithm allows to recover an element from its black box representation. However, we avoid Maurer's idealized model with CDH oracle for the multiplication in the hidden ring by introducing a new representation compatible with ring operations. An element is encoded by its action over the factor basis. Consequently, we can multiply two elements with classical descent computations in sieving algorithms. As the algorithms we propose work without using an expensive linear algebra computation at the end, even though they manipulate large sparse matrices, we can exploit a high-level of parallelism.

Then, we consider general groups such as imaginary quadratic class group and the Jacobian of a hyperelliptic curve, and obtain new methods for group order computation. The repeated squaring problem and the adaptive root problem used in the construction of Verifiable Delay Functions are particularly easy to solve in the black box modular ring, the high degree of parallelism provided by our method allows a reduction in the time to solve them. We improve the smoothing time, and as a result, we break Verifiable Delay Functions and factorize weak keys with lower Area-Time cost.

Finally, we show new AT costs for computing a discrete logarithm over an adversarial basis in finite fields.

Then, we consider general groups such as imaginary quadratic class group and the Jacobian of a hyperelliptic curve, and obtain new methods for group order computation. The repeated squaring problem and the adaptive root problem used in the construction of Verifiable Delay Functions are particularly easy to solve in the black box modular ring, the high degree of parallelism provided by our method allows a reduction in the time to solve them. We improve the smoothing time, and as a result, we break Verifiable Delay Functions and factorize weak keys with lower Area-Time cost.

Finally, we show new AT costs for computing a discrete logarithm over an adversarial basis in finite fields.

###### Benedikt Bünz, Alessandro Chiesa, William Lin, Pratyush Mishra, Nicholas Spooner

ePrint Report
Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme for their proofs.

In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a *split accumulation scheme*, which is a weak form of accumulation that we introduce.

We additionally construct a transparent non-interactive argument of knowledge for R1CS whose accumulation is verifiable via a *constant number of group and field operations*. This leads, via the random oracle heuristic and our result above, to efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for a simple polynomial commitment scheme based on Pedersen commitments.

Our results are supported by a modular and efficient implementation.

In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a *split accumulation scheme*, which is a weak form of accumulation that we introduce.

We additionally construct a transparent non-interactive argument of knowledge for R1CS whose accumulation is verifiable via a *constant number of group and field operations*. This leads, via the random oracle heuristic and our result above, to efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for a simple polynomial commitment scheme based on Pedersen commitments.

Our results are supported by a modular and efficient implementation.

###### Steve Thakur

ePrint Report
We study non-interactive arguments of knowledge (AoKs) for commitments in groups of hidden order. We provide protocols whereby a Prover can demonstrate certain properties of and relations between committed sets/multisets, with succinct proofs that are publicly verifiable against the constant-sized commitments. In particular, we provide AoKs for the disjointness of committed sets/multisets in cryptographic accumulators, with a view toward applications to verifiably outsourcing data storage and sharded stateless blockchains.

Recent work ([DGS20]) suggests that the hidden order groups need to be substantially larger in size that previously thought, in order to ensure the desired security level. Thus, in order to keep the communication complexity between the Prover and the the Verifier to a minimum, we have designed the protocols so that the proofs entail a constant number of group elements, independent of the number of the committed sets/multisets rather than just independent of the sizes of these sets/multisets.

If the underlying group of hidden order is an appropriate imaginary quadratic class group or a genus three Jacobian, the argument systems are transparent. Furthermore, since all challenges are public coin, the protocols can be made non-interactive using the Fiat-Shamir heuristic. We build on the techniques from [BBF19] and [Wes18].

Recent work ([DGS20]) suggests that the hidden order groups need to be substantially larger in size that previously thought, in order to ensure the desired security level. Thus, in order to keep the communication complexity between the Prover and the the Verifier to a minimum, we have designed the protocols so that the proofs entail a constant number of group elements, independent of the number of the committed sets/multisets rather than just independent of the sizes of these sets/multisets.

If the underlying group of hidden order is an appropriate imaginary quadratic class group or a genus three Jacobian, the argument systems are transparent. Furthermore, since all challenges are public coin, the protocols can be made non-interactive using the Fiat-Shamir heuristic. We build on the techniques from [BBF19] and [Wes18].

#### 30 December 2020

###### Fan Peng, Hao Chen, Chang-An Zhao

ePrint Report
In Chen-Cramer Crypto 2006 paper \cite{cc} algebraic geometric secret sharing schemes were proposed such that the ``Fundamental Theorem in Information-Theoretically Secure Multiparty Computation" by Ben-Or, Goldwasser and Wigderson \cite{BGW88} and Chaum, Cr\'{e}peau and Damg{\aa}rd \cite{CCD88} can be established over constant-size base
finite fields. These algebraic geometric secret sharing schemes defined by a curve of genus $g$ over a constant size finite field ${\bf F}_q$ is quasi-threshold in the following sense, any subset of $u \leq T-1$ players (non qualified) has no information of the secret and any subset of $u \geq T+2g$ players (qualified) can reconstruct the secret. It is natural to ask that how far
from the threshold these quasi-threshold secret sharing schemes are? How many subsets of $u \in [T, T+2g-1]$ players can recover the secret or have no information of the secret?

In this paper it is proved that almost all subsets of $u \in [T,T+g-1]$ players have no information of the secret and almost all subsets of $u \in [T+g,T+2g-1]$ players can reconstruct the secret when the size $q$ goes to the infinity and the genus satisfies $\lim \frac{g}{\sqrt{q}}=0$. Then algebraic geometric secretsharing schemes over large finite fields are asymptotically threshold in this case. We also analyze the case when the size $q$ of the base field is fixed and the genus goes to the infinity.

In this paper it is proved that almost all subsets of $u \in [T,T+g-1]$ players have no information of the secret and almost all subsets of $u \in [T+g,T+2g-1]$ players can reconstruct the secret when the size $q$ goes to the infinity and the genus satisfies $\lim \frac{g}{\sqrt{q}}=0$. Then algebraic geometric secretsharing schemes over large finite fields are asymptotically threshold in this case. We also analyze the case when the size $q$ of the base field is fixed and the genus goes to the infinity.

###### Guoai Xu, Jiangtao Yuan, Guosheng Xu

ePrint Report
Multipartite secret sharing schemes are those that have multipartite access structures. The set of the participants in those schemes is divided into several parts, and all the participants in the same part play the equivalent role. One type of such access structure is the compartmented access structure. We propose an ideal and efficient compartmented multi-secret sharing scheme based on the linear homogeneous recurrence (LHR) relations. In the construction phase, the shared secrets are hidden in some terms of the linear homogeneous recurrence sequence. In the recovery phase, the shared secrets are obtained by solving those terms in which the shared secrets are hidden. When the global threshold is $t$, our scheme can reduce the computational complexity from $O(n^{t-1})$ to $O(n^{\max(t_i-1)}\log n)$, where $t_i<t$. The security of the proposed scheme is based on Shamir's threshold scheme. Moreover, it is efficient to share the multi-secret and to change the shared secrets in the proposed scheme. That is, the proposed scheme can improve the performances of the key management and the distributed system.

###### Aljosha Judmayer, Nicholas Stifter, Alexei Zamyatin, Itay Tsabary, Ittay Eyal, Peter Gazi, Sarah Meiklejohn, Edgar Weippl

ePrint Report
A long standing question in the context of cryptocurrencies based on Nakamoto consensus is whether such constructions are
incentive compatible, i.e., the intended properties of the system emerge from the appropriate utility model for participants. Bribing and other related attacks, such as front-running or Goldfinger attacks, aim to directly influence the incentives of actors within (or outside) of the targeted cryptocurrency system. The theoretical feasibility of bribing attacks on cryptocurrencies was first highlighted in 2016 by Bonneau, with various different techniques and approaches having since been proposed. Some
of these attacks are designed to gain in-band profits, while others intend to break the mechanism design and render the cryptocurrency worthless. In this paper, we systematically expose the large but scattered body of research in this area which has accumulated over the years. We summarize these bribing attacks and similar techniques that leverage on programmatic execution and verification under the term algorithmic incentive manipulation (AIM) attacks, and show that the problem space is not yet fully explored. Based on our analysis we present several research gaps and opportunities that warrant further investigation. In particular, we highlight no- and near-fork attacks as a powerful, yet largely underestimated, AIM category that raises serious security concerns not only for smart contract platforms.

###### -

Event Calendar
Event date: to

Submission deadline: 31 July 2021

Submission deadline: 31 July 2021