International Association
for Cryptologic Research

This paper is a report on how we tackled constructing a digital signature scheme whose multi-user security with corruption can be tightly reduced to search assumptions. We fail to (dis)prove the statement but obtain the following new results:

- We reveal two new properties of signature schemes whose security cannot be tightly reduced to standard assumptions.

- We construct a new signature scheme. Its multi-user security with corruption is reduced to the CDH assumption (in the ROM), and its reduction loss is independent of the number of users but depends on the number of RO queries.

We consider protocols for secure multi-party computation (MPC) built from FHE under honest majority, i.e., for $n=2t+1$ players of which $t$ are corrupt, that is robust. Surprisingly there exists no robust threshold FHE scheme based on BFV to design an MPC protocol. Precisely, all existing methods for generating a common relinearization key can abort as soon as one player deviates. We solve this issue, with a new relinearization key (adapted from [CDKS19, CCS'19]) which we show how to securely generate in parallel of the threshold encryption key, in the same broadcast. We thus obtain the first robust threshold BFV scheme, moreover using only one broadcast for the generation of keys instead of two previously.

Of independent interest, as an optional alternative, we propose the first threshold FHE decryption enabling simultaneously: (i) robustness over asynchronous channels with honest majority; (ii) tolerating a power-of-small-prime ciphertext modulus, e.g., $2^e$; and (iii) secret shares of sizes quasi-independent of $n$.

Homomorphically multiplying a plaintext matrix with a ciphertext matrix (PC-MM) is a central task for the private evaluation of transformers, commonly used for large language models. We provide several RLWE-based algorithms for PC-MM that consist of multiplications of plaintext matrices (PC-MM) and comparatively cheap pre-processing and post-processing steps: for small and large dimensions compared to the RLWE ring degree, and with and without precomputation. For the algorithms with precomputation, we show how to perform a PC-MM with a single floating-point PP-MM of the same dimensions. This is particularly meaningful for practical purposes as a floating-point PC-MM can be implemented using high-performance BLAS libraries.

The algorithms rely on the multi-secret variant of RLWE, which allows to represent multiple ciphertexts more compactly. We give algorithms to convert from usual shared-secret RLWE ciphertexts to multi-secret ciphertexts and back. Further, we show that this format is compatible with homomorphic addition, plaintext-ciphertext multiplication, and key-switching. This in turn allows us to accelerate the slots-to-coeffs and coeffs-to-slots steps of CKKS bootstrapping when several ciphertexts are bootstrapped at once. Combining batch-bootstrapping with efficient PC-MM results in MaMBo (Matrix Multiplication Bootstrapping), a bootstrapping algorithm that can perform a PC-MM for a limited overhead.

Passwords are widely adopted for user authentication in practice, which led to the question of whether we can bootstrap a strongly-secure setting based on them. Historically, this has been extensively studied for key exchange; bootstrap from a low-entropy password to a high entropy key securing the communication. Other instances include digital lockers, signatures, secret sharing, and encryption.

Motivated by a recent work on consumable tokens (Almashaqbeh et al., Eurocrypt 2022), we extend these efforts and investigate the unified notion of password-authenticated cryptography in which knowing a password allows executing cryptographic functionalities. Our model is resistant to exhaustive search attacks due to the self-destruction and unclonability properties of consumable tokens. We study two directions; the first is password-authenticated delegation of cryptographic capabilities in which a party can delegate her, e.g., signing or encryption/decryption, rights to another such that exercising the delegation requires knowing a password. The second direction is password-authenticated MPC, in which only participants who share the correct password can execute the MPC protocol. In both cases, an adversary who does not know the password can try a few guesses after which the functionality self-destructs.

We formally define the notions above and build constructions realizing them. Our primary goal in this work is examining the power of consumable tokens in building password-authenticated cryptography in terms of viable constructions and supported adversary models, and thus, outlining open problems and potential future work directions.

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