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:
03 January 2023
Antonio Guimarães, Hilder V. L. Pereira, Barry van Leeuwen
Micciancio and Sorrel (ICALP 2018) proposed a bootstrapping algorithm that can refresh many messages at once with sublinearly many homomorphic operations per message. However, despite the attractive asymptotic cost, it is unclear if their algorithm can be practical, which reduces the impact of their results. In this work, we follow their general framework, but propose an amortized bootstrapping that is conceptually simpler and asymptotically cheaper. We reduce the number of homomorphic operations per refreshed message from $O(3^\rho \cdot n^{1/\rho} \cdot \log n)$ to $O(\rho \cdot n^{1/\rho})$, and the noise overhead from $\tilde{O}(n^{2 + 3 \cdot \rho})$ to $\tilde{O}(n^{1.5 + \rho})$. To obtain a concrete instantiation of our bootstrapping algorithm, we propose a double-CRT (aka RNS) version of the GSW scheme, including a new operation, called shrinking, used to speed-up homomorphic operations by reducing the dimension and ciphertext modulus of the ciphertexts. We provide a C++ implementation of our algorithm, thus showing that the amortized bootstrapping is not only theoretical, but practical. Moreover, it is up to 2.7 times faster than an equivalent non-amortized version for the smallest parameter set we consider, and gains are expected to increase as the parameters increase.
Tako Boris Fouotsa, Tomoki Moriya, Christophe Petit
The SIDH protocol is an isogeny-based key exchange protocol using supersingular isogenies, designed by Jao and De Feo in 2011.
The protocol underlies the SIKE algorithm which advanced to the fourth round of NIST's post-quantum standardization project in May 2022.
The algorithm was considered very promising: indeed the most significant attacks against SIDH were meet-in-the-middle variants with exponential complexity, and torsion point attacks which only applied to unbalanced parameters (and in particular, not to SIKE).
This security picture dramatically changed in August 2022 with new attacks by Castryck-Decru, Maino-Martindale and Robert. Like prior attacks on unbalanced versions, these new attacks exploit torsion point information provided in the SIDH protocol. Crucially however, the new attacks embed the isogeny problem into a similar isogeny problem in a higher dimension to also affect the balanced parameters. As a result of these works, the SIKE algorithm is now fully broken both in theory and in practice.
Given the considerable interest attracted by SIKE and related protocols in recent years, it is natural to seek countermeasures to the new attacks. In this paper, we introduce two such countermeasures based on partially hiding the isogeny degrees and torsion point information in the SIDH protocol. We present a preliminary analysis of the resulting schemes including non-trivial generalizations of prior attacks. Based on this analysis we suggest parameters for our M-SIDH variant with public key sizes of 4434, 7037 and 9750 bytes respectively for NIST security levels 1, 3, 5.
This security picture dramatically changed in August 2022 with new attacks by Castryck-Decru, Maino-Martindale and Robert. Like prior attacks on unbalanced versions, these new attacks exploit torsion point information provided in the SIDH protocol. Crucially however, the new attacks embed the isogeny problem into a similar isogeny problem in a higher dimension to also affect the balanced parameters. As a result of these works, the SIKE algorithm is now fully broken both in theory and in practice.
Given the considerable interest attracted by SIKE and related protocols in recent years, it is natural to seek countermeasures to the new attacks. In this paper, we introduce two such countermeasures based on partially hiding the isogeny degrees and torsion point information in the SIDH protocol. We present a preliminary analysis of the resulting schemes including non-trivial generalizations of prior attacks. Based on this analysis we suggest parameters for our M-SIDH variant with public key sizes of 4434, 7037 and 9750 bytes respectively for NIST security levels 1, 3, 5.
Dimitris Mouris, Daniel Masny, Ni Trieu, Shubho Sengupta, Prasad Buddhavarapu, Benjamin Case
Private matching for compute (PMC) establishes a match between two databases owned by mutually distrusted parties ($C$ and $P$) and allows the parties to input more data for the matched records for arbitrary downstream secure computation without rerunning the private matching component. The state-of-the-art PMC protocols only support two parties and assume that both parties can participate in computationally intensive secure computation. We observe that such operational overhead limits the adoption of these protocols to solely powerful entities as small data owners or devices with minimal computing power will not be able to participate.
We introduce two protocols to delegate PMC from party $P$ to untrusted cloud servers, called delegates, allowing multiple smaller $P$ parties to provide inputs containing identifiers and associated values. Our Delegated Private Matching for Compute protocols, called DPMC and D$^S$PMC, establish a join between the databases of party $C$ and multiple delegators $P$ based on multiple identifiers and compute secret shares of associated values for the identifiers that the parties have in common. We introduce a novel rerandomizable encrypted oblivious pseudorandom function (OPRF) construction, called EO, which allows two parties to encrypt, mask, and shuffle their data and is secure against semi-honest adversaries. Note that EO may be of independent interest. Our D$^S$PMC protocol limits the leakages of DPMC by combining our novel EO scheme and secure three-party shuffling. Finally, our implementation demonstrates the efficiency of our constructions by outperforming related works by approximately $10\times$ for the total protocol execution and by at least $20\times$ for the computation on the delegators.
We introduce two protocols to delegate PMC from party $P$ to untrusted cloud servers, called delegates, allowing multiple smaller $P$ parties to provide inputs containing identifiers and associated values. Our Delegated Private Matching for Compute protocols, called DPMC and D$^S$PMC, establish a join between the databases of party $C$ and multiple delegators $P$ based on multiple identifiers and compute secret shares of associated values for the identifiers that the parties have in common. We introduce a novel rerandomizable encrypted oblivious pseudorandom function (OPRF) construction, called EO, which allows two parties to encrypt, mask, and shuffle their data and is secure against semi-honest adversaries. Note that EO may be of independent interest. Our D$^S$PMC protocol limits the leakages of DPMC by combining our novel EO scheme and secure three-party shuffling. Finally, our implementation demonstrates the efficiency of our constructions by outperforming related works by approximately $10\times$ for the total protocol execution and by at least $20\times$ for the computation on the delegators.
Sietse Ringers
We review the two RSA-based accumulators introduced by Camenisch and Lysyanskaya in 2002 in the setting of revocation for anonymous credential schemes, such as Idemix or BBS+. We show that in such a setting, the lower and upper bounds placed on the accumulated values in the paper are unnecessarily strict; they can be removed almost entirely (up to the group order of the credential scheme). This allows the accumulators to be used on elliptic curves of ordinary sizes, such as the ones on which BBS+ is commonly implemented. We also offer some notes and optimizations for implementations of anonymous credential schemes that use these accumulators to enable revocation.
Martin Brain, Carlos Cid, Rachel Player, Wrenna Robson
Developers of computer-aided cryptographic tools are optimistic that formal methods will become a vital part of developing new cryptographic systems. We study the use of such tools to specify and verify the implementation of Classic McEliece, one of the code-based cryptography candidates in the fourth round of the NIST Post-Quantum standardisation Process. From our case study we draw conclusions about the practical applicability of these methods to the development of novel cryptography.
Adi Akavia, Ben Galili, Hayim Shaul, Mor Weiss, Zohar Yakhini
With the development of sequencing technologies, viral strain classification -- which is critical for many applications, including disease monitoring and control -- has become widely deployed. Typically, a lab (client) holds a viral sequence, and requests classification services from a centralized repository of labeled viral sequences (server). However, such ``classification as a service'' raises privacy concerns.
In this paper we propose a privacy-preserving viral strain classification protocol that allows the client to obtain classification services from the server, while maintaining complete privacy of the client's viral strains. The privacy guarantee is against active servers, and the correctness guarantee is against passive ones. We implemented our protocol and performed extensive benchmarks, showing that it obtains almost perfect accuracy ($99.8\%$--$100\%$) and microAUC ($0.999$), and high efficiency (amortized per-sequence client and server runtimes of $4.95$ms and $0.53$ms, respectively, and $0.21$MB communication).
In addition, we present an extension of our protocol that guarantees server privacy against passive clients, and provide an empirical evaluation showing that this extension provides the same high accuracy and microAUC, with amortized per sequences overhead of only a few milliseconds in client and server runtime, and 0.3MB in communication complexity.
Along the way, we develop an enhanced packing technique in which two reals are packed in a single complex number, with support for homomorphic inner products of vectors of ciphertexts. We note that while similar packing techniques were used before, they only supported additions and multiplication by constants.
Mick G.D. Remmerswaal, Lichao Wu, Sébastien Tiran, Nele Mentens
Template attacks~(TAs) are one of the most powerful Side-Channel Analysis~(SCA) attacks. The success of such attacks relies on the effectiveness of the profiling model in modeling the leakage information. A crucial step for TA is to select relevant features from the measured traces, often called Points Of Interest~(POIs), to extract the leakage information. Previous research indicates that properly selecting the input leaking features could significantly increase the attack performance. However, due to the presence of SCA countermeasures and advancements in technology nodes, such features become increasingly difficult to extract with conventional approaches such as Principle Component Analysis (PCA) and the Sum Of Squared pairwise T-differences based method (SOST).
This work proposes a framework, AutoPOI, based on proximal policy optimization to automatically find, select, and scale down features. The input raw features are first grouped into small regions. The best candidates selected by the framework are further scaled down with an online-optimized dimensionality reduction neural network. Finally, the framework rewards the performance of these features with the results of TA. Based on the experimental results, the proposed framework can extract features automatically that lead to comparable state-of-the-art performance on several commonly used datasets.
This work proposes a framework, AutoPOI, based on proximal policy optimization to automatically find, select, and scale down features. The input raw features are first grouped into small regions. The best candidates selected by the framework are further scaled down with an online-optimized dimensionality reduction neural network. Finally, the framework rewards the performance of these features with the results of TA. Based on the experimental results, the proposed framework can extract features automatically that lead to comparable state-of-the-art performance on several commonly used datasets.
Haodong Jiang, Zhi Ma, Zhenfeng Zhang
Recently, in post-quantum cryptography migration, it has been shown that an IND-1-CCA-secure key encapsulation mechanisms (KEM) is required for replacing an ephemeral Diffie-Hellman (DH) in widely-used protocols, e.g., TLS, Signal, and Noise. IND-1-CCA security is a notion similar to the traditional IND-CCA security except that the adversary is restricted to one single decapsulation query. At EUROCRYPT 2022, based on CPA-secure public-key encryption (PKE), Huguenin-Dumittan and Vaudenay presented two IND-1-CCA KEM constructions called $T_{CH}$ and $T_H$, which are much more efficient than the widely-used IND-CCA-secure Fujisaki-Okamoto (FO) KEMs. The security of $T_{CH}$ was proved in both random oracle model (ROM) and quantum random oracle model (QROM). However, the QROM proof of $T_{CH}$ requires that the ciphertext size of the resulting KEM is twice as large as the one of the underlying PKE. While, the security of $T_H$ was only proved in the ROM, and the QROM proof is left open.
In this paper, we present an IND-1-CCA KEM construction $T_{RH}$, which can be seen as an implicit variant $T_H$, and is as efficient as $T_H$. We prove the security of $T_{RH}$ in both ROM and QROM with much tighter reductions than Huguenin-Dumittan and Vaudenay's work. In particular, our proof will not lead to ciphertext expansion. Moreover, for $T_{RH}$, $T_H$ and $T_{CH}$, we also show that a $O(1/q)$ ($O(1/q^2)$, resp.) reduction loss is unavoidable in the ROM (QROM, resp.), and thus claim that our ROM proof is optimal in tightness. Finally, we make a comprehensive comparison among the relative strengths of IND-1-CCA and IND-CCA in the ROM and QROM.
In this paper, we present an IND-1-CCA KEM construction $T_{RH}$, which can be seen as an implicit variant $T_H$, and is as efficient as $T_H$. We prove the security of $T_{RH}$ in both ROM and QROM with much tighter reductions than Huguenin-Dumittan and Vaudenay's work. In particular, our proof will not lead to ciphertext expansion. Moreover, for $T_{RH}$, $T_H$ and $T_{CH}$, we also show that a $O(1/q)$ ($O(1/q^2)$, resp.) reduction loss is unavoidable in the ROM (QROM, resp.), and thus claim that our ROM proof is optimal in tightness. Finally, we make a comprehensive comparison among the relative strengths of IND-1-CCA and IND-CCA in the ROM and QROM.
Thomas Marquet, Elisabeth Oswald
This paper investigates different ways of applying multi-task learning in the context of two masked AES implementations (via the ASCADv1 and ASCADv2 databases). We propose novel ideas: jointly using multiple single-task models (aka multi-target learning), custom layers (enabling the use of multi-task learning without the need for information about randomness), and hierarchical multi-task models (owing to the idea of encoding the hierarchy flow directly into a multi-task learning model). Our work provides comparisons with existing approaches to deep learning and delivers a first attack using multi-task models without randomness during training, and a new best attack for the ASCADv2 dataset.
Shuai Cheng, Shengke Zeng, Haoyu Zeng, Yawen Feng, Jixiang Xiao
The redundant of multimedia data made an unnecessary waste in encrypted cloud storage, unlike text with completely consistent content, multimedia data allows a certain degree of similarity in deduplication, In this work, we focus on the multimedia data which takes a seriously proportion of storage in scenarios such as data outsourcing to propose secure fuzzy deduplication without the additional servers based on Convergent Encryption(CE), say the Single-server Fuzzy Deduplication (SSFD). Compared to the related fuzzy deduplication, SSFD is strong at resisting brute-force attacks caused by server-server collusion, moreover, we also put server-client collusion attacks into security solutions. Additionally, to enhance the security of data, the proposed scheme provides both protection against replay attacks and verification of label consistency and adds no extra communication such as Proof of Ownership(PoW) in interaction. We separately presented a formal security analysis and performed performance at last to prove security solutions and evaluate the experimental results, it shows SSFD provides both a reliable fuzzy images secure deduplication protocol and a computationally feasible solution.
Grad Vodice, Croatia, 5 June - 9 June 2023
Event date: 5 June to 9 June 2023
Submission deadline: 22 January 2023
Notification: 30 January 2023
Submission deadline: 22 January 2023
Notification: 30 January 2023
02 January 2023
Chicago, USA, 2 July - 8 July 2023
Event date: 2 July to 8 July 2023
Submission deadline: 12 February 2023
Notification: 2 April 2023
Submission deadline: 12 February 2023
Notification: 2 April 2023
Melbourne, Australia, 11 July - 14 July 2023
Event date: 11 July to 14 July 2023
Submission deadline: 27 March 2023
Notification: 28 May 2023
Submission deadline: 27 March 2023
Notification: 28 May 2023
Melbourne, Australia, 10 July 2023
Event date: 10 July 2023
Submission deadline: 15 February 2023
Notification: 31 March 2023
Submission deadline: 15 February 2023
Notification: 31 March 2023
Aarhus, Denmark, 6 June - 8 June 2023
Event date: 6 June to 8 June 2023
Submission deadline: 6 February 2023
Notification: 17 April 2023
Submission deadline: 6 February 2023
Notification: 17 April 2023
Kyoto, Japan, 19 June - 22 June 2023
Event date: 19 June to 22 June 2023
Submission deadline: 15 March 2023
Notification: 19 April 2023
Submission deadline: 15 March 2023
Notification: 19 April 2023
Kyoto, Japan, 19 June - 22 June 2023
Event date: 19 June to 22 June 2023
Submission deadline: 20 March 2023
Notification: 19 April 2023
Submission deadline: 20 March 2023
Notification: 19 April 2023
Florida Atlantic University
The Department of Mathematical Sciences at Florida Atlantic University has availability for a postdoc position to work in various areas of mathematical cryptology, including but not limited to:
http://www.math.fau.edu/mathdepartment/crypto.php
- post-quantum cryptography
- lattice-based cryptography
- code-based cryptography
- cryptanalysis
- elliptic curves and isogenies
- zero-knowledge proofs
- ...
http://www.math.fau.edu/mathdepartment/crypto.php
Closing date for applications:
Contact: Edoardo Persichetti (epersichetti@fau.edu); Shi Bai (sbai@fau.edu); Francesco Sica (sicaf@fau.edu); Veronika Kuchta (vkuchta@fau.edu)
University of Luxembourg
The successful candidate will join the CryptoLux team led by Prof. Alex Biryukov. He or she will contribute to a research project entitled "Advanced Cryptography for Finance and Privacy (CryptoFin)", which is funded by the Luxembourgish Fonds National de la Recherche (FNR) through the CORE program. Candidates with research interests in one or more of the following areas are particularly encouraged to apply:
• Applied or symmetric cryptography
• Cryptofinance, cryptoeconomics, blockchains
• Anonymity and privacy on the Internet
The main responsibility of the successful candidate would be to:
• Conduct, publish and present research results at conferences
• Provide guidance to the two Ph.D. students of the project
• Attract funding in cooperation with academic and industrial partners
Closing date for applications:
Contact: For inquiries, please contact Prof. Alex Biryukov by e-mail: first name dot family name (at) uni.lu
More information: http://emea3.mrted.ly/3agad
Hyunji Kim, Sejin Lim, Aubhab Baksi, Dukyoung Kim, Seyoung Yoon, Kyungbae Jang, Hwajeong Seo
With the recent development of quantum computers, various studies on quantum artificial intelligence technology are being conducted. Quantum artificial intelligence can improve performance in terms of accuracy and memory usage compared to deep learning on classical computers. In this work, we proposed an attack technique that recovers keys by learning patterns in cryptographic algorithms by applying quantum artificial intelligence to cryptanalysis. Cryptanalysis was performed in the current practically usable quantum computer environment, and this is the world's first study to the best of our knowledge.
As a result, we reduced 70 epochs and reduced the parameters by 19.6%. In addition, higher average BAP (Bit Accuracy Probability) was achieved despite using fewer epochs and parameters. For the same epoch, the method using a quantum neural network achieved a 2.8% higher BAP with fewer parameters.
In our approach, quantum advantages in accuracy and memory usage were obtained with quantum neural networks. It is expected that the cryptanalysis proposed in this work will be better utilized if a larger-scale stable quantum computer is developed in the future.