IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
06 February 2024
Zeyu Liu, Yunhao Wang
In this work, we inspect the BGV/BFV bootstrapping procedure from a different angle. We provide a generalized bootstrapping definition that relaxes the correctness requirement of regular bootstrapping, allowing constructions that support only certain kinds of circuits with arbitrary depth. In addition, our definition captures a form of functional bootstrapping. In other words, the output encrypts a function evaluation of the input instead of the input itself. Under this new definition, we provide a bootstrapping procedure supporting different types of functions. Our construction is 1-2 orders of magnitude faster than the state-of-the-art BGV/BFV bootstrapping algorithms, depending on the evaluated function. Of independent interest, we show that our technique can be used to improve the batched FHEW/TFHE bootstrapping construction introduced by Liu and Wang (Asiacrypt 2023). Our optimization provides a speed-up of 6x in latency and 3x in throughput for batched binary gate bootstrapping and a plaintext-space-dependent speed-up for batched functional bootstrapping with plaintext space smaller than $\mathbb{Z}_{512}$.
Tairong Huang, Shihe Ma, Anyu Wang, XiaoYun Wang
Trevor Yap Hong Eng, Shivam Bhasin, Léo Weissbart
Prasanna Ravi, Dirmanto Jap, Shivam Bhasin, Anupam Chattopadhyay
Breaking the Cubic Barrier: Distributed Key and Randomness Generation through Deterministic Sharding
Hanwen Feng, Zhenliang Lu, Qiang Tang
We introduce the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring $\widetilde{\mathcal{O}}(n^{2.5}\lambda)$ total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element. This property makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. Additionally, both DKG protocols straightforwardly imply an improved (single-shot) common coin protocol.
At the core of our techniques, we develop a simple-yet-effective methodology via deterministic sharding that arbitrarily groups nodes into shards; and a new primitive called consortium-dealer secret sharing, to enable a shard of nodes to securely contribute a secret to the whole population only at the cost of one-dealer. We also formalize simulation-based security for publicly verifiable secret sharing (PVSS), making it possible for a modular analysis for DKG. Those might be of independent interest.
Trevor Yap, Dirmanto Jap
Hao Guo, Jintai Ding
Brent Waters, David J. Wu
Shihe Ma, Tairong Huang, Anyu Wang, Xiaoyun Wang
Chun Guo, Xiao Wang, Kang Yang, Yu Yu
05 February 2024
Copenhagen, Denmark, 19 August - 22 August 2024
Submission deadline: 15 March 2024
Notification: 20 May 2024
London, United Kingdom, 2 September - 4 September 2024
Submission deadline: 3 May 2024
Notification: 5 June 2024
Darmstadt, Germany, 3 June - 6 June 2024
Submission deadline: 26 February 2024
Notification: 22 March 2024
Logos (Nomos ZK Team)
Key Responsibilities
Develop an in-depth understanding of the multi-layered architecture of Nomos and how Zero Knowledge proofs can be effectively utilized at various stages. Collaborate with other researchers and developers to ensure that Nomos's systems and protocols are efficiently designed and implemented. Address and solve upgradeability concerns related to ZK schemes and ensure consensus proofs are ZK-friendly. Design and help implement privacy-centered protocols that require the use of ZK proofs. Evaluate and integrate ZK tools and frameworks to optimize the performance and efficiency of our systems. Stay abreast of the latest developments and trends in the field of Zero Knowledge proofs and blockchain technology. Provide support and guidance to the team on ZK proofs related issues.
You ideally will have
Closing date for applications:
Contact: Angel
More information: https://grnh.se/60ae0cb71us
SanboxAQ (USA, remote; Europe, remote; Canada, remote)
The SandboxAQ team is looking for a Research Scientist to help functionalize the next generation of cryptographic systems. A successful candidate will be comfortable with research in post-quantum cryptography. We are open to strong candidates that reinforce existing expertise of the team as well as candidates extending our expertise. They will be part of a team of diverse cryptographers and engineers, where they will play a key role in efficient and effective enablement of the technologies being developed. They can learn more about what we’ve been doing so far by checking out the publications of our permanent researchers: Carlos Aguilar Melchor, Martin Albrecht, Nina Bindel, James Howe, Andreas Hülsing, and Anand Kumar Narayanan
Core Responsibilities- Research and design of new post-quantum cryptography primitives and protocols
- Engage in team collaborations to meet ambitious product and engineering goals
- Present research discoveries and developments including updates and results clearly and efficiently both internally and externally, verbally and in writing
- PhD in Mathematics or Computer Science or equivalent practical experience
- Strong background in post-quantum cryptography with a proven publication record at flagship conferences
- Deep understanding of cryptographic primitives and protocols
- Capacity to work both as an individual contributor and on collaborative projects with strong teamwork skills
- Experience in C, C++, Rust or Go, or equivalent skills to implement and validate innovative cryptographic constructions and/or protocols
- Experience with the real-world aspects of cryptography
- Experience contributing to open source projects and standardization bodies
- Curiosity in a variety of domains of cryptography, security, privacy, or engineering
Closing date for applications:
Contact: carlos.aguilar@sandboxaq.com
More information: https://www.sandboxaq.com/careers-list?gh_jid=5072034004
UCLouvain Crypto Group, Louvain-la-Neuve, Belgium
Closing date for applications:
Contact: Candidates are invited to send a resume and motivation letter to Dr. Gaetan Cassiers and Pr. Francois-Xavier Standaert (email: first name dot last name at uclouvain.be).
More information: https://simple-crypto.org
Kasra Abbaszadeh, Christodoulos Pappas, Dimitrios Papadopoulos, Jonathan Katz
Kaizen relies on two essential building blocks to achieve both prover efficiency and verification succinctness. First, we construct an optimized GKR-style (sumcheck-based) proof system for the gradient-descent algorithm with concretely efficient prover cost; this scheme allows the prover to generate a proof for each iteration of the training process. Then, we recursively compose these proofs across multiple iterations to attain succinctness. As of independent interests, we propose a framework for recursive composition of GKR-style proofs and techniques, such as aggregatable polynomial commitment schemes, to minimize the recursion overhead.
Benchmarks indicate that Kaizen can handle a large model of VGG-$11$ with $10$ million parameters and batch size $16$. The prover runtime is $22$ minutes (per iteration), which is $\mathbf{43\times}$ faster than generic recursive proofs, while we further achieve at least $\mathbf{224 \times}$ less prover memory overhead. Independent of the number of iterations and, hence, the size of the dataset, the proof size is $1.36$ megabytes, and the verifier runtime is only $103$ milliseconds.
Mingshu Cong, Tsz Hon Yuen, Siu Ming Yiu
Xiaohai Dai, Guanxiong Wang, Jiang Xiao, Zhengxuan Guo, Rui Hao, Xia Xie, Hai Jin
Suvradip Chakraborty, Stanislav Peceny, Srinivasan Raghuraman, Peter Rindal
We present two constructions with communication bandwidth and rounds tradeoff. Logstar, our bandwidth-optimized construction, takes inspiration from Falk and Ostrovsky (ITC, 2021) and runs in $O(n\log^*n)$ time and communication with $O(\log n)$ rounds. In particular, for all conceivable $n$, the $\log^*n$ factor will be equal to the constant $2$ and therefore we achieve a near-linear running time. Median, our rounds-optimized construction, builds on the classic parallel median-based merge approach of Valiant (SIAM J. Comput., 1975), and requires $O(n \log^c n)$, $1
We introduce two additional constructions that merge input lists of different sizes. SquareRootMerge, merges lists of sizes $n^{\frac{1}{2}}$ and $n$, and runs in $O(n)$ time and communication with $O(\log n)$ rounds. CubeRootMerge is inspired by Blunk et al.'s (2022) construction and merges lists of sizes $n^{\frac{1}{3}}$ and $n$. It runs in $O(n)$ time and communication with $O(1)$ rounds.
We optimize our constructions for concrete efficiency. Today, concretely efficient secure merge protocols rely on standard techniques such as GMW or generic sorting. These approaches require a $O(n \log n)$ sized circuit of $O(\log n)$ depth. In contrast, our constructions are efficient and achieve superior asymptotics. We benchmark our constructions and obtain significant improvements. For example, Logstar reduces bandwidth costs $\approx 3.3\times$ and Median reduces rounds $\approx2.43\times$.