IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
13 October 2023
Hyunji Kim, Kyoungbae Jang, Yujin Oh, Woojin Seok, Wonhuck Lee, Kwangil Bae, Ilkwon Sohn, Hwajeong Seo
While 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
\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
Yansong Feng, Abderrahmane Nitaj, Yanbin Pan
Dipayan Saha, Shams Tarek, Katayoon Yahyaei, Sujan Kumar Saha, Jingbo Zhou, Mark Tehranipoor, Farimah Farahmandi
Samuel Hand, Alexander Koch, Pascal Lafourcade, Daiki Miyahara, Léo Robert
12 October 2023
Toronto, Canada, 23 March - 24 March 2024
Submission deadline: 22 November 2023
Notification: 22 January 2024
King's College London; UK
We 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
Closing date for applications:
Contact: Kaj Grønbæk, Professor, Head of Department, e-mail: kgronbak@cs.au.dk
Aarhus University (DK)
Deadline: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
Closing 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
Siemen Dhooghe, Artemii Ovchinnikov, Dilara Toprakhisar
Yanbin Xu, Yonglin Hao, Mingxing Wang
Srivatsan Sridhar, Dionysis Zindros, David Tse
Yuncong Zhang, Shi-Feng Sun, Ren Zhang, Dawu Gu
In 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}$.
Miranda Christ, Kevin Choi, Joseph Bonneau
Sourav Das, Ling Ren
In this paper, we present the first adaptively secure threshold BLS signature scheme that relies on the hardness of DDH and co-CDH in asymmetric pairing group in the Random Oracle Model (ROM). Our signature scheme also has non-interactive signing, compatibility with non-threshold BLS verification, and practical efficiency like Boldyreva's scheme. Moreover, to achieve static security, our scheme only needs the hardness of CDH in the ROM, which is the same as the standard non-threshold BLS signature. These properties make our protocol a suitable candidate for practical adoption with the added benefit of provable adaptive security. We also present an efficient distributed key generation (DKG) protocol to set up the signing keys for our signature scheme. We implement our scheme in Go and evaluate its signing and aggregation costs.
Xiuquan Ding, Giulio Malavolta, Tianwei Zhang
In this work, we consider the problem of doubly efficient batched PIR (DEBPIR), where the client wishes to download multiple entries. This problem arises naturally in many practical applications of PIR, or when the database contains large entries. Our main result is a construction of DEBPIR where the amortized communication and server computation overhead is $\tilde{O}(1)$, from the Ring-LWE problem. This represents an exponential improvement compared with known constructions, and it is optimal up to poly-logarithmic factors in the security parameter. Interestingly, the server’s online operations are entirely combinatorial and all algebraic computations are done in the pre-processing or delegated to the client.