IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
17 October 2023
Alex Lombardi, Fermi Ma, John Wright
To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary $A^f$. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory.
We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.
Balthazar Bauer, Pooya Farshim, Patrick Harasser, Markulf Kohlweiss
We formulate the uber-knowledge (UK) assumption, a standard-model assumption that naturally extends the uber-assumption family to knowledge assumptions. We justify the soundness of the UK in both the bilinear GGM and bilinear AGM. Along the way we extend these models to incorporate hashing into groups, an adversarial capability that is available in many concrete groups. (In contrast to standard assumptions, hashing may affect the validity of knowledge assumptions.) These results, in turn, enable a modular approach to security in GGM and AGM.
As example applications, we use the UK to prove knowledge-soundness of Groth16 and KZG polynomial commitments in the standard model, where for the former we reuse the existing AGM proof without hashing.
Gaëtan Cassiers, Barbara Gigerl, Stefan Mangard, Charles Momin, Rishub Nagpal
Thomas Lavaur, Jérôme Lacan
Léo Weissbart, Stjepan Picek
Anamaria Costache, Lea Nürnberger, Tjerand Silde
In more detail, we consider the notion of circuit privacy along four dimensions: whether the adversary is internal or external (i.e. does the adversary hold the secret key or not), and in a semi-honest and malicious setting. Our starting point is Gentry’s definition, which we change from statistical to computational indistinguishability. Doing so allows us to prove that the BGV scheme is computationally circuit-private in a semi-honest setting to an external adversary out of the box.
We then propose a new definition by extending Gentry’s definition to an internal adversary. This is appropriate since the scenario that the client is the adversary (and therefore has access to the decryption key) is a realistic one. Further, we remark that our definition is strictly stronger than Gentry’s – our definition requires that a scheme be circuit private according to Gentry’s definition and additionally, the distribution of the ciphertext noise in all ciphertexts to be computationally indistinguishable. Given this new definition, and using previous results of Costache, Nürnberger and Player (CT-RSA’23), we show that slight modifications to the BGV scheme will make it fulfill this new definition. Finally, we show how to extend these results to a malicious setting if we require that the client attaches proofs of well-formedness of keys and ciphertexts.
Raja Adhithan Radhakrishnan
Sofia Celi, Shai Levin, Joe Rowell
Hannah Keller, Helen Möllering, Thomas Schneider, Oleksandr Tkachenko, Liang Zhao
We introduce efficient MPC protocols that securely realize noise sampling for several plaintext DP mechanisms that are secure against existing precision-based attacks: the discrete Laplace and Gaussian mechanisms, the snapping mechanism, and the integer-scaling Laplace and Gaussian mechanisms. Due to their inherent trade-offs, the favorable mechanism for a specific application depends on the available computation resources, type of function evaluated, and desired (epsilon,delta)-DP guarantee.
The benchmarks of our protocols implemented in the state-of-the-art MPC framework MOTION (Braun et al., TOPS'22) demonstrate highly efficient online runtimes of less than 32 ms/query and down to about 1ms/query with batching in the two-party setting. Also the respective offline phases are practical, requiring only 51 ms to 5.6 seconds/query depending on the batch size.
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.