International Association
for Cryptologic Research

Evaluating resistance of ciphers against differential cryptanalysis is essential to define the number of rounds of new designs and to mount attacks derived from differential cryptanalysis.

In this paper, we compare existing automatic tools to find the best differential characteristic on the SKINNY block cipher. As usually done in the literature, we split this search in two stages denoted by Step 1 and Step 2. In Step 1, each difference variable is abstracted with a Boolean variable and we search for the value that minimizes the trail weight, whereas Step 2 tries to instantiate each difference value while maximizing the overall differential characteristic probability. We model Step 1 using a MILP tool, a SAT tool, an ad-hoc method and a CP tool based on the Choco-solver library and provide performance results. Step 2 is modeled using the Choco-solver as it seems to outperform all previous methods on this stage.

Notably, for SKINNY-128 in the SK model and for 13 rounds, we retrieve the results of Abdelkhalek et al. within a few seconds (to compare with 16 days) and we provide, for the first time, the best differential related-tweakey characteristic up to respectively 14 and 12 rounds for the TK1 and TK2 models.

Event date: 8 July to 9 July 2021

(virtual) TCC 2020 starts on Monday Nov 16th with an exciting keynote talk on "The Impact of Cryptographic Thinking on TCS and Beyond" by Avi Wigderson.

The conference program and details on how to join can be found at https://tcc.iacr.org/2020/program.php

The University of St. Gallen in Switzerland and the chair of Cyber Security invites applications from PhD holders in the area of cryptography and information security. The researcher will join a group of researchers focusing in applied and theoretical cryptography, network and information security and privacy-preservation led by Prof. Katerina Mitrokotsa. We are affiliated to the Department of Computer Science (DCS) and the Institute of Computer Science. The postdoctoral fellowship is available for three years and a project proposal needs to be submitted that will be evaluated by the research committee.
Topics of research interest include:

• Verifiable computation
• Secure Multi Party Computation
• Privacy-preserving authentication
• Cryptographic primitives

Requirements:

• Publications in top venues in Cryptography and Information Security
• Young researchers who hold a doctorate (PhD) or will complete their doctorate within the next six months
• Young researchers with a completed doctorate (PhD) have been awarded the degree at most two years before 15th of Jan 2021.

Deadline for applicants to be considered: 7th of Dec. 2020
Deadline for project proposal: 15th of Jan. 2021
To Apply: Send your cv and research statement to aikaterini.mitrokotsa@unisg.ch with subject ''Post-doc Fellowship'' by the 9th of Dec. 2020

Closing date for applications:

Contact: Katerina Mitrokotsa

The CryptoLux group of the University of Luxembourg has a vacancy for a post-doctoral researcher in the area of symmetric cryptography. The successful candidate will contribute to a research project entitled Analysis and Protection of Lightweight Cryptographic Algorithms (APLICA), which is funded by the Luxembourgish Fonds National de la Recherche and the German Research Foundation. Starting in 2021, APLICA will run over a period of 3 years as a joint research project between the CryptoLux group and the Workgroup for Symmetric Cryptography of Ruhr-University Bochum. The mission of the APLICA project is to develop new cryptanalytic techniques for lightweight authenticated encryption algorithms and hash functions, and to design and implement new countermeasures against side-channel attacks that are suitable for constrained devices.

Candidates must have a Ph.D. degree in symmetric cryptography or a closely related field. Preference will be given to candidates with a strong publication record that includes at least one paper at an IACR conference/workshop or one of the top-4 security conferences. Experience in software development for embedded systems or mounting side-channel attacks is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:

• Cryptanalysis of authenticated encryption algorithms or hash functions
• Leakage resilience or leakage reduction by design (e.g. modes of operation)
• Security evaluation of leakage-resilient primitives or constructions

The position is available from Jan. 2021 on basis of a fixed-term contract for 3 years. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Alex Biryukov before Dec. 15, 2020 (early submission is strongly encouraged, applications will be processed upon receipt). The application material should contain a cover letter explaining the candidate's research interests, a CV (incl. photo), a list of publications, scans of diploma certificates, and contact details of 3 references

Closing date for applications:

Contact: Prof. Alex Biryukov (alex.biryukov@uni.lu)

More information: https://www.fnr.lu/projects/analysis-and-protection-of-lightweight-cryptographic-algorithms/

The University of Luxembourg invites applications from M.Sc. holders in the general area of applied cryptography. Cryptolux.org is a team of cryptographers and security researchers interested in applied cryptography, cryptanalysis, privacy, cryptographic blockchains and is led by Prof. Alex Biryukov.

Area (potential topics of the thesis)

• Cryptanalysis and design of cryptographic primitives
• Lightweight block ciphers, hash functions, authenticated encryption schemes
• Privacy Enhancing Technology (Tor-like networks, privacy for cryptocurrencies, blockchains)
• Blockchain Cryptography
• White-box cryptography

The University offers a Ph.D. study program with an Initial contract of 36 months, with a further possible 1-year extension if required. The University offers competitive salaries and is an equal opportunity employer.

Starting date 1-Feb-2020 or later upon agreement. Early submission is encouraged; applications will be processed upon receipt.

Closing date for applications:

Contact: Prof. Alex Biryukov

More information: https://www.cryptolux.org/index.php/Vacancies

The CryptoLux group of the University of Luxembourg invites applications from Ph.D. holders in the general area of applied cryptography. CryptoLux is a group of cryptographers and security researchers interested in applied cryptography, cryptanalysis, privacy and is led by Prof. Alex Biryukov.

• Design and cryptanalysis of symmetric cryptographic primitives
• Cryptocurrencies, ZK proofs, blockchain
• Privacy enhancing technologies, Tor, etc
• Side-channel attacks and countermeasures
• White-box cryptography

Your Profile

• A Ph.D. degree in Computer Science, Applied Mathematics or a related field
• Competitive research record in applied cryptography or information security (at least one paper in top 10 IT security conferences or several papers at conferences like ToSC, CHES, PETS, PKC)
• Strong mathematical and algorithmic CS background
• Good development skills in C or C++ and/or scripting languages
• Fluent written and verbal English

We offer

The University offers a two-year employment contract (Ref: F1-070025, OTP code R-STR-8019-00-A), which may be extended up to five years. The University offers highly competitive salaries and is an equal opportunity employer.

Closing date for applications:

Contact: Alex Biryukov

More information: https://www.cryptolux.org

Several PhD student openings in the domains of cryptography, computer security, privacy, and blockchain-based systems are available at the University of Connecticut (UConn), Computer Science and Engineering department, led by Prof. Ghada Almashaqbeh. The positions provide a great opportunity for students with interest in interdisciplinary projects that combine knowledge from various fields towards the design of secure systems and protocols. We target real-world timely problems and aim to provide secure and practical solutions backed by rigorous foundations and efficient implementations/thorough performance testing. We are also interested in conceptual projects that contribute in bridging the gap between theory and practice of Cryptography. For more information about our current and previous projects please check https://ghadaalmashaqbeh.github.io/research/. For interested students, please send your CV to ghada.almashaqbeh@uconn.edu and provide any relevant information about the topics you want to work on and the skills/related background you have.

Closing date for applications:

Contact: Ghada Almashaqbeh

More information: https://ghadaalmashaqbeh.github.io/

We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else. 

In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation, delegated computation, depth-reduction of cryptographic primitives, complexity lower-bounds, and more. However, a quantum analogue for garbling general circuits was not known prior to this work. We hope that our quantum randomized encoding scheme can similarly be useful for applications in quantum computing and cryptography.

To illustrate the usefulness of quantum randomized encoding, we use it to design a conceptually-simple zero-knowledge (ZK) $\Sigma$-protocol for the complexity class QMA. Our protocol has a single-bit challenge, and allows the inputs to be delayed to the last round. The only previously-known ZK $\Sigma$-protocol for QMA is due to Broadbent and Grilo (FOCS 2020), which does not have the aforementioned properties.

Transferable e-cash is the most faithful digital analog of physical cash, as it allows users to transfer coins between them without interacting with the bank (or a "ledger"). Strong anonymity requirements and the need for mechanisms to trace illegal behavior (double-spending of coins) have made instantiating the concept notoriously hard. Baldimtsi et al. (PKC'15) have given a first instantiation, which relied on a powerful cryptographic primitive that made the scheme non-practical.

In this paper we first revisit the model for transferable e-cash, proposing simpler yet stronger security definitions and then give the first concrete instantiation of the primitive, basing it on bilinear groups, and analyze its concrete efficiency.

We present a novel public key encryption scheme that enables users to exchange many bits messages by means of \emph{at least} two large prime numbers in a Goldwasser-Micali manner. Our cryptosystem is in fact a generalization of the Joye-Libert scheme (being itself an abstraction of the first probabilistic encryption scheme). We prove the security of the proposed cryptosystem in the standard model (based on the gap $2^k$-residuosity assumption) and report complexity related facts. We also describe an application of our scheme to biometric authentication and discuss the security of our suggested protocol. Last but not least, we indicate several promising research directions.

A special class of linear codes, having important applications in secret sharing and secure two-party computation, called minimal is characterized by the property that none of the codewords is covered by some other codeword. Denoting by $w_{min}$ and $w_{max}$ the minimal and maximal weight of a binary linear code respectively, a sufficient but not necessary condition for achieving minimality is that $w_{min} /w_{max} > 1/2$ (called Ashikhmin-Barg’s bound). Those minimal codes satisfying the condition $w_{min} /w_{max} \leq 1/2$ are called wide in this article (generally harder to construct), whereas codes satisfying $w_{min} /w_{max} > 1/2$ are called narrow. In this article, we first show that the so-called direct sum of Boolean functions of the form $h(x,y) = f(x) + g(y)$ induces narrow minimal codes whenever g is a bent function. Then, we introduce the concept of non-covering permutations (referring to the property of minimality) which is shown to be sufficient for providing many infinite classes of minimal binary linear codes of larger dimension by employing a suitable subspace of derivatives of the bent function g. In the second part of this article, we first provide one efficient method (with easily satisfied initial conditions) of generating wide minimal codes. Then, we again consider the use of derivatives (along with the underlying Boolean function given as the direct sum) for the purpose of defining another class of wide minimal codes. To the best of our knowledge, the latter method is the most general framework for designing wide binary linear codes. It uses a (suitable) subspace of derivatives of $h(x,y) = f(x) + g(y)$, where $g$ is a bent function and f satisfies certain minimality requirements. For a fixed suitable function $f$, one can derive a huge class of non-equivalent wide binary linear codes of the same length by varying the permutation $\phi$ when specifying the bent function $g(y^{(1)} , y^{(2)} ) = $\phi( y^{(2)} )\cdot y^{(1)} $ in the Maiorana-McFarland class.

In this paper, we show how multiplication for polynomial rings used in the NIST PQC finalists Saber and NTRU can be efficiently implemented using the Number-theoretic transform (NTT). We obtain superior performance compared to the previous state of the art implementations using Toom–Cook multiplication on both NIST’s primary software optimization targets AVX2 and Cortex-M4. Interestingly, these two platforms require different approaches: On the Cortex-M4, we use 32-bit NTT-based polynomial multiplication, while on Intel we use two 16-bit NTT-based polynomial multiplications and combine the products using the Chinese Remainder Theorem (CRT). For Saber, the performance gain is particularly pronounced. On Cortex-M4, the Saber NTT-based matrix-vector multiplication is 61% faster than the Toom–Cook multiplication resulting in a 22% speed-up of Saber encapsulation. For NTRU, the speed-up is less impressive, but still NTT-based multiplication performs better than Toom–Cook for all parameter sets on Cortex-M4. The NTT-based polynomial multiplication for NTRU-HRSS is 10% faster than Toom–Cook which results in a 6% speed-up for encapsulation. On AVX2, we obtain speed-ups for three out of four NTRU parameter sets. As a further illustration, we also include code for AVX2 and Cortex-M4 for the Chinese Association for Cryptologic Research competition award winner LAC (also a NIST round 2 candidate) which outperforms existing code.

Recently, privacy-preserving logistic regression techniques on distributed data among several data owners drew attention in terms of their applicability in federated learning environment. Many of them have been built upon cryptographic primitives such as secure multiparty computations(MPC) and homomorphic encryptions(HE) to protect the privacy of data. The secure multiparty computation provides fast and secure unit operations for arithmetic and bit operations but they often does not scale with large data well enough due to large computation cost and communication overhead. From recent works, many HE primitives provide their operations in a batch sense so that the technique can be an appropriate choice in a big data environment. However computationally expensive operations such as ciphertext slot rotation or refreshment(so called bootstrapping) and large public key size are hurdles that hamper widespread of the technique in the industry-level environment.

In this paper, we provide a new hybrid approach of a privacy-preserving logistic regression training and a inference, which utilizes both MPC and HE techniques to provide efficient and scalable solution while minimizing needs of key management and complexity of computation in encrypted state. Utilizing batch sense properties of HE, we present a method to securely compute multiplications of vectors and matrices using one HE multiplication, compared to the naive approach which requires linear number of multiplications regarding to the size of input data. We also show how we used a 2-party additive secret sharing scheme to control noises of expensive HE operations such as bootstrapping efficiently.

We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of constant-round post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest:

- A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. - Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against parallel verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. - A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.

With the location-based services (LBS) booming, the volume of spatial data inevitably explodes. In order to reduce local storage and computational overhead, users tend to outsource data and initiate queries to the cloud. However, sensitive data or queries may be compromised if cloud server has access to raw data and plaintext token. To cope with this problem, searchable encryption for geometric range is applied. Geometric range search has wide applications in many scenarios, especially the circular range search.

In this paper, a practical and secure circular range search scheme (PSCS) is proposed to support searching for spatial data in a circular range. With our scheme, a semi-honest cloud server will return data for a given circular range correctly without uncovering index privacy or query privacy. We propose a polynomial split algorithm which can decompose the inner product calculation neatly. Then, we define the security of our PSCS formally and prove that it is secure under same-closeness-pattern chosen-plaintext attacks (CLS-CPA) in theory. In addition, we demonstrate the efficiency and accuracy through analysis and experiments compared with existing schemes.

Digital contact tracing apps allow to alert people who have been in contact with people who may be contagious. The Apple/Google Exposure Notification (EN) system is based on Bluetooth proximity estimation. It has been adopted by many countries around the world. However, many possible attacks are known. The goal of some of them is to inject a false alert on someone else’s phone. This way, an adversary can eliminate a competitor in a sport event or a business in general. Political parties can also prevent people from voting.

In this report, we review several methods to inject false alerts. One of them requires to corrupt the clock of the smartphone of the victim. For that, we build a time-traveling machine to be able to remotely set up the clock on a smartphone and experiment our attack. We show how easy this can be done. We successfully tested several smartphones with either the Swiss or the Italian app (SwissCovid or Immuni).

Boyle et al. (TCC 2019) proposed a new approach for secure computation in the preprocessing model building on function secret sharing (FSS), where a gate $g$ is evaluated using an FSS scheme for the related offset family $g_r(x)=g(x+r)$. They further presented efficient FSS schemes based on any pseudorandom generator (PRG) for the offset families of several useful gates $g$ that arise in "mixed-mode'' secure computation. These include gates for zero test, integer comparison, ReLU, and spline functions. The FSS-based approach offers significant savings in online communication and round complexity compared to alternative techniques based on garbled circuits or secret sharing.

In this work, we improve and extend the previous results of Boyle et al. by making the following three kinds of contributions: - Improved Key Size: The preprocessing and storage costs of the FSS-based approach directly depend on the FSS key size. We improve the key size of previous constructions through two steps. First, we obtain roughly 4x reduction in key size for Distributed Comparison Function (DCF), i.e., FSS for the family of functions $f^<_a_,_b(x)$ that output $b$ if $x < a$ and $0$ otherwise. DCF serves as a central building block in the constructions of Boyle et al. Second, we improve the number of DCF instances required for realizing useful gates $g$. For example, whereas previous FSS schemes for ReLU and $m$-piece spline required 2 and $2m$ DCF instances, respectively, ours require only a single instance of DCF in both cases. This improves the FSS key size by 6-22x for commonly used gates such as ReLU and sigmoid. - New Gates: We present the first PRG-based FSS schemes for arithmetic and logical shift gates, as well as for bit-decomposition where both the input and outputs are shared over $Z_N$ for $N = 2^n$. These gates are crucial for many applications related to fixed-point arithmetic and machine learning. - A Barrier: The above results enable a 2-round PRG-based secure evaluation of "multiply-then-truncate,'' a central operation in fixed-point arithmetic, by sequentially invoking FSS schemes for multiplication and shift. We identify a barrier to obtaining a 1-round implementation via a single FSS scheme, showing that this would require settling a major open problem in the area of FSS: namely, a PRG-based FSS for the class of bit-conjunction functions.

In this paper, we initiate the study of interactive proofs for the promise problem $\mathsf{QBBC}$ (i.e., quantum black-box computations), which consists of a quantum device $\mathcal{D}$ acting on $(n+m)$ qubits, a classical device $\mathcal{R}_F$ deciding the input-output relation of some unknown function $F:\{0,1\}^n \rightarrow \{0,1\}^m$, and two reals $0< b < a \leq 1$. Let $p(\mathcal{D},x) = \| |x,F(x)\rangle \langle x,F(x)| \mathcal{D}(|x\rangle |0^m\rangle)\|^2$ be the probability of obtaining $(x,F(x))$ as a result of a standard measurement of the $(n+m)$-qubit state returned by $\mathcal{D}$ on input $|x\rangle |0^m\rangle$. The task of the problem $\mathsf{QBBC}(\mathcal{D},\mathcal{R}_F,a,b)$ is to distinguish between two cases for all $x\in \{0,1\}^n$: \\

$\bullet$ YES Instance: $p(\mathcal{D},x) \geq a$;

$\bullet$ NO Instance: $p(\mathcal{D},x) \leq b$.

First, we show that for any constant $15/16< a \leq 1$, the problem $\mathsf{QBBC}(\mathcal{D},\mathcal{R}_F,a,b)$ has an efficient two-round interactive proof $(\mathcal{P}^{\mathcal{D}},\mathcal{V}^{\mathcal{R}_F})$ which basically allows a verifier $\mathcal{V}$, given a classical black-box device $\mathcal{R}_F$, to efficiently verify if the prover $\mathcal{P}$ has a quantum black-box device $\mathcal{D}$ (correctly) computing $F$. This proof system achieves completeness $\frac{1 + a}{2}$ and soundness error $\frac{31}{32} + \frac{\epsilon}{2} + \mathsf{negl}(n)$ for any constant $\max(0,b-\frac{15}{16})<\epsilon<a - \frac{15}{16}$, given that the verifier $\mathcal{V}$ has some (limited) quantum capabilities. In terms of query complexities, the prover $\mathcal{P}^\mathcal{D}$ will make at most two quantum queries to $\mathcal{D}$, while the verifier $\mathcal{V}^{\mathcal{R}_F}$ only makes a single classical query to $\mathcal{R}_F$. This result is based on an information versus disturbance lemma, which may be of independent interest.

Second, under the learning with errors (LWE) assumption in (Regev 2005), we show that the problem $\mathsf{QBBC}(\mathcal{D},\mathcal{R}_F,a,b)$ can even have an efficient interactive proof $(\mathcal{P}^{\mathcal{D}},\mathcal{V}^{\mathcal{R}_F})$ with a fully classical verifier $\mathcal{V}$ that does not have any quantum capability. This proof system achieves completeness $\frac{1 + a}{2}-\mathsf{negl}(n)$ and soundness error $\frac{1+b}{2} + \mathsf{negl}(n)$, and thus applies to any $\mathsf{QBBC}(\mathcal{D},\mathcal{R}_F,a,b)$ with constants $0< b<a \leq 1$. Moreover, this proof system has the same query complexities as above. This result is based on the techniques introduced in (Brakerski et al. 2018) and (Mahadev 2018).

As an application, we show that the problem of distinguishing the random oracle model (ROM) and the quantum random oracle model (QROM) in cryptography can be naturally seen as a $\mathsf{QBBC}$ problem. By applying the above result, we immediately obtain a separation between ROM and QROM under the standard LWE assumption.

Threshold signing research progressed a lot in the last three years, especially for ECDSA, which is less MPC-friendly than Schnorr-based signatures such as EdDSA. This progress was mainly driven by blockchain applications, and boosted by breakthrough results concurrently published by Lindell and by Gennaro & Goldfeder. Since then, several research teams published threshold signature schemes with different features, design trade-offs, building blocks, and proof techniques. Furthermore, threshold signing is now deployed within major organizations to protect large amounts of digital assets. Researchers and practitioners therefore need a clear view of the research state, of the relative merits of the protocols available, and of the open problems, in particular those that would address "real-world" challenges.

This survey therefore proposes to (1) describe threshold signing and its building blocks in a general, unified way, based on the extended arithmetic black-box formalism (ABB+); (2) review the state-of-the-art threshold signing protocols, highlighting their unique properties and comparing them in terms of security assurance and performance, based on criteria relevant in practice; (3) review the main open-source implementations available.