International Association
for Cryptologic Research

The analytical perspective employed in the study classifies the theoretical research on dependencies in differential characteristics into two types. By categorising all dependence representations from the value restrictions and the theory of quasidifferential trails, we pinpoint a specific set of nonlinear constraints, which we term linearised nonlinear constraints. We aim to establish a method that utilises value restrictions to identify these constraints, as the current method based on value restrictions is found to be lacking in this area. A linearisation method for searching linearised nonlinear constraints for a given differential characteristic is developed by leveraging linear dependencies between inputs and outputs of active S-boxes. Then, we propose a three-stage evaluation approach to more accurately evaluate differential characteristics with linearised nonlinear constraints. Four differential characteristics of GIFT-64 are analysed using the three-stage evaluation approach, and the exact right key spaces and remaining probabilities are given. According to our results, the right key spaces of the four differential characteristics do not cover the entire key space, and the remaining probabilities are not equivalent to the stated probabilities. Concerning GIFT-128, we find six differential characteristics subject to linearised nonlinear constraints. Besides, inconsistencies are detected in the linear and linearised nonlinear constraints in the characteristics of two differentials employed to initiate the most effective differential attack on GIFT-128. Based on these results, we strongly advise reassessing the differential attacks that rely on these distinguishers. An additional advantage of using the linearisation method and the three-stage evaluation approach is their ability to identify linear and nonlinear constraints in ciphers that utilise the Generalised Feistel Network (GFN). It leads to the first instantiations of linear and nonlinear constraints in the GFN cipher WARP.

We're on a mission to solve the foundational scientific and engineering problems that stand in the way of mainstream blockchain adoption. We're starting by focusing on the areas of interoperability, scalability, and usability. But we can't conquer this frontier alone, we're therefore on the hunt for brilliant minds to join us. We're primarily seeking senior engineers to join our team, though we have exciting opportunities across other roles as well. View our open positions at https://commonprefix.com/careers

Closing date for applications:

Contact: Dimitris Lamprinos (careers@commonprefix.com)

More information: https://commonprefix.com

We seek to hire a full-time postdoctoral researcher in the area of security and privacy.

The University offers:

• A 2.5-year contract at an exciting international environment.
• Generous travel funds.
• Possibility to co-supervise PhD students.

Your role:

The successful candidate is expected to contribute to the PROVTOPIA project, which focuses on counteracting disinformation via Secure and Private Provenance Verification of Media Content. The candidate will work under the umbrella of the Crises research group (https://crises-deim.urv.cat/) and the direction of Dr. Rolando Trujillo. Candidates with experience in applied cryptography, threat modelling or formal verification are encouraged to apply.

Include in your application the following documents:

• Curriculum Vitae
• Research statement
• Contact information for 3 referees

Deadline for applications is 15 January 2025 . Early applications are highly encouraged, though, as they will be processed upon reception.

Closing date for applications:

Contact: Dr. Rolando Trujillo (rolando.trujillo@urv.cat)

More information: https://rolandotr.bitbucket.io/open-positions.html

Aalto University School of Electrical Engineering is hiring new faculty members. The ideal candidate will have expertise in fields, such as but not limited to, hardware-accelerated computing, heterogeneous architectures, compiler technologies and code generation, or the co-design of software and hardware systems. The application closes on 29.12.2024. For more information, see https://www.aalto.fi/en/open-positions/professor-computer-engineering.

Closing date for applications:

Contact: For additional information about the position, please contact Professor Riku Jäntti at riku.jantti at aalto.fi. For questions related to the recruitment process, HR Partner Hanna Koli at hanna.koli at aalto.fi.

More information: https://www.aalto.fi/en/open-positions/professor-computer-engineering

We introduce the notion of non-interactive zero-knowledge (NIZK) proofs with certified deletion. Our notion enables the recipient of a quantum NIZK proof for a (quantumly hard) NP statement to delete the proof and collapse it into a classical deletion certificate. Once this certificate is successfully validated, we require the recipient of the proof to lose their ability to find accepting inputs to NIZK verification.

We formally define this notion and build several candidate constructions from standard cryptographic assumptions. In particular, we propose a primary construction from classical NIZK for NP and one-way functions, albeit with two limitations: (i) deletion certificates are only privately verifiable, and (ii) both prover and verifier are required to be quantum algorithms. We resolve these hurdles in two extensions that assume the quantum hardness of the learning with errors problem. The first one achieves publicly verifiable certificates, and the second one requires merely classical communication between classical provers and quantum verifiers.

Non-Interactive Zero-Knowledge Arguments (NIZKs) are cryptographic protocols that enable a prover to demonstrate the validity of an $\mathsf{NP}$ statement to a verifier with a single message, without revealing any additional information. The soundness and zero-knowledge properties of a NIZK correspond to security against a malicious prover and a malicious verifier respectively. Statistical NIZKs (S-NIZKs) are a variant of NIZKs for which the zero-knowledge property is guaranteed to hold information-theoretically. Previous works have shown that S-NIZKs satisfying a weak version of soundness known as static soundness exist based on standard assumptions. However, the work of Pass (TCC 2013) showed that S-NIZKs with the stronger \emph{adaptive} soundness property are inherently challenging to obtain. The work proved that standard (black-box) proof techniques are insufficient to prove the security of an S-NIZK based on any standard (falsifiable) assumption. We extend this result to the setting where parties can perform quantum computations and communicate using quantum information, while the quantum security reduction is restricted to query the adversary classically. To this end, we adapt the well-known meta-reduction paradigm for showing impossibility results to the quantum setting. Additionally, we reinterpret our result using a new framework for studying quantum reductions, which we believe to be of independent interest.

The hardness of lattice problems offers one of the most promising security foundations for quantum-safe cryptography. Basic schemes for public key encryption and digital signatures are already close to standardization at NIST and several other standardization bodies, and the research frontier has moved on to building primitives with more advanced privacy features. At the core of many such primi- tives are zero-knowledge proofs. In recent years, zero-knowledge proofs for (and using) lattice relations have seen a dramatic jump in efficiency and they currently provide arguably the shortest, and most computationally efficient, quantum-safe proofs for many sce- narios. The main difficulty in using these proofs by non-experts (and experts!) is that they have a lot of moving parts and a lot of internal parameters depend on the particular instance that one is trying to prove. Our main contribution is a library for zero-knowledge and suc- cinct proofs which consists of efficient and flexible C code under- neath a simple-to-use Python interface. Users without any back- ground in lattice-based proofs should be able to specify the lattice relations and the norm bounds that they would like to prove and the library will automatically create a proof system, complete with the intrinsic parameters, using either the succinct proofs of LaBRADOR (Beullens and Seiler, Crypto 2023) or the linear-size, though smaller for certain application, proofs of Lyubashevsky et al. (Crypto 2022). The Python interface also allows for common operations used in lattice-based cryptography which will enable users to write and pro- totype their full protocols within the syntactically simple Python environment. We showcase some of the library’s usefulness by giving protocol implementations for blind signatures, anonymous credentials, the zero-knowledge proof needed in the recent Swoosh protocol (Gaj- land et al., Usenix 2024), proving knowledge of Kyber keys, and an aggregate signature scheme. Most of these are the most efficient, from a size, speed, and memory perspective, known quantum-safe instantiations.

This paper partly solves the open problem of tight trade-off of client storage and server time in the client preprocessing setting of private information retrieval (PIR). In the client preprocessing setting of PIR, the client is allowed to store some hints generated from the database in a preprocessing phase and use the hints to assist online queries. We construct a new single-server client preprocessing PIR scheme. For a database with $n$ entries of size $w$, our protocol uses $S=O((n/T) \cdot (\log n + w))$ bits of client storage and $T$ amortized server probes over $n/T$ queries, where $T$ is a tunable online time parameter. Our scheme matches (up to constant factors) a $ST = \Omega(nw)$ lower bound generalized from a recent work by Yeo (EUROCRYPT 2023) and a communication barrier generalized from Ishai, Shi, and Wichs (CRYPTO 2024).

From a technical standpoint, we present a novel organization of hints where each PIR query consumes a hint, and entries in the consumed hint are relocated to other hints. We then present a new data structure to track the hint relocations and use small-domain pseudorandom permutations to make the hint storage sublinear while maintaining efficient lookups in the hints.

We construct and implement an efficient post-quantum commutative cryptographic group action based on combining the SCALLOP framework for group actions from isogenies of oriented elliptic curves on one hand with the recent Clapoti method for polynomial-time evaluation of the CM group action on elliptic curves on the other. We take advantage of the very attractive performance of $(2^e, 2^e)$-isogenies between products of elliptic curves in the theta coordinate system. To successfully apply Clapoti in dimension $2$, it is required to resolve a particular quadratic diophantine norm equation, for which we employ a slight variant of the KLPT algorithm. Our work marks the first practical instantiation of the CM group action for which both the setup as well as the online phase can be computed in (heuristic) polynomial time.

We prove that Basefold(Crypto 2024) is secure in the $\textit{list decoding regime}$, within the double Johnson bound and with error probability $\frac{O(n)}{|F|}$. At the heart of this proof is a new, stronger statement for $\textit{correlated agreement}$, which roughly states that if a linear combination of vectors $\pi_L + r \pi_R$ agrees with a codeword at every element in $S \subset [n]$, then so do $\pi_L, \pi_R$. Our result is purely combinatorial and therefore extends to any finite field and any linear code. As such, it can be applied to any coding-based multilinear Polynomial Commitment Scheme to reduce its communication complexity.

We introduce Zero-Knowledge Location Privacy (ZKLP), enabling users to prove to third parties that they are within a specified geographical region while not disclosing their exact location. ZKLP supports varying levels of granularity, allowing for customization depending on the use case. To realize ZKLP, we introduce the first set of Zero-Knowledge Proof (ZKP) circuits that are fully compliant to the IEEE 754 standard for floating-point arithmetic. Our results demonstrate that our floating point circuits amortize efficiently, requiring only $64$ constraints per multiplication for $2^{15}$ single-precision floating-point multiplications. We utilize our floating point implementation to realize the ZKLP paradigm. In comparison to a baseline, we find that our optimized implementation has $15.9 \times$ less constraints utilizing single precision floating-point values, and $12.2 \times$ less constraints when utilizing double precision floating-point values. We demonstrate the practicability of ZKLP by building a protocol for privacy preserving peer-to-peer proximity testing - Alice can test if she is close to Bob by receiving a single message, without either party revealing any other information about their location. In such a configuration, Bob can create a proof of (non-)proximity in $0.26 s$, whereas Alice can verify her distance to about $470$ peers per second.

Lookups are a popular way to express repeated constraints in state-of-the art SNARKs. This is especially the case for zero-knowledge virtual machines (zkVMs), which produce succinct proofs of correct execution for programs expressed as bytecode according to a specific instruction set architecture (ISA). The Jolt zkVM (Arun, Setty & Thaler, Eurocrypt 2024) for RISC-V ISA employs Lasso (Setty, Thaler & Wahby, Eurocrypt 2024), an efficient lookup argument for massive structured tables, to prove correct execution of instructions. Internally, Lasso performs multiple lookups into smaller subtables, then combines the results.

We present an approach to formally verify Lasso-style lookup arguments against the semantics of instruction set architectures. We demonstrate our approach by formalizing and verifying all Jolt 32-bit instructions corresponding to the RISC-V base instruction set (RV32I) using the ACL2 theorem proving system. Our formal ACL2 model has undergone extensive validation against the Rust implementation of Jolt. Due to ACL2's bit-blasting, rewriting, and developer-friendly features, our formalization is highly automated.

Through formalization, we also discovered optimizations to the Jolt codebase, leading to improved efficiency without impacting correctness or soundness. In particular, we removed one unnecessary lookup each for four instructions, and reduced the sizes of three subtables by 87.5\%.

Pseudorandom codes are error-correcting codes with the property that no efficient adversary can distinguish encodings from uniformly random strings. They were recently introduced by Christ and Gunn [CRYPTO 2024] for the purpose of watermarking the outputs of randomized algorithms, such as generative AI models. Several constructions of pseudorandom codes have since been proposed, but none of them are robust to error channels that depend on previously seen codewords. This stronger kind of robustness is referred to as adaptive robustness, and it is important for meaningful applications to watermarking.

In this work, we show the following. - Adaptive robustness: We show that the pseudorandom codes of Christ and Gunn are adaptively robust, resolving a conjecture posed by Cohen, Hoover, and Schoenbach [S&P 2025]. Our proof involves several new ingredients, combining ideas from both cryptography and coding theory and taking hints from the analysis of Boolean functions. - Ideal security: We define an ideal pseudorandom code as one which is indistinguishable from the ideal functionality, capturing both the pseudorandomness and robustness properties in one simple definition. We show that any adaptively robust pseudorandom code for single-bit messages can be bootstrapped to build an ideal pseudorandom code with linear information rate, under no additional assumptions. - CCA security: In the setting where the encoding key is made public, we define a CCA-secure pseudorandom code in analogy with CCA-secure encryption. We show that any adaptively robust public-key pseudorandom code for single-bit messages can be used to build a CCA-secure pseudorandom code with linear information rate, in the random oracle model.

Together with the result of Christ and Gunn, it follows that there exist ideal pseudorandom codes assuming the $2^{O(\sqrt{n})}$-hardness of LPN. This extends to CCA security in the random oracle model. These results immediately imply stronger robustness guarantees for generative AI watermarking schemes, such as the practical quality-preserving image watermarks of Gunn, Zhao, and Song (2024).

In the digital age, the concept of consent for online actions executed by third parties is crucial for maintaining trust and security in third-party services. This work introduces the notion of cryptographically secure digital consent, which aims to replicate the traditional consent process in the online world. We provide a flexible digital consent solution that accommodates different use cases and ensures the integrity of the consent process.

The proposed framework involves a client (referring to the user or their devices), an identity manager (which authenticates the client), and an agent (which executes the action upon receiving consent). It supports various applications and ensures compatibility with existing identity managers. We require the client to keep no more than a password. The design addresses several security and privacy challenges, including preventing offline dictionary attacks, ensuring non-repudiable consent, and preventing unauthorized actions by the agent. Security is maintained even if either the identity manager or the agent is compromised, but not both.

Our notion of an identity manager is broad enough to include combinations of different authentication factors such as a password, a smartphone, a security device, biometrics, or an e-passport. We demonstrate applications for signing PDF documents, e-banking, and key recovery.

APN functions offer optimal resistance to differential attacks and are instrumental in the design of block ciphers in cryptography. While finding APN functions is very difficult in general, a promising way to construct APN functions is through symmetric matrices called Quadratic APN matrices (QAM). It is known that the search space for the QAM method can be reduced by means of orbit partitions induced by linear equivalences. This paper builds upon and improves these approaches in the case of homogeneous quadratic functions over $\mathbb{F}_{2^n}$ with coefficients in the subfield $\mathbb{F}_{2^m}$. We propose an innovative approach for computing orbit partitions for cases where it is infeasible due to the large search space, resulting in the applications for the dimensions $(n,m)=(8,4)$, and $(n,m)=(9,3)$. We find and classify, up to CCZ-equivalence, all quadratic APN functions for the cases of $(n,m)=(8,2),$ and $(n,m)=(10,1)$, discovering a new APN function in dimension $8$. Also, we show that an exhaustive search for $(n,m) = (10,2)$ is infeasible for the QAM method using currently available means, following partial searches for this case.

Searchable symmetric encryption (SSE) enables queries over symmetrically encrypted databases. To achieve practical efficiency, SSE schemes incur a certain amount of leakage; however, this leads to the possibility of leakage cryptanalysis, i.e., cryptanalytic attacks that exploit the leakage from the target SSE scheme to subvert its data and query privacy guarantees. Leakage cryptanalysis has been widely studied in the context of SSE schemes supporting either keyword queries or range queries, often with devastating consequences. However, little or no attention has been paid to cryptanalysing substring-SSE schemes, i.e., SSE schemes supporting arbitrary substring queries over encrypted data. This is despite their relevance to many real-world applications, e.g., in the context of securely querying outsourced genomic databases. In particular, the first ever substring-SSE scheme, proposed nearly a decade ago by Chase and Shen (PoPETS '15), has not been cryptanalysed to date.

In this paper, we present the first leakage cryptanalysis of the substring-SSE scheme of Chase and Shen. We propose a novel inference-based query reconstruction attack that: (i) exploits a reduced version of the actual leakage profile of their scheme, and (ii) assumes a weaker attack model as compared to the one in which Chase and Shen originally claimed security. We implement our attack and experimentally validate its success rate and efficiency over two real-world datasets. Our attack achieves high query reconstruction rate with practical efficiency, and scales smoothly to large datasets containing $100,000$ strings.

To the best of our knowledge, ours is the first and only query reconstruction attack on (and the first systematic leakage cryptanalysis of) any substring-SSE scheme till date.

Classical symmetric encryption algorithms use $N$ bits of a shared secret key to transmit $N$ bits of a message over a one-way channel in an information theoretically secure manner. This paper proposes a hybrid quantum-classical symmetric cryptosystem that uses a quantum computer to generate the secret key. The algorithm leverages quantum circuits to encrypt a message using a one-time pad-type technique whilst requiring a shorter classical key. We show that for an $N$-qubit circuit, the maximum number of bits needed to specify a quantum circuit grows as $N^{3/2}$ while the maximum number of bits that the quantum circuit can encode grows as $N^2$. We do not utilise the full expressive capability of the quantum circuits as we focus on second order Pauli expectation values only. The potential exists to encode an exponential number of bits using higher orders of Pauli expectation values. Moreover, using a parameterised quantum circuit (PQC), we could further augment the amount of securely shared information by introducing a secret key dependence on some of the PQC parameters. The algorithm may be suitable for an early fault-tolerant quantum computer implementation as some degree of noise can be tolerated. Simulation results are presented along with experimental results on the 84-qubit Rigetti Ankaa-2 quantum computer.

We present techniques for constructing zero-knowledge argument systems from garbled circuits, extending the GC-to-ZK compiler by Jawurek, Kerschbaum, and Orlandi (ACM CCS 2023) and the GC-to-Σ compiler by Hazay and Venkitasubramaniam (J. Crypto, 2020) to the following directions:

- Our schemes are hybrid, commit-and-prove zero-knowledge argument systems that establish a connection between secrets embedded in algebraic commitments and a relation represented by a Boolean circuit. - Our schemes incorporate diverse cross-domain secrets embedded within distinct algebraic commitments, simultaneously supporting Pedersen-like commitments and lattice-based commitments.

As an application, we develop circuit-represented compositions of Σ-protocols that support attractive access structures, such as weighted thresholds, that can be easily represented by a small circuit. For predicates P1, . . . , Pn individually associated with a Σ-protocol, and a predicate C represented by a Boolean circuit, we construct a Σ-protocol for proving C(P1, . . . , Pn) = 1. This result answers positively an open question posed by Abe, et. al., at TCC 2021.

CryptoNext Security develops post-quantum cryptography solutions to protect critical data from emerging quantum threats. We work with clients like banks, governments, and security institutions to secure the future of cybersecurity.

In this role, you will design and implement cryptographic algorithms in languages like C and Java, optimize them for embedded and IoT systems, and address side-channel attacks. You’ll develop and integrate protocols such as TLS and IPSEC using tools like OpenSSL and ensure the security and performance of our software through rigorous testing. Collaboration is key as you’ll work closely with the team to integrate CryptoNext solutions with HSMs, VPNs, and PKI.

We’re looking for someone with a strong background in cryptography, including public-key, and proficiency in programming languages like C or Java. Problem-solving and independence are essential, and fluency in French and English is required.

You’ll join a high-level R&D team, working on cutting-edge projects in a hybrid environment at our Paris office near Gare de Lyon.

Closing date for applications:

Contact:

Apply here: https://apply.workable.com/cryptonext-security/j/B1F279EA06/

More information: https://apply.workable.com/cryptonext-security/j/B1F279EA06/

We are seeking applicants for Ph.D. positions at Université de Montréal. 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:

• Design of new quantum cryptographic protocols
• 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

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. A prior research experience is also desirable.

Université de Montréal is a French speaking institution. Fluency in French is an asset, but all are welcome to apply. Information on the Ph.D. program can be found here: https://diro.umontreal.ca/english/programs/graduate-programs/phd-in-computer-science

Possible start dates are the Summer or Fall 2025 semesters. To apply, send your resume, course transcript and any other relevant documents to philippe.lamontagne.1@umontreal.ca by December 31st, 2024.

Closing date for applications:

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

More information: https://diro.umontreal.ca/english/programs/graduate-programs/phd-in-computer-science