International Association
for Cryptologic Research

Post-quantum cryptography (PQC) is a trend that has a deserved NIST status, and which aims to be resistant to quantum computer attacks like Shor and Grover algorithms. NIST is currently leading the third-round search of a viable set of standards, all based on traditional approaches as code-based, lattice-based, multi quadratic-based, or hash-based cryptographic protocols [1]. We choose to follow an alternative way of replacing all numeric field arithmetic with GF(2^8) field operations [2]. By doing so, it is easy to implement R-propped asymmetric systems as the present paper shows [3,4]. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid is immune against quantum algorithms and resist classical linearization attacks like Tsaban’s Algebraic Span [5] or Roman’kov linearization attacks [6]. The Burmester-Desmedt (B-D) conference key distribution protocol [7] has been proved to be secure against passive adversaries if the computational Diffie-Hellman problem remains hard. The authors refer that the proposed scheme could also be secure against active adversaries under the same assumptions as before if an authentication step is included to foil attacks like MITM (man in the middle). Also, this protocol proved to be semantical secure against adaptative IND-CPA2 [8, 9] if the discrete log problem is intractable. We discuss the features of our present work and a practical way to include an authentication step. Classical and quantum security levels are also discussed. Finally, we present a numerical example of the proposed R-Propped protocol.

The Cryptography and Privacy Research Group at Microsoft Research, Redmond, is looking for candidates for Researcher positions.

Topics of particular interest to us include (but are not limited to) secure computing (FHE, MPC, TEE), ML privacy, end-to-end encryption, web privacy and security, post-quantum cryptography, and zero-knowledge proofs. Our work ranges from protocol design and security analysis to cryptography and privacy engineering, so we encourage people with any relevant experiences to apply.

Responsibilities: Working with other researchers and multi-disciplinary teams to create and build practical solutions to real-world privacy problems. Publishing papers in academic conferences.

Required Qualifications:

• A PhD (or close to completion) in computer science, electrical engineering, mathematics, or a related field
• Publications in top conferences, or submitted/accepted papers in top journals.

Apply: https://careers.microsoft.com/us/en/job/953748/Researcher-Cryptography-and-Privacy-Microsoft-Research

Closing date for applications:

Contact: Kim Laine, Melissa Chase, or Esha Ghosh

More information: https://careers.microsoft.com/us/en/job/953748/Researcher-Cryptography-and-Privacy-Microsoft-Research

The Cryptography and Privacy Research Group at Microsoft Research, Redmond, is looking for candidates for Post-Doc Researcher positions.

Topics of particular interest to us include (but are not limited to) secure computing (FHE, MPC, TEE), ML privacy, end-to-end encryption, web privacy and security, post-quantum cryptography, and zero-knowledge proofs. Our work ranges from protocol design and security analysis to cryptography and privacy engineering, so we encourage people with any relevant experiences to apply.

Responsibilities: Working with other researchers and multi-disciplinary teams to create and build practical solutions to real-world privacy problems. Publishing papers in academic conferences.

Required Qualifications: A PhD (or close to completion) in computer science, electrical engineering, mathematics, or a related field Publications in top conferences, or submitted/accepted papers in top journals.

Apply: https://careers.microsoft.com/us/en/job/953746/Post-Doc-Researcher-Cryptography-and-Privacy-Microsoft-Research

Closing date for applications:

Contact: Kim Laine, Melissa Chase, or Esha Ghosh

More information: https://careers.microsoft.com/us/en/job/953746/Post-Doc-Researcher-Cryptography-and-Privacy-Microsoft-Research

We have an open PhD position in the domain of Scalable and Secure Data Sharing funded FWO SBO (strategic basic research) project MOZAIK. The prospective candidate is expected to investigate how conventional lightweight symmetric ciphers perform over MPC, as well as benchmark their performance over MPC. The work also entails provable security in this context. The candidate must hold a Master's degree in mathematics / computer science / electrical engineering / cryptography. Strong background in mathematics / computer science / cryptography is expected. Any prior publications and experience in C/C++ and Python are merited. Please visit our website to find out more details as well as the exact application procedure.

Closing date for applications:

Contact: jobs-cosic@esat.kuleuven.be

More information: https://www.esat.kuleuven.be/cosic/vacancies/

COSIC is hiring a motivated researcher who fit into the following profile: Postdoc researcher to work on efficient MPC protocols for privacy-preserving machine learning Job description: We have an open postdoc position in the domain of Scalable and Secure Data Sharing funded FWO SBO (strategic basic research) project MOZAIK. The prospective candidate is expected to design and develop efficient MPC protocols for privacy-preserving data analytics. The work includes, but not limited to, investigating machine learning algorithms that best suit MPC and that can be efficiently implemented over MPC. You will be working closely with tools such as https://github.com/KULeuven-COSIC/SCALE-MAMBA. Specific skills required:The candidate must hold a PhD degree in Cryptography or a related subject with strong publication records in crypto/security venues. In addition to a strong background in both public and symmetric cryptography, good knowledge in MPC, machine learning algorithms, and cryptographic protocols are expected.

Closing date for applications:

Contact: jobs-cosic@esat.kuleuven.be

More information: https://www.esat.kuleuven.be/cosic/vacancies/

The term permissionless has established itself within the context of blockchain and distributed ledger research to characterize protocols and systems that exhibit similar properties to Bitcoin. However, the notion of what is meant by permissionlessness is often vague or left implicit within the various literature, rendering it imprecise and hard to compare. We hereby shed light onto this topic by revising research that either incorporates or defines the term permissionless and systematically expose the properties and characteristics that its utilization intends to capture. Based on this review, we highlight current shortcomings and blind spots within the available definitions. In particular, the ability to freely perform transactions between users is often not adequately incorporated and different actor roles are left unspecified. Furthermore, the topics of privacy and governance appear to be largely overlooked.

In this paper we propose new techniques related to division property. We describe for the first time a practical algorithm for computing the propagation tables of 16-bit Super-Sboxes, increasing the precision of the division property by removing a lot of false division trails. We also improve the complexity of the procedure introduced by Lambin et al. (Design, Codes and Cryptography, 2020) to extend a cipher with linear mappings and show how to decrease the number of transitions to look for. While search procedures for integral distinguishers most often rely on MILP or SAT solvers for their ease of programming the propagation constraints, such generic solvers can only handle small 4/8-bit Sboxes. Thus we developed an ad-hoc tool handling larger Sboxes and all the improvements described in the paper. As a result, we found new integral distinguishers on SKINNY-64, HIGHT and Midori-64.

Fast Near collision attacks on the stream ciphers Grain v1 and A5/1 were presented at Eurocrypt 2018 and Asiacrypt 2019 respectively. They use the fact that the entire internal state can be split into two parts so that the second part can be recovered from the first one which can be found using the keystream prefix and some guesses of the key materials. In this paper we reevaluate the complexity of these attacks and show that actually they are inferior to previously known results. Basically, we show that their complexity is actually much higher and we point out the main problems of these papers based on information theoretic ideas. We also check that some distributions do not have the predicted entropy loss claimed by the authors. Checking cryptographic attacks with galactic complexity is difficult in general. In particular, as these attacks involve many steps it is hard to identify precisely where the attacks are flawed. But for the attack against A5/1, it could have been avoided if the author had provided a full experiment of its attack since the overall claimed complexity was lower than 232 in both time and memory

In this paper we describe a new tool to search for boomerang distinguishers. One limitation of the MILP model of Liu et al. is that it handles only one round for the middle part while Song et al. have shown that dependencies could affect much more rounds, for instance up to 6 rounds for SKINNY. Thus we describe a new approach to turn an MILP model to search for truncated characteristics into an MILP model to search for truncated boomerang characteristics automatically handling the middle rounds. We then show a new CP model to search for the best possible instantiations to identify good boomerang distinguishers. Finally we systematized the method initiated by Song et al. to precisely compute the probability of a boomerang. As a result, we found many new boomerang distinguishers up to 24 rounds in the TK3 model. In particular, we improved by a factor $2^{30}$ the probability of the best known distinguisher against 18-round SKINNY-128/256.

This paper makes a comprehensive comparison of the efficiencies of vectorized implementations of Kummer lines and Montgomery curves at various security levels. For the comparison, nine Kummer lines are considered, out of which eight are new, and new assembly implementations of all nine Kummer lines have been made. Seven previously proposed Montgomery curves are considered and new vectorized assembly implementations have been made for five of them. Our comparisons show that for all security levels, Kummer lines are consistently faster than Montgomery curves, though the speed-up gap is not much.

To maintain the secure information sharing among vehicles in the Internet of Vehicles, various message authentication schemes were proposed. Recently, Sutrala et al. proposed a conditional privacy preserving authentication scheme (``On the Design of Conditional Privacy Preserving Batch Verification-Based Authentication Scheme for Internet of Vehicles Deployment,'' IEEE Trans. Veh. Technol., vol. 69, no. 5, pp. 5535-5548, May 2020.) to against various potential attacks. However, our observations show that, contrary to what is claimed, the scheme is insecure. Any (malicious) vehicle can forge signature for any message, which can be validated successfully and cannot be traceable. Our observations also show that, the security proof based on the standard random oracle model is wrong.

This paper presents a new protocol for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client’s string. A web-browser vendor, for instance, can use our protocol to figure out which homepages are popular, without learning any user’s homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients.

Our protocols use two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Our protocols protect client privacy against arbitrary misbehavior by one of the servers and our approach requires no public- key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions.

A limitation of our heavy-hitters protocol is that it reveals to the servers slightly more information than the set of popular strings itself. We precisely define and quantify this leakage and explain how to ameliorate its effects. In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, our protocols could compute heavy hitters over ten million clients in just over one hour of computation.

Black-box separations have been successfully used to identify the limits of a powerful set of tools in cryptography, namely those of black-box reductions. They allow proving that a large set of techniques are not capable of basing one primitive $\mathcal{P}$ on another $\mathcal{Q}$. Such separations, however, do not say anything about the power of the combination of primitives $\mathcal{Q}_1,\mathcal{Q}_2$ for constructing $\mathcal{P}$, even if $\mathcal{P}$ cannot be based on $\mathcal{Q}_1$ or $\mathcal{Q}_2$ alone.

By introducing and formalizing the notion of black-box uselessness, we develop a framework that allows us to make such conclusions. At an informal level, we call primitive $\mathcal{Q}$ black-box useless (BBU) for primitive $\mathcal{P}$ if $\mathcal{Q}$ cannot help constructing $\mathcal{P}$ in a black-box way, even in the presence of another primitive $\mathcal{Z}$. This is formalized by saying that $\mathcal{Q}$ is BBU for $\mathcal{P}$ if for any auxiliary primitive $\mathcal{Z}$, whenever there exists a black-box construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, then there must already also exist a black-box construction of $\mathcal{P}$ from $\mathcal{Z}$ alone. We also formalize various other notions of black-box uselessness, and consider in particular the setting of efficient black-box constructions when the number of queries to $\mathcal{Q}$ is below a threshold.

Impagliazzo and Rudich (STOC'89) initiated the study of black-box separations by separating key agreement from one-way functions. We prove a number of initial results in this direction, which indicate that one-way functions are perhaps also black-box useless for key agreement. In particular, we show that OWFs are black-box useless in any construction of key agreement in either of the following settings: (1) the key agreement has perfect correctness and one of the parties calls the OWF a constant number of times; (2) the key agreement consists of a single round of interaction (as in Merkle-type protocols). We conjecture that OWFs are indeed black-box useless for general key agreement protocols.

We also show that certain techniques for proving black-box separations can be lifted to the uselessness regime. In particular, we show that known lower bounds for assumptions behind black-box constructions of indistinguishability obfuscation (IO) can be extended to derive black-box uselessness of a variety of primitives for obtaining (approximately correct) IO. These results follow the so-called "compiling out" technique, which we prove to imply black-box uselessness.

Eventually, we study the complementary landscape of black-box uselessness, namely black-box helpfulness. Formally, we call primitive $\mathcal{Q}$ black-box helpful (BBH) for $\mathcal{P}$, if there exists an auxiliary primitive $\mathcal{Z}$ such that there exists a black-box construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, but there exists no black-box construction of $\mathcal{P}$ from $\mathcal{Z}$ alone.

We put forth the conjecture that one-way functions are black-box helpful for building collision-resistant hash functions. We define two natural relaxations of this conjecture, and prove that both of these conjectures are implied by a natural conjecture regarding random permutations equipped with a collision finder oracle, as defined by Simon (Eurocrypt'98). This conjecture may also be of interest in other contexts, such as hardness amplification.

In recent years, numerous attacks have appeared that aim to steal secret information from their victim, using the power side channel vector, without direct physical access and using instead, resources that are present inside the victim environment. These attacks are called Remote Power Attacks or Remote Power Analysis. However, there is no unified definition about the limitations that a power attack requires to be defined as remote. This paper aims to propose a unified definition and threat model to clearly differentiate remote power attacks from non-remote ones. Additionally, we collect the main remote power attacks performed so far from the literature, and the principal proposed countermeasures to avoid them. The search of such countermeasures denoted a clear gap in order to find technical details on how to prevent remote power attacks. Thus, the academic community must face an important challenge to avoid this emerging threat, given the clear room for improvement that should be addressed in terms of defense and security of devices that work with private information.

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: