International Association
for Cryptologic Research

We propose a new NTRU-based Public-Key Encryption (PKE) scheme called $\mathsf{NTRU+}\mathsf{PKE}$, which effectively incorporates the Fujisaki-Okamoto transformation for PKE (denoted as $\mathsf{FO}_{\mathsf{PKE}}$) to achieve chosen-ciphertext security in the Quantum Random Oracle Model (QROM). While $\mathsf{NTRUEncrypt}$, a first-round candidate in the NIST PQC standardization process, was proven to be chosen-ciphertext secure in the Random Oracle Model (ROM), it lacked corresponding security proofs for QROM. Our work extends the capabilities of the recent $\mathsf{ACWC}_{2}$ transformation, proposed by Kim and Park in 2023, by demonstrating that an $\mathsf{ACWC}_{2}$-transformed scheme can serve as a sufficient foundation for applying $\mathsf{FO}_\mathsf{PKE}$. Specifically, we show that the $\mathsf{ACWC}_{2}$-transformed scheme achieves (weak) $\gamma$-spreadness, an essential property for constructing an IND-CCA secure PKE scheme. Moreover, we provide the first proof of the security of $\mathsf{FO}_\mathsf{PKE}$ in the QROM. Finally, we show that $\mathsf{FO}_\mathsf{PKE}$ can be further optimized into a more efficient transformation, $\overline{\mathsf{FO}}_\mathsf{PKE}$, which eliminates the need for re-encryption during decryption. By instantiating an $\mathsf{ACWC}_{2}$-transformed scheme with appropriate parameterizations, we construct $\mathsf{NTRU+}\mathsf{PKE}$, which supports 256-bit message encryption. Our implementation results demonstrate that at approximately a classical 180-bit security level, $\mathsf{NTRU+}\mathsf{PKE}$ is about 1.8 times faster than \textsc{Kyber} + AES-256-GCM in AVX2 mode.

The goal of this note is to describe and analyze a simplified variant of the zk-SNARK construction used in the Aztec protocol. Taking inspiration from the popular notion of Incrementally Verifiable Computation[Val09] (IVC) we define a related notion of $\textrm{Repeated Computation with Global state}$ (RCG). As opposed to IVC, in RCG we assume the computation terminates before proving starts, and in addition to the local transitions some global consistency checks of the whole computation are allowed. However, we require the space efficiency of the prover to be close to that of an IVC prover not required to prove this global consistency. We show how RCG is useful for designing a proof system for a private smart contract system like Aztec.

This paper presents a survey of the state-of-the-art pre-silicon security verification techniques for System-on-Chip (SoC) designs, focusing on ensuring that designs, implemented in hardware description languages (HDLs) and synthesized circuits, meet security requirements before fabrication in semiconductor foundries. Due to several factors, pre-silicon security verification has become an essential yet challenging aspect of the SoC hardware lifecycle. The modern SoC design process often adheres to a design reuse philosophy, integrating multiple functional blocks or Intellectual Property (IP) cores sourced from various vendors onto a single chip. While beneficial for reducing costs and accelerating time-to-market, this approach introduces numerous untrustworthy third-party entities into the supply chain. It increases the potential for introducing security vulnerabilities significantly. Additionally, hardware fabrication, assembly, and testing are frequently outsourced to third-party entities, further exacerbating security risks. Moreover, the growing complexity of SoC designs leads to unanticipated interactions between hardware and software layers, creating potential gateways for attackers to exploit and steal confidential information from devices. In response to these challenges, recent years have seen a surge in the development of innovative SoC security verification techniques. This survey provides an overview of these methods, their high-level working principles, strengths, and weaknesses. By understanding these techniques, designers can better evaluate their effectiveness and select the most appropriate methods aligned with the specific security objectives for their SoC designs.

Several cryptographic primitives, especially succinct proofs of various forms, transform the satisfaction of high-level properties to the existence of a polynomial quotient between a polynomial that interpolates a set of values with a cleverly arranged divisor. Some examples are SNARKs, like Groth16, and polynomial commitments, such as KZG. Such a polynomial division naively takes $O(n \log n)$ time with Fast Fourier Transforms, and is usually the asymptotic bottleneck for these computations.

Several works have targeted specific constructions to optimize these computations and trade-off one-time setup costs with faster online computation times. In this paper, we present a unified approach to polynomial division related computations for a diverse set of schemes. We show how our approach provides a common abstract lens which recasts and improves existing approaches. Additionally, we present benchmarks for the Groth16 and the KZG systems, illustrating the significant practical benefits of our approach in terms of speed, memory, and parallelizability. We get a speedup of $2\times$ over the state-of-the-art in computing all openings for KZG commitments and a speed-up of about $2-3\%$ for Groth16 proofs when compared against the Rust Arkworks implementation. Although our Groth16 speedup is modest, our approach supports twice the number of gates as Arkworks and SnarkJS as it avoids computations at higher roots of unity. Conversely this reduces the need for employing larger groups for bigger circuits.

Our core technical contributions are novel conjugate representations and compositions of the derivative operator and point-wise division under the Discrete Fourier Transform. These allow us to leverage l'Hôpital's rule to efficiently compute polynomial division, where in the evaluation basis such divisions maybe of the form $0/0$. As a concrete example, our technique allows applying a Toeplitz-matrix transform to a vector of elliptic curve group elements using only $n\log{n}$ elliptic-curve scalar multiplcations, whereas earlier techniques can at best achieve $\frac{3}{2}n\log{n}$ complexity. Our techniques are generic with potential applicability to many existing protocols.

In this paper, we propose quantum key recovery attacks on 4-round iterated Even-Mansour (IEM) with a key schedule that applies two keys alternately. We first show that a conditional periodic function such that one of the secret keys appears as a period conditionally can be constructed using the encryption function and internal permutations. By applying the offline Simon's algorithm to this function, we construct a key recovery attack with a complexity of $O(\sqrt{N} \log N)$ for $N = 2^n$, where $n$ is the block size and one secret key size. Using quantum queries, this attack outperforms the generic quantum attack, i.e., Grover's search which takes the time complexity of $O(N)$. Moreover, we propose the quantum version of the multibridge attack proposed by Dinur et al. in ASIACRYPT 2014 to analyze the 4-round IEM. As a result, we show that the quantum multibridge attack can achieve the optimal complexity of $O(N)$ even if we have only $O(1)$ data without quantum queries, while the classical attack requires $O(N)$ data to achieve the same time complexity. Furthermore, we show that the quantum multibridge attack slightly outperforms Grover's search when considering the quantum circuit depth for these attacks.

Masking has become a widely applied and heavily researched method to protect cryptographic implementations against SCA attacks. The success of masking is primarily attributed to its strong theoretical foundation enabling it to formally prove security by modeling physical properties through so-called probing models. Specifically, the robust $d$-probing model enables us to prove the security for arbitrarily masked hardware circuits, manually or with the assistance of automated tools, even when considering the imperfect nature of physical hardware, including the occurrence of physical defaults such as glitches. However, the generic strategy employed by the robust $d$-probing model comes with a downside: It tends to over-conservatively model the information leakage caused by glitches meaning that the robust $d$-probing model considers glitches that can never occur in practice. This implies that in theory, an adversary could gain more information than she would obtain in practice. From a designer's perspective, this entails that (1) securely designed hardware circuits may need to be withdrawn due to potential insecurity under the robust $d$-probing model and (2) designs that satisfy the security requirements of the robust $d$-probing model may incur unnecessary overhead, such as increased circuit size or latency. In this work, we refine the formal treatment of glitches within the robust $d$-probing model to address glitches more accurately within a formal adversary model. Unlike the robust $d$-probing model, our approach considers glitches based on the operations performed and the data processed, ensuring that only manifesting glitches are accounted for. As a result, we introduce the RR $d$-probing model, a formal adversary model maintaining the same level of security as the robust $d$-probing model but without the overly conservative treatment of glitches. Leveraging our new model, we prove the security of \ac{LMDPL} gadgets, a class of physically secure gadgets reported as insecure based on the robust $d$-probing model. We provide manual proofs and automated security evaluations employing an updated version of PROLEAD capable of verifying the security of masked circuits under our new model.

A compiler introduced by Kalai et al. (STOC'23) converts any nonlocal game into an interactive protocol with a single computationally-bounded prover. Although the compiler is known to be sound in the case of classical provers, as well as complete in the quantum case, quantum soundness has so far only been established for special classes of games. In this work, we establish a quantum soundness result for all compiled two-player nonlocal games. In particular, we prove that the quantum commuting operator value of the underlying nonlocal game is an upper bound on the quantum value of the compiled game. Our result employs techniques from operator algebras in a computational and cryptographic setting to establish information-theoretic objects in the asymptotic limit of the security parameter. It further relies on a sequential characterization of quantum commuting operator correlations which may be of independent interest.

MIFARE Classic smart cards, developed and licensed by NXP, are widely used but have been subjected to numerous attacks over the years. Despite the introduction of new versions, these cards have remained vulnerable, even in card-only scenarios. In 2020, the FM11RF08S, a new variant of MIFARE Classic, was released by the leading Chinese manufacturer of unlicensed "MIFARE compatible" chips. This variant features specific countermeasures designed to thwart all known card-only attacks and is gradually gaining market share worldwide. In this paper, we present several attacks and unexpected findings regarding the FM11RF08S. Through empirical research, we discovered a hardware backdoor and successfully cracked its key. This backdoor enables any entity with knowledge of it to compromise all user-defined keys on these cards without prior knowledge, simply by accessing the card for a few minutes. Additionally, our investigation into older cards uncovered another hardware backdoor key that was common to several manufacturers.

For secure multi-party computation in the line of the secret-sharing based SPDZ protocol, actively secure multiplications consume correlated randomness in the form of authenticated Beaver triples, which need to be generated in advance. Although it is a well-studied problem, the generation of Beaver triples is still a bottleneck in practice. In the two-party setting, the best solution with low communication overhead is the protocol by Boyle et al. (Crypto 2020), which is derived from the recent primitive of Pseudorandom Correlation Generators (PCGs) (Crypto 2019). Their protocol requires less than 2 MB of communication to generate about 100 MB of Beaver triples (per party). In this work, we improve their protocol in terms of communication (7%), computation (20% for its interactive phase), and the amount of correlated randomness consumed by internal secure two-party computations (11% storage). To achieve our improvements, we propose a novel actively secure protocol for the efficient generation of (authenticated) secret-shared scaled unit vectors, which in general are the main building blocks of current PCG protocols.

Zero-knowledge proofs allow one party to prove the truth of a statement without disclosing any extra information. Recent years have seen great improvements in zero-knowledge proofs. Among them, zero-knowledge SNARKs are notable for their compact and efficiently-verifiable proofs but face challenges with high prover costs for large-scale applications. To accelerate proof generation, Pianist (Liu et al, S&P 2024) proposes to distribute the proof generation process across multiple machines, and achieves a significant reduction in overall prover time. However, Pianist inherits the quasi-linear computational complexity from its underlying SNARK proof system Plonk, limiting its scalability and efficiency with large circuits. In this paper, we introduce HyperPianist, a fully distributed proof system with linear-time prover complexity and logarithmic communication cost among distributed machines. Starting from deVirgo (Cheng et al., CCS 2024), we study their distributed multivariate SumCheck protocol and achieve logarithmic communication cost by using an additively homomorphic multivariate polynomial commitment scheme in the distributed setting. Given the distributed SumCheck protocol, we then adapt HyperPlonk (Chen et al., EuroptCrypt 2023), a proof system based on multivariate polynomials, to the distributed setting without extra overhead for witness re-distribution. In addition, we propose a more efficient construction of lookup arguments based on Lasso (Setty et al., Eurocrypt 2024), and adapt it to the distributed setting to enhance HyperPianist and obtain HyperPianist+.

The Secure Intelligent Systems (SecInt) research group at the University of Passau conducts research and teaching on various aspects of hardware security and physical attacks resistance.

Starting October 1, 2024, to support research and teaching within the framework of the project A Unified Hardware Design for the USA and German Post-Quantum Standards funded by the German Research Foundation (DFG) and the US National Science Foundation (NSF), the Assistant Professorship for Secure Intelligent Systems (Professor Dr.-Ing. Elif Bilge Kavun) is seeking to fill the position of a Research Assistant (m/f/d) with 100 percent of regular working hours for an initial limited period of one year. Remuneration will be in accordance with pay group 13 of the TV-L. There is the possibility of an extension of the employment in this project up to a total of three years, if the personal and pay scale requirements are met.

You must have completed (or be close to completing) a university master’s degree in Computer Science, Computer Engineering, Electrical Engineering, or closely related research disciplines with outstanding grades. Top candidates should demonstrate knowledge & expertise in most (or at least two) of the following areas:

Cryptography

Post-quantum cryptography

Hardware (ASIC/FPGA) design (with HDL)

Cryptographic hardware design

Side-channel attacks and countermeasures

Fluency in English is required, and knowledge of German is preferred.

Please send your application by e-mail with relevant documents (i.e., CV and degree & work certificates, and if you have any, academic publications and references) only in PDF format as one file (email subject: Application-Secure_Intelligent_Systems Surname) to elif.kavun[AT]uni-passau.de by August 25, 2024.

We refer to our data protection information, available at https://www.uni-passau.de/en/university/current-vacancies/.

Closing date for applications:

Contact: If you have any questions, please contact Prof. Dr.-Ing. Elif Bilge Kavun via the e-mail address elif.kavun[AT]uni-passau.de.

More information: https://www.uni-passau.de/en/university/current-vacancies/

Applications are invited for the position of Assistant Professor. We are looking for applicants with a strong research record in either cryptographic engineering or machine learning in cryptography. In particular, we are looking for candidates with experience in security evaluation of cryptographic hardware or hardware/software co-design for cryptography.

The position is within the Digital Security (DiS) section of the Institute for Computing and Information Science (iCIS). As an Assistant Professor you will be responsible for the development and coordination of security courses at the Bachelor’s and Master’s levels. You will be expected to develop connections within our institute and Radboud University and beyond and contribute to administrative tasks and outreach activities. This position has a good balance between teaching, research and administration, giving the candidate time to write research proposals and further develop their research lines and career.

Profile:

Your expertise is in good synergy with the current expertise of the Digital Security group and is supported by publications at high-profile venues, invitations to scientific conferences, and/or research grants. You have good teaching skills and experience, a clear vision on teaching, and the willingness to teach a broad variety of Bachelor’s degree courses, as well as courses related to your research expertise in the Master’s programme in Cyber Security. You are a team player who is eager to collaborate with other academics and build bridges between different research areas within and outside DiS and Radboud University, and within and outside academia, nationally and internationally. You have good communication skills. You are interested, and preferably have experience, in security research for industry and real-world applications. You have the ability to successfully apply for external funding.

Deadline: September 15, 2014

Closing date for applications:

Contact: Lejla Batina

More information: https://www.ru.nl/en/working-at/job-opportunities/assistant-professor-of-digital-security-hardware-for-cryptography

The appointed candidate is expected to provide academic leadership by contributing to the planning, development, and implementation of strategies for continuous improvement in a new Bachelor of Science (Hons) in Cyber Security programme. Candidates can apply directly at: https://www.vtc.edu.hk/html/en/jobDetail.php?id=36796

Closing date for applications:

Contact: Dr KY Cheong

More information: https://www.vtc.edu.hk/html/en/jobDetail.php?id=36796

Lancaster University invites applications for one post of Assistant Professor (Lecturer) in Computer Science to join at its exciting new campus in Leipzig, Germany. Located in one of Germany’s most vibrant, livable, and attractive cities, the Leipzig campus offers the same high academic quality and fully rounded student experience as in the UK, with a strong strategic vision of excellence in teaching, research, and engagement.

The position is to support the upcoming MSc programme in Cyber Security, and to complement the department’s current research strengths. You are expected to have solid research foundations and a strong commitment in teaching Cyber Security topics such as Cybercrime, Information System Risk Management, or Information System Security Management.

You should have a completed PhD degree and demonstrated capabilities in teaching, research, and engagement in the areas of Cyber Security. You should be able to deliver excellent teaching at graduate and undergraduate level, pursue your own independent research, and develop publications in high quality academic journals or conferences. You are expected to have a suitable research track record of targeting high quality journals or a record of equivalent high-quality research outputs.

Colleagues joining LU Leipzig’s computer science department will benefit from a very active research team, but will also have access to the research environment at the School of Computing and Communications in the UK. We offer a collegial and multidisciplinary environment with enormous potential for collaboration and work on challenging real-world problems especially.

German language skills are not a prerequisite for the role, though we are seeking applicants with an interest in making a long-term commitment to Lancaster University in Leipzig.

Closing date for applications:

Contact: For an informal discussion about these roles please contact,

• the Academic Dean: Prof Constantin Blome (c.blome@lancaster.ac.uk)
• the Head of Department: Dr Fabio Papacchini (f.papacchini@lancaster.ac.uk)

More information: https://hr-jobs.lancs.ac.uk/Vacancy.aspx?ref=0850-24

We’re looking for a PhD student (4 years, full position) to work with us on the NWO project EPOCHAL (Extensions of POst-quantum CryptograpHy and ALgorithms). The last years have seen a lot of focus on building encryption systems and signature schemes that are secure against quantum attacks. This involves analyzing them in a security model where the attacker has a quantum computer. While the replacement schemes are not perfect fits in terms of speed or size, the community has reached some workable solutions. However, there is a lot of usage of public-key cryptography that goes beyond these core building blocks – many real-world solutions need to establish related public keys, which involves using the structure of elliptic curves, or to verify the validity of public keys. Currently deployed protocols often inherently use properties of the pre-quantum building blocks. For those, we do not (yet) have matching or sufficiently efficient replacements among systems that can resist attacks with quantum computers. The goal of this project is to develop exactly such solutions and to analyze their security. The PhD position is embedded in the Coding Theory and Cryptology group in the Discrete Mathematics (DM) cluster with Tanja Lange as main supervisor. We work closely with the Applied and Provable Security group (also part of DM) and Kathrin Hövelmanns is part of the project team. Please note that applications must be received via the TU/e application site https://jobs.tue.nl/en/vacancy/phd-on-postquantum-cryptography-1101449.html and the "APPLY NOW" button on that page. The page also has some general information about the employment conditions.

Closing date for applications:

Contact: Tanja Lange

More information: https://jobs.tue.nl/en/vacancy/phd-on-postquantum-cryptography-1101449.html

We are looking for a candidate with proven scientific expertise in the field of Security & Privacy. The following areas are of particular interest:

• AI Safety and Security
• Privacy
• Cryptography
• Formal Methods for Security
• System Security
• Digital Identities
• Usable Security

The successful candidate will cover one of these fields or any other field in Security & Privacy that complements the existing strengths in the department. The professorship will be part of the Institute of Applied Information Processing and Communications, which is an internationally highly visible research environment with more than 60 researchers in information security. It has been active in this field for more than 30 years and performs research in the following four areas: Cryptology & Privacy, Formal Methods, System Security, and Secure Applications.

The new professor will build an internationally visible group, and will be an engaged teacher in the Computer Science programs at the Bachelor’s, Master’s, and PhD level, and will actively participate in academic self-administration. At Graz University of Technology, undergraduate courses are taught in German or English and graduate courses are taught in English.

Closing date for applications:

Contact: Please send your application via this link:

https://jobs.tugraz.at/en/jobs/2ce67149-7069-cc79-2bdc-65b9f66b2c32/apply?preview=true

For further questions, please contact Stefan Mangard (stefan.mangard@iaik.tugraz.at).

More information: https://jobs.tugraz.at/de/jobs/c9dc1465-5885-6706-d049-6650453181d0

We study the linear code equivalence problem (LEP) for linear $[n,k]$-codes over finite fields $\mathbb{F}_q$. Recently, Chou, Persichetti and Santini gave an elegant heuristic algorithm that solves LEP over large finite fields (with $q = \Omega(n)$) in time $2^{\frac{1}{2}\operatorname{H}\left(\frac{k}{n}\right)n}$, where $\operatorname{H}(\cdot)$ denotes the binary entropy function. However, for small finite fields, their algorithm can be significantly slower. In particular, for fields of constant size $q = \mathcal{O}(1)$, its runtime increases by an exponential factor $2^{\Theta(n)}$. We present an improved and provably correct version of their algorithm, which achieves the desired runtime of $2^{\frac{1}{2}\operatorname{H}\left(\frac{k}{n}\right)n}$ for all finite fields of size $q \geq 7$. For a wide range of parameters, this improves over the runtime of all previously known algorithms by an exponential factor.

The recent VOLE-based interactive zero-knowledge (VOLE-ZK) protocols along with non-interactive zero-knowledge (NIZK) proofs based on MPC-in-the-Head (MPCitH) and VOLE-in-the-Head (VOLEitH) extensively utilize the commitment schemes, which adopt a circular correlation robust (CCR) hash function as the core primitive. Nevertheless, the state-of-the-art CCR hash construction by Guo et al. (S&P'20), building from random permutations, can only provide 128-bit security, when it is instantiated from AES. This brings about a gap between AES-based CCR hash function and high security (beyond 128-bit security). In this paper, we fill this gap by constructing a new CCR hash function from AES, supporting three security levels (i.e., 128, 192 and 256). Using the AES-based CCR hash function, we present an all-but-one vector commitment (AVC) scheme, which constitutes a computationally intensive part of the NIZK proofs from MPCitH and VOLEitH, where these NIZK proofs can in turn be transformed into the promising post-quantum signature candidates. Furthermore, we obtain an efficient VOLE-ZK protocol with security levels higher than 128 from the CCR hash function. Our benchmark results show that the AES-based CCR hash function has a comparable performance with CCR hash functions based on Rijndael with larger block sizes, which is not standardized and has a limited application range. In the AVC context, the expensive commitment component instantiated with our AES-based CCR hash function improves the running time by a factor of $7 \sim 30 \times$, compared to the SHA3-based instantiation used in the recent post-quantum signature algorithm FAEST.

\scarf, an ultra low-latency tweakable block cipher, is the first cipher designed for cache randomization. The block cipher design is significantly different from the other common tweakable block ciphers; with a block size of only 10 bits, and yet the input key size is a whopping $240$ bits. Notably, the majority of the round key in its round function is absorbed into the data path through AND operations, rather than the typical XOR operations. In this paper, we present a key-recovery attack on a round-reduced version of SCARF with 4 + 4 rounds under the single-tweak setting. Our attack is essentially a Meet-in-the-Middle (MitM) attack, where the matching phase is represented by a system of linear equations. Unlike the cryptanalysis conducted by the designers, our attack is effective under both security requirements they have outlined. The data complexity of our attack is $2^{10}$ plaintexts, with a time complexity of approximately $2^{60.63}$ 4-round of SCARF encryptions. It is important to note that our attack does not threaten the overall security of SCARF.

This study addresses the challenge of strengthening cryptographic security measures in the face of evolving cyber threats. The aim is to apply Kleene's Theorem and automata theory to improve the modeling and analysis of cybersecurity scenarios, focusing on the CyberMoraba game. Representing the game's strategic moves as regular expressions and mapping them onto finite automata provides a solid framework for understanding the interactions between attackers and defenders. This approach helps in identifying optimal strategies and predicting potential outcomes, which contributes to the development of stronger cryptographic security protocols. The research advances the theoretical use of automata theory in cybersecurity while offering practical insights into enhancing defense mechanisms against complex cyber attacks. This work connects theoretical computer science with practical cybersecurity, demonstrating the importance of automata theory in cryptology.