International Association
for Cryptologic Research

Though the multilinear maps have many cryptographic applications, secure and efficient construction of such maps is an open problem. Many multilinear maps like GGH, GGH15, CLT, and CLT15 have been and are being proposed, while none of them is both secure and efficient. The construction of some multilinear maps is based on the Graded Encoding Scheme (GES), where, the necessity of announcing zero-testing parameter and encoding of zero has destroyed the security of the multilinear map. Attempt is made to propose a new GES, where, instead of encoding an element, the users can obtain the encoding of an associated but unknown random element. In this new setting, there is no need to publish the encodings of zero and one. This new GES provides the actual functionality of the usual GES and can be applied in constructing a secure and efficient multilinear map and a multi-party non-interactive key exchange (MP-NIKE) scheme. We also improve the MP-NIKE scheme and turn it into an ID-based MP-NIKE scheme.

We describe and illustrate the local neighbourhoods of vertices and edges in the (2, 2)-isogeny graph of principally polarized abelian surfaces, considering the action of automorphisms. Our diagrams are intended to build intuition for number theorists and cryptographers investigating isogeny graphs in dimension/genus 2, and the superspecial isogeny graph in particular.

We investigate special structures due to automorphisms in isogeny graphs of principally polarized abelian varieties, and abelian surfaces in particular. We give theoretical and experimental results on the spectral and statistical properties of (2, 2)-isogeny graphs of superspecial abelian surfaces, including stationary distributions for random walks, bounds on eigenvalues and diameters, and a proof of the connectivity of the Jacobian subgraph of the (2, 2)-isogeny graph. Our results improve our understanding of the performance and security of some recently-proposed cryptosystems, and are also a concrete step towards a better understanding of general superspecial isogeny graphs in arbitrary dimension.

The problem of solving explicitly the equation $P_a(X):=X^{q+1}+X+a=0$ over the finite field $\GF{Q}$, where $Q=p^n$, $q=p^k$ and $p$ is a prime, arises in many different contexts including finite geometry, the inverse Galois problem \cite{ACZ2000}, the construction of difference sets with Singer parameters \cite{DD2004}, determining cross-correlation between $m$-sequences \cite{DOBBERTIN2006} and to construct error correcting codes \cite{Bracken2009}, cryptographic APN functions \cite{BTT2014,Budaghyan-Carlet_2006}, designs \cite{Tang_2019}, as well as to speed up the index calculus method for computing discrete logarithms on finite fields \cite{GGGZ2013,GGGZ2013+} and on algebraic curves \cite{M2014}.

Subsequently, in \cite{Bluher2004,HK2008,HK2010,BTT2014,Bluher2016,KM2019,CMPZ2019,MS2019,KCM19}, the $\GF{Q}$-zeros of $P_a(X)$ have been studied. In \cite{Bluher2004}, it was shown that the possible values of the number of the zeros that $P_a(X)$ has in $\GF{Q}$ is $0$, $1$, $2$ or $p^{\gcd(n, k)}+1$. Some criteria for the number of the $\GF{Q}$-zeros of $P_a(x)$ were found in \cite{HK2008,HK2010,BTT2014,KM2019,MS2019}. However, while the ultimate goal is to explicit all the $\GF{Q}$-zeros, even in the case $p=2$, it was solved only under the condition $\gcd(n, k)=1$ \cite{KM2019}. In this article, we discuss this equation without any restriction on $p$ and $\gcd(n,k)$. In \cite{KCM19}, for the cases of one or two $\GF{Q}$-zeros, explicit expressions for these rational zeros in terms of $a$ were provided, but for the case of $p^{\gcd(n, k)}+1$ $\GF{Q}-$ zeros it was remained open to explicitly compute the zeros. This paper solves the remained problem, thus now the equation $X^{p^k+1}+X+a=0$ over $\GF{p^n}$ is completely solved for any prime $p$, any integers $n$ and $k$.

Compression is widely used in Internet communication to save communication time and bandwidth. Recently invented by Jarek Duda asymmetric numeral system (ANS) offers an improved efficiency and a close to optimal compression. The ANS algorithm has been deployed by major IT companies such as Facebook, Google and Apple. Compression by itself does not provide any security (such as confidentiality or authentication of transmitted data). An obvious solution to this problem is an encryption of compressed bitstream. However, it requires two algorithms: one for compression and the other for encryption.

In this work, we investigate natural properties of ANS that allow to incorporate authenticated encryption using as little cryptography as possible. We target low-level security communication such as transmission of data from IoT devices/sensors. In particular, we propose three solutions for joint compression and encryption (compcrypt). All of them use a pseudorandom bit generator (PRGB) based on lightweight stream ciphers. The first solution applies state jumps controlled by PRGB. The second one employs two ANS algorithms, where compression switches between the two. The switch is controlled by a PRGB bit. The third compcrypt modifies the encoding function of ANS depending on PRGB bits. Security and efficiency of the proposed compcrypt algorithms are evaluated.

Abstract: Off-chain is a common approach to deal with the scalability problem of blockchain networks. It enables users toexecute multiple payments without committing each of them to the blockchain by relying on predefined payment channels. Apair of users can employ a payment even without a direct channel between them, via routing the payment through off-chainchannels involving other intermediate users. Users together with the off-chain channels form a graph, known as the off-chainnetwork topology. The off-chain topology and the payment characteristics affect network performance such as the averagenumber of intermediate users a payment is routed through, the amount of fees, or channel capacities needed to successfullyroute payments. In this paper, we study two basic problems in off-chain network design. First, efficiently mapping users toan off-chain topology with a known structure. Second, constructing a topology of a bounded number of channels that canserve well users with associated payments. We design algorithms for both problems and evaluate them based on real datafrom Raiden, the off-chain extension for Ethereum. Keywors:

Event date: 15 August to 19 August 2021
Submission deadline: 24 February 2021

Event date: 21 June to 22 June 2021
Submission deadline: 12 March 2021
Notification: 16 April 2021

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.

Main Objectives:

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.

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:

embedded devices / micro-architecture, and/or

side-channel analysis, and/or

statistics, machine learning, deep learning.

Closing date for applications:

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

Event date: 1 June to 3 June 2021
Submission deadline: 14 February 2021
Notification: 9 April 2021

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.

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.

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).

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.

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.

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.

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.

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.

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.

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.