IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
16 February 2024
Yilei Chen, Xinyu Mao
In this paper, we construct UCE with strongly computationally unpredictable one-query sources from lattice assumptions based on the GGH15 encodings [GGH15], without using iO. Security is proven under the following assumptions: (1) LWE with subexponential hardness; (2) evasive LWE, which is a new assumption proposed by Wee [Wee22]; (3) the existence of AIPO in NC1. Our UCE directly implies a universal hardcore function that outputs a polynomial number of bits, giving the first lattice-based universal hardcore function without using iO. We also put forth a new primitive called obliviously programmable function as an intermediate abstraction; it makes our analysis more modularized and could be of independent interest
Nir Bitansky, Nathan Geier
Sri Aravinda Krishnan Thyagarajan, Ke Wu, Pratik Soni
In this work, we \emph{initiate} the comprehensive study of game-theoretic fairness for multi-party \emph{sampling from general distributions}. In particular, for the case of $m$-sided \emph{uniform} coin-toss we give a nearly complete characterization of the regime in which game-theoretic fairness is feasible. Interestingly, contrary to standard fairness notions in cryptography, the composition of game-theoretically fair two-sided coin-toss protocols does not necessarily yield game-theoretically fair multi-sided coins. To circumvent this, we introduce new techniques compatible with game-theoretic fairness. In particular, we give the following results:
- We give a protocol from standard cryptographic assumptions that achieves game-theoretic fairness for uniform $m$-sided coin-toss against half- or more-sized adversarial coalitions. - To complement our protocol, we give a general impossibility result that establishes the optimality of our protocol for a broad range of parameters modulo an additive constant. Even in the worst-case, the gap between our protocol and our impossibility result is only a small constant multiplicative factor.
- We also present a game-theoretically fair protocol for \emph{any} efficiently sampleable $m$-outcome distribution in the dishonest majority setting. For instance, even for the case of $m=2$ (i.e., two-sided coin-toss), our result implies a game-theoretically fair protocol for an \emph{arbitrary} Bernoulli coin. In contrast, the work of Wu, Asharov, and Shi only focussed on a Bernoulli coin with parameter $1/2$.
Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher
In this paper, we show that using only $o(n)$ work qubits, one can obtain the first bit of the modular exponentiation output. We combine this result with May and Schlieper's truncation technique (ToSC 2022) and the Ekerå-Håstad variant of Shor's algorithm (PQCrypto 2017) to obtain a quantum factoring algorithm requiring only $n/2 + o(n)$ qubits in the case of an $n$-bit RSA modulus, while current envisioned implementations require about $2n$ qubits.
Our algorithm uses a Residue Number System and succeeds with a parametrizable probability. Being completely classical, we have implemented and tested it. Among possible trade-offs, we can reach a gate count $\mathcal{O}(n^3)$ for a depth $\mathcal{O}(n^2 \log^3 n)$, which then has to be multiplied by $\mathcal{O}(\log n)$ (the number of measurement results required by Ekerå-Håstad). Preliminary logical resource estimates suggest that this circuit could be engineered to use less than 1700 qubits and $2^{36}$ Toffoli gates, and require 60 independent runs to factor an RSA-2048 instance.
Dimitris Mouris, Christopher Patton, Hannah Davis, Pratik Sarkar, Nektarios Georgios Tsoutsos
We introduce Mastic, a flexible protocol for private and verifiable general-purpose statistics based on function secret sharing and zero-knowledge proofs on secret shared data. Mastic is the first to solve the more general problem of weighted heavy-hitters, enabling new use cases, not supported by Prio or Poplar. In addition, Mastic allows grouping general-purpose metrics by user attributes, such as their geographic location or browser version, without sacrificing privacy or incurring high-performance costs, which is a major improvement over Prio. We demonstrate Mastic's benefits with two real-world applications, private network error logging and browser telemetry, and compare our protocol with Prio and Poplar on a wide area network. Overall, we report over one order of magnitude performance improvement over Poplar for heavy hitters and $1.5-2\times$ improvement over Prio for attribute-based metrics.
John Preuß Mattsson
Pierre Pébereau
We give new attacks for UOV$^{\hat +}$ and VOX targeting singular points of the public key equations. Our attacks lower the security of the schemes, both asymptotically and in number of gates, showing in particular that the parameters sets proposed for these schemes do not meet the NIST security requirements. More precisely, we show that the security of UOV$^{\hat +}$ was overestimated by factors $2^{22}, 2^{36}, 2^{59}$ for security levels $I, III, V$ respectively. We conclude the attack on VOX by showing that an attacker can perform a full key recovery from one vector obtained in the previous attacks.
Mustafa Khairallah, Srinivasan Yadhunathan, Shivam Bhasin
David Du Pont, Jonas Bertels, Furkan Turan, Michiel Van Beirendonck, Ingrid Verbauwhede
We present a hardware architecture for the NTT targeting generalized cyclotomics within the context of the BGV FHE scheme. We explore different non-power-of-two NTT algorithms, including the Prime-Factor, Rader, and Bluestein NTTs. Our most efficient architecture targets the 21845-th cyclotomic polynomial --- a practical parameter for BGV --- with ideal properties for use with a combination of the Prime-Factor and Rader algorithms. The design achieves high throughput with optimized resource utilization, by leveraging parallel processing, pipelining, and reusing processing elements. Compared to Wu et al.'s VLSI architecture of the Bluestein NTT, our approach showcases 2$\times$ to 5$\times$ improved throughput and area efficiency. Simulation and implementation results on an AMD Alveo U250 FPGA demonstrate the feasibility of the proposed hardware design for FHE.
Pedro Branco, Nico Döttling, Akshayaram Srinivasan, Riccardo Zanotto
Devadas, Goyal, Kalai, and Vaikuntanathan (FOCS 2022) introduced a variant of somewhere extractable hashing called rate-1 fully local SE hash functions. The rate-1 requirement states that the size of the digest is $m + \mathsf{poly}(\lambda)$ (where $\lambda$ is the security parameter). The fully local property requires that for any index $i$, there is a "very short" opening showing that $i$-th bit of the hashed input is equal to $b$ for some $b \in \{0,1\}$. The size of this opening is required to be independent of $m$ and in particular, this means that its size is independent of the size of the digest. Devadas et al. gave such a construction from Learning with Errors (LWE).
In this work, we give a construction of a rate-1 fully local somewhere extractable hash function from Decisional Diffie-Hellman (DDH) and BARGs. Under the same assumptions, we give constructions of rate-1 BARG and RAM SNARG with partial input soundness whose proof sizes are only matched by prior constructions based on LWE.
Alexander Bienstock, Sarvar Patel, Joon Young Seo, Kevin Yeo
Using our compression schemes, we obtain state-of-the-art schemes for batch private information retrieval (PIR) where a client wishes to privately retrieve multiple entries from a server-held database in one query. We show that our compression schemes may be used to reduce communication by up to 30% for batch PIR in both the single- and two-server settings.
Additionally, we study labeled private set intersection (PSI) in the unbalanced setting where one party's set is significantly smaller than the other party's set and each entry has associated data. By utilizing our novel compression algorithm, we present a protocol with 65-88% reduction in communication with comparable computation compared to prior works.
Michele Battagliola, Andrea Flamini
Since its introduction, the Fiat-Shamir Transform has been the most popular way to design standard digital signature schemes. In this work, we translate the Fiat-Shamir Transform into a multi-party setting, building a framework that seeks to be an alternative, easier, way to design threshold digital signatures. We do that by introducing the concept of threshold identification scheme and threshold sigma protocol, and showing necessary and sufficient conditions to prove the security of the threshold signature schemes derived from them.
Lastly, we show a practical application of our framework providing an alternative security proof for Sparkle, a recent threshold Schnorr signature. In particular, we consider the threshold identification scheme underlying Sparkle and prove the security of the signature derived from it.
We show that using our framework the effort required to prove the security of threshold signatures might be drastically lowered. In fact, instead of reducing explicitly its security to the security of a hard problem, it is enough to prove some properties of the underlying threshold sigma protocol and threshold identification scheme. Then, by applying the results that we prove in this paper it is guaranteed that the derived threshold signature is secure.
Charlotte Lefevre
Elijah Pelofske
Tao Zhang, Shang Shi, Md Habibur Rahman, Nitin Varshney, Akshay Kulkarni, Farimah Farahmandi, Mark Tehranipoor
13 February 2024
Warszawa, Polska, 20 June - 21 June 2024
Submission deadline: 8 April 2024
Notification: 6 May 2024
IFT | Logos | Vac
This role is within the Vac Nescience unit, which develops Nescience A zkVM leveraging hiding properties.
The role
In this role, you will be responsible implementing and analysing components of zero knowledge argument systems and architectures for private computation. The ideal candidate should be well-versed in zero-knowledge circuits written in Rust, with the ability to adapt to evolving research needs.
Your responsibilities will include implementing zero-knowledge circuits and writing comprehensive specifications. Additionally, your role will involve measuring the performance of circuits, while also possessing the skills to debug and optimize as needed.
Join us in pushing the boundaries of private computation technology and contribute to groundbreaking advancements in the field of zkVMs.
Closing date for applications:
Contact: Maya
More information: https://grnh.se/0ee4300f1us
SandboxAQ
We have postdoc and PhD residency positions available at SandboxAQ [1]. We seek people interested in doing research in the areas of post-quantum cryptography, privacy, and machine learning applied to cybersecurity. The positions are remote, but allow for travel to collaborate with team members. The postdoc residencies are initially for two years, but with the option to extend it to up to three years, on mutual agreement. PhD residencies are up to one year.
We are open to strong candidates that reinforce existing expertise of the team as well as candidates extending our expertise. We are committed to creating an inclusive culture where we have zero tolerance for discrimination. We invest in our employees' personal and professional growth. Learn more about what we’ve been doing so far by checking out our publications page [2] or the individual DBLP pages of our permanent researchers listed below for each of the teams associated with these residencies. [1] www.sandboxaq.com [2] pub.sandboxaq.com Rolling deadline. More information: https://www.sandboxaq.com/careers. PQC members’ information:- Carlos Aguilar Melchor: https://dblp.org/pid/71/4606.html
- Martin Albrecht: https://dblp.org/pid/92/7397.html
- Nina Bindel: https://dblp.org/pid/167/3021.html
- James Howe: https://dblp.org/pid/163/8680.html
- Andreas Hülsing: https://dblp.org/pid/27/1744.html
- Nicolas Gama: https://dblp.org/pid/49/4575.html
- Sandra Guasch Castelló: https://dblp.org/pid/86/8292.html
- Raphael Labaca-Castro: raphael.labaca@sandboxaq.com
- Parth Mishra: parth.mishra@sandboxaq.com
Closing date for applications:
Contact:
- PQC: martin.albrecht@sandboxaq.com and james.howe@sandboxaq.com
- Privacy: nicolas.gama@sandboxaq.com and sandra.guasch@sandboxaq.com
- ML: raphael.labaca@sandboxaq.com and parth.mishra@sandboxaq.com
More information: https://www.sandboxaq.com/careers
University of Wollongong, Australia
Closing date for applications:
Contact: Dr Yannan Li (first_name@uow.edu.au)
University of Wollongong, Australia
Closing date for applications:
Contact: Dr Yannan Li (first_name@uow.edu.au)