IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
08 May 2023
Jakob Burkhardt, Ivan Damgård, Tore Frederiksen, Satrajit Ghosh, Claudio Orlandi
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.
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.
Ning Luo, Chenkai Weng, Jaspal Singh, Gefei Tan, Ruzica Piskac, Mariana Raykova
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.
- 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.
Sylvain Chatel, Christian Mouchet, Ali Utkan Sahin, Apostolos Pyrgelis, Carmela Troncoso, Jean-Pierre Hubaux
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.
Charles Gouert, Vinu Joseph, Steven Dalton, Cedric Augonnet, Michael Garland, Nektarios Georgios Tsoutsos
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.
Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, Benjamin Wesolowski
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.
Lena Heimberger, Fredrik Meisingseth, Christian Rechberger
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.
Shahram Rasoolzadeh
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.
Jean Liénardy
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.
Gustavo Banegas, Florian Caullery
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.
Schwinn Saereesitthipitak, Dionysis Zindros
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.
Sreyosi Bhattacharyya, Kaushik Nath, Palash Sarkar
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%.
04 May 2023
University of Klagenfurt, Klagenfurt, Austria
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/
L'Aquila, Italy, 25 July - 29 July 2023
Event date: 25 July to 29 July 2023
Submission deadline: 15 May 2023
Notification: 15 May 2023
Submission deadline: 15 May 2023
Notification: 15 May 2023
Stanford, United States, 28 August - 30 August 2023
Event date: 28 August to 30 August 2023
Submission deadline: 11 May 2023
Notification: 26 June 2023
Submission deadline: 11 May 2023
Notification: 26 June 2023
Luxemburg, Luxemburg, 3 October - 6 October 2023
Event date: 3 October to 6 October 2023
Submission deadline: 15 May 2023
Submission deadline: 15 May 2023
Berlin, Germany, 23 July - 25 July 2023
Event date: 23 July to 25 July 2023
Submission deadline: 12 May 2023
Notification: 1 June 2023
Submission deadline: 12 May 2023
Notification: 1 June 2023
Srivilliputtur, India, 2 January - 7 January 2024
Event date: 2 January to 7 January 2024
Submission deadline: 30 June 2023
Notification: 30 September 2023
Submission deadline: 30 June 2023
Notification: 30 September 2023
03 May 2023
Anubhab Baksi, Sylvain Guilley, Ritu-Ranjan Shrivastwa, Sofiane Takarabt
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.
Jung Hee Cheon, Minsik Kang, Taeseong Kim, Junyoung Jung, Yongdong Yeo
Secure Machine Learning as a Service is a viable
solution where clients seek secure delegation of
the ML computation while protecting their sensi-
tive data. We propose an efficient method to se-
curely evaluate deep standard convolutional neu-
ral networks based on CKKS fully homomorphic
encryption, in the manner of batch inference. In
this paper, we introduce a packing method called
Channel-by-Channel Packing that maximizes the
slot compactness and single-instruction-multiple-
data capabilities in ciphertexts. Along with fur-
ther optimizations such as lazy rescaling, lazy
Baby-Step Giant-Step, and ciphertext level man-
agement, we could significantly reduce the com-
putational cost of standard ResNet inference. Sim-
ulation results show that our work has improve-
ments in amortized time by 5.04× (from 79.46s
to 15.76s) and 5.20×(from 455.56s to 87.60s) for
ResNet-20 and ResNet-110, compared to the pre-
vious best results, resp. We also got a dramatic
reduction in memory usage for rotation keys from
several hundred GBs to 6.91GB, which is about
38× smaller than the previous result.
KeYi LIU, Chungen Xu, Bennian Dou
Homomorphic encryption can perform calculations on encrypted data, which can protect the privacy of data during the usage of data. Functional Bootstraps algorithm proposed by I. Chillotti et al. can compute arbitrary functions represented as lookup table whilst bootstrapping, but the computational efficiency of F unctional Bootstraps with large lookup table or highly precise functions is not high enough. To tackle this issue, we propose a new Tree-BML algorithm. Our Tree-BML algorithm accelerates the computation of F unctional Bootstraps with large LUT by compressing more LWE ciphertexts to a TRLWE ciphertext and utilizing the PBSmanyLUT algorithm which was proposed by I. Chillotti et al. in 2021. The Tree-BML algorithm reduces the running time of LUT computation by 72.09% compared to Tree-based method(Antonio Guimarães et al., 2021). Additionally, we introduce a new TLWE-to-TRLWE Packing Key Switching algorithm which reduces the storage space required and communication overhead of homomorphic encryption algorithm by only generating one of those key-switching key ciphertexts of polynomials with the same non-zero coefficient values but only those values located in different slots. Our algorithm reduces the key-switching key size by 75% compared to Base-aware TLWE-to-TRLWE Key Switching algorithm. Finally, we obtained that our algorithms does not introduce new output error through theoretical and experiment result.