International Association
for Cryptologic Research

In this paper we study the security of two constructions for variable-length universal hash functions by means of their universality. Both constructions make use of a fixed-length unkeyed function that we call a block function. One construction is serial and is an idealization of the compression phase of Pelican-MAC. The other construction is parallel and is an idealization of the compression phase of Farfalle. Both are instances of a class of functions we call semi-group accumulators. We prove that the universality of these constructions is fully determined by the differential probability of block function differentials and, if not a permutation, the relative frequency of block function outputs. We show that both block function parallelization and serialization have equal security (against forgery) in the Wegman-Carter(-Shoup) construction. However, for the block functions we target, parallelization can provide significantly better security than serialization in the Protected Hash (PH) construction. Moreover, below a certain data limit, PH provides better security than WC(S) for the block function parallelization, despite the fact that it does not require a nonce. We show evidence of this effect by taking Xoodoo[3] as the block function .

The latest message driven (LMD) greedy heaviest observed sub-tree (GHOST) consensus protocol is a critical component of future proof-of-stake (PoS) Ethereum. In its current form, the protocol is brittle and intricate to reason about, as evidenced by recent attacks, patching attempts, and Görli testnet reorgs. We present Goldfish, which can be seen as a considerably simplified variant of the current protocol, and prove that it is secure and reorg resilient in synchronous networks with dynamic participation, assuming a majority of the nodes (called validators) follows the protocol honestly. Furthermore, we show that subsampling validators can improve the communication efficiency of Goldfish, and that Goldfish is composable with finality gadgets and accountability gadgets. The aforementioned properties make Goldfish a credible candidate for a future protocol upgrade of PoS Ethereum, as well as a versatile pedagogical example. Akin to traditional propose-and-vote-style consensus protocols, Goldfish is organized into slots, at the beginning of which a leader proposes a block containing new transactions, and subsequently members of a committee take a vote towards block confirmation. But instead of using quorums, Goldfish is powered by a new mechanism that carefully synchronizes the inclusion and exclusion of votes in honest validators' views.

Event date: 26 March to
Submission deadline: 19 November 2022
Notification: 25 January 2023

Event date: 3 April to 4 April 2023
Submission deadline: 28 November 2022
Notification: 23 January 2023

Event date: 6 October to 7 October 2022
Submission deadline: 12 September 2022
Notification: 13 September 2022

We have a vacancy for a postdoctoral fellowship at the Department of Mathematical Sciences at NTNU in Trondheim, Norway. The postdoctoral fellowship position is a temporary position where the main goal is to qualify for work in senior academic positions.

The position is funded by the Norwegian Research Council in the project: “OffPAD - Optimizing balance between high security and usability. An innovative approach to endpoint security”.

The NIST Post Quantum Cryptography Standardization is expected to end in 2024, and post-quantum cryptography will be required to secure all sensitive information in the years to come shortly after, e.g., in protocols such as TLS, SSH, FIDO and other systems. Additionally, NIST have announced a new call for quantum secure digital signature algorithms.

The goal of this project is to conduct research on post-quantum authentication protocols and improve upon the frameworks used today when it comes to long-term security.

The postdoc will be part of the NTNU Applied Cryptology Lab, a multidisciplinary research group consisting of members from the Department of Mathematical Sciences and the Department of Information Security and Communication Technology.

A list of possible, but not limited, research topics for the postdoctoral position are:

Post-quantum cryptography

Key-exchange

Digital signatures

Zero-knowledge proofs

Multi-party computation

Homomorphic encryption

Provable security

Your main supervisor will be Associate Professor Tjerand Silde at the Department of Information Security and Communication Technology.

Closing date for applications:

Contact: Tjerand Silde (tjerand.silde@ntnu.no)

More information: https://www.jobbnorge.no/en/available-jobs/job/231938/postdoctoral-fellow-in-cryptography-focusing-on-post-quantum-authentication-protocols

In a fast changing world, it takes pioneering spirit to create trustworthy technology. We enable secure connectivity and payment solutions for billions of people around the globe. At Giesecke+Devrient, you will play a key role in realizing the digital transformation.

Giesecke+Devrient is looking for a Cryptography Engineer (m/f/d) for its Cryptology department at its Munich Headquarters as soon as possible

Job Description:

• Secure implementation of cryptographic algorithms and security relevant OS components for smart cards in assembler
• Optimization regarding run time and memory consumption
• Design and implementation of countermeasures to defend against hardware related attacks against smart cards
• Analysis of the results of side-channel attacks and derivation of effective countermeasures

Your Profile:

• Background in mathematics, computer science or electronic engineering
• Ideally PhD in cryptography or 3+ years experience in cryptography or related area
• Programming skills in assembler for embedded microcontrollers
• Ideally experience in embedded security and side-channel-attacks

Your Benefits:

• High level of responsibility and exciting projects
• Working in an international security technology company
• Very flexible working hours and home office possibilities
• Wide range of training and further education opportunities
• Attractive family benefits such as a summer holiday camp for children
• Other benefits such as an own sports club and a canteen subsidized by the employer

We are looking forward to receiving your application!

https://careers.gi-de.com/job/Munich-Kryptologen-%28mfd%29-81677/723297801/

Closing date for applications:

Contact: Dr. Harald Vater (Harald.Vater (at) gi-de.com)

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.