International Association
for Cryptologic Research

We present the first comprehensive approach for detecting and analyzing symmetric cryptographic primitives in gate-level descriptions of hardware. To capture both ASICs and FPGAs, we model the hardware as a directed graph, where gates become nodes and wires become edges. For modern chips, those graphs can easily consist of hundreds of thousands of nodes. More abstractly, we find subgraphs corresponding to cryptographic primitives in a potentially huge graph, the sea-of-gates, describing an entire chip. As we are particularly interested in unknown cryptographic algorithms, we cannot rely on searching for known parts such as S-boxes or round constants. Instead, we are looking for parts of the chip that perform highly local computations. A major result of our work is that many symmetric algorithms can be reliably located and sometimes even identified by our approach, which we call HAWKEYE. Our findings are verified by extensive experimental results, which involve SPN, ARX, Feistel, and LFSR-based ciphers implemented for both FPGAs and ASICs. We demonstrate the real-world applicability of HAWKEYE by evaluating it on OpenTitan's Earl Grey chip, an open-source secure micro-controller design. HAWKEYE locates all major cryptographic primitives present in the netlist comprising 424341 gates in 44.3 seconds.

In this paper, we study the computation of complex mathematical functions in statements executed on top of zero-knowledge proofs (ZKP); these functions may include roots, exponentials and logarithms, trigonometry etc. While existing approaches to these functions in privacy-preserving computations (and sometimes also in general-purpose processors) have relied on polynomial approximation, more powerful methods are available for ZKP. In this paper, we note that in ZKP, all algebraic functions are exactly computable. Recognizing that, we proceed to the approximation of transcendental functions with algebraic functions. We develop methods of approximation, instantiate them on a number of common transcendental functions, and benchmark their precision and efficiency in comparison with best polynomial approximations.

As an applied cryptographer, you’ll be pushing the boundaries of cryptographic knowledge along with the Zircuit core research team. You will work together with Zircuit’s elite and tight-knit team to tackle new theoretical problems using cryptography and apply existing cryptographic systems in innovative ways.

Zircuit’s cryptographic problems mainly revolve around zero knowledge proofs (zk-SNARK specifically). We do not expect mastery in all zero knowledge proof systems, but mastery in at least one is required. You should have a strong theoretical background and be comfortable reading and writing code.

If this sounds like you, then we highly encourage you to apply!

Expertise

Mastery of at least one zk-SNARK/zk-STARK proof system

Ability to code and develop software. Experience in least one major programming language and familiarity with versioning software

Ability to read and interpret academic papers

Ability to communicate complex ideas effectively and bridge the gap between theory and practice

Nice to have - familiarity with Circom for writing zero knowledge circuits

Nice to have - familiarity with existing designs of zero knowledge applications in blockchain.

Compensation & Perks

A competitive salary that matches your experience, plus performance bonuses and token grants

Work from anywhere, 100% remote, and flexible working hours

Generous paid time off, including maternity/paternity leave

Retirement/pension plan

Free gym membership, or any virtual alternative of your choice

Join all-expenses-paid retreats in exotic/exclusive locations with the team

Closing date for applications:

Contact: candidate-upload-to-job-rlPL6O4rdXfOvml@inbox.ashbyhq.com

More information: https://jobs.ashbyhq.com/Zircuit/64780490-7248-4e56-8d20-3c29161c6634

We are recruiting a postdoc to work with us (Razvan Barbulescu and Alice Pellet-Mary) on quantum cryptanalysis. More precisely, we are interested in

• quantum cryptanalysis of lattice problems (LWE, SIS, shortest vector problem, ...)
• quantum cryptanalysis of pre-quantum cryptography (e.g., optimizing quantum algorithms for discrete logarithm and factorization)

The starting date is flexible, between September 2024 and September 2025.

The deadline for application is June 30th.

More information about the position and how to apply are available at https://apelletm.pages.math.cnrs.fr/page-perso/documents/positions/HQI_post-doc.pdf

Closing date for applications:

Contact: Alice Pellet-Mary (alice.pellet-mary@math.u-bordeaux.fr) and Razvan Barbulescu (razvan.barbulescu@math.u-bordeaux.fr)

More information: https://apelletm.pages.math.cnrs.fr/page-perso/documents/positions/HQI_post-doc.pdf

We have an opening for an Assistant Professor in Verification of Cryptographic Implementations. We are looking for an enthusiastic colleague to strengthen our team and complement our research and teaching activities. We conduct research in many applied as well as theoretical areas of cryptology. Our team is especially known for our contributions to post-quantum cryptography. We provide an excellent environment for collaboration and support each other in continuous growth as scholars.
We are looking for:

• A team player,
• holding a PhD in an area related to cryptography or formal methods,
• experienced in doing high quality research, demonstrated, for example, by publications in top tier venues on cryptography, security, or formal methods,
• that is also interested in teaching students about their research.

We offer:

• A fun team, open for collaborations,
• supporting you in applying for personal grants, and growing into the role of a professor,
• with a large network for collaborations in academia and industry,
• providing funding for a first PhD student and travel, and
• employment conditions of a Dutch university (including two additional salaries per year and 40+ vacation days).

For questions, please reach out to Andreas Hülsing.

Closing date for applications:

Contact: Andreas Hülsing (a.t.huelsing at tue.nl)

More information: https://jobs.tue.nl/en/vacancy/assistant-professor-in-verification-of-cryptographic-implementations-1083077.html

We are recruiting a postdoc to work with us on "practical advanced post-quantum cryptography from lattices". Here "advanced" does not mean Functional Encryption or Indistinguishability Obfuscation, but OPRFs, Blind Signatures, Updatable Public-Key Encryption, even NIKE.

Cryptanalysis of newfangled assumptions, constructions from standard and new lattice assumptions, proof-of-concept implementations, higher-level protocols, hybrids etc are all in scope. If in doubt, drop us an e-mail and we can discuss.

Key data of the position:

Salary: The salary will be paid at Grade 6, £43,205 – £50,585 per annum or at Grade 7, £51,974 to £61,021 per annum, including London Weighting Allowance.

Closing date: 07 July 2024

Duration: This post will be offered on a fixed-term contract for 2 years, not exceeding 31st December 2028. This is a full-time post.

Closing date for applications:

Contact: Martin Albrecht <martin.albrecht@kcl.ac.uk>

More information: https://martinralbrecht.wordpress.com/2024/05/30/postdoc-position-in-lattice-based-cryptography/

Event date: 24 September to 26 September 2024
Submission deadline: 22 July 2024
Notification: 27 August 2024

The Ascon specification defines among others an encryption scheme offering authenticated encryption with associated data (AEAD) which is based on a duplex mode of a sponge. With that it is the first of such algorithm selected and about to be standardized by NIST. The sponge size is comparatively small, 320 bits, as expected for lightweight cryptography. With that, the strength of the defined AEAD algorithm is limited to 128 bits. Albeit, the definition of the Ascon AEAD algorithm integrates with the associated sponge, it is mathematically not bound to exactly this sponge function. Thus, the Ascon AEAD specification can be used with a different sponge and still operate as defined by the Ascon authors. This specification defines the Ascon-Keccak AEAD algorithm which replaces the Ascon sponge with the Keccak sponge, leaving the Ascon AEAD algorithm unchanged. The selected parameters for Ascon-Keccak AEAD offer two algorithm strengths: Ascon-Keccak 256 with a classic security strength of 256 bits and a quantum security strength of 128 bits. In addition, Ascon-Keccak 512 provides an algorithm with 512 bit classic security strength and 256 bit quantum security strength. The selected parameters for Ascon-Keccak 256 offer a significant higher performance on 64-bit architectures than Ascon-128 and Ascon-128a. The performance of Ascon-Keccak 512 is in league with Ascon-128. Yet, with the Keccak sponge size of 1600 bits, Ascon-Keccak cannot be considered a lightweight cryptographic algorithm any more. A reference implementation of the algorithm is provided as referenced in the document.

We present a framework for speeding up the search for preimages of candidate one-way functions based on highly biased differential-linear distinguishers. It is naturally applicable to preimage attacks on hash functions. Further, a variant of this framework applied to keyed functions leads to accelerated key-recovery attacks. Interestingly, our technique is able to exploit related-key differential-linear distinguishers in the single-key model without querying the target encryption oracle with unknown but related keys. This is in essence similar to how we speed up the key search based on the well known complementation property of DES, which calls for caution from the designers in building primitives meant to be secure in the single-key setting without a thorough cryptanalysis in the related-key model. We apply the method to sponge-based hash function Ascon-HASH, XOFs XOEsch/Ascon-XOF and AEAD Schwaemm, etc. Accelerated preimage or key-recovery attacks are obtained. Note that all the differential-linear distinguishers employed in this work are highly biased and thus can be experimentally verified.

We construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence pseudorandom generators (PRGs) in $\mathsf{NC}^0$ with polynomial stretch from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an intermediate step in our construction, we abstract away a notion of structured-seed polynomial-stretch PRGs in $\mathsf{NC}^0$ which suffices for IO and is implied by both sparse LPN and the existence of polynomial-stretch PRGs in $\mathsf{NC}^0$.

As immediate applications, from the sub-exponential hardness of the decisional linear assumption on bilinear groups, large-field LPN, and sparse LPN, we get alternative constructions of (a) fully homomorphic encryption (FHE) without lattices or circular security assumptions (Canetti, Lin, Tessaro, and Vaikuntanathan, TCC 2015), and (b) perfect zero-knowledge adaptively-sound succinct non-interactive arguments (SNARGs) for NP (Waters and Wu, STOC 2024).

The rise of Generative AI (GenAI) brings about transformative potential across sectors, but its dual-use nature also amplifies risks. Governments globally are grappling with the challenge of regulating GenAI, balancing innovation against safety. China, the United States (US), and the European Union (EU) are at the forefront with initiatives like the Management of Algorithmic Recommendations, the Executive Order, and the AI Act, respectively. However, the rapid evolution of GenAI capabilities often outpaces the development of comprehensive safety measures, creating a gap between regulatory needs and technical advancements.

A workshop co-organized by Google, University of Wisconsin, Madison (UW-Madison), and Stanford University aimed to bridge this gap between GenAI policy and technology. The diverse stakeholders of the GenAI space—from the public and governments to academia and industry—make any safety measures under consideration more complex, as both technical feasibility and regulatory guidance must be realized. This paper summarizes the discussions during the workshop which addressed questions, such as: How regulation can be designed without hindering technological progress? How technology can evolve to meet regulatory standards? The interplay between legislation and technology is a very vast topic, and we don’t claim that this paper is a comprehensive treatment on this topic. This paper is meant to capture findings based on the workshop, and hopefully, can guide discussion on this topic.

HyperPlonk is a recent SNARK proposal (Eurocrypt'23) that features a linear-time prover and supports custom gates of larger degree than Plonk. For the time being, its instantiations are only proven to be knowledge-sound (meaning that soundness is only guaranteed when the prover runs in isolation) while many applications motivate the stronger notion of simulation-extractability (SE). Unfortunately, the most efficient SE compilers are not immediately applicable to multivariate polynomial interactive oracle proofs. To address this problem, we provide an instantiation of HyperPlonk for which we can prove simulation-extractability in a strong sense. As a crucial building block, we describe KZG-based commitments to multivariate polynomials that also provide simulation-extractability while remaining as efficient as malleable ones. Our proofs stand in the combined algebraic group and random oracle model and ensure straight-line extractability (i.e., without rewinding).

At Eurocrypt $2021$, Li and Micciancio demonstrated that the IND-CPA notion of security is not sufficient to cover the passive security of approximate homomorphic encryption schemes, by outlining a key recovery attack against the CKKS scheme (Cheon, Kim, Kim, Seong, Asiacrypt $2017$). They proposed the notion of $q$-IND-CPA-D security, which allows an adversary to make $q$ calls to a restricted decryption oracle. Li and Micciancio left achieving $q$-IND-CPA-D security as an open problem, but proposed two approaches: noise flooding and an exact version of CKKS. The first approach was addressed by Li, Micciancio, Schultz and Sorrell (Crypto 2022), but leads to substantial efficiency loss.

In this work, we look at the second approach. We define $(\delta, r)$-exact CKKS, a version of CKKS that returns exact results on all except the least $r$ significant bits with (high) probability $\delta$, based on bounds on the noise. We prove that the advantage of a $q$-IND-CPA-D attacker against $(\delta, r)$-exact CKKS is determined by the failure probability of those bounds. We conduct a tight average-case and implementation-specific noise analysis of all elementary operations in CKKS, as implemented in the Lattigo library, including the bootstrapping operation. We propose bounds that have small enough failure probability for the advantage of a $q$-IND-CPA-D attacker against $(\delta,r)$-exact CKKS to become smaller than $2^{-128}$, while the parameter sets needed remain practical. We furthermore present an estimator tool that combines the bounds on basic operations and returns tight noise estimates, even for large circuits. We validate our bounds by showcasing experimental results on different iterative algorithms, homomorphic encoding, decoding and bootstrapping.

In this research, we introduce MIND-Crypt, a novel attack framework that uses deep learning (DL) and transfer learning (TL) to challenge the indistinguishability of block ciphers, specifically SPECK32/64 encryption algorithm in CBC mode (Cipher Block Chaining) against Known Plaintext Attacks (KPA). Our methodology includes training a DL model with ciphertexts of two messages encrypted using the same key. The selected messages have the same byte-length and differ by only one bit at the binary level. This DL model employs a residual network architecture. For the TL, we use the trained DL model as a feature extractor, and these features are then used to train a shallow machine learning, such as XGBoost. This dual strategy aims to distinguish ciphertexts of two encrypted messages, addressing traditional cryptanalysis challenges.

Our findings demonstrate that the deep learning model achieves an accuracy of approximately 99% under consistent cryptographic conditions (Same Key or Rounds) with the SPECK32/64 cipher. However, performance degrades to random guessing levels (50%) when tested with ciphertext generated from different keys or different encryption rounds of SPECK32/64. To enhance the results, the DL model requires retraining with different keys or encryption rounds using larger datasets ($10^{7}$ samples). To overcome this limitation, we implement TL, achieving an accuracy of about 53% with just 10,000 samples, which is better than random guessing. Further training with 580,000 samples increases accuracy to nearly 99%, showing a substantial reduction in data requirements by over 94%. This shows that an attacker can utilize machine learning models to break indistinguishability by accessing pairs of plaintexts and their corresponding ciphertexts encrypted with the same key, without directly interacting with the communicating parties.

A primary challenge in isogeny-based cryptography lies in the substantial computational cost associated to computing and evaluating prime-degree isogenies. This computation traditionally relied on Vélu's formulas, an approach with time complexity linear in the degree but which was further enhanced by Bernstein, De Feo, Leroux, and Smith to a square-root complexity. The improved square-root Vélu's formulas exhibit a degree of parallelizability that has not been exploited in major implementations. In this study, we introduce a theoretical framework for parallelizing isogeny computations and provide a proof-of-concept implementation in C with OpenMP. While the parallelization effectiveness exhibits diminishing returns with the number of cores, we still obtain strong results when using a small number of cores. Concretely, our implementation shows that for large degrees it is easy to achieve speedup factors of up to $1.74$, $2.54$, and $3.44$ for two, four, and eight cores, respectively.

What are the minimal cryptographic assumptions that suffice for constructing efficient argument systems, and for which tasks? Recently, Amit and Rothblum [STOC 2023] showed that one-way functions suffice for constructing constant-round arguments for bounded-depth computations. In this work we ask: what other tasks have efficient argument systems based only on one-way functions? We show two positive results:

First, we construct a new argument system for batch-verification of $k$ $UP$ statements ($NP$ statements with a unique witness) for witness relations that are verifiable in depth $D$. Taking $M$ to be the length of a single witness, the communication complexity is $O(\log k) \cdot (M + k \cdot D \cdot n^{\sigma})$, where $\sigma > 0$ is an arbitrarily small constant. In particular, the communication is quasi-linear in the length of a single witness, so long as ${k < M / (D \cdot n^{\sigma})}$. The number of rounds is constant and the honest prover runs in polynomial time given witnesses for all $k$ inputs' membership in the language.

Our second result is a constant-round doubly-efficient argument system for languages in $P$ that are computable by bounded-space Turing machines. For this class of computations, we obtain an exponential improvement in the trade-off between the number of rounds and the (exponent of the) communication complexity, compared to known unconditionally sound protocols [Reingold, Rothblum and Rothblum, STOC 2016].

The proliferation of artificial intelligence and big data has resulted in a surge in data demand and increased data dimensionality. This escalation has consequently heightened the costs associated with storage and processing. Concurrently, the confidential nature of data collected by various institutions, which cannot be disclosed due to personal privacy concerns, has exacerbated the challenges associated with data analysis and machine learning model training. Therefore, designing a secure and efficient high-dimensional data reduction method that supports multi-party joint participation becomes critical to solving these problems.

This paper proposes a novel homomorphic encryption dimensionality reduction scheme (HE-DR) based on CKKS, which modifies the Rank-Revealing (RR) method to make it more applicable to fully homomorphic encryption, thereby achieving fast and secure dimension reduction for high-dimensional data. Compared to traditional homomorphic encryption dimensionality reduction schemes, our approach does not transmit the user’s original data to other participants in any format (Ciphertext or Plaintext). Moreover, our method's computational efficiency is nearly $60-200$ times faster than similar algorithms, and the communication overhead is only $1/3$ of theirs. Finally, we have shown that our proposed scheme can preserve its computational efficiency and accuracy even when dealing with high-dimensional data. As dimensionality escalates, the ratio of ciphertext to plaintext computational efficiency plateaus at approximately 5 times, while the computational error (distance between subspaces) remains around $1e^{-11}$

PLONK is a zk-SNARK system by Gabizon, Williamson, and Ciobotaru with proofs of constant size (0.5 KB) and sublinear verification time. Its setup is circuit-independent supporting proofs of arbitrary statements up to a certain size bound.

Although deployed in several real-world applications, PLONK's zero-knowledge property had only been argued informally. Consequently, we were able to find and fix a vulnerability in its original specification, leading to an update of PLONK in eprint version 20220629:105924.

In this work, we construct a simulator for the patched version of PLONK and prove that it achieves statistical zero knowledge. Furthermore, we give an attack on the previous version of PLONK showing that it does not even satisfy the weaker notion of (statistical) witness indistinguishability.

We prove that the permutation computed by a reversible circuit with $\widetilde{O}(nk\cdot \log(1/\epsilon))$ random $3$-bit gates is $\epsilon$-approximately $k$-wise independent. Our bound improves on currently known bounds in the regime when the approximation error $\epsilon$ is not too small. We obtain our results by analyzing the log-Sobolev constants of appropriate Markov chains rather than their spectral gaps.

Asynchronous Remote Key Generation (ARKG) is a primitive introduced by Frymann et al. at ACM CCS 2020. It enables a sender to generate a new public key $pk'$ for a receiver ensuring only it can, at a later time, compute the corresponding private key sk'. These key pairs are indistinguishable from freshly generated ones and can be used in various public-key cryptosystems such as digital signatures and public-key encryption. ARKG has been explored for applications in WebAuthn credential backup and delegation, as well as for enhancing receiver privacy via stealth addresses.

In this paper, we introduce distributed ARKG (dARKG) aiming to provide similar security properties in a distributed setting. Here, a sender generates $pk'$ for a group of $n$ receivers and the corresponding $sk'$ can only be computed by any sub-group of size $t\leq n$. This introduces threshold-based access protection for $sk'$, enabling for instance a set of proxies to jointly access a WebAuthn account or claim blockchain funds.

We construct dARKG using one-round publicly verifiable asymmetric key agreement, called 1PVAKA, a new primitive formalized in this work. Unlike traditional distributed key generation protocols where users interact with one another, 1PVAKA is asynchronous and allows a third party to verify and generate a public key from users' outputs.

We discuss 1PVAKA and dARKG instantiations tailored for use with bilinear groups and demonstrate practicality with implementation and performance analysis for the BLS12-381 curve.