IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
17 October 2023
Quang Dao, Yuval Ishai, Aayush Jain, Huijia Lin
In this work, we give the first construction of a multi-party HSS scheme for a non-trivial function class, from an assumption not known to imply FHE. In particular, we construct an HSS scheme for an arbitrary number of parties with an arbitrary corruption threshold, supporting evaluations of multivariate polynomials of degree $\log / \log \log$ over arbitrary finite fields. As a consequence, we obtain a secure multiparty computation (MPC) protocol for any number of parties, with (slightly) sub-linear per-party communication of roughly $O(S / \log \log S)$ bits when evaluating a layered Boolean circuit of size $S$.
Our HSS scheme relies on the Sparse Learning Parity with Noise assumption, a standard variant of LPN with a sparse public matrix that has been studied and used in prior works. Thanks to this assumption, our construction enjoys several unique benefits. In particular, it can be built on top of any linear secret sharing scheme, producing noisy output shares that can be error-corrected by the decoder. This yields HSS for low-degree polynomials with optimal download rate. Unlike prior works, our scheme also has a low computation overhead in that the per-party computation of a constant degree polynomial takes $O(M)$ work, where $M$ is the number of monomials.
Zhengjun Cao, Lihua Liu
Yanyi Liu, Rafael Pass
Under standard derandomization assumptions, we can show the same result also w.r.t. the standard notion of time-bounded Kolmogorov complexity, K^t.
Guillaume Goy, Julien Maillard, Philippe Gaborit, Antoine Loiseau
16 October 2023
Florida Atlantic University, Department of Mathematics; Boca Raton, Florida, USA.
The candidate will conduct research in cryptography/cryptanalysis. Strong candidates from all areas of cryptology are encouraged to apply. Preference will be given to candidates with several broad areas of interest including, but not limited to, symmetric and public-key cryptography, post-quantum cryptography, quantum algorithms in cryptography, mathematical cryptography, or a closely related area. The candidate should have a strong record of research accomplishments, demonstrated potential for extramural funding, and a commitment to excellence in education. FAU possesses a culture that fosters internal collaboration and innovation as well as partnerships with local, national, and international agencies, and thus candidates must display strong collaborative potential and the ability to conduct transformative externally funded research within their area of specialization.
The Department of Mathematical Sciences is a collegial and research-active department demonstrating excellence in teaching, research, and service. The department has an established national and international reputation for research innovation through our Center for Cryptology and Information Security (CCIS). FAU is also recognized as a National Center of Academic Excellence in Cybersecurity for Cyber Research (CAE-R) for academic years 2012-2024. More information about the department can be found at: http://www.math.fau.edu/
Application Deadline: 2024-01-03.
Closing date for applications:
Contact: Informal inquiries can be made to Shi Bai (sbai@fau.edu), formal applications must be submitted through: https://fau.wd1.myworkdayjobs.com/FAU/job/Boca-Raton/Assistant-Professor--Cryptology_REQ17017
More information: https://fau.wd1.myworkdayjobs.com/FAU/job/Boca-Raton/Assistant-Professor--Cryptology_REQ17017
Shield Lab, Huawei France Research Center, Paris, France
Closing date for applications:
Contact: Prof. Houda Labiod (houda.labiod@huawei.com) and Dr. Guilin Wang (wang.guilin@huawei.com)
University of South Florida
The Department of Mathematics & Statistics of the University of South Florida seeks to fill a nine-month, full-time and tenure-earning Assistant Professor position in Applied Algebra to begin August 7, 2024. A Ph.D. in Mathematics or a closely-related field is required, with preference for applications of algebra to Cryptography, Coding Theory, and Quantum Computing.
The Department is home to the USF Center for Cryptographic Research (usf-crypto.org), which is run in collaboration with the Department of Computer Science & Engineering. The Department of Mathematics & Statistics offers vertically-integrated programs in Applied Algebra at all levels: postdoctoral supervision in Applied Algebra, a graduate sequence in Applied Algebra, an undergraduate certificate in Cryptography, a Research Undergraduate Experience ( REU Site : usf-crypto.org/reu-program) program in Cryptography and Coding Theory, as well as a K–12 summer program in cybersecurity (codebreakhers.org).
Applications from individuals who are ABD will be accepted, but the degree must be conferred by the start date of the appointment. We seek applicants with a strong record of research productivity, the potential to secure external funding, and experience teaching university undergraduates. Special consideration will be given to candidates who possess experience beyond the Ph.D. level and the potential for excellence in teaching at the graduate level. Applications from women and minorities are encouraged. Salary is negotiable. To receive consideration, applications must be submitted no later than November 15, 2023.
To apply, please follow the instructions on the Mathjob advertisement for this position: https://www.mathjobs.org/jobs/list/23078
Closing date for applications:
Contact: Jean-François Biasse
More information: https://www.mathjobs.org/jobs/list/23078
13 October 2023
Nicolas Bon, David Pointcheval, Matthieu Rivain
Khue Do, Lucjan Hanzlik, Eugenio Paracucchi
In this paper, we investigate the security of a class of blind signatures constructed from Sigma-protocols with small challenge space $\mathcal{C}_{\Sigma}$ (i.e., polynomial in the security parameter), using $k$ repetitions of the protocol to decrease the chances of a cheating prover. This class of schemes includes, among others, the Schnorr blind signature scheme with bit challenges and the recently proposed isogeny-based scheme CSI-Otter (Crypto'23), as well as potential blind signatures designed from assumptions with the well-known Sigma-protocol for the graph-isomorphism problem (e.g., Lattice Isomorphism Problem).
For this class of blind signatures, we show a $\mathit{polynomial}$-$\mathit{time}$ attack that breaks one-more unforgeability for any $\ell \geq k$ concurrent sessions in time $O(k \cdot |\mathcal{C}_{\Sigma}|)$. Contrary to the ROS attack, ours is generic and does not require any particular algebraic structure. We also propose a computational trade-off, where, for any $t \leq k$, our attack works for $\ell = \frac{k}{t}$ in time $O(\frac{k}{t} \cdot |\mathcal{C}_{\Sigma}|^t)$.
The consequences of our attack are as follows. Schemes in the investigated class of blind signatures should not be used concurrently without applying specific transformations to boost the security to support more signing sessions. Moreover, for the parameters proposed for CSI-Otter ($k=128$ and $|\mathcal{C}_{\Sigma}|=2$), the scheme becomes forgeable after 128 concurrent signing sessions for the basic attack and with only eight sessions in our optimized attack. We also show that for those parameters, it is even possible to compute two signatures in around 10 minutes with just one signing session using the computation power of the Bitcoin network. Thus, we show that, for sequential security, the parameter $k$ must be at least doubled in the security parameter for any of the investigated schemes.
Sönke Jendral, Kalle Ngo, Ruize Wang, Elena Dubrova
Ittai Abraham, Naama Ben-David, Gilad Stern, Sravya Yandamuri
In some settings, our attempts to prove lower bounds on round complexity fail. Instead, we show new, tight, rather surprising round complexity upper bounds for Byzantine fault tolerant BCA with and without a PKI setup.
Yuzhe Zhang, Qin Wang, Shiping Chen, Chen Wang
We propose a Bayesian model to quantify normal users' trust in delegatees, which we further incorporate into a game-theoretical model to simulate users' reactions against a set of critical factors identified through extensive research (including 10+ staking service providers as well as 30+ PoS blockchains). Our results reveal that users tend to choose their delegatees and utilize their tokens by carefully weighing the delegation cost, the behaviors of other users, and the reputation of delegatees, ultimately reaching a Nash equilibrium. Unfortunately, the collective trend significantly increases the likelihood of token concentration on a small number of delegatees.
Hanjun Li, Tianren Liu
In the random oracle model, we construct two garbling schemes: $\bullet$ The first scheme targets mixed circuits modulo some $N\approx 2^b$. Addition gates are free. Each multiplication gate costs $O(\lambda \cdot b^{1.5})$ communication. Each bit-decomposition costs $O(\lambda \cdot b^{2} / \log{b})$. $\bullet$ The second scheme targets mixed circuit modulo some $N\approx 2^b$. Each addition gate and multiplication gate costs $O(\lambda \cdot b \cdot \log b / \log \log b)$. Every bit-decomposition costs $O(\lambda \cdot b^2 / \log b)$. Our schemes improve on the work of Ball, Malkin, and Rosulek [CCS'16] in the same model.
Additionally relying on the DCR assumption, we construct in the programmable random oracle model a more efficient garbling scheme targeting mixed circuits over $\mathbb{Z}_{2^b}$, where addition gates are free, and each multiplication or bit-decomposition gate costs $O(\lambda_{\text{DCR}} \cdot b)$ communication. We improve on the recent work of Ball, Li, Lin, and Liu [Eurocrypt'23] which also relies on the DCR assumption.
Rachit Garg, George Lu, Brent Waters, David J. Wu
Broadcast encryption offers one solution to this problem, but at the cost of introducing a central trusted party who issues keys to different users (and correspondingly, has the ability to decrypt all ciphertexts). Recently, several works have introduced notions like distributed broadcast encryption and flexible broadcast encryption, which combine the decentralized, trustless model of traditional public-key encryption with the efficiency guarantees of broadcast encryption. In the specific case of a flexible broadcast encryption scheme, users generate their own public/private keys and can then post their public key in any public-key directory. Subsequently, a user can encrypt to an arbitrary set of user public keys with a ciphertext whose size scales polylogarithmically with the number of public keys in the broadcast set. A distributed broadcast encryption scheme is a more restrictive primitive where each public key is also associated with an index, and one can only encrypt to a set of public keys corresponding to different indices.
In this work, we introduce a generic compiler that takes any distributed broadcast encryption scheme and produces a flexible broadcast encryption scheme. Moreover, whereas existing concretely-efficient constructions of distributed broadcast encryption have public keys whose size scales with the maximum number of users in the system, our resulting flexible broadcast encryption scheme has the appealing property that the size of each public key scales with the size of the maximum broadcast set.
We provide an implementation of the flexible broadcast encryption scheme obtained by applying our compiler to the distributed broadcast encryption scheme of Kolonelos, Malavolta, and Wee (ASIACRYPT 2023). With our scheme, a sender can encrypt a 128-bit symmetric key to a set of over 1000 recipients (from a directory with a million users) with a 2 KB ciphertext. This is 16$\times$ smaller than separately encrypting to each user using standard ElGamal encryption. The cost is that the user public keys in flexible broadcast encryption are much larger (50 KB) compared to standard ElGamal public keys (32 bytes). Compared to the similarly-instantiated distributed broadcast encryption scheme, we achieve a 32$\times$ reduction in the user's public key size (50 KB vs. 1.6 MB) without changing the ciphertext size. Thus, flexible broadcast encryption provides an efficient way to encrypt messages to large groups of users at the cost of larger individual public keys (relative to vanilla public-key encryption).
Jesko Dujmovic, Rachit Garg, Giulio Malavolta
In light of this challenge, we present novel TLP constructions that offer batch-solving capabilities without using heavy cryptographic hammers. Our proposed schemes are simple and concretely efficient, and they can be constructed based on well-established cryptographic assumptions based on pairings or learning with errors (LWE). Along the way, we introduce new constructions of puncturable key-homomorphic PRFs both in the lattice and in the pairing setting, which may be of independent interest. Our analysis leverages an interesting connection to Hall's marriage theorem and incorporates an optimized combinatorial approach, enhancing the practicality and feasibility of our TLP schemes.
Furthermore, we introduce the concept of "rogue-puzzle attacks", where maliciously crafted puzzle instances may disrupt the batch-solving process of honest puzzles. We then propose constructions of concrete and efficient TLPs designed to prevent such attacks.
Chris Brzuska, Christoph Egger, Kirthivaasan Puniamurthy
One SSP core feature is the re-use of code, e.g., a package of code might be used in a game and be part of the description of a reduction as well. Thus, in a proof, the linear structure of a paper either requires the reader to turn pages to find definitions or writers to re-state them, thereby interrupting the visual flow of the game hops that are defined by a sequence of graphs.
We present an interactive proof viewer for state-separating proofs (SSPs) which addresses the limitations and perform three case studies: The equivalence between simulation-based and game-based notions for symmetric encryption, the security proof of the Goldreich-Goldwasser-Micali construction of a pseudorandom function from a pseudorandom generator, and Brzuska's and Oechsner's SSP formalization of the proof for Yao's garbling scheme.
Vincent Hwang, Chi-Ting Liu, Bo-Yin Yang
Tianyu Zheng, Shang Gao, Yu Guo, Bin Xiao
This paper introduces KiloNova, a non-uniform PCD system with zero-knowledge properties derived from generic folding schemes. Motivated by HyperNova (Kothapalli et al. ePrint 2023), we derive an invariant of the Customizable Constraint System with linear claims on circuits and inputs to avoid cross items. With the new constraint system, we propose a generic folding scheme for multiple instances of different circuits and ensure the zero-knowledge property with various effective methods. Consequently, we build a non-uniform ZK-PCD scheme from the generic folding scheme and improve its performance with some optimization techniques, such as circuit aggregation and decoupling. We propose a new construction for ZK-PCD that does not use a ZK argument system and has little influence on the complexity. The theoretical evaluation shows our non-uniform ZK-PCD scheme outperforms previous models. A single multi-scalar multiplication dominates the prover cost at each step. The recursive circuit is dominated by $O(\log(n))$ random-oracle-like hashes and $O(k)$ scalar multiplications, where $n$ is the circuit input length and $k$ is the instance number at each step.