International Association
for Cryptologic Research

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.

We study the problem of generating public unbiased randomness in a distributed manner within the recent You Only Speak Once (YOSO) framework for stateless multiparty computation, introduced by Gentry et al. in CRYPTO 2021.

Such protocols are resilient to adaptive denial-of-service attacks and are, by their stateless nature, especially attractive in permissionless environments.

While most works in the YOSO setting focus on independent random corruptions, we consider YOSO protocols with worst-case corruptions, a model introduced by Nielsen et al. in CRYPTO 2022.

Prior work on YOSO public randomness generation with worst-case corruptions designed information-theoretic protocols for $t$ corruptions with either $n=6t+1$ or $n=5t$ roles, depending on the adversarial network model.

However, a major drawback of these protocols is that their communication and computational complexities scale exponentially with $t$.

In this work, we complement prior inefficient results by presenting and analyzing simple and efficient protocols for YOSO public randomness generation secure against worst-case corruptions in the computational setting.

Our first protocol is based on publicly verifiable secret sharing and uses $n=3t+2$ roles.

Since this first protocol requires setup and somewhat heavy cryptographic machinery, we also provide a second lighter protocol based on ElGamal commitments and verifiable secret sharing which uses $n=5t+4$ or $n=4t+4$ roles depending on the underlying network model. We demonstrate the practicality of our second protocol by showing experimental evaluations, significantly improving over prior proposed solutions for worst-case corruptions, especially in terms of transmitted data size.

The formal verification of architectural strength in terms of computational complexity is achieved through reduction of the Non-Commutative Grothendieck problem in the form of a quadratic lattice. This multivariate form relies on equivalences derived from a k-clique problem within a multigraph. The proposed scheme reduces the k-clique problem as an input function, resulting in the generation of a quadratic used as parameters for the lattice. By Grothendieck’s inequality, the satisfiability of lattice constraints in terms of NP-Hard and NP-Complete bounds is provably congruent to a closest vector problem in the lattice. The base vectors of the resulting lattice are treated as a holomorphic vector bundle. From the resulting bilinear matrices, the tight hardness reduction of the closest vector problem as the shortest vector problem is introduced within the system. The derivation of the closest vector problem requires that the lattice is necessarily generated by a <0|1>-Matrix expressed as a quadratic. This vector bundle is denoted as the unit ball with congruent topology to the Riemann sphere, symbolized as ?. For the Grothendieck constraints, the relative vector norms necessarily result in satisfaction of NP-Hard requirements for shortest vector problems in the lattice.

Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the network topology from within a given class of graphs. Although broadcast is a privacy-free task, it is known that THB for certain graph classes necessitates computational assumptions, even against "honest but curious" adversaries, and even given a single corrupted party. Recent works have tried to understand when THB can be obtained with information-theoretic (IT) security (without cryptography or setup assumptions) as a function of properties of the corresponding graph class.

We revisit this question through a case study of the class of wheel graphs and their subgraphs. The $n$'th wheel graph is established by connecting $n$ nodes who form a cycle with another "center" node, thus providing a natural extension that captures and enriches previously studied graph classes in the setting of IT-THB.

We present a series of new findings in this line. We fully characterize feasibility of IT-THB for any class of subgraphs of the wheel, each possessing an embedded star (i.e., a well-defined center connected to all other nodes). Our characterization provides evidence that IT-THB feasibility may correlate with a more fine-grained degree structure---as opposed to pure connectivity---of the corresponding graphs. We provide positive results achieving perfect IT-THB for new graph classes, including ones where the number of nodes is unknown. Further, we provide the first feasibility of IT-THB on non-degenerate graph-classes with $t>1$ corruptions, for the class of friendship graphs (Erdos, Renyi, Sos '66).

This paper surveys interactions between choices of elliptic curves and the security of elliptic-curve cryptography. Attacks considered include not just discrete-logarithm computations but also attacks exploiting common implementation pitfalls.

Lookup arguments have recently attracted a lot of developments due to their applications in the constructions of succinct non-interactive arguments of knowledge (SNARKs). A closely related topic is subsequence arguments in which one can prove that string $\mathbf{s}$ is a subsequence of another string $\mathbf{t}$, i.e., deleting some characters in $\mathbf{t}$ can achieve $\mathbf{s}$. A dual notion, namely, non-subsequence arguments, is to prove that $\mathbf{s}$ is not a subsequence of $\mathbf{t}$. These problems have a lot of important applications in DNA sequence analysis, internet of things, blockchains, natural language processing, speech recognition, etc. However, despite their applications, they are not well-studied in cryptography, especially succinct arguments for non-subsequences with efficient proving time and sublinear verification time.

In this work, we propose the first succinct non-subsequence argument. Our solution applies the sumcheck protocol and is instantiable by any multivariate polynomial commitment schemes (PCSs). We achieve an efficient prover whose running time is linear in the size of sequences $\mathbf{s}$, $\mathbf{t}$ and their respective alphabet $\Sigma$. Our proof is succinct and the verifier time is sublinear assuming the employed PCS has succinct commitments and sublinear verification time. When instantiating with Sona PCS (EUROCRYPT'24), we achieve proof size $\mathcal{O}(\log_2|\mathbf{s}| + \log_2|\mathbf{t}|+\log_2|\Sigma|)$, prover time $\mathcal{O}(|\mathbf{s}|+|\mathbf{t}|+|\Sigma|)$ and verifier time $\mathcal{O}(\sqrt{|\mathbf{s}|}+\sqrt{|\mathbf{t}|}+\sqrt{|\Sigma|})$.

Extending our technique, we can achieve a batch subsequence argument for proving in batch $k$ interleaving subsequence and non-subsequence arguments without proof size suffering a linear blow-up in $k$.

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. In 2002, Elkamchouchi, Elshenawy and Shaban introduced an RSA-like cryptosystem that uses the key equation $ed - k (p^2-1)(q^2-1) = 1$, instead of the classical RSA key equation $ed - k (p-1)(q-1) = 1$. Another variant of RSA, presented in 2017 by Murru and Saettone, uses the key equation $ed - k (p^2+p+1)(q^2+q+1) = 1$. Despite the authors' claims of enhanced security, both schemes remain vulnerable to adaptations of common RSA attacks. Let $n$ be an integer. This paper proposes two families of RSA-like encryption schemes: one employs the key equation $ed - k (p^n-1)(q^n-1) = 1$ for $n > 0$, while the other uses $ed - k [(p^n-1)(q^n-1)]/[(p-1)(q-1)] = 1$ for $n > 1$. Note that we remove the conventional assumption of primes having equal bit sizes. In this scenario, we show that regardless of the choice of $n$, continued fraction-based attacks can still recover the secret exponent. Additionally, this work fills a gap in the literature by establishing an equivalent of Wiener's attack when the primes do not have the same bit size.