International Association
for Cryptologic Research

We extend the known pseudorandomness of Ring-LWE to be based on lattices that do not correspond to any ideal of any order in the underlying number field. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the additional algebraic structure of ideals of Dedekind domains leaves open the possibility that such ideal lattices are not as hard as general lattices.

In this work we show that hardness of $q$-Ring-LWE can be based on worst-case hardness of ideal lattices in arbitrary orders $O$, as long as the order $O$ satisfies the property that $\frac{1}{m}\cdot O$ contains the ring of integers, for some $m$ co-prime to $q$. Further, the hard lattice problems need not be given the order $O$ itself as input. The reduction requires that the noise be a factor $m$ more than the original Ring-LWE reduction. We also show that for the power-of-two cyclotomic number fields, there exist orders with $m=4$ such that non-trivial ideals of the order, which are not contained in the conductor, are non-invertible.

Another reduction shows that hardness of $q$-Ring-LWE can be based on worst-case hardness of lattices that correspond to sum of ideal-lattices in arbitrary and different orders in the number field, as long as the (set of) orders $\{O_i\}$ satisfy the property that $\frac{1}{m}\cdot O_i$ contains the ring of integers, for some $m$ co-prime to $q$. We also show that for the power-of-two cyclotomic number fields, there exist orders $O_1, O_2$ with $m=8$ such that there are ideals $I_1, I_2$ of $O_1, O_2$ resp. with $I_1+ I_2$ not an ideal of any order in the number field.

There appears to be a widespread belief that some processes of selecting cryptosystems are less risky than other processes. As a case study of quantifying the difference in risks, this paper compares the currently-known-failure rates of three large groups of cryptosystems: (1) the round-1 submissions to the NIST Post-Quantum Cryptography Standardization Project, (2) the round-1 submissions not broken by the end of round 1, and (3) the round-1 submissions selected by NIST for round 2 of the same project. These groups of cryptosystems turn out to have currently-known-failure rates that are strikingly high, and that include statistically significant differences across the groups, not matching the pattern of differences that one might expect. Readers are cautioned that the actual failure rates could be much higher than the currently-known-failure rates.

Panny [3] described how to forge the “tropical signatures” proposed by Chen, Grigoriev and Shpilrain [1]. (These signatures are loosely related to the NP-complete problem of factoring tropical polynomials). We describe more methods to forge these tropical signatures. We also describe some patches that thwart all but one of these forgery methods (which we summarize as re-hashing an honest signature).

A proof of sequential work (PoSW) scheme allows the prover to convince a verifier that it computed a certain number of computational steps sequentially. Very recently, graph-labeling PoSW schemes, found applications in light-client blockchain protocols, most notably bootstrapping. A bootstrapping protocol allows a light client, with minimal information about the blockchain, to hold a commitment to its stable prefix. An incremental PoSW (iPoSW) scheme allows the prover to non-trivially increment proofs: given $\chi,\pi_1$ and integers $N_1,N_2$ such that $\pi_1$ is a valid proof for $N_1$, it generates a valid proof $\pi$ for $N_1+N_2$. In this work, we construct an iPoSW scheme based on the skiplist-based PoSW scheme of Abusalah et al. and prove its security in the random oracle model by employing the powerful on-the-fly sampling technique of Döttling et al. Moreover, unlike the iPoSW scheme of Döttling et al., ours is the first iPoSW scheme which is suitable for constructing incremental non-interactive arguments of chain knowledge (SNACK) schemes, which are at the heart of space and time efficient blockchain light-client protocols. In particular, our scheme works for general weight distributions, which we characterize as incrementally sampleable distributions. Our general treatment recovers the distribution underlying the scheme of Döttling et al. as well as the distribution underlying SNACK-enabled bootstrapping application as special cases. In realizing our general construction, we develop a new on-the-fly sampling technique.

Vehicle Ad Hoc Networks (VANETs) play a pivotal role in intelligent transportation systems, offering dynamic communication between vehicles, Road Side Units (RSUs), and the internet. Given the open-access nature of VANETs and the associated threats, such as impersonation and privacy violations, ensuring the security of these communications is of utmost importance. This paper presents the Identity-based Cluster Authentication and Key Exchange (ID-CAKE) scheme, a new approach to address security challenges in VANETs. The ID-CAKE scheme integrates the Cluster Consensus Identity-based Identification (CCIBI) with Zero-Knowledge (ZK) proofs and the Identity-based Multireceiver Key Exchange Mechanism (ID-mKEM) signature scheme. This integration provides robust authorization via CCIBI, while ID-mKEM signatures ensure message integrity, and guarantee both non-repudiation and unforgeability through mKEM for message broadcasting. The scheme employs a novel three-party ZK proof for batch verification using mKEM, which significantly reduces computational burdens. Our scheme also ensures anonymity and unlinkability by introducing pseudo-identities to all users in the cluster. The rigorous security proofs provided confirm the resilience of the ID-CAKE scheme against potential attacks, adhering to the different scenarios, against the hardness of the elliptic curve computational Diffie-Hellman under the random oracle model. The ID-CAKE scheme establishes a robust security framework for VANETs, and its introduction highlights potential pathways for future exploration in the realm of VANET security.

In spite of being a popular technique for designing block ciphers, Lai-Massey networks have received considerably less attention from a security analysis point-of-view than Feistel networks and Substitution-Permutation networks. In this paper we study the beyond-birthday-bound (BBB) security of Lai-Massey networks with independent random round functions against chosen-plaintext adversaries. Concretely, we show that five rounds are necessary and sufficient to achieve BBB security.

QARMAv2 is a general-purpose and hardware-oriented family of lightweight tweakable block ciphers (TBCs) introduced in ToSC 2023. QARMAv2, as a redesign of QARMA with a longer tweak and tighter security margins, is also designed to be suitable for cryptographic memory protection and control flow integrity. The designers of QARMAv2 provided a relatively comprehensive security analysis in the design specification, e.g., some bounds for the number of attacked rounds in differential and boomerang analysis, together with some concrete impossible differential, zero-correlation, and integral distinguishers. As one of the first third-party cryptanalysis of QARMAv2, Hadipour et al. significantly improved the integral distinguishers of QARMAv2 and provided the longest concrete distinguishers of QARMAv2 up to now. However, they provided no key recovery attack based on their distinguishers.

This paper delves into the cryptanalysis of QARMAv2 to enhance our understanding of its security. Given that the integral distinguishers of QARMAv2 are the longest concrete distinguishers for this cipher so far, we focus on integral attack. To this end, we first further improve the automatic tool introduced by Hadipour et al., for finding integral distinguishers of TBCs following the TWEAKEY framework. This new tool exploits the MixColumns property of QARMAv2 to find integral distinguishers more suitable for key recovery attacks. Then, we combine several techniques for integral key recovery attacks, e.g., Meet-in-the-middle and partial-sum techniques to build a fine-grained integral key recovery attack on QARMAv2. Notably, we demonstrate how to leverage the low data complexity of the integral distinguishers of QARMAv2 to reduce the memory complexity of the meet-in-the-middle technique. As a result, we managed to propose the first concrete key recovery attacks on reduced-round versions of QARMAv2 by attacking 13 rounds of QARMAv2-64-128 with a single tweak block, 14 rounds of QARMAv2-64-128 with two independent tweak blocks, and 16 rounds of QARMAv2-128-256 with two independent tweak blocks. Our attacks do not compromise the claimed security of QARMAv2, but they shed more light on the cryptanalysis of this cipher.

The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta complexity problems relate to one another, and to the task of function inversion.

In this note, we present resolutions to some of these questions with respect to the \emph{black-box} analog of these problems. In more detail, let $MK^t_MP[s]$ denote the language consisting of strings $x$ with $K_{M}^t(x) < s(|x|)$, where $K_M^t(x)$ denotes the $t$-bounded Kolmogorov complexity of $x$ with $M$ as the underlying (Universal) Turing machine, and let $search-MK^t_MP[s]$ denote the search version of the same problem.

We show that if there for every Universal Turing machine $U$ there exists a $2^{\alpha n}poly(n)$-size $U$-oracle aided circuit deciding $MK^t_UP [n-O(1)]$, then for every function $s$, and every not necessarily universal Turing machine $M$, there exists a $2^{\alpha s(n)}poly(n)$ size $M$-oracle aided circuit solving $search-MK^t_MP[s(n)]$; this in turn yields circuits of roughly the same size for both the Minimum Circuit Size Problem (MCSP), and the function inversion problem, as they can be thought of as instantiating $MK^t_MP$ with particular choices of (a non universal) TMs $M$ (the circuit emulator for the case of MCSP, and the function evaluation in the case of function inversion).

As a corollary of independent interest, we get that the complexity of black-box function inversion is (roughly) the same as the complexity of black-box deciding $MK^t_UP[n-O(1)]$ for any universal TM $U$; that is, also in the worst-case regime, black-box function inversion is ``equivalent" to black-box deciding $MKtUP$.

An important criteria to assert the security of a cryptographic primitive is its resistance against differential cryptanalysis. For word-oriented primitives, a common technique to determine the number of rounds required to ensure the immunity against differential distinguishers is to consider truncated differential characteristics and to count the number of active S-boxes. Doing so allows one to provide an upper bound on the probability of the best differential characteristic with a reduced computational cost. However, in order to design very efficient primitives, it might be needed to evaluate the probability more accurately. This is usually done in a second step, during which one tries to instantiate truncated differential characteristics with actual values and computes its corresponding probability. This step is usually done either with ad-hoc algorithms or with CP, SAT or MILP models that are solved by generic solvers. In this paper, we present a generic tool for automatically generating these models to handle all word-oriented ciphers. Furthermore the running times to solve these models are very competitive with all the previous dedicated approaches.

Dynamic vector commitments that enable local updates of opening proofs have applications ranging from verifiable databases with membership changes to stateless clients on blockchains. In these applications, each user maintains a relevant subset of the committed messages and the corresponding opening proofs with the goal of ensuring a succinct global state. When the messages are updated, users are given some global update information and update their opening proofs to match the new vector commitment. We investigate the relation between the size of the update information and the runtime complexity needed to update an individual opening proof. Existing vector commitment schemes require that either the information size or the runtime scale linearly in the number $k$ of updated state elements. We construct a vector commitment scheme that asymptotically achieves both length and runtime that is sublinear in $k$, namely $k^\nu$ and $k^{1-\nu}$ for any $\nu \in (0,1)$. We prove an information-theoretic lower bound on the relation between the update information size and runtime complexity that shows the asymptotic optimality of our scheme. For $\nu = 1/2$, our constructions outperform Verkle commitments by about a factor of $2$ in terms of both the update information size and runtime, but makes use of larger public parameters.

In May 2020, Zoom Video Communications, Inc. (Zoom) announced a multi-step plan to comprehensively support end-to-end encrypted (E2EE) group video calls and subsequently rolled out basic E2EE support to customers in October 2020. In this work we provide the first formal security analysis of Zoom's E2EE protocol, and also lay foundation to the general problem of E2EE group video communication.

We observe that the vast security literature analyzing asynchronous messaging does not translate well to synchronous video calls. Namely, while strong forms of forward secrecy and post compromise security are less important for (typically short-lived) video calls, various liveness properties become crucial. For example, mandating that participants quickly learn of updates to the meeting roster and key, media streams being displayed are recent, and banned participants promptly lose any access to the meeting. Our main results are as follows:

1. Propose a new notion of leader-based continuous group key agreement with liveness, which accurately captures the E2EE properties specific to the synchronous communication scenario. 2. Prove security of the core of Zoom's E2EE meetings protocol in the above well-defined model. 3. Propose ways to strengthen Zoom's liveness properties by simple modifications to the original protocol, which subsequently influenced updates implemented in production.

Motivated by the violation of two fundamental assumptions in secure communication - receiver-privacy and sender-freedom - by a certain entity referred to as ``the dictator'', Persiano et al. introduced the concept of Anamorphic Encryption (AME) for public key cryptosystems (EUROCRYPT 2022). Specifically, they presented receiver/sender-AME, directly tailored to scenarios where receiver privacy and sender freedom assumptions are compromised, respectively. In receiver-AME, entities share a double key to communicate in anamorphic fashion, raising concerns about the online distribution of the double key without detection by the dictator. The sender-AME with no shared secret is a potential candidate for key distribution. However, the only such known schemes (i.e., LWE and Dual LWE encryptions) suffer from an intrinsic limitation and cannot achieve reliable distribution.

Here, we reformulate the sender-AME, present the notion of $\ell$-sender-AME and formalize the properties of (strong) security and robustness. Robustness refers to guaranteed delivery of duplicate messages to the intended receiver, ensuring that decrypting normal ciphertexts in an anamorphic way or decrypting anamorphic ciphertexts with an incorrect duplicate secret key results in an explicit abort signal. We first present a simple construction for pseudo-random and robust public key encryption that shares the similar idea of public-key stegosystem by von Ahn and Hopper (EUROCRYPT 2004). Then, inspired by Chen et al.'s malicious algorithm-substitution attack (ASA) on key encapsulation mechanisms (KEM) (ASIACRYPT 2020), we give a generic construction for hybrid PKE with special KEM that encompasses well-known schemes, including ElGamal and Cramer-Shoup cryptosystems.

The constructions of $\ell$-sender-AME motivate us to explore the relations between AME, ASA on PKE, and public-key stegosystem. The results show that a strongly secure $\ell$-sender-AME is such a strong primitive that implies reformulated receiver-AME, public-key stegosystem, and generalized ASA on PKE. By expanding the scope of sender-anamorphic encryption and establishing its robustness, as well as exploring the connections among existing notions, we advance secure communication protocols under challenging conditions.

Event date: 25 May to 26 May 2024
Submission deadline: 16 February 2024
Notification: 30 March 2024

We are excited to announce an internship opportunity at Microsoft Research focused broadly around cryptography, mathematical modeling, and system design for online trust, safety, and reliability in the age of AI. Our interns will have the opportunity to work on real-world problems alongside other interns, researchers, and engineers.

We are looking for creative thinkers, doers, and problem solvers, who are unafraid to venture outside their comfort zone to find solutions to difficult and messy real-world problems. If you are unsure whether you have appropriate background and match this description, we highly recommend applying anyway!

Apply now at: https://jobs.careers.microsoft.com/global/en/job/1639824

Closing date for applications:

Contact: Kim Laine (kim.laine@microsoft.com)

There is an open call for a Postdoc position in the Cyber Security and Applied Cryptograhy research group at the Institute of Computer Science, University of St.Gallen, led by Prof. Katerina Mitrokotsa.

Our research interests are centered around information security and applied cryptography, with the larger goal of safeguarding communications and providing strong privacy guarantees. We are active in several areas, a subset of which include:

• Verifiable computation
• Secure, private and distributed aggregation
• Secure multi-party computation
• Privacy-preserving biometric authentication
• Anonymous credentials
• Distributed and privacy-preserving authentication

Candidates should have a strong background in applied cryptography and provable security, are able to work independently and also collaborate in a team. Applicants must hold a Ph.D., with contributions in the relevant research topics and have publications in good venues.

The starting date for the position is flexible and come with a very competitive salary. The selection process runs until the suitable candidate has been found. The University of St.Gallen conducts excellent research with international implications. The city of St.Gallen is located one hour from Zurich and offers a high quality of life.

Please apply by 10th December 2023 through the job portal (via link).

Closing date for applications:

Contact:
Please apply through the job portal (via link).

Eriane Breu (Administrative matters)
Prof. Katerina Mitrokotsa (Research related questions)

More information: https://jobs.unisg.ch/offene-stellen/postdoc-fellow-in-cryptography-information-security-m-f-d-m-w-d/831c6e8a-e191-48ec-92d5-320b2822a9ab

The candidate will be working on algorithmic and mathematical aspects of lattice-based or isogeny-based cryptography, in the context of ERC project AGATHA CRYPTY.
The candidate will be joining the Number Theory team of ENS de Lyon. They will benefit from the resources of AGATHA CRYPTY (travelling, equipment, organizing events, hiring interns...).
The candidate should hold a PhD degree in Mathematics or Computer Science. They should have a strong record related to any of the following research topics: number theory, computational number theory, lattice-based cryptography, isogeny-based cryptography.

Closing date for applications:

Contact: Benjamin Wesolowski. Candidates should apply at: https://emploi.cnrs.fr/Offres/CDD/UMR5669-BENWES-002/Default.aspx?lang=EN

More information: https://emploi.cnrs.fr/Offres/CDD/UMR5669-BENWES-002/Default.aspx?lang=EN

Teaching. The expected profile is a teacher-researcher capable of teaching the fundamentals of Computer Science (in the core curriculum of an engineering cycle in computer science), as well as specialized subjects close to his/her research themes (in the engineering cycle majors, in apprenticeship training, in the school's international Master's degree and/or Bachelor's degree in cybersecurity). The teaching load is approximately that of a university lecturer.

Research. We are recruiting to consolidate our teams and research areas in the following areas:

• Software and architecture security:
  • Detection of security attacks (learning);
  • Malware and reverse engineering;
  • Cryptography;
• Systems:
  • Operating systems and kernels;
  • Cloud computing and virtualization;
  • Embedded system.

The teacher-researcher's profile will fit into one of these three fields: mathematical computer science, fundamental computer science or applied computer science, a geeky and versatile profile being very welcome.

The "research" component is expected to account for around 45% of time, including participation in national and international research activities (review of articles, etc.). Research will be carried out within a local team and with external collaborators as appropriate. A dynamic approach to setting up and participating in collaborative projects and/or industrial contracts will be highly appreciated

Closing date for applications:

Contact: thierry.geraud@epita.fr

More information: https://www.lre.epita.fr/

With Carbyne Stack (https://carbynestack.io), Bosch is developing an open source cloud platform for computing on encrypted data using Secure Multi-party Computation (MPC). Potential use cases include Privacy-Preserving Machine Learning and Privacy-Preserving Data Analytics. For such large computations on big data, active secure MPC becomes quite expensive. Bosch Research is therefore trying to reduce the computational and communication costs of MPC by optimizing the underlying cryptographic primitives and protocols.

Thus, we are looking for a highly motivated PhD candidate with a strong background and/or interest in applied cryptography. The successful candidate will:

• become a part of the team and advance research on MPC
• develop novel approaches to improve the practical efficiency of actively secure MPC protocols
• design efficient MPC protocols for diverse use-cases
• integrate the results into our Cabyne Stack open source MPC platform
• publish and present the results in top-tier journals and at conferences

The candidates should meet the following requirements:

• Education: Hold an M.Sc. degree (or equivalent) with excellent grades in IT security, computer science, mathematics, or a related field
• Experience and Knowledge: Strong background in (applied) cryptography with a particular focus on cryptographic protocols/MPC, including security models and basic security proof techniques. Good software development/programming skills and the motivation to integrate scientific results into Carbyne Stack.
• Personality and Working Practice: Self-motivated and enthusiastic, independent, reliable, creative, and able to work in an international team with diverse background
• Language: Fluent English language skills

Please submit your application via: https://smrtr.io/hmG3C

Closing date for applications:

Contact: Informal inquiries can be made to Christoph Bösch (christoph.boesch (at) de.bosch.com). Formal applications must be submitted through: https://smrtr.io/hmG3C

We are looking for a bright and motivated PhD student to work in the topics of information security and cryptography.

The student is expected to work on topics that include security and privacy issues in authentication. More precisely, the student will be working on investigating efficient and privacy-preserving authentication that provides: i) provable security guarantees, and ii) rigorous privacy guarantees.

Key Responsibilities:

• Perform exciting and challenging research in the domain of information security and cryptography.
• Support and assist in teaching computer security and cryptography courses.

Profile:

• The PhD student is expected to have a MSc degree or equivalent, and strong background in cryptography, network security and mathematics.
• Experience in one or more domains such as cryptography, design of protocols, secure multi-party computation and differential privacy is beneficial.
• Excellent programming skills.
• Excellent written and verbal communication skills in English

The Chair of Cyber Security, https://cybersecurity.unisg.ch/, led by Prof. Katerina Mitrokotsa, is a part of the Institute of Computer Science (ICS) at the University of St.Gallen. Our research interests are centered around information security and applied cryptography, with the larger goal of safeguarding communications and providing strong privacy guarantees. We are currently active in multiple areas including the design of provably secure cryptographic protocols and cryptographic primitives that can be employed for reliable authentication, outsourcing computations in cloud-assisted settings, network security problems as well as secure and privacy-preserving machine learning. As a doctoral student you will be a part of the Doctoral School of Computer Science (DCS), https://dcs.unisg.ch.

The starting date for the position is flexible and come with a very competitive salary. The selection process runs until the suitable candidate has been found.

Please apply by 10th December 2023 through the job portal (via link).

Closing date for applications:

Contact:
Please apply through the job portal (via link).
Eriane Breu (Administrative matters)
Prof. Katerina Mitrokotsa (Research related questions)

More information: https://jobs.unisg.ch/offene-stellen/funded-phd-student-in-applied-cryptography-privacy-preserving-biometric-authentication-m-f-d-m-w-d/6ce1d454-47ca-4710-a9f2-33429243b4ac

Password-Authenticated Key Exchange (PAKE) allows two parties to establish a common high-entropy secret from a possibly low-entropy pre-shared secret such as a password. In this work, we provide the first PAKE protocol with subversion resilience in the framework of universal composability (UC), where the latter roughly means that UC security still holds even if one of the two parties is malicious and the honest party's code has been subverted (in an undetectable manner).

We achieve this result by sanitizing the PAKE protocol from oblivious transfer (OT) due to Canetti et al. (PKC'12) via cryptographic reverse firewalls in the UC framework (Chakraborty et al., EUROCRYPT'22). This requires new techniques, which help us uncover new cryptographic primitives with sanitation-friendly properties along the way (such as OT, dual-mode cryptosystems, and signature schemes).

As an additional contribution, we delve deeper in the backbone of communication required in the subversion-resilient UC framework, extending it to the unauthenticated setting, in line with the work of Barak et al. (CRYPTO'05).