International Association
for Cryptologic Research

We remark that the key agreement scheme [IEEE Internet Things J., 8(5), 2021, 3801--3811] is flawed. (1) It is insecure against internal attack, because any unauthorized sensing device (not revoked) can retrieve the final session key. (2) It could be insecure against external attack.

The functional bootstrap in FHEW/TFHE allows for fast table lookups on ciphertexts and is a powerful tool for privacy-preserving computations. However, the functional bootstrap suffers from two limitations: the negacyclic constraint of the lookup table (LUT) and the limited ability to evaluate large-precision LUTs. To overcome the first limitation, several full-domain functional bootstraps (FDFB) have been developed, enabling the evaluation of arbitrary LUTs. Meanwhile, algorithms based on homomorphic digit decomposition have been proposed to address the second limitation. Although these algorithms provide effective solutions, they are yet to be optimized. This paper presents four new FDFB algorithms and two new homomorphic decomposition algorithms that improve the state-of-the-art. Our FDFB algorithms reduce the output noise, thus allowing for more efficient and compact parameter selection. Across all parameter settings, our algorithms reduce the runtime by up to $39.2\%$. Furthermore, our FDFB algorithms introduce an error that can be as small as 1/15 of that introduced by previous algorithms when evaluating continuous functions. Our homomorphic decomposition algorithms also run at 2.0x and 1.5x the speed of prior algorithms. We have implemented and benchmarked all previous FDFB and homomorphic decomposition algorithms and our methods in OpenFHE.

Secure distributed generation of RSA moduli (e.g., generating $N=pq$ where none of the parties learns anything about $p$ or $q$) is an important cryptographic task, that is needed both in threshold implementations of RSA-based cryptosystems and in other, advanced cryptographic protocols that assume that all the parties have access to a trusted RSA modulo. In this paper, we provide a novel protocol for secure distributed RSA key generation based on the Miller-Rabin test. Compared with the more commonly used Boneh-Franklin test (which requires many iterations), the Miller-Rabin test has the advantage of providing negligible error after even a single iteration of the test for large enough moduli (e.g., $4096$ bits).

From a technical point of view, our main contribution is a novel divisibility test which allows to perform the primality test in an efficient way, while keeping $p$ and $q$ secret.

Our semi-honest RSA generation protocol uses any underlying secure multiplication protocol in a black-box way, and our protocol can therefore be instantiated in both the honest or dishonest majority setting based on the chosen multiplication protocol. Our semi-honest protocol can be upgraded to protect against active adversaries at low cost using existing compilers. Finally, we provide an experimental evaluation showing that for the honest majority case, our protocol is much faster than Boneh-Franklin.

Motivated by the privacy requirements in network intrusion detection and DNS policy checking, we have developed a suite of protocols and algorithms for regular expression matching with enhanced privacy:

- A new regular expression matching algorithm that is oblivious to the input strings, of which the complexity is only $O(mn)$ where $m$ and $n$ are the length of strings and the regular expression respectively. It is achieved by exploiting the structure of the Thompson nondeterministic automata. - A zero-knowledge proof of regular expression pattern matching in which a prover generates a proof to demonstrate that a public regular expression matches her input string without revealing the string itself. -Two secure-regex protocols that ensure the privacy of both the string and regular expression. The first protocol is based on the oblivious stack and reduces the complexity of the state-of-the-art from $O(mn^2)$ to $O(mn\log n)$. The second protocol relies on the oblivious transfer and performs better empirically when the size of regular expressions is smaller than $2^{12}$.

We also evaluated our protocols in the context of encrypted DNS policy checking and intrusion detection and achieved 4.5X improvements over the state-of-the-art. These results also indicate the practicality of our approach in real-world applications.

Multiparty fully homomorphic encryption (MFHE) schemes enable multiple parties to efficiently compute functions on their sensitive data while retaining confidentiality. However, existing MFHE schemes guarantee data confidentiality and the correctness of the computation result only against honest-but-curious adversaries. In this work, we provide the first practical construction that enables the verification of MFHE operations in zero-knowledge, protecting MFHE from malicious adversaries. Our solution relies on a combination of lattice-based commitment schemes and proof systems which we adapt to support both modern FHE schemes and their implementation optimizations. We implement our construction in PELTA. Our experimental evaluation shows that PELTA is one to two orders of magnitude faster than existing techniques in the literature.

Fully Homomorphic Encryption (FHE) is a cryptographic method that guarantees the privacy and security of user data during computation. FHE algorithms can perform unlimited arithmetic computations directly on encrypted data without decrypting it. Thus, even when processed by untrusted systems, confidential data is never exposed. In this work, we develop new techniques for accelerated encrypted execution and demonstrate the significant performance advantages of our approach. Our current focus is the Fully Homomorphic Encryption over the Torus (CGGI) scheme, which is a current state-of-the-art method for evaluating arbitrary functions in the encrypted domain. CGGI represents a computation as a graph of homomorphic logic gates and each individual bit of the plaintext is transformed into a polynomial in the encrypted domain. Arithmetic on such data becomes very expensive: operations on bits become operations on entire polynomials. Therefore, evaluating even relatively simple nonlinear functions, such as a sigmoid, can take thousands of seconds on a single CPU thread. Using our novel framework for end-to-end accelerated encrypted execution called ArctyrEX, developers with no knowledge of complex FHE libraries can simply describe their computation as a C program that is evaluated over 40x faster on an NVIDIA DGX A100 and 6x faster with a single A100 relative to a 256-threaded CPU baseline.

We present an attack on SIDH utilising isogenies between polarized products of two supersingular elliptic curves. In the case of arbitrary starting curve, our attack (discovered independently from [CD22]) has subexponential complexity, thus significantly reducing the security of SIDH and SIKE. When the endomorphism ring of the starting curve is known, our attack (here derived from [CD22]) has polynomial-time complexity assuming the generalised Riemann hypothesis. Our attack applies to any isogeny-based cryptosystem that publishes the images of points under the secret isogeny, for example SÉTA and B-SIDH. It does not apply to CSIDH, CSI-FiSh, or SQISign.

Oblivious Pseudorandom Functions are an elementary building block in cryptographic and privacy-preserving applications. However, while there are numerous pre-quantum secure OPRF constructions, few options exist in a post-quantum secure setting. Isogeny group actions and the associated low bandwidth seem like a promising candidate to construct a quantum-resistant OPRF. While there have been relevant attacks on isogeny-related hardness assumptions, the commutative CSIDH is unaffected. In this work, we propose OPUS, a novel OPRF with small communication complexity, requiring only CSIDH as the security assumption. Our results also revisit the Naor-Reingold OPRF from CSIDH and show how to efficiently compute offline evaluations. Additionally, we analyze a previous proposal of a CSIDH-based instantiation of the Naor-Reingold construction. We report several issues with the straightforward instantiation of the protocol and propose mitigations to address those shortcomings. Our mitigations require additional hardness assumptions and more expensive computations but result in a competitive protocol with low communication complexity and few rounds. Our comparison against the state of the art shows that OPUS and the repaired, generic construction are competitive with other proposals in terms of speed and communication size. More concretely, OPUS achieves almost two orders of magnitude less communication overhead compared to the next-best lattice-based OPRF at the cost of higher latency and higher computational cost.

We apply Siegenthaler's construction, along with several techniques, to classify all $(n-4)$-resilient Boolean functions with $n$ variables, for all values of $n \geq 4$, up to extended variable-permutation equivalence. We show that, up to this equivalence, there are only 761 functions for any $n$ larger than or equal to 10, and for smaller values of $n$, i.e., for $n$ increasing from 4 to 9, there are 58, 256, 578, 720, 754, and 760 functions, respectively. Furthermore, we classify all 1-resilient 6-variable Boolean functions and show that there are 1035596784 such functions up to extended variable-permutation equivalence.

In this note, we identify a minor flaw in the design of the XOCB mode, presented at Eurocrypt '23. This vulnerability enables trivial tag forgeries and arises from the padding applied to messages. We examine the security proof and pinpoint the presence of the flaw within it. Furthermore, we propose a simple fix for this issue, drawing upon the features of OCB3, and discuss the implications of this modification on the proof of security.

Hash-based signatures are a type of Digital Signature Algorithms that are positioned as one of the most solid quantum-resistant constructions. As an example SPHINCS+, has been selected as a standard during the NIST Post-Quantum Cryptography competition. However, hash-based signatures suffer from two main drawbacks: signature size and slow signing process. In this work, we give a solution to the latter when it is used in a mobile device. We take advantage of the fact that hash-based signatures are highly parallelizable. More precisely, we provide an implementation of SPHINCS+ on the Snapdragon 865 Mobile Platform taking advantage of its eight CPUs and their vector extensions. Our implementation shows that it is possible to have a speed-up of 15 times when compared to a purely sequential and non-vectorized implementation. Furthermore, we evaluate the performance impact of side-channel protection using vector extensions in the SPHINCS+ version based on SHAKE.

Witness Encryption is a holy grail of cryptography that remains elusive. It asks that a secret is only revealed when a particular computational problem is solved. Modern smart contracts and blockchains make assumptions of “honest majority”, which allow for a social implementation of Witness Encryption. The core idea is to make use of a partially trusted committee to carry out the responsibilities mandated by these functionalities – such as keeping the secret private, and then releasing it publicly after a solution to the computational puzzle is presented. We implement Witness Encryption (with public witness security) in the form of an open source composable smart contract that can be utilized as an oracle by others within the broader DeFi ecosystem. We devise a cryptoeconomic scheme to incentivize honest participation, and analyze its security under the honest majority and rational majority settings. We conclude by measuring and optimizing gas costs and illustrating the practicality of our scheme.

This paper makes a comprehensive study of two important strategies for polynomial hashing over a prime order field $\mathbb{F}_p$, namely usual polynomial based hashing and hashing based on Bernstein-Rabin-Winograd (BRW) polynomials, and the various ways to combine them. Several hash functions are proposed and upper bounds on their differential probabilities are derived. Concrete instantiations are provided for the primes $p=2^{127}-1$ and $p=2^{130}-5$. A major contribution of the paper is an extensive 64-bit implementation of all the proposed hash functions in assembly targeted at modern Intel processors. The timing results suggest that using the prime $2^{127}-1$ is significantly faster than using the prime $2^{130}-5$. Further, a judicious mix of the usual polynomial based hashing and BRW-polynomial based hashing can provide a significantly faster alternative to only usual polynomial based hashing. In particular, the timing results of our implementations show that our final hash function proposal for the prime $2^{127}-1$ is much faster than the well known Poly1305 hash function defined over the prime $2^{130}-5$, achieving speed improvements of up to 40%.

The Cybersecurity Research Group is looking to expand. There is a job opportunity for a post-doctoral researcher who wishes to work in applied cryptography, including topics such as leakage resilience, secure implementations, side channels, or primitives for PETs, ZK, etc. The job includes a small teaching load (4hrs per week during term time), and it requires willingness to collaborate with members of the Digital Age Research Centre (across typical disciplinary boundaries). The starting salary is just over 60k (paid in 14 instalments), the starting date is negotiable (ideally no later than September 2023).

Closing date for applications:

Contact: Elisabeth.OswaldATaau.at

More information: https://jobs.aau.at/en/job/senior-scientist-all-genders-welcome-6/

Event date: 25 July to 29 July 2023
Submission deadline: 15 May 2023
Notification: 15 May 2023

Event date: 28 August to 30 August 2023
Submission deadline: 11 May 2023
Notification: 26 June 2023

Event date: 3 October to 6 October 2023
Submission deadline: 15 May 2023

Event date: 23 July to 25 July 2023
Submission deadline: 12 May 2023
Notification: 1 June 2023

Event date: 2 January to 7 January 2024
Submission deadline: 30 June 2023
Notification: 30 September 2023

With the escalating demand for lightweight ciphers as well as side channel protected implementation of those ciphers in recent times, this work focuses on two aspects. First, we present a tool for automating the task of finding a Threshold Implementation (TI) of a given Substitution Box (SBox). Our tool returns `with decomposition' and `without decomposition' based TI. The `with decomposition' based implementation returns a combinational SBox; whereas we get a sequential SBox from the `without decomposition' based implementation. Despite being high in demand, it appears that this kind of tool has been missing so far. Second, we show an algorithmic approach where a given cipher implementation can be tweaked (without altering the cipher specification) so that its TI cost can be significantly reduced. We take the PRESENT cipher as our case study (our methodology can be applied to other ciphers as well). Indeed, we show over 31 percent reduction in area and over 52 percent reduction in depth compared to the basic threshold implementation.