International Association
for Cryptologic Research

Event date: 19 October to 20 October 2020

Three Ph.D. positions opening at Dr. Jiafeng Harvest Xie's research group at the Department of Electrical and Computer Engineering of Villanova University, Villanova, PA (west of Philadelphia, USA). The research topics of these positions are focused on cryptographic engineering and fault detection related security analysis. Interested ones are warmly welcomed to apply and send their resume/CV to Dr. Xie through email: jiafeng.xie@villanova.edu

Requirements: preferred to be at the majors of Computer Science or Computer Engineering. Majoring in Mathematics are also ok. Proficiency in programming languages such as C, C++, Python, and so on is needed. Good at English communication and writing. Great enthusiasm of doing research oriented tasks. Excellent team worker.

Degree: both B.S. and M.S. graduates or similar are warmly welcomed to apply.

Deadline: better to start at Spring 2021 (Fall 2021 is also ok). It is always better to apply as early as possible. Positions are open until they are filled.

Closing date for applications:

Contact: Jiafeng Harvest Xie (jiafeng.xie@villanova.edu)

We have an open PhD position in the domain of Scalable and Secure Data Sharing. 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, with strong grades. Strong background in mathematics / computer science / cryptography is expected. Any prior publications and experience in C/C++ and Python are merited.

Closing date for applications:

Contact: jobs-cosic@esat.kuleuven.be

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

We have an open postdoc position in the domain of Scalable and Secure Data Sharing. 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. 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. The candidate should also have coding experience in C/C++ and Python, experience in practical aspects of secure computation is a must.

Closing date for applications:

Contact: jobs-cosic@esat.kuleuven.be

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

Verifiable mix nets, and specifically proofs of (correct) shuffle, are a fundamental building block in numerous applications: these zero-knowledge proofs allow the prover to produce a public transcript which can be perused by the verifier to confirm the purported shuffle. They are particularly vital to verifiable electronic voting, where they underpin almost all voting schemes with non-trivial tallying methods. These complicated pieces of cryptography are a prime location for critical errors which might allow undetected modification of the outcome.

The best solution to preventing these errors is to machine-check the cryptographic properties of the design and implementation of the mix net. Particularly crucial for the integrity of the outcome is the soundness of the design and implementation of the verifier (software). Unfortunately, several different encryption schemes are used in many different slight variations which makes t infeasible to machine-check every single case individually. However, a particular optimized variant of the Terelius-Wikstrom mix net is, and has been, widely deployed in elections including national elections in Norway, Estonia and Switzerland, albeit with many slight variations and several different encryption schemes.

In this work, we develop the logical theory and formal methods tools to machine-check the design and implementation of all these variants of Terelius-Wikstrom mix nets, for all the different encryption schemes used; resulting in provably correct mix nets for all these different variations. We do this carefully to ensure that we can extract a formally verified implementation of the verifier (software) which is compatible with existing deployed implementations of the Terelius-Wikstrom mix net. This gives us provably correct implementations of the verifiers for more than half of the national elections which have used verifiable mix nets.

Our implementation of a proof of correct shuffle is the first to be machine-checked to be cryptographically correct and able to verify proof transcripts from national elections. We demonstrate the practicality of our implementation by verifying transcripts produced by the Verificatum mix net system and the CHVote evoting system from Switzerland.

Almost perfect nonlinear functions possess the optimal resistance to the differential cryptanalysis and are widely studied. Most known APN functions are obtained as functions over finite fields $\mathbb{F}_{2^n}$ and very little is known about combinatorial constructions in $\mathbb{F}_2^n$. In this work we proposed two approaches for obtaining quadratic APN functions in $\mathbb{F}_2^n$. The first approach exploits a secondary construction idea, it considers how to obtain quadratic APN function in $n+1$ variables from a given quadratic APN function in $n$ variables using special restrictions on new terms. The second approach is searching quadratic APN functions that have matrix form partially filled with standard basis vectors in a cyclic manner. This approach allowed us to find a new APN function in 7 variables. Also, we conjectured that a quadratic part of an arbitrary APN function has a low differential uniformity. This conjecture allowed us to introduce a new subclass of APN functions, so-called stacked APN functions. We found cubic examples of such functions for dimensions up to 6.

Mixed Integer Linear Programming (MILP) is a powerful tool that helps to automate several cryptanalysis techniques for symmetric key primitives. $\textsf{Gurobi}$ is one of the most popular solvers used by researchers to obtain useful results from the MILP models corresponding to these cryptanalysis techniques. In this report, we provide a cautionary note on the use of $\textsf{Gurobi}$ in the context of bit-based division property integral attacks. In particular, we report four different examples in which $\textsf{Gurobi}$ gives contradictory results when solving the same MILP model by just changing the number of used threads or reordering some constraints.

An efficient scalar multiplication algorithm is a crucial component of elliptic curve cryptosystems. In this paper we propose a scalar multiplication algorithm based on scalar recodings that is regular in nature and provides resistance against simple power analysis attacks. Our scalar multiplication algorithm is made from two scalar recoding algorithms called Recode and Align. Recode is the generalization of the signed non-zero bit recoding algorithm given by Hedabou, Pinel and Beneteau in 2005. It recodes the $k$-$ary$ representation of the given scalar into a signed nonzero form by means of a small lookup table. On the other hand, Align is the generalized $k$-$ary$ version of the sign-aligned columns recoding algorithm given by Faz-Hernandez, Longa and Sanchez in 2014. It recodes the $k$-$ary$ representation of a scalar in such a way that the sign of each of its digits agrees a given $\{1,-1\}$-valued sequence of signs. When analyzing the choice of $k$ in $\{2,3\}$, we find some theoretical evidence that $k=3$ may offer better performance in certain scenarios.

Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA and over variants of Schnorr signatures, however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signature schemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or contain subtle issues in their security proofs.

In this paper, we construct several lattice-based distributed signing protocols with low round complexity following the Fiat--Shamir with Aborts paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme. A key step to achieve security (overlooked in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message---which can inevitably happen in the Fiat--Shamir with Aborts setting. We manage to do so using lattice-based homomorphic commitments as constructed by Baum et al. (SCN 2018).

We first propose a three-round $n$-out-of-$n$ signature from Module-LWE with tight security (using ideas from lossy identification schemes). Then, we further reduce the complexity to two rounds, at the cost of relying on Module-SIS as an additional assumption, losing tightness due to the forking lemma, and requiring somewhat more expensive trapdoor commitments. The construction of suitable trapdoor commitments from lattices is a side contribution of this paper. Finally, we also obtain a two-round multi-signature scheme as a variant of our two-round $n$-out-of-$n$ protocol.

At a combined computational expense of about $6{\ell}$ field operations, V\'elu's formulae are used to construct and evaluate degree-$\ell$ isogenies in the vast majority of isogeny-based primitive implementations. Recently, Bernstein, de Feo, Leroux and Smith introduced a new approach for solving this same problem at a reduced cost of just $\tilde{O}(\sqrt{\ell})$ field operations. In this work, we present a concrete computational analysis of these novel formulae, along with several algorithmic tricks that helped us to slightly, but noticeably, reduce their practical cost. Furthermore, we report a Python-3 implementation of several instantiations of CSIDH and B-SIDH using a combination of the novel formulae and an adaptation of the optimal strategies commonly used in the SIDH/SIKE protocols. Compared to a traditional V\'elu constant-time implementation of CSIDH, our experimental results report a saving of 5.357\%, 13.68\% and 25.938\% base field operations for CSIDH-512, CSIDH-1024, and CSIDH-1792, respectively. Additionally, the first implementation of the B-SIDH scheme in the open literature is reported here.

This paper introduces a new approach to computing isogenies called "radical isogenies" and a corresponding method to compute chains of $N$-isogenies that is very efficient for small $N$. The method is fully deterministic and completely avoids generating $N$-torsion points. It is based on explicit formulae for the coordinates of an $N$-torsion point $P'$ on the codomain of a cyclic $N$-isogeny $\varphi : E \to E'$, such that composing $\varphi$ with $E' \to E' / \langle P' \rangle$ yields a cyclic $N^2$-isogeny. These formulae are simple algebraic expressions in the coefficients of $E$, the coordinates of a generator $P$ of $\ker \varphi$, and an $N$th root $\sqrt[N]{\rho}$, where the radicand $\rho$ itself is given by an easily computable algebraic expression in the coefficients of $E$ and the coordinates of $P$. The formulae can be iterated and are particularly useful when computing chains of $N$-isogenies over a finite field $\mathbb{F}_q$ with $\gcd(q-1, N) = 1$, where taking an $N$th root is a simple exponentiation. Compared to the state-of-the-art, our method results in an order of magnitude speed-up for $N \leq 13$; for larger $N$, the advantage disappears due to the increasing complexity of the formulae. When applied to CSIDH, we obtain a speed-up of about $19 \%$ over the implementation by Bernstein, De Feo, Leroux and Smith for the CSURF-512 parameters.

A $\mathit{multi\text{-}recipient}$ key encapsulation mechanism, or $\mathsf{mKEM}$, provides a scalable solution to securely communicating to a large group, and offers savings in both bandwidth and computational cost compared to the trivial solution of communicating with each member individually. All prior works on $\mathsf{mKEM}$ are only limited to classical assumptions and, although some generic constructions are known, they all require specific properties that are not shared by most post-quantum schemes. In this work, we first provide a simple and efficient generic construction of $\mathsf{mKEM}$ that can be instantiated from versatile assumptions, including post-quantum ones. We then study these $\mathsf{mKEM}$ instantiations at a practical level using 8 post-quantum $\mathsf{mKEM}$s (which are lattice and isogeny-based NIST candidates), and CSIDH, and show that compared to the trivial solution, our $\mathsf{mKEM}$ offers savings of at least one order of magnitude in the bandwidth, and make encryption time shorter by a factor ranging from 1.92 to 35. Additionally, we show that by combining $\mathsf{mKEM}$ with the TreeKEM protocol used by MLS $-$ an IETF draft for secure group messaging $-$ we obtain significant bandwidth savings.

We prove a tight lower bound on the number of group operations required for batch verification by any generic-group accumulator that stores a less-than-trivial amount of information. Specifically, we show that $\Omega(t \cdot (\lambda / \log \lambda))$ group operations are required for the batch verification of any subset of $t \geq 1$ elements, where $\lambda \in \mathbb{N}$ is the security parameter, thus ruling out non-trivial batch verification in the standard non-interactive manner.

Our lower bound applies already to the most basic form of accumulators (i.e., static accumulators that support membership proofs), and holds both for known-order (and even multilinear) groups and for unknown-order groups, where it matches the asymptotic performance of the known bilinear and RSA accumulators, respectively. In addition, it complements the techniques underlying the generic-group accumulators of Boneh, B{\"{u}}nz and Fisch (CRYPTO '19) and Thakur (ePrint '19) by justifying their application of the Fiat-Shamir heuristic for transforming their interactive batch-verification protocols into non-interactive procedures.

Moreover, motivated by a fundamental challenge introduced by Aggarwal and Maurer (EUROCRYPT '09), we propose an extension of the generic-group model that enables us to capture a bounded amount of arbitrary non-generic information (e.g., least-significant bits or Jacobi symbols that are hard to compute generically but are easy to compute non-generically). We prove our lower bound within this extended model, which may be of independent interest for strengthening the implications of impossibility results in idealized models.

Private Set Intersection Cardinality (PSI-CA) allows two parties, each holding a set of items, to learn the size of the intersection of those sets without revealing any additional information. To the best of our knowledge, this work presents the first protocol that allows one of the parties to delegate PSI-CA computation to untrusted servers. At the heart of our delegated PSI-CA protocol is a new oblivious distributed key PRF (Odk-PRF) abstraction, which may be of independent interest.

We explore in detail how to use our delegated PSI-CA protocol to perform privacy-preserving contact tracing. It has been estimated that a significant percentage of a given population would need to use a contact tracing app to stop a disease’s spread. Prior privacy-preserving contact tracing systems, however, impose heavy bandwidth or computational demands on client devices. These demands present an economic disincentive to participate for end users who may be billed per MB by their mobile data plan or for users who want to save battery life. We propose Catalic (ContAct TrAcing for LIghtweight Clients), a new contact tracing system that minimizes bandwidth cost and computation workload on client devices. By applying our new delegated PSI-CA protocol, Catalic shifts most of the client-side computation of contact tracing to untrusted servers, and potentially saves each user hundreds of megabytes of mobile data per day while preserving privacy.

High-assurance cryptography leverages methods from program verification and cryptography engineering to deliver efficient cryptographic software with machine-checked proofs of memory safety, functional correctness, cryptographic security, and side-channel protection. Traditionally, these guarantees are established under a sequential execution semantics. However, this semantics is not aligned with the behavior of modern processors that make use of speculative execution to improve performance. This mismatch, combined with the high-profile Spectre-style attacks that exploit speculative execution, may naturally cast doubts on the robustness of high-assurance cryptography guarantees. In this paper, we dispel these doubts by showing that the benefits of high-assurance cryptography extend to speculative execution, at the cost of a modest performance overhead. We build atop the Jasmin verification framework an end-to-end approach for proving properties of cryptographic software under speculative execution, and validate our approach experimentally with efficient, functionally correct, side-channel protected assembly implementations of ChaCha20 and Poly1305.

Higher-order masking countermeasures provide strong provable security against side-channel attacks at the cost of incurring significant overheads, which largely hinders its applicability. Previous works towards remedying cost mostly concentrated on ``local'' calculations, i.e., optimizing the cost of computation units such as a single AND gate or a field multiplication. This paper explores a complementary ``global'' approach, i.e., considering multiple operations in the masked domain as a batch and reducing randomness and computational cost via amortization. In particular, we focus on the amortization of $\ell$ parallel field multiplications for appropriate integer $\ell > 1$, and design a kit named {\it packed multiplication} for implementing such a batch. For $\ell+d\leq2^m$, when $\ell$ parallel multiplications over $\mathbb{F}_{2^{m}}$ with $d$-th order probing security are implemented, packed multiplication consumes $d^2+2\ell d + \ell$ bilinear multiplications and $2d^2 + d(d+1)/2$ random field variables, outperforming the state-of-the-art results with $O(\ell d^2)$ multiplications and $\ell \left \lfloor d^2/4\right \rfloor + \ell d$ randomness. To prove $d$-probing security for packed multiplications, we introduce some weaker security notions for multiple-inputs-multiple-outputs gadgets and use them as intermediate steps, which may be of independent interest. As parallel field multiplications exist almost everywhere in symmetric cryptography, lifting optimizations from ``local'' to ``global'' substantially enlarges the space of improvements. To demonstrate, we showcase the method on the AES Subbytes step, GCM and TET (a popular disk encryption). Notably, when $d=8$, our implementation of AES Subbytes in ARM Cortex M architecture achieves a gain of up to $33\%$ in total speeds and saves up to $68\%$ random bits than the state-of-the-art bitsliced implementation reported at ASIACRYPT~2018.

Post-quantum cryptography (PQC) is a trend that has a deserved NIST status, and which aims to be resistant to quantum computers attacks like Shor and Grover algorithms. In this paper, we propose a method for designing post-quantum provable IND-CPA/IND-CCA2 public key cryptosystems based on polynomials over a non-commutative algebraic extension ring. The key ideas of our proposal is that (a) for a given non-commutative ring of rank-3 tensors, we can define polynomials and take them as the underlying work structure (b) we replace all numeric field arithmetic with GF(2^8) field operations. By doing so, it is easy to implement R-propped Diffie-Helman-like key exchange protocol and consequently ElGamal-like cryptosystems. 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 or Roman’kov. The protocols have been proved to be semantically secure. Finally, we present numerical examples of the proposed R-Propped protocols.

First implemented in Bitcoin, Nakamoto Consensus (NC) is the most influential consensus protocol in cryptocurrencies despite all the alternative protocols designed afterward. Nevertheless, NC is trapped with a security-performance tradeoff, largely limiting the latter. In this paper, we propose NC-Max, a consensus protocol that breaks the throughput limit and enables the full utilization of the nodes' bandwidth in confirming transactions. In particular, after identifying the mechanism through which NC's security limits its performance, we decouple transaction synchronization from confirmation with a two-step mechanism, relieving the limits on the block size and the block interval. Further, we introduce an accurate dynamic difficulty adjustment mechanism to explore the real-time network condition and to adjust the protocol's throughput accordingly. We analyze the security of NC-Max, proving that it resists selfish mining and transaction withholding attacks better than NC does. Our performance evaluation shows that NC-Max not only fully exploits the nodes' bandwidth to confirm transactions, but also shortens the overall transaction confirmation latency by at least a factor of four compared to NC without compromising security.

Reducing the rounds of interaction in secure multiparty computation (MPC) protocols has been the topic of study of many works. One popular approach to reduce rounds is to construct *round compression compilers*. A round compression compiler is one that takes a highly interactive protocol and transforms it into a protocol with far fewer rounds. The design of round compression compilers has traditionally focused on preserving the security properties of the underlying protocol and in particular, not much attention has been given towards preserving their computational and communication efficiency. Indeed, the recent round compression compilers that yield round-optimal MPC protocols incur large computational and communication overhead.

In this work, we initiate the study of *efficiency-preserving* round compression compilers, i.e. compilers that translate the efficiency benefits of the underlying highly interactive protocols to the fewer round setting. Focusing on the honest majority setting (with near-optimal corruption threshold $\frac{1}{2} - \varepsilon$, for any $\varepsilon > 0$), we devise a new compiler that yields two round (i.e., round optimal) semi-honest MPC with similar communication efficiency as the underlying (arbitrary round) protocol. By applying our compiler on the most efficient known MPC protocols, we obtain a two-round semi-honest protocol based on one-way functions, with total communication (and per-party computation) cost $\widetilde{O}(s+n^4)$ -- a significant improvement over prior two-round protocols with cost $\widetilde{O}(n^\tau s+n^{\tau+1}d)$, where $\tau\geq 2$, $s$ is the size of the circuit computing the function and $d$ the corresponding depth. Our result can also be extended to handle malicious adversaries, either using stronger assumptions in the public key infrastructure (PKI) model, or in the plain model using an extra round.

An artifact of our approach is that the resultant protocol is ``unbalanced'' in the amount of computation performed by different parties. We give evidence that this is *necessary* in our setting. Our impossibility result makes novel use of the ``MPC-in-the-head" paradigm which has typically been used to demonstrate feasibility results.

We propose the first tightly secure and unbounded hierarchical identity-based encryption (HIBE) scheme based on standard assumptions. Our main technical contribution is a novel proof strategy that allows us to tightly randomize user secret keys for identities with arbitrary hierarchy depths using low entropy hidden in a small and hierarchy-independent master public key.

The notion of unbounded HIBE is proposed by Lewko and Waters (Eurocrypt 2011). In contrast to most HIBE schemes, an unbounded scheme does not require any maximum depth to be specified in the setup phase, and user secret keys or ciphertexts can be generated for identities of arbitrary depths with hierarchy-independent system parameters.

While all the previous unbounded HIBE schemes have security loss that grows at least linearly in the number of user secret key queries, the security loss of our scheme is only dependent on the security parameter, even in the multi-challenge setting, where an adversary can ask for multiple challenge ciphertexts. We prove the adaptive security of our scheme based on the Matrix Decisional Diffie-Hellman assumption in prime-order pairing groups, which generalizes a family of standard Diffie-Hellman assumptions such as k-Linear.