International Association
for Cryptologic Research

We’re a small team with a big mission and we’re looking for our Founding Cryptographic Software Engineer. Sovereign Systems was founded on the premise that personal data is valuable, and so are privacy and security. Historically, this premise has represented a paradox, as users and organizations have been forced to trade one for the other. Sovereign Systems is providing a solution to this paradox.

This is an opportunity to get in on the ground floor and shape the technical vision and strategy. You’ll work directly alongside the CEO and Chief Data Scientist with the support of an all-star team of A-list and highly active advisors. You’ll start by doing, rolling your sleeves up, and cranking out code. As we grow, you’ll help to build our technical team and collaborate with key stakeholders on the processes and frameworks that will allow the company to run both joyfully and efficiently.

In this role, you will have the opportunity to:

• You will have the chance to craft solutions and develop software for millions of users around the world.
• You'll be part of a company whose commitment to user privacy is at the heart of everything.
• You'll be surrounded by the most creative, passionate, and talented engineers in the industry, constantly being challenged to go beyond the norm to find new, innovative ways of solving problems and to make software safer, easier, and more fun to use.

Key qualifications :

• Passion for creating effective and pragmatic cryptographic schemes.
• MS/Ph.D. in Computer Science or CSE or equivalent experience. 5+ years building cloud-based and distributed systems.
• Understanding of fundamental cryptographic algorithms and the underlying mathematics, such as finite field arithmetic.
• Experience implementing privacy-preserving cryptographic primitives and protocols like fully homomorphic and oblivious encryption, and garbled circuits, and using libraries such as Zama, Microsoft SEAL, HELayers.
• Experience implementing high-performance cryptographic protocols in languages like Rust, Java, Go, Python, or C/C++.

Closing date for applications:

Contact: Jackie Peters

The Cybersecurity Group at TU Delft now opens a 4-year PhD position and two 2/3-year Post-doc positions within the Horizon Europe projects. The successful candidates are expected to do cutting-edge research on the topic of applied cryptography (in particular UC, lattice-based crypto) with renowned international researchers. They will be provided excellent research environment, international visiting/collaborations, and competitive salary and allowance packages.

For PhD: candidates are required to hold a MSc in math, computer science or related subject (preferably with some related backgrounds on cryptography). Further, they should provide sufficient English skills, e.g., International English test certificate.
For Post-doc: candidates must hold a PhD in mathematics or computer science with expertise on cryptography, and they are expected to have great backgrounds on UC or lattice-base crypto, and/or cryptography in general. Candidates must have a strong track record, academic writing and communication ability.

All the positions may have flexible starting date. Please prepare a detailed resume (including a list of publications if have), bachelor and MSc transcripts (for the PhD position), 1 page motivation letter, International English certificate (if have), and two references (names and contact emails).

Please contact shihui.fu@tudelft.nl for further questions.

Closing date for applications:

Contact: Dr. S. Fu (shihui.fu@tudelft.nl)

The University of Amsterdam offers a PhD position related to information security in machine learning applications. The project is especially concerned with trade-offs between security and other properties such as accuracy and energy consumption. This includes the accuracy and energy impact of cryptographic approaches to privacy-preserving machine learning, using for example secure multiparty computing or homomorphic encryption.

More information: https://vacatures.uva.nl/UvA/job/PhD-Position-in-Energy-and-Security-of-Machine-Learning-Applications-in-the-Cloud-to-Edge-Continuum/745019702/

Closing date for applications:

Contact: dr. Ana Oprescu (a.m.oprescu at uva.nl)

More information: https://vacatures.uva.nl/UvA/job/PhD-Position-in-Energy-and-Security-of-Machine-Learning-Applications-in-the-Cloud-to-Edge-Continuum/745019702/

We present TRIFORS (TRIlinear FOrms Ring Signature), a logarithmic post-quantum (linkable) ring signature based on a novel assumption regarding equivalence of alternating trilinear forms. The basis of this work is the construction by Beullens, Katsumata and Pintore from 2020 to obtain a linkable ring signature from a cryptographic group action. The group action on trilinear forms used here is the same employed in the signature presented by Tang et al. at EUROCRYPT 22. We first define a sigma protocol that, given a set of public keys, the ring, allows to prove the knowledge of a secret key corresponding to a public one in the ring. Furthermore, some optimisations are used to reduce the size of the signature: among others, we use a novel application of the combinatorial number system to the space of the challenges. Using the Fiat-Shamir transform, we obtain a (linkable) ring signature of competitive length with the state-of-the-art among post-quantum proposals for security levels 128 and 192.

Dynamic-committee proactive secret sharing (DPSS) enables the update of secret shares and the alternation of shareholders, which makes it a promising technology for long-term key management and committee governance. However, there is a huge gap in communication costs between the state-of-the-art asynchronous and non-asynchronous DPSS schemes. In this paper, we fill this gap and propose the first practical DPSS scheme, DyCAPS, with a cubic communication cost w.r.t. the number of shareholders. DyCAPS can be efficiently integrated into existing asynchronous BFT-based blockchains to support the member change in BFT committees, without increasing the overall asymptotic communication cost. The experimental results show that DyCAPS introduces acceptable latency during the reconfiguration of the committees.

Multi-input functional encryption, MIFE, is a powerful generalization of functional encryption that allows computation on encrypted data coming from multiple different data sources. In a recent work, Agrawal, Goyal, and Tomida (CRYPTO 2021) constructed MIFE for the class of quadratic functions. This was the first MIFE construction from bilinear maps that went beyond inner product computation. We advance the state-of-the-art in MIFE, and propose new constructions with stronger security and broader functionality.

Stronger Security: In the typical formulation of MIFE security, an attacker is allowed to either corrupt all or none of the users who can encrypt the data. In this work, we study MIFE security in a stronger and more natural model where we allow an attacker to corrupt any subset of the users, instead of only permitting all-or-nothing corruption. We formalize the model by providing each user a unique encryption key, and letting the attacker corrupt all non-trivial subsets of the encryption keys, while still maintaining the MIFE security for ciphertexts generated using honest keys. We construct a secure MIFE system for quadratic functions in this fine-grained corruption model from bilinear maps. Our construction departs significantly from the existing MIFE schemes as we need to tackle a more general class of attackers.

Broader Functionality: The notion of multi-client functional encryption, MCFE, is a useful extension of MIFE. In MCFE, each encryptor can additionally tag each ciphertext with appropriate metadata such that ciphertexts with only matching metadata can be decrypted together. In more detail, each ciphertext is now annotated with a unique label such that ciphertexts encrypted for different slots can now only be combined together during decryption as long as the associated labels are an exact match for all individual ciphertexts. In this work, we upgrade our MIFE scheme to also support ciphertext labelling. While the functionality of our scheme matches that of MCFE for quadratic functions, our security guarantee falls short of the general corruption model studied for MCFE. In our model, all encryptors share a secret key, therefore this yields a secret-key version of quadratic MCFE, which we denote by SK-MCFE. We leave the problem of proving security in the general corruption model as an important open problem.

Bootstrapping, which enables the full homomorphic encryption scheme that can perform an infinite number of operations by restoring the modulus of the ciphertext with a small modulus, is an essential step in homomorphic encryption. However, bootstrapping is the most time and memory consuming of all homomorphic operations. As we increase the precision of bootstrapping, a large amount of computational resources is required. Specifically, for any of the previous bootstrap designs, the precision of bootstrapping is limited by rescaling precision.

In this paper, we propose a new bootstrapping algorithm of the Cheon-Kim-Kim-Song (CKKS) scheme to use a known bootstrapping algorithm repeatedly, so called { Meta-BTS}. By repeating the original bootstrapping operation twice, one can obtain another bootstrapping with its precision essentially doubled; it can be generalized to be $k$-fold bootstrapping operations for some $k>1$ while the ciphertext size is large enough. Our algorithm overcomes the precision limitation given by the rescale operation.

This paper presents a new McEliece-type encryption scheme based on Gabidulin codes, which uses linearized transformations to disguise the private key. When endowing this scheme with the partial cyclic structure, we obtain a public key of the form $GM^{-1}$, where $G$ is a partial circulant generator matrix of Gabidulin code and $M$ as well as $M^{-1}$ is a circulant matrix of large rank weight, even as large as the code length. Another difference from Loidreau's proposal at PQCrypto 2017 is that both $G$ and $M$ are publicly known. Recovering the private key can be reduced to deriving from $M$ a linearized transformation and two circulant matrices of small rank weight. This new scheme is shown to resist all the known distinguisher-based attacks, such as the Overbeck attack and Coggia-Couvreur attack, and also has a very small public key size. For instance, 2592 bytes are enough for our proposal to achieve the security of 256 bits, which is 400 times smaller than Classic McEliece that has been selected into the fourth round of the NIST Post-Quantum Cryptography (PQC) standardization process.

Group-based cryptography is a relatively young family in post-quantum cryptography. In this paper we give the first dedicated security analysis of a central problem in group-based cryptography: the so-called Semidirect Product Key Exchange(SDPKE). We present a subexponential quantum algorithm for solving SDPKE. To do this we reduce SDPKE to the Abelian Hidden Shift Problem (for which there are known quantum subexponential algorithms). We stress that this does not per se constitute a break of SDPKE; rather, the purpose of the paper is to provide a connection to known problems.

In this short note, we describe a process for halving a point on a twisted Edwards curve. This can be used to test whether a given point is in the subgroup of prime order $\ell$, which is used by some cryptographic protocols. On Curve25519, this new test is about twice faster than the classic method consisting of multiplying the source point by $\ell$.

At Eurocrypt 2022, May et al. proposed a partial key exposure (PKE) attack on CRT-RSA that efficiently factors $N$ knowing only a $\frac{1}{3}$-fraction of either most significant bits (MSBs) or least significant bits (LSBs) of private exponents $d_p$ and $d_q$ for public exponent $e \approx N^{\frac{1}{12}}$. In practice, PKE attacks typically rely on the side-channel leakage of these exponents, while a side-channel resistant implementation of CRT-RSA often uses additively blinded exponents $d^{\prime}_p = d_p + r_p(p-1)$ and $d^{\prime}_q = d_q + r_q(q-1)$ with unknown random blinding factors $r_p$ and $r_q$, which makes PKE attacks more challenging.

Motivated by the above, we extend the PKE attack of May et al. to CRT-RSA with additive exponent blinding. While admitting $r_pe\in(0,N^{\frac{1}{4}})$, our extended PKE works ideally when $r_pe \approx N^{\frac{1}{12}}$, in which case the entire private key can be recovered using only $\frac{1}{3}$ known MSBs or LSBs of the blinded CRT exponents $d^{\prime}_p$ and $d^{\prime}_q$. Our extended PKE follows their novel two-step approach to first compute the key-dependent constant $k^{\prime}$ ($ed^{\prime}_p = 1 + k^{\prime}(p-1)$, $ed^{\prime}_q = 1 + l^{\prime}(q-1)$), and then to factor $N$ by computing the root of a univariate polynomial modulo $k^{\prime}p$. We extend their approach as follows. For the MSB case, we propose two options for the first step of the attack, either by obtaining a single estimate $k^{\prime}l^{\prime}$ and calculating $k^{\prime}$ via factoring, or by obtaining multiple estimates $k^{\prime}l^{\prime}_1,\ldots,k^{\prime}l^{\prime}_z$ and calculating $k^{\prime}$ probabilistically via GCD.

For the LSB case, we extend their approach by constructing a different univariate polynomial in the second step of the LSB attack. A formal analysis shows that our LSB attack runs in polynomial time under the standard Coppersmith-type assumption, while our MSB attack either runs in sub-exponential time with a reduced input size (the problem is reduced to factor a number of size $e^2r_pr_q\approx N^{\frac{1}{6}}$) or in probabilistic polynomial time under a novel heuristic assumption. Under the settings of the most common key sizes (1024-bit, 2048-bit, and 3072-bit) and blinding factor lengths (32-bit, 64-bit, and 128-bit), our experiments verify the validity of the Coppersmith-type assumption and our own assumption, as well as the feasibility of the factoring step.

To the best of our knowledge, this is the first PKE on CRT-RSA with experimentally verified effectiveness against 128-bit unknown exponent blinding factors. We also demonstrate an application of the proposed PKE attack using real partial side-channel key leakage targeting a Montgomery Ladder exponentiation CRT implementation.

Bilinear pairings have been used in different cryptographic applications and demonstrated to be a key building block for a plethora of constructions. In particular, some Succinct Non-interactive ARguments of Knowledge (SNARKs) have very short proofs and very fast verifi- cation thanks to a multi-pairing computation. This succinctness makes pairing-based SNARKs suitable for proof recursion, that is proofs veri- fying other proofs. In this scenario one requires to express efficiently a multi-pairing computation as a SNARK arithmetic circuit. Other com- pelling applications such as verifying Boneh–Lynn–Shacham (BLS) sig- natures or Kate–Zaverucha–Goldberg (KZG) polynomial commitment opening in a SNARK fall into the same requirement. The implementation of pairings is challenging but the literature has very detailed approaches on how to reach practical and optimized implementations in different contexts and for different target environments. However, to the best of our knowledge, no previous publication has addressed the question of ef- ficiently implementing a pairing as a SNARK arithmetic circuit. In this work, we consider efficiently implementing pairings in Rank-1 Constraint Systems (R1CS), a widely used model to express SNARK statements. We implement our techniques in the gnark open-source ecosystem and show that the arithmetic circuit depth can be almost halved compared to the previously best known pairing implementation on a Barreto–Lynn–Scott (BLS) curve of embedding degree 12, resulting in a significantly faster proving time. We also investigate and implement the case of BLS curves of embedding degree 24.

In this expository article we present an overview of the current state-of-the-art in post-quantum group-based cryptography. We describe several families of groups that have been proposed as platforms, with special emphasis in polycyclic groups and graph groups, dealing in particular with their algorithmic properties and cryptographic applications. We then, describe some applications of combinatorial algebra in fully homomorphic encryption. In the end we discussing several open problems in this direction.

The aim of this paper is to prove that the Scholz conjecture on addition chain is true for all integers with $v(n)=4$, $v(n)$ is the number of ''1'' in the binary expansion of $n$.

There are many recent results on reverse-engineering (potentially hidden) structure in cryptographic S-boxes. The problem of recovering structure in the other main building block of symmetric cryptographic primitives, namely, the linear layer, has not been paid that much attention so far. To fill this gap, in this work, we develop a systematic approach to decomposing structure in the linear layer of a substitution-permutation network (SPN), covering the case in which the specification of the linear layer is obfuscated from applying secret linear transformations to the S-boxes. We first present algorithms to decide whether an $ms \times ms$ matrix with entries in a prime field $\mathbb{F}_p$ can be represented as an $m \times m$ matrix over the extension field $\mathbb{F}_{p^s}$. We then study the case of recovering structure in MDS matrices by investigating whether a given MDS matrix follows a Cauchy construction. As an application, for the first time, we show that the $8 \times 8$ MDS matrix over $\mathbb{F}_{2^8}$ used in the hash function Streebog is a Cauchy matrix.

K-Cipher is an ultra-low latency block cipher with variable-length parameters designed by Intel Labs. In this work, we analyze the security of K-Cipher and propose a differential cryptanalysis attack with the complexity of $2^{29.7}$ for a variant of K-Cipher with state size $n=24$ bits state and block size $m=8$ bits. Our attack recovers the secret key and secret randomizer values with a total length of 240 bits in $\sim 30$ minutes on a standard desktop machine. We show that it is possible to extend the same attack for an arbitrary set of parameters.

We propose three constructions of classically verifiable non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models.

1. We construct a CV-NIZK for QMA in the quantum secret parameter model where a trusted setup sends a quantum proving key to the prover and a classical verification key to the verifier. It is information theoretically sound and zero-knowledge.

2. Assuming the quantum hardness of the learning with errors problem, we construct a CV-NIZK for QMA in a model where a trusted party generates a CRS and the verifier sends an instance-independent quantum message to the prover as preprocessing. This model is the same as one considered in the recent work by Coladangelo, Vidick, and Zhang (CRYPTO '20). Our construction has the so-called dual-mode property, which means that there are two computationally indistinguishable modes of generating CRS, and we have information theoretical soundness in one mode and information theoretical zero-knowledge property in the other. This answers an open problem left by Coladangelo et al, which is to achieve either of soundness or zero-knowledge information theoretically. To the best of our knowledge, ours is the first dual-mode NIZK for QMA in any kind of model.

3. We construct a CV-NIZK for QMA with quantum preprocessing in the quantum random oracle model. This quantum preprocessing is the one where the verifier sends a random Pauli-basis states to the prover. Our construction uses the Fiat-Shamir transformation. The quantum preprocessing can be replaced with the setup that distributes Bell pairs among the prover and the verifier, and therefore we solve the open problem by Broadbent and Grilo (FOCS '20) about the possibility of NIZK for QMA in the shared Bell pair model via the Fiat-Shamir transformation.

The income of companies working on data markets steadily grows year by year. Private function evaluation (PFE) is a valuable tool in solving corresponding security problems. The task of Controlled Private Function Evaluation (CPFE) and its relaxed version (rCPFE) was proposed in [11]. We define an ideal functionality for the latter task and present a UC-secure realization of the functionality against static malicious parties. The core primitive is functional encryption (FE) and essentially this determines the conditions of realizability. Accordingly, in the case of non-adaptive FE-setting secure realization of the ideal functionality is achievable in the standard model, otherwise, accessibility of random oracle is required.

We propose the signature scheme Hawk, a concrete instantiation of proposals to use the Lattice Isomorphism Problem (LIP) as a foundation for cryptography that focuses on simplicity. This simplicity stems from LIP, which allows the use of lattices such as $\mathbb{Z}^n$ , leading to signature algorithms with no floats, no rejection sampling, and compact precomputed distributions. Such design features are desirable for constrained devices, and when computing signatures inside FHE or MPC. The most significant change from recent LIP proposals is the use of module lattices, reusing algorithms and ideas from NTRUSign and Falcon.

Its simplicity makes Hawk competitive. We provide cryptanalysis with experimental evidence for the design of Hawk and implement two parameter sets, Hawk-512 and Hawk-1024. Signing using Hawk-512 and Hawk-1024 is four times faster than Falcon on x86 architectures, produces signatures that are about 15% more compact, and is slightly more secure against forgeries by lattice reduction attacks. When floating-points are unavailable, Hawk signs 15 times faster than Falcon.

We provide a worst case to average case reduction for module LIP. For certain parametrisations of Hawk this applies to secret key recovery and we reduce signature forgery in the random oracle model to a new problem called the one more short vector problem.

The efficiency of constant-time SM4 implementation has been lagging behind that of AES for most internet traffic and applicable data encryption scenarios. The best performance before our works was 3.77 cpb for x86 platform (AESNI + AVX2), and 8.62 cpb for Arm platform (NEON). Meanwhile the state of art constant-time AES implementation could reach 0.63 cpb. Dedicated SM4 instruction set extensions like those optionally available in Armv8.2, could achieve comparable cpb to AES. But they are only available in limited processors, therefore does not impact much to real-world uses. To fill the gap we explored some novel techniques with Intel GFNI instruction set extension and Arm NEON coprocessor. We achieved 1.51 cpb with GFNI + AVX512 and 2.62 cpb with GFNI + AVX2 for Intel processors; we also achieved 6.74 cpb with NEON. In addition, we simplified the algebraic expression of SM4 S-Box. And our technique to exploit L1 cache could also be applied to other applications and hardware platforms if the circumstances apply.