IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
13 October 2023
Giuseppe Ateniese, Foteini Baldimtsi, Matteo Campanelli, Danilo Francati, Ioanna Karantaidou
ePrint ReportAndre Esser, Paolo Santini
ePrint ReportIn this work we initiate a systematic study of the hardness of the RSD problem starting from its asymptotics. We classify different parameter regimes revealing large regimes for which RSD instances are solvable in polynomial time and on the other hand regimes that lead to particularly hard instances. Against previous perceptions, we show that a classification solely based on the uniqueness of the solution is not sufficient for isolating the worst case parameters. Further we provide an in-depth comparison between SD and RSD in terms of reducibility and computational complexity, identifying regimes in which RSD instances are actually harder to solve.
We provide the first asymptotic analysis of the CCJ algorithm, establishing its worst case decoding complexity as $2^{0.141n}$. We then introduce \emph{regular-ISD} algorithms by showing how to tailor the whole machinery of advanced Information Set Decoding (ISD) techniques from attacking SD to the RSD setting. The fastest regular-ISD algorithm improves the worst case decoding complexity significantly to $2^{0.112n}$. Eventually, we show that also with respect to suggested parameters regular-ISD outperforms previous approaches in most cases, reducing security levels by up to 40 bits.
Yujin Yang, Kyungbae Jang, Yujin Oh, Hwajeong Seo
ePrint ReportYujin Oh, Kyungbae Jang, Yujin Yang, Hwajeong Seo
ePrint ReportHyunji Kim, Kyoungbae Jang, Yujin Oh, Woojin Seok, Wonhuck Lee, Kwangil Bae, Ilkwon Sohn, Hwajeong Seo
ePrint ReportWhile many works focus on Grover’s attacks in symmetric key cryptography, there has been no research on the practical implementation of the quantum approach for lattice-based cryptography. Currently, only theoretical analyses involve the application of Grover's search to various Sieve algorithms.
In this work, for the first time, we present a quantum NV Sieve implementation to solve SVP, posing a threat to lattice-based cryptography. Additionally, we implement the extended version of the quantum NV Sieve (i.e., the dimension and rank of the lattice vector). Our extended implementation could be instrumental in extending the upper limit of SVP (currently, determining the upper limit of SVP is a vital factor). Lastly, we estimate the quantum resources required for each specific implementation and the application of Grover's search.
In conclusion, our research lays the groundwork for the quantum NV Sieve to challenge lattice-based cryptography. In the future, we aim to conduct various experiments concerning the extended implementation and Grover's search.
Binwu Xiang, Jiang Zhang, Yi Deng, Yiran Dai, Dengguo Feng
ePrint Report\qquad In this paper, we propose a new blind rotation algorithm based on a GSW-like encryption from the NTRU assumption. Our algorithm has performance asymptotically independent from the key distributions, and outperforms AP and GINX in both the evaluation key size and the computational efficiency(especially for large key distributions). By using our blind rotation algorithm as a building block, we present new bootstrapping algorithms for both LWE and RLWE ciphertexts.
We implement our bootstrapping algorithm for LWE ciphertexts, and compare the actual performance with two bootstrapping algorithms, namely, FHEW/AP by Ducas and Micciancio (EUROCRYPT 2015) and TFHE/GINX by Chillotti, Gama, Georgieva and Izabach\`ene (Journal of Cryptology 2020), that were implemented in the OpenFHE library. For parameters with ternary key distribution at 128-bit security, our bootstrapping only needs to store evaluation key of size 18.65MB for blind rotation, which is about 89.8 times smaller than FHEW/AP and 2.9 times smaller than TFHE/GINX. Moreover, our bootstrapping can be done in 112ms on a laptop, which is about 3.2 times faster than FHEW/AP and 2.1 times faster than TFHE/GINX. More improvements are available for large key distributions such as Gaussian distributions.
Akira Ito, Rei Ueno, Rikuma Tanaka, Naofumi Homma
ePrint ReportYansong Feng, Abderrahmane Nitaj, Yanbin Pan
ePrint ReportDipayan Saha, Shams Tarek, Katayoon Yahyaei, Sujan Kumar Saha, Jingbo Zhou, Mark Tehranipoor, Farimah Farahmandi
ePrint ReportSamuel Hand, Alexander Koch, Pascal Lafourcade, Daiki Miyahara, Léo Robert
ePrint Report12 October 2023
Toronto, Canada, 23 March - 24 March 2024
Event CalendarSubmission deadline: 22 November 2023
Notification: 22 January 2024
King's College London; UK
Job PostingWe are looking for a postdoc to work with us on lattice-based cryptography. Broadly speaking, this is to build/analyse practical post-quantum privacy-preserving primitives and protocols.
Job ad: https://www.kcl.ac.uk/jobs/076525-research-fellowresearch-associate-in-cryptography
Closing date: 31 January 2024
Closing date for applications:
Contact: Martin Albrecht <martin.albrecht@kcl.ac.uk>
More information: https://martinralbrecht.wordpress.com/2023/10/12/postdoc-positions/
Department of Computer Science, Aarhus University, Denmark
Job PostingClosing date for applications:
Contact: Kaj Grønbæk, Professor, Head of Department, e-mail: kgronbak@cs.au.dk
Aarhus University (DK)
Job PostingDeadline:1 November 2023. https://phd.nat.au.dk/for-applicants/open-calls/november-2023/verified-voting-protocols-and-blockchains
The PhD positions include full tuition waiver and a very competitive scholarship. Aarhus University provides international students with a safe and stable environment, a high standard of living and a wealth of social opportunities. Besides having an excellent reputation that enables our PhD graduates to find outstanding employment prospects, Aarhus University offers attractive working conditions, research support and campus resources.
https://cs.au.dk/education/phd/
https://international.au.dk/
This project is supported by the Danish DIREC research center. It is a collaboration between Aarhus University, the Alexandra Institute and Concordium ApS. The aim of the project is work towards secure implementations of Blockchain Voting Governance Protocols and Internet Voting Protocols.
Voting and blockchains are intimately connected. Voting is used in blockchains for consensus, governance, and decentralized organizations. Conversely, elections are based on trust, which means that election systems ideally should be based on algorithms and data structures that are already trusted. Blockchains provide such a technology. They provide a trusted bulletin board, which can be used as part of some voting protocols. Moreover, voting crucially depends on establishing the identity of the voter to avoid fraud and to establish eligibility verifiability. Decades of research in voting protocols have shown how difficult it is to combine the privacy of the vote with the auditability of the election outcome. It is easy to achieve one without the other, but hard to combine both into one protocol. Thus, the topic of this research proposal is to investigate voting protocols and their relation to blockchains. The team will work on security proofs of these protocols and their implementations.
Closing date for applications:
Contact: Bas Spitters
More information: https://phd.nat.au.dk/for-applicants/open-calls/november-2023/verified-voting-protocols-and-blockchains
a16z crypto research, New York, NY, USA
Job PostingClosing date for applications:
Contact: Joseph Bonneau
More information: https://a16z.com/about/jobs/?gh_jid=5766443003
11 October 2023
Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer, Krijn Reijnders
ePrint ReportSiemen Dhooghe, Artemii Ovchinnikov, Dilara Toprakhisar
ePrint ReportYanbin Xu, Yonglin Hao, Mingxing Wang
ePrint ReportSrivatsan Sridhar, Dionysis Zindros, David Tse
ePrint ReportYuncong Zhang, Shi-Feng Sun, Ren Zhang, Dawu Gu
ePrint ReportIn this work, we focus on random-access memory, an influential and expensive component of ZKVMs. Specifically, we investigate the state-of-the-art protocols for validating the correct functioning of memory, which we refer to as the \emph{memory consistency checks}. Isolating these checks from the rest of the system allows us to formalize their definition and security notion. Furthermore, we summarize the state-of-the-art constructions using the Polynomial IOP model and formally prove their security. Observing that the bottleneck of existing designs lies in sorting the entire memory trace, we break away from this paradigm and propose a novel memory consistency check, dubbed $\mathsf{Permem}$. $\mathsf{Permem}$ bypasses this bottleneck by introducing a technique called the address cycle method, which requires fewer building blocks and---after instantiating the building blocks with state-of-the-art constructions---fewer online polynomial oracles and evaluation queries. In addition, we propose $\mathsf{gcq}$, a new construction for the lookup argument---a key building block of the memory consistency check, which costs fewer online polynomial oracles than the state-of-the-art construction $\mathsf{cq}$.