International Association
for Cryptologic Research

Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson (JACM'91), zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments. In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action (Eurocrypt’22). We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We consider three representations: arithmetic circuits, rank-1 constraint systems and branching programs. This work gives the first attempt at constructing a post-quantum generic proof system from isogeny assumptions (the group action DDH problem). Though the resulting proof systems are linear in the circuit size, they possess interesting features such as non-interactivity, statistical zero-knowledge, and online-extractability.

In 2012, Ding, Xie and Lin designed a key exchange protocol based on Ring-LWE problem, called the DXL key exchange protocol, which can be seen as an extended version of the Diffie-Hellman key exchange. In this protocol, Ding et al. achieved key exchange between the communicating parties according to the associativity of matrix multiplications, that is, $(x^T\cdot A)\cdot y = x^T\cdot (A\cdot y)$, where $x,y$ are column vectors and $A$ is a square matrix. However, the DXL key exchange protocol cannot resist key reuse attacks. At ESORICS 2022, Qin et al. proposed a method that an adversary can recover the reused private key after forging the public keys for several times. Nevertheless, Qin et al.'s method leads to a lot of redundant operations. In this paper, we improve Qin et al.'s method to a more general case and propose an effective approach to combine signal leakage attacks with depth first search. Compared with state-of-the-art result appeared at ESORICS 2022, the number of reused private key have been decreased from 29 to 10. In other words, if the number of reuses exceeds 10, the private key will be restored. Moreover, we validate the effectiveness of the results through experiments.

The Boolean map $\chi_n \colon \mathbb{F}_2^n \to \mathbb{F}_2^n,\ x \mapsto y$ defined by $y_i = x_i + (x_{i+1}+1)x_{i+2}$ (where $i\in \mathbb{Z}/n\mathbb{Z}$) is used in various permutations that are part of cryptographic schemes, e.g., Keccak-f (the SHA-3-permutation), ASCON (the winner of the NIST Lightweight competition), Xoodoo, Rasta and Subterranean (2.0). In this paper, we study various algebraic properties of this map. We consider $\chi_n$ (through vectorial isomorphism) as a univariate polynomial. We show that it is a power function if and only if $n=1,3$. We furthermore compute bounds on the sparsity and degree of these univariate polynomials, and the number of different univariate representations. Secondly, we compute the number of monomials of given degree in the inverse of $\chi_n$ (if it exists). This number coincides with binomial coefficients. Lastly, we consider $\chi_n$ as a polynomial map, to study whether the same rule ($y_i = x_i + (x_{i+1}+1)x_{i+2}$) gives a bijection on field extensions of $\mathbb{F}_2$. We show that this is not the case for extensions whose degree is divisible by two or three. Based on these results, we conjecture that this rule does not give a bijection on any extension field of $\mathbb{F}_2$.

Several key exchange protocols based on tropical circulant matrices were proposed in the last two years. In this paper, we show that protocols offered by M. Durcheva [M. I. Durcheva. TrES: Tropical Encryption Scheme Based on Double Key Exchange. In: Eur. J. Inf. Tech. Comp. Sci. 2.4 (2022), pp. 11–17], by B. Amutha and R. Perumal [B. Amutha and R. Perumal. Public key exchange protocols based on tropical lower circulant and anti-circulant matrices. In: AIMS Math. 8.7 (2023), pp. 17307–17334.], and by H. Huang, C. Li, and L. Deng [H. Huang, C. Li, and L. Deng. Public-Key Cryptography Based on Tropical Circular Matrices. In: Appl. Sci. 12.15 (2022), p. 7401] are insecure.

Private Set Intersection Cardinality(PSI-CA) is a type of secure two-party computation. It enables two parties, each holding a private set, to jointly compute the cardinality of their intersection without revealing any other private information about their respective sets.

In this paper, we manage to break two PSI-CA protocols by recovering the specific intersection items in polynomial time. Among them, the PSI-CA protocol proposed by De Cristofaro et al. in 2012 is the most popular PSI-CA protocol based on the Google Scholar search results and it is still deemed one of the most efficient PSI-CA protocols.

In this paper, we also propose several solutions to these protocols' security problems.

Interactive Oracle Proof of Proximity (IOPPs) are a powerful tool for constructing succinct non-interactive arguments of knowledge (SNARKs) in the random oracle model, which are fast and plausibly post-quantum secure. The Fast Reed Solomon IOPP (FRI) is the most widely used in practice, while tensor-code IOPPs (such as Brakedown) achieve significantly faster prover times at the cost of much larger proofs. IOPPs are used to construct polynomial commitment schemes (PCS), which are not only an important building block for SNARKs but also have a wide range of independent applications.

This work introduces Basefold, a generalization of the FRI IOPP to a broad class of linear codes beyond Reed-Solomon, which we call $\textit{foldable linear codes}$. We construct a new family of foldable linear codes, which are a special type of randomly punctured Reed-Muller code, and prove tight bounds on their minimum distance. Finally, we introduce a new construction of a multilinear PCS from any foldable linear code, which is based on interleaving Basefold with the classical sumcheck protocol for multilinear polynomial evaluation. As a special case, this gives a new multilinear PCS from FRI.

In addition to these theoretical contributions, the Basefold PCS instantiated with our new foldable linear codes offers a more reasonable tradeoff between prover time, proof size, and verifier time than prior constructions. For instance, for polynomials over a $64$-bit field with $12$ variables, the Basefold prover is faster than both Brakedown and FRI-PCS ($2$ times faster than Brakedown and $3$ times faster than FRI-PCS), and its proof is $4$ times smaller than Brakedown's. On the other hand, for polynomials with $25$ variables, Basefold's prover is $6.5$ times faster than FRI-PCS, it's proof is $2.5$ times smaller than Brakedown's and its verifier is $7.5$ times faster. Using Basefold to compile the Hyperplonk PIOP [CBBZ23] results in an extremely fast implementation of Hyperplonk, which in addition to having competitive performance on general circuits, is particularly fast for circuits with high-degree custom gates (e.g., signature verification and table lookups). Hyperplonk with Basefold is approximately equivalent to the speed of Hyperplonk with Brakedown, but with a proof size that is more than $5$ times smaller. Finally, Basefold maintains performance across a wider variety of field choices than FRI, which requires FFT-friendly fields. Thus, Basefold can have an extremely fast prover compared to SNARKs from FRI for special applications. Benchmarking a circom ECDSA verification circuit with curve secp256k1, Hyperplonk with Basefold has a prover time that is more than $200\times$ faster than with FRI and its proof size is $5.8$ times smaller than Hyperplonk with Brakedown.

Event date: 5 March to 8 March 2024
Submission deadline: 15 November 2023
Notification: 22 December 2023

Event date: 8 March 2024
Submission deadline: 15 December 2023
Notification: 12 January 2024

Healthcare sector specifically remote healthcare sector depends on existing technical solutions that enable patients and healthcare professionals to interact. Though network security is not a new topic, but the specific demands of this sector cannot be met by existing solutions. There is a scope of further development that will help the sector grow more and impact the society in a positive way. Our experience during Covid time showed us the importance of remote healthcare. The problem with remote healthcare is that we need to provide health care securely to every patient. For this, we need to consider data collection from different sensors from patients and how to securely send that to a secure server. Also, we need to consider how drug delivery, or any other instruction is received from a secure server and delivered to patient's sensors. Our task is to improve the trust on the existing system and build new systems such that the remote healthcare sector can improve the lives more effectively. This proposed project aims to develop solutions to help solve some existing problems like remote authentication and secure drug delivery. In this project the student will investigate the existing network solutions and embedded architectures to ensure security of health-related data. This will involve exploring the IoT solutions that are currently available to understand their current limitations. The student will propose and implement novel architectural solutions. The target will be to propose one or more of the following to ensure security in the network and establishment of trust on the overall system using hardware security - new processor pipeline, new memory management unit, new on-chip network routers for multi-processor systems, new cache design, new memory controller etc. FPGA board-based development is a part of this work. In addition, the student will also implement required changes to compilers and/or operating systems needed to run applications on the proposed architecture and also to test the security both for the particular node and also for the whole network connected system.

Closing date for applications:

Contact: Arnab Kumar Biswas

More information: https://www.qub.ac.uk/courses/postgraduate-research/phd-opportunities/remote-healthcare-security.html

Traditional satellite communication network involves mainly two or three segments – the satellite, ground station and possible ground users. This method of communication has several disadvantages from resource usage point of view. As a solution, federated satellite system concept is introduced. Under this concept, several satellites from different organisations can form a satellite constellation system and cooperate to increase resource utilization under a profitable business agreement (e.g., usage-based pricing). This cooperation model is further extended by multi-tenant spacecraft concept where several users can reuse the resources of same spacecraft. But all these scenarios also require robust security solutions so that malicious actors cannot profit from any existing vulnerabilities in the whole system for example during routing, network access, and handover. This project aims to solve this security problem and to help the sector to grow further. In this project, the student will develop novel computer architecture required to support the security protocols proposed and/or standardized by CCSDS and will also propose new protocols. The student will also work on Software defined Satellite networking to enable programmability and reconfigurability of the system. The work will involve design of novel computer architecture and/or novel operating system and/or novel multiparty security protocol.

Closing date for applications:

Contact: Arnab Kumar Biswas

More information: https://www.qub.ac.uk/courses/postgraduate-research/phd-opportunities/secure-satellite-constellation-system.html

The CWI Cryptology Group in Amsterdam, The Netherlands has several openings for post-doc positions, with an inital 2-yr appointment.

We invite candidates with a strong (published) research record in (applied or theoreretical) cryptology and with a PhD in mathematics or computer science to apply. All areas of research covered by the Group are eligible.

The senior research staff of the CWI Cryptology Group consists of Ronald Cramer (head), Leo Ducas, Serge Fehr, Lisa Kohl, Marc Stevens, and Thomas Attema (part-time).

Each position is with a flexible starting date, available as of immediately. Applications will be reviewed continuously until the positions are filled.

All applications should include a motivation letter, a detailed resume (including a list of publications), a research statement (max 2 pages) discussing prior, current and future research, and the names of at least three references.

Closing date for applications:

Contact: Ronald Cramer (cramer@cwi.nl, cramer@math.leidenuniv.nl)

Security proofs of symmetric-key primitives typically consider an idealized world with access to a (uniformly) random function. The starting point of our work is the observation that such an ideal world leads to underestimating the actual security of certain primitives. As a demonstrating example, $\mathsf{XoP2}$, which relies on two independent random permutations, is proven to exhibit far superior concrete security compared to $\mathsf{XoP}$, which employs a single permutation with domain separation. But the main reason for this is an artifact of the idealized model used in the proof, in particular, that (in the random-function-ideal world) $\mathsf{XoP}$ might hit a trivially bad event (outputting 0) which does not occur in the real/domain-separated world. Motivated by this, we put forth the analysis of such primitives in an updated ideal world, which we call the {\em fine-tuned} setting, where the above artifact is eliminated. We provide fine-tuned (and enhanced) security analyses for $\mathsf{XoP}$ and $\mathsf{XoP}$-based MACs: $\mathsf{nEHtM}$ and $\mathsf{DbHtS}$. Our analyses demonstrate that the security of $\mathsf{XoP}$-based and $\mathsf{XoP2}$-based constructions are, in fact, far more similar than what was previously proven. Concretely, for the number of users $u$ and the maximum number of queries per user $q_m$, we show that the multi-user ``fine-tuned'' security bound of $\mathsf{XoP}$ can be proven as $O\left({u^{0.5}{q_m}^{2}}/{2^{2n}}\right)$ via the Squared-ratio method proposed by Chen et al. [CRYPTO'23], resulted to the same security bound of $\mathsf{XoP2}$ proven there. We also show the compatibility of the fine-tuned model with the Chi-squared method proposed by Dai et al. [CRYPTO'17], and show that $\mathsf{XoP}$ and $\mathsf{XoP2}$ enjoy the same security bound in the fine-tuned setting regardless of proving tools. Finally, we turn to the security analysis of MACs in the multi-user setting, where the effect of transitioning the proofs to the fine-tuned setting is even higher. Concretely, we are able to prove unexpected improvements in the security bounds for both $\mathsf{nEHtM}$ and $\mathsf{DbHtS}$. Our security proofs rely on a fine-tuned and extended version of Mirror theory for both lower and upper bounds, which yields more versatile and improved security proofs. Of independent interest, this extension allows us to prove the multi-user MAC security of $\mathsf{nEHtM}$ in the nonce-misuse model, while the previous analysis only applied to the multi-user PRF security in the nonce-respecting model. As a side note, we also point out (and fix) a flaw in the original analysis of Chen et al..

When outsourcing a database to an untrusted remote server, one might want to verify the integrity of contents while accessing it. To solve this, Blum et al. [FOCS `91] propose the notion of memory checking. Memory checking allows a user to run a RAM program on a remote server, with the ability to verify integrity of the storage with small local storage. In this work, we define and initiate the formal study of memory checking for Parallel RAMs (PRAMs). The parallel RAM model is very expressive and captures many modern architectures such as multi-core architectures and cloud clusters. When multiple clients run a PRAM algorithm on a shared remote server, it is possible that there are concurrency issues that cause inconsistencies. Therefore, integrity verification is even more desirable property in this setting. Assuming only the existence of one-way functions, we construct an online memory checker (one that reports faults as soon as they occur) for PRAMs with $O(\log N)$ simulation overhead in both work and depth. In addition, we construct an offline memory checker (one that reports faults only after a long sequence of operations) with amortized $O(1)$ simulation overhead in both work and depth. Our constructions match the best known simulation overhead of the memory checkers in the standard single-user RAM setting. As an application of our parallel memory checking constructions, we additionally construct the first maliciously secure oblivious parallel RAM (OPRAM) with polylogarithmic overhead.

Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness (SS-NIZK), that allows the adversary to access the simulator in superposition. We show a separation between post-quantum and quantum security of SS-NIZK, and prove that both Sahai’s construction for SS-NIZK (in the CRS model) and the Fiat-Shamir transformation (in the QROM) can be made quantumly-simulation-sound. As an immediate application of our new notion, we prove the security of the Naor-Yung paradigm in the quantum settings, with respect to a strong quantum IND-CCA security notion. This provides the quantum analogue of the classical dual key approach to prove the security of encryption schemes. Along the way, we introduce a new notion of quantum-query advantage functions, which may be used as a general framework to show classical/quantum separation for other cryptographic primitives, and it may be of independent interest.

Integral, zero-correlation (ZC), and impossible-differential (ID) attacks are three of the most important attacks on block ciphers. However, manually finding these attacks can be a daunting task, which is why automated methods are becoming increasingly important. Most of the automatic tools regarding integral, ZC and ID attacks have been focused only on finding distinguishers rather than complete attacks. At EUROCRYPT 2023, Hadipour et al. proposed a generic and efficient constraint programming (CP) model based on satisfiability for finding ID, ZC, and integral distinguishers. This new model can be extended to a unified CP model for finding full key recovery attacks. However, their method has some limitations, including the fact that the location of contradiction should be determined in advance, and the model is a cell-wise model unsuitable for weakly aligned ciphers, e.g., Ascon and PRESENT. In addition, they left developing a CP model for the partial-sum technique in key recovery as a future work.

In this paper, we improve the method by Hadipour et al. in several ways. First, we remove the limitation of determining the contradiction location in advance. Second, we show how to extend the distinguisher model to a bit-wise model, considering the internal structure of S-boxes and keeping the model based on satisfiability. Third, we introduce a CP model for the partial-sum technique for the first time. To show the usefulness and versatility of our approach, we applied it to different designs, from strongly aligned designs such as ForkSKINNY and QARMAv2 to weakly aligned designs such as Ascon and PRESENT, obtaining significantly improved results. To mention a few of our results, we improve the integral distinguisher of QARMAv2-128 (resp. QARMAv2-64) by 7 (resp. 5) rounds, and the integral distinguisher of ForkSKINNY by 1 round, only thanks to our cell-wise distinguisher modelings. By using our new bit-wise modeling, our tool can find a group of $2^{155}$ 5-round ID and ZC distinguishers for Ascon in only one run, taking a few minutes on a regular laptop. Thanks to the new CP model for the partial-sum technique, we could improve the integral attacks on all variants of SKINNY. Particularly, we improved the best attack on SKINNY-$n$-$n$ in the single-key setting by 1 round. We also improved the ID attacks on ForkSKINNY and analyzed this cipher in the limited reduced-round setting for the first time. Our methods are generic and applicable to other block ciphers.

Protocols for secure multi-party computation (MPC) supporting mixed-mode computation have found a lot of applications in recent years due to their flexibility in representing the function to be evaluated. However, existing mixed-mode MPC protocols are only practical for a small number of parties: they are either tailored to the case of two/three parties, or scale poorly for a large number of parties. In this paper, we design and implement a new system for highly efficient and scalable mixed-mode MPC tolerating an arbitrary number of semi-honest corruptions. Our protocols allow secret data to be represented in Encrypted, Boolean, Arithmetic, or Yao form, and support efficient conversions between these representations. 1. We design a multi-party table-lookup protocol, where both the index and the table can be kept private. The protocol is scalable even with hundreds of parties. 2. Using the above protocol, we design efficient conversions between additive arithmetic secret sharings and Boolean secret sharings for a large number of parties. For 32 parties, our conversion protocols require 1184× to 8141× less communication compared to the state- of-the-art protocols MOTION and MP-SPDZ; this leads to up to 1275× improvement in running time under 1 Gbps network. The improvements are even larger with more parties. 3. We also use new protocols to design an efficient multi-party distributed garbling protocol. The protocol could achieve asymptotically constant communication per party.

Our implementation will be made public.

In this paper, we introduce Oblivious Homomorphic Encryption (OHE) which provably separates the computation spaces of multiple clients of a fully homomorphic encryption (FHE) service while keeping the evaluator blind about whom a result belongs. We justify the importance of this strict isolation property of OHE by showing an attack on a recently proposed key-private cryptocurrency scheme. Our two OHE constructions are based on a puncturing function where the evaluator can effectively mask ciphertexts from rogue and potentially colluding clients. We show that this can be implemented via a FHE scheme plus an anonymous commitment scheme. OHE can be used to provide provable anonymity to cloud applications, to single server implementations of anonymous messaging as well as to account-based cryptocurrencies.

The idea of balancing the side-channel leakage in software was proposed more than a decade ago. Just like with other hiding-based countermeasures, the goal is not to hide the leakage completely but to significantly increase the effort required for the attack. Previous approaches focused on two directions: either balancing the Hamming weight of the processed data or deriving the code by using stochastic leakage profiling.

In this brief, we build upon these results by proposing a novel approach that combines the two directions. We provide the theory behind our encoding scheme backed by experimental results on a 32-bit ARM Cortex-M4 microcontroller. Our results show that such a combination gives better side-channel resistance properties than each of the two methods separately.

This paper presents full round distinguishing and key recovery attacks on lightweight block cipher SAND-2 with 64-bit block size and 128-bit key size, which appears to be a mixture of the AND-Rotation-XOR (AND-RX) based ciphers SAND and ANT. However, the security arguments against linear and some other attacks are not fully provided. In this paper, we find that the combination of a SAND-like nibble-based round function and ANT-like bit-based permutations will cause dependencies and lead to iterative linear and differential trails with high probabilities. By exploiting these, full round distinguishing attacks on SAND-2 work with $2^{46}$ queries for linear and $2^{58.60}$ queries for differential in the single-key setting. Then, full round key recovery attacks are also mounted, which work with the time complexity $2^{48.23}$ for linear and $2^{64.10}$ for differential. It should be noted that the dependency observed in this paper only works for SAND-2 and will not threaten SAND and ANT. From the point of designers, our attacks show the risk of mixing the parts of different designs, even though each of them is well-studied to be secure.

We show that the Yang et al.'s key agreement scheme [Future Gener. Comput. Syst., 145, 415-428 (2023)] is flawed. (1) There are some inconsistent computations, which should be corrected. (2) The planned route of a target vehicle is almost exposed. The scheme neglects the basic requirement for bit-wise XOR, and tries to encrypt the route by the operator. The negligence results in some trivial equalities. (3) The scheme is insecure against impersonation attack launched by the next roadside unit.