International Association
for Cryptologic Research

In SAC’14, Biham and Carmeli presented a novel attack on DES, involving a variation of Partitioning Cryptanalysis. This was further extended in ToSC’18 by Biham and Perle into the Conditional Linear Cryptanalysis in the context of Feistel ciphers. In this work, we formalize this cryptanalytic technique for block ciphers in general and derive several properties. This conditional approximation is then used to approximate the inv : GF(2^8) → GF(2^8) : x → x^254 function which forms the only source of non-linearity in the AES. By extending the approximation to encompass the full AES round function, a linear distinguisher for four-round AES in the known-plaintext model is constructed; the existence of which is often understood to be impossible. We furthermore demonstrate a key-recovery attack capable of extracting 32 bits of information in 4-round AES using 2^125.62 data and time. In addition to suggesting a new approach to advancing the cryptanalysis of the AES, this result moreover demonstrates a caveat in the standard interpretation of the Wide Trail Strategy — the design framework underlying many SPN-based ciphers published in recent years.

In this paper, we observe that it is possible to solve partially-synchronous BFT and simultaneously achieves $O(n^2)$ worst-case communication, optimistically linear communication, a two-phase commit regime within a view, and optimistic responsiveness. Prior work falls short in achieving one or more of these properties, e.g., the most closely related work, HotStuff, requires a three-phase view while achieving all other properties. We demonstrate that these properties are achievable through a two-phase HotStuff variant named HotStuff-2.

The quest for two-phase HotStuff variants that achieve all the above desirable properties has been long, producing a series of results that are yet sub-optimal and, at the same time, are based on somewhat heavy hammers. HotStuff-2 demonstrates that none of these are necessary: HotStuff-2 is remarkably simple, adding no substantive complexity to the original HotStuff protocol.

The main takeaway is that two phases are enough for BFT after all.

Starting from the problem of $d$-Tensor Isomorphism ($d$-TI), we study the relation between various Code Equivalence problems in different metrics. In particular, we show a reduction from the sum-rank metric (CE${}_{sr}$) to the rank metric (CE${}_{rk}$). To obtain this result, we investigate reductions between tensor problems. We define the Monomial Isomorphism problem for $d$-tensors ($d$-TI${}^*$ ), where, given two $d$-tensors, we ask if there are $d-1$ invertible matrices and a monomial matrix sending one tensor into the other. We link this problem to the well-studied $d$-TI and the TI-completeness of $d$-TI${}^*$ is shown. Due to this result, we obtain a reduction from CE${}_{sr}$ to CE${}_{rk}$. In the literature, a similar result was known, but it needs an additional assumption on the automorphisms of matrix codes. Since many constructions based on the hardness of Code Equivalence problems are emerging in cryptography, we analyze how such reductions can be taken into account in the design of cryptosystems based on CE${}_{sr}$.

Registered encryption (Garg {\em et al.}, TCC'18) is an emerging paradigm that tackles the key-escrow problem associated with identity-based encryption by replacing the private-key generator with a much weaker entity known as the key curator. The key curator holds no secret information, and is responsible to: (i) update the master public key whenever a new user registers its own public key to the system; (ii) provide helper decryption keys to the users already in the system, in order to make them still able to decrypt. For practical purposes, tasks (i) and (ii) need to be efficient, in the sense that the size of the public parameters, of the master public key, and of the helper decryption keys, as well as the running time for key generation and user registration, and the number of updates, must be small.

In this paper, we generalize the notion of registered encryption to the setting of functional encryption (FE). Our contributions are twofold: On the one hand, we show that registered FE exists assuming indistinguishability obfuscation and somewhere statistically binding hash functions. On the other hand, we show an efficient construction of registered FE for the special case of inner-product predicates, over asymmetric bilinear groups of prime order, with provable security in the generic group model.

Continuous Group Key Agreement (CGKA) lets a evolving group of clients agree on a sequence of group keys. An important application of CGKA is scalable asynchronous end-to-end (E2E) encrypted group messaging.

A major problem preventing the use of CGKA over unreliable infrastructure are so-called forks. A fork occurs when group members have diverging views of the group's history (and thus its current state); e.g. due to network or server failures. Once communication channels are restored, members resolve a fork by agreeing on the state of the group again. Today's CGKA protocols make fork resolution challenging, as natural resolution strategies seem to conflict with the way the protocols enforce group state agreement and forward secrecy. Meanwhile, secure group messaging protocols which do support fork resolution do not scale nearly as well as CGKA does.

In this work, we pave the way to practical scalable E2E messaging over unreliable infrastructure. To that end, we generalize CGKA to Fork Resilient-CGKA which allows clients to process significantly more types of out-of-order network traffic. This is important for many natural fork resolution procedures as they are based, in part, on replaying missed traffic. Next, we give two FR-CGKA constructions: a practical one based on the CGKA underlying the MLS messaging standard and an optimally secure one (albeit with only theoretical efficiency). To further assist with fork resolution, we introduce a simple new abstraction to describe a client's local protocol state. The abstraction describes all and only the information relevant to natural fork resolution, making it easier for higher-level fork resolution procedures to work with and reason about. We define a black-box extension of an FR-CGKA which maintains such a description of a client's internal state. Finally, as a proof of concept, we give a basic fork resolution protocol.

Given two KZG-committed polynomials $f(X),g(X)\in \mathbb{F}_{

The goal of a covert learning algorithm is to learn a function $f$ by querying it, while ensuring that an adversary, who sees all queries and their responses, is unable to (efficiently) learn any more about $f$ than they could learn from random input-output pairs. We focus on a relaxation that we call local covertness, in which queries are distributed across $k$ servers and we only limit what is learnable by $k - 1$ colluding servers.

For any constant $k$, we give a locally covert algorithm for efficiently learning any Fourier-sparse function (technically, our notion of learning is improper, agnostic, and with respect to the uniform distribution). Our result holds unconditionally and for computationally unbounded adversaries. Prior to our work, such an algorithm was known only for the special case of $O(\log n)$-juntas, and only with $k = 2$ servers, Ishai et al. (Crypto 2019).

Our main technical observation is that the original Goldreich-Levin algorithm only utilizes i.i.d. pairs of correlated queries, where each half of every pair is uniformly random. We give a simple generalization of this algorithm in which pairs are replaced by $k$-tuples in which any $k - 1$ components are jointly uniform. The cost of this generalization is that the number of queries needed grows exponentially with $k$.

NIST selected the A SCON family of cryptographic primitives for standardization in February 2023 as the final step in the Lightweight Cryptography Competition. The ASCON submission to the competition provided Authenticated Encryption with Associated Data (AEAD), hashing, and Extensible Output Function (XOF) modes. Real world cryptography systems often need more than packet encryption and simple hashing. Keyed message authentication, key derivation, cryptographically secure pseudo-random number generation (CSPRNG), password hashing, and encryption of sensitive values in memory are also important. This paper defines additional modes that can be deployed on top of ASCON based on proven designs from the literature.

The present article provides a novel hash function $\mathcal{H}$ to any elliptic curve of $j$-invariant $\neq 0, 1728$ over a finite field $\mathbb{F}_{\!q}$ of large characteristic. The unique bottleneck of $\mathcal{H}$ consists in extracting a square root in $\mathbb{F}_{\!q}$ as well as for most hash functions. However, $\mathcal{H}$ is designed in such a way that the root can be found by (Cipolla-Lehmer-)Müller's algorithm in constant time. Violation of this security condition is known to be the only obstacle to applying the given algorithm in the cryptographic context. When the field $\mathbb{F}_{\!q}$ is highly $2$-adic and $q \equiv 1 \ (\mathrm{mod} \ 3)$, the new batching technique is the state-of-the-art hashing solution except for some sporadic curves. Indeed, Müller's algorithm costs $\approx 2\log_2(q)$ multiplications in $\mathbb{F}_{\!q}$. In turn, (constant-time) Tonelli-Shanks's square root algorithm has asymptotic complexity $O(\log(q) + \nu^2)$, where $\nu$ is the $2$-adicity of $\mathbb{F}_{\!q}$. As an example, Müller's algorithm needs $\approx 4561$ fewer multiplications in the field $\mathbb{F}_{\!q}$ (whose $\nu = 96$) of the standardized curve NIST P-224. In other words, there is an acceleration of about $11$ times.

An important tool that has contributed to collision search on Keccak/SHA3 is the Target Difference Algorithm (TDA) and its inter- nal differential counterpart Target Internal Difference Algorithm (TIDA), which were introduced by Dinur et al. in separate works in FSE 2012 and 2013 respectively. These algorithms provide an ingenious way of extend- ing the differential trails by one round and exploiting the affine subspaces generated due to the low algebraic degree of the Keccak S-box. The cur- rent work introduces TIDAL, which can extend TIDA by one more round capitalizing on linearization techniques introduced by Guo et al. in JoC. This approach requires increment consistency checks, which is also im- proved in this work. The TIDAL strategy, in conjunction with a determin- istic internal differential trail, has been applied to Keccak variants up to 400-bit state-size and leads to practical collision attacks for most of them up to 5 rounds. In particular collisions have been confirmed for 4-round Keccak[136, 64] with a complexity of 220 and on 6-round of Keccak[84,16] with a complexity of 25 . Further, this work completely characterizes all collision attacks on state-reduced variants, showcasing that TIDAL covers most space up to 5 rounds. As state and round-reduced Keccak variants are used to realize the internal states of many crypto primitives, the re- sults presented here generate a significant impact. Finally, it shows new directions for the long-standing problem of state-reduced variants being difficult to be attacked.

Blind signatures allow a signer to issue signatures on messages chosen by the signature recipient. The main property is that the recipient's message is hidden from the signer. There are many applications, including Chaum's e-cash system and Privacy Pass, where no special distribution of the signed message is required, and the message can be random. Interestingly, existing notions do not consider this practical use case separately.

In this paper, we show that constraining the recipient's choice over the message distribution spawns a surprising new primitive that improves the well-established state-of-the-art. We formalize this concept by introducing the notion of non-interactive blind signatures (${\sf NIBS}$). Informally, the signer can create a presignature with a specific recipient in mind, identifiable via a public key. The recipient can use her secret key to finalize it and receive a blind signature on a random message determined by the finalization process. The key idea is that online interaction between the signer and recipient is unnecessary. We show an efficient instantiation of ${\sf NIBS}$ in the random oracle model from signatures on equivalence classes.

The exciting part is that, in this case, for the recipient's public key, we can use preexisting keys for Schnorr, ECDSA signatures, El-Gamal encryption scheme, or even the Diffie-Hellman key exchange. Reusing preexisting public keys allows us to distribute anonymous tokens similarly to cryptocurrency airdropping. Additional contributions include tagged non-interactive blind signatures (${\sf TNIBS}$) and their efficient instantiation. A generic construction in the random oracle or common reference string model based on verifiable random functions, standard signatures, and non-interactive proof systems.

We propose and analyze a simple strategy for constructing 1-key constrained pseudorandom functions (CPRFs) from homomorphic secret sharing. In the process, we obtain the following contributions. First, we identify desirable properties for the underlying HSS scheme for our strategy to work. Second, we show that (most) recent existing HSS schemes satisfy these properties, leading to instantiations of CPRFs for various constraints and from various assumptions. Notably, we obtain the first (1-key selectively secure, private) CPRFs for inner-product and (1-key selectively secure) CPRFs for NC 1 from the DCR assumption, and more. Lastly, we revisit two applications of HSS, equipped with these additional properties, to secure computation: we obtain secure computation in the silent preprocessing model with one party being able to precompute its whole preprocessing material before even knowing the other party, and we construct one-sided statistically secure computation with sublinear communication for restricted forms of computation.

The Digital Markets Act (DMA) is a nascent European Union regulation adopted in May 2022. One of its most controversial provisions is a requirement that so-called “gatekeepers” offering end-to-end encrypted messaging apps, such as WhatsApp, implement “interoperability” with other messaging apps: in essence, encrypted messaging across service providers. This requirement represents a fundamental shift in the design assumptions of existing encrypted messaging systems, most of which are designed to be centralized. Technologists have not really begun thinking about the myriad security, privacy, and functionality questions raised by the interoperability requirement; given that the DMA’s interoperability mandate may take effect as soon as mid-2024, it is critical for researchers to begin understanding the challenges and offering solutions.

In this paper, we take an initial step in this direction. We break down the DMA’s effects on the design of encrypted messaging systems into three main areas: identity, or how to resolve identities across service providers; protocols, or how to establish a secure connection between clients on different platforms; and abuse prevention, or how service providers can detect and take action against users engaging in abuse or spam. For each area, we identify key security and privacy requirements, summarize existing proposals, and examine whether proposals meet our security and privacy requirements. Finally, we propose our own design for an interoperable encrypted messaging system, and point out open problems.

The Restricted Syndrome Decoding Problem (R-SDP) cor- responds to the Syndrome Decoding Problem (SDP) with the additional constraint that entries of the solution vector must live in a desired sub- set of a finite field. In this paper we study how this problem can be applied to the construction of signatures derived from Zero-Knowledge (ZK) proofs. First, we show that R-SDP appears to be well suited for this type of applications: almost all ZK protocols relying on SDP can be modified to use R-SDP, with important reductions in the communication cost. Then, we describe how R-SDP can be further specialized, so that solutions can be represented with a number of bits that is slightly larger than the security parameter (which clearly provides an ultimate lower bound), thus enabling the design of ZK protocols with tighter and rather competitive parameters. Finally, we show that existing ZK protocols can greatly benefit from the use of R-SDP, achieving signature sizes in the order of 7 kB, which are smaller than those of several other schemes ob- tained from ZK protocols. For instance, this beats all schemes based on the Permuted Kernel Problem (PKP), almost all schemes based on SDP and several schemes based on rank metric problems.

We present Origami verifiable delay function, build from the MinRoot hash and our dedicated plonk proof system that utilizes a tai- lored custom gate and a folding scheme. MinRoot VDF is the leading candidate for Ethereum adoption. For N iterations of MinRoot hash func- tion, the overall cost of Origami is N +o(N ) group operations; improving the previous best known result of 6N from a Nova based solution. The proof size is 128k + 224 bytes if we fold the proofs for k times; and may be further reduce to around 960 bytes, regardless of k, via a standard recursive prover.

Randomness cannot be compressed, hence expanded randomness is ‘contaminated randomness’ where hidden pattern is used. Current cryptography uses little randomness (the key) to generate large randomness (the ciphertext). The pattern used for this expansion is subject to cryptanalysis. By contrast, Vernam and the new breed of Trans-Vernam ciphers project security with sufficient supply of genuine randomness. Having no hidden pattern in their process, they expose no vulnerability to cryptanalysis, other than brute force, the efficacy of which, is well gauged by using enough randomness to brute-force through. Unlike the original genuine randomness cipher (the Vernam cipher; US patent: 1,310,719), the new breed of Trans-Vernam ciphers (US patents: 10,541,802, 10,911,215, 11,159,317 to name a few) projects security with shared randomness (between transmitter and recipient) as well as with unilateral randomness determined ad hoc by the transmitter, thereby controlling the vulnerability of the transmitted message, including eliminating it all together, rising to Vernam grade. The new Trans-Vernam ciphers exploit new technologies for generating high-grade randomness, storing it and communicating it in large quantities. Their security is mathematically established and barring faulty implementation these ciphers are unbreakable. We are looking at a flat cyberspace, no more hierarchy based on math skills: Vernam grade security delivered through modern Trans-Vernam ciphers. Robust privacy of communication will be claimed by all – for good and for ill; law-enforcement and national security will have to adjust. It's a new cryptography, and a new society.

Homomorphic secret sharing (HSS) is a form of secret sharing that supports the local evaluation of functions on the shares, with applications to multi-server private information retrieval, secure computation, and more. Insisting on additive reconstruction, all known instantiations of HSS from "Learning with Error (LWE)"-type assumptions either have to rely on LWE with superpolynomial modulus, come with non-negligible error probability, and/or have to perform expensive ciphertext multiplications, resulting in bad concrete efficiency.

In this work, we present a new 2-party local share conversion procedure, which allows to locally convert noise encoded shares to non-noise plaintext shares such that the parties can detect whenever a (potential) error occurs and in that case resort to an alternative conversion procedure. Building on this technique, we present the first HSS for branching programs from (Ring-)LWE with polynomial input share size which can make use of the efficient multiplication procedure of Boyle et al.~(Eurocrypt 2019) and has no correctness error. Our construction comes at the cost of a -- on expectation -- slightly increased output share size (which is insignificant compared to the input share size) and a more involved reconstruction procedure. More concretely, we show that in the setting of 2-server private counting queries we can choose ciphertext sizes of only a quarter of the size of the scheme of Boyle et al. at essentially no extra cost.

Description We are seeking applicants for fully funded Ph.D. positions at Université de Montréal, the birthplace of quantum cryptography. The position is funded as part of the QUébec Ontario consoRtium on quantUM protocols (QUORUM). As a member of of the Consortium, candidates will have the opportunity to collaborate with Canada's foremost experts in cryptography and quantum information. Candidates will have the opportunity to undertake high-quality research in one of the following topics:

• New cryptographic protocols based on uniquely quantum phenomena
• Security of classical cryptography against quantum adversaries
• Cryptography based on the hardness of keeping qubits in quantum superposition
• Quantum zero-knowledge proof systems
• Quantum multiparty secure computation
• Quantum money

Requirements The ideal applicant will have a strong background in theoretical computer science and mathematics, knowledge of cryptography and/or quantum information, and strong written and oral communication skills.

Information on the Ph.D. program can be found here: https://diro.umontreal.ca/english/programs/graduate-programs/phd-in-computer-science/

Closing date for applications:

Contact: Philippe Lamontagne (philippe.lamontagne.1@umontreal.ca)

Job Responsibilities: 1. Focus on the commercialization of cryptographic public key zero-knowledge proofs in the blockchain field. 2. Participate in the theoretical research and design implementation of various rollups of the blockchain cutting-edge technology layer2. 3. Research on key blockchain technologies such as interactive verifiable computing and zero-knowledge proof. 4. Research and design the landing application of the combination of blockchain and zero-knowledge proof technology. 5. It is possible to explore future research extensions of cryptography public key zero-knowledge proofs in various fields of new infrastructure in a forward-looking manner. job requirements: 1. Master degree or above in cryptography, mathematics, computer and other related majors. 2. In the later stage, you can master one of the Rust mainstream blockchain system development languages, and you can carry out self-engineering. 3. Familiar with the principles and codes of common public key algorithms such as cryptography rsa, ecdsa, and ecdh, and master the use of cryptographic algorithms and open source libraries. bonus: 1. Master the design principles of blockchain technology, be familiar with a common blockchain open source project, and have actual blockchain implementation scenarios and implementation experience are preferred. 2. Researchers with zero-knowledge proof, homomorphic encryption, ring signature, aggregate signature, and threshold signature are preferred. 3. Researchers with various cryptography technologies in the blockchain are preferred.

Closing date for applications:

Contact: judith.li@protocol.ai - please send CV's to this email

More information: https://github.com/ipfs-force-community

The School of Engineering, Physical and Mathematical Sciences (EPMS) at Royal Holloway, University of London comprises the Departments of Electronic Engineering, Computer Science, Information Security, Mathematics and Physics. We are pleased to announce that the School is embarking on an ambitious period of expansion in data science, artificial intelligence, computing, information security, digital engineering and physical science and, as part of this expansion, applications are invited for three Lectureships within the Department of Information Security.

The Department of Information Security has a record of outstanding research and hosts established research groups in Systems and Software Security, Smart Card and Internet of Things Security, Cryptography, Interdisciplinary Security, and Ethnography.

For one of the posts, we are looking for applicants with interests that would support our new Media Broadcasting Security Centre (MBSC). For the other two we welcome applications from a broad range of areas related to information security, especially those with expertise and experience in software and systems security and applications of AI in security. Applicants should either have, or have the potential for producing, high quality publications and attracting significant research funding. Applicants will have a track record demonstrated excellence, or will show the potential for excellence, in delivering undergraduate and postgraduate teaching and the supervision of both undergraduate and postgraduate students. The post holder will be expected to contribute strongly to the development of research impact, and the successful applicant will have, or have the potential to have, a strong track record in this area.

The post is based in Egham, Surrey where the College is situated in a beautiful, leafy campus near to Windsor Great Park and within commuting distance from London. There will be also the opportunity to develop and deliver postgraduate programmes at our Central London campus, located in Bloomsbury.

Closing date for applications:

Contact: For an informal discussion about the post, please contact Professor Chris Mitchell (c.mitchell@rhul.ac.uk).

More information: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0323-132