IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
07 November 2022
Mi-Ying (Miryam) Huang, Er-Cheng Tang
ePrint ReportSteven D. Galbraith, Trey Li
ePrint ReportIn this paper we give much more general obfuscation tools that allow to obfuscate evasive membership testing in arbitrary algebraic sets (including projective sets) over finite fields of arbitrary (prime power) order. We give two schemes and prove input-hiding security based on relatively standard assumptions. The first scheme is based on the preimage resistance property of cryptographic hash functions; and the second scheme is based on the hardness assumptions required for small superset obfuscation. We also introduce a new security notion called span-hiding, and prove that the second scheme achieves span-hiding assuming small superset obfuscation.
One special case of algebraic sets over finite fields is boolean polynomials, which means our methods can be applied to obfuscate any evasive function defined by a polynomial-size collection of boolean polynomials. As a corollary, we obtain an input-hiding obfuscator for evasive functions defined by circuits in NC^0.
Hoeteck Wee, David J. Wu
ePrint ReportWe introduce a new framework for constructing lattice-based vector commitments and their generalizations. A simple instantiation of our framework yields a new vector commitment scheme from the standard short integer solution (SIS) assumption that supports private openings and large messages. We then show how to use our framework to obtain the first succinct functional commitment scheme that supports openings with respect to arbitrary Boolean circuits of bounded depth. In this scheme, a user can commit to a vector $\mathbf{x} \in \{0,1\}^\ell$, and later on, open the commitment to any function $f(\mathbf{x})$. Both the commitment and the opening are succinct: namely, they have size $\textsf{poly}(\lambda, d, \log \ell)$, where $\lambda$ is the security parameter and $d$ is the depth of the Boolean circuit computing $f$. Previous constructions of functional commitments could only support constant-degree polynomials, or require a trusted online authority, or rely on non-falsifiable assumptions. The security of our functional commitment scheme is based on a new (and falsifiable) family of "basis-augmented" SIS assumptions BASIS we introduce in this work.
We also show how to use our vector commitment framework to obtain (1) a polynomial commitment scheme where the user can commit to a polynomial $f \in \mathbb{Z}_q[x]$ and subsequently open the commitment to an evaluation $f(x) \in \mathbb{Z}_q$; and (2) an aggregatable vector (resp., functional) commitment where a user can take a set of openings to multiple indices (resp., function evaluations) and aggregate them into a single short opening. Both of these extensions rely on the same BASIS assumption we use to obtain our succinct functional commitment scheme.
Prabhanjan Ananth, Aditya Gulati, Luowen Qian, Henry Yuen
ePrint Report1. New Definitions: We study variants of pseudorandom function-like state (PRFS) generators, introduced by Ananth, Qian, and Yuen (CRYPTO'22), where the pseudorandomness property holds even when the generator can be queried adaptively or in superposition. We show the feasibility of these variants assuming the existence of post-quantum one-way functions. 2. Classical Communication: We show that PRS generators with logarithmic output length imply commitment and encryption schemes with classical communication. Previous constructions of such schemes from PRS generators required quantum communication. 3. Simplified Proof: We give a simpler proof of the Brakerski-Shmueli (TCC'19) result that polynomially-many copies of uniform superposition states with random binary phases are indistinguishable from Haar-random states. 4. Necessity of Computational Assumptions: We also show that a secure PRS with output length logarithmic, or larger, in the key length necessarily requires computational assumptions.
Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, Pramod Viswanath
ePrint ReportThibauld Feneuil
ePrint ReportThis work focus on the third type of MPCitH-based signatures. Following the same methodology as the work of Feneuil, Joux and Rivain (CRYPTO'22), we apply the MPC-in-the-Head paradigm to several problems: the multivariate quadratic problem, the MinRank problem, the rank syndrome decoding problem and the permuted kernel problem. Our goal is to study how this paradigm behaves for each of those problems.
For the multivariate quadratic problem, our scheme outperforms slightly the existing schemes when considering large fields (as $\mathbb{F}_{256}$), and for the permuted kernel problem, we obtain larger sizes. Even if both schemes do not outperform the existing ones according to the communication cost, they are highly parallelizable and compatible with some MPC-in-the-Head techniques (like fast signature verification) while the former proposals were not.
Moreover, we propose two efficient MPC protocols to check that the rank of a matrix over a field $\mathbb{F}_q$ is upper bounded by a public constant. The first one relies on the rank decomposition while the second one relies on $q$-polynomials. We then use them to build signature schemes relying on the MinRank problem and the rank syndrome decoding problem. Those schemes outperform the former schemes, achieving sizes below $6$ KB (while using only 256 parties for the MPC protocol).
Saikrishna Badrinarayanan, Daniel Masny, Pratyay Mukherjee, Sikhar Patranabis, Srinivasan Raghuraman, Pratik Sarkar
ePrint Report- The first round-optimal maliciously secure OT and MPC protocols in the plain model that achieve (black-box) simulation-based security while relying on the computational CSIDH assumption.
- The first round-optimal maliciously secure OT and MPC protocols that achieves Universal Composability (UC) security in the presence of a trusted setup (common reference string plus random oracle) while relying on the computational CSIDH assumption.
Prior plausibly quantum-safe isogeny-based OT protocols (with/without setup assumptions) are either not round-optimal, or rely on potentially stronger assumptions.
We also build a 3-round maliciously-secure OT extension protocol where each base OT protocol requires only 4 isogeny computations. In comparison, the most efficient isogeny-based OT extension protocol till date due to Lai et al. [Eurocrypt 2021] requires 12 isogeny computations and 4 rounds of communication, while relying on the same assumption as our construction, namely the reciprocal CSIDH assumption.
Matteo Campanelli, Dario Fiore, Hamidreza Khoshakhlagh
ePrint ReportIn this work we introduce and construct a new notion of encryption that has a strong flavor of WE and that, crucially, we can build from well-studied assumptions (based on bilinear pairings) for interesting classes of computation. Our new notion, witness encryption for (succinct) functional commitment, takes inspiration from a prior weakening of witness encryption introduced by Benhamouda and Lin (TCC 2020). In a nutshell, theirs is a WE where: the encryption statement consists of a (non compressible) commitment $\mathsf{cm}$, a function $G$ and a value $y$; the decryption witness consists of a (non succinct) NIZK proof about the fact that $\mathsf{cm}$ opens to $v$ such that $y=G(v)$. Benhamouda and Lin showed how to apply this primitive to obtain MPC with non-interactive and reusability properties—dubbed $\mathsf{mrNISC}$—replacing the requirement of WE in existing round-collapsing techniques. Our new WE-like notion is motivated by supporting both commitments of a fixed size and fixed decryption complexity, independent of the size of the value $v$—in contrast to the work by Benhamouda and Lin where this complexity is linear. As a byproduct, our efficiency requirement substantially improves the offline stage of $\mathsf{mrNISC}$ protocols.
From a technical standpoint, our work shows how to solve additional challenges arising from relying on computationally binding commitments and computational soundness (of functional commitments), as opposed to statistical binding and unconditional soundness (of NIZKs), used in Benhamouda and Lin's work. In order to tackle them, we need not only to modify their basic blueprint, but also to model and instantiate different types of projective hash functions as building blocks. Our techniques are of independent interest and may highlight new avenues to design practical variants of witness encryption.
As an additional contribution, we show that our new WE-flavored primitive and its efficiency properties are versatile: we discuss its further applications and show how to extend this primitive to better suit these settings.
Enrique Larraia, Tamara Finogina, Nuria Costa
ePrint ReportFirst, we derive the trust model for complete verifiability and voting secrecy from the Swiss Chancellery's requirements [1][2], supporting our interpretation by quotes from and references to relevant excerpts of the ordinance and the corresponding technical annex.
Then, based on the derived model, we prove that sVote with Control Components provides complete verifiability and guarantees voting secrecy and the non-disclosure of early provisional results. We demonstrate that sVote fulfills the requirements of the Swiss federal chancellery for completely verifiable E-voting systems. In other words, we show that an adversary cannot break the complete verifiability and voting secrecy properties of sVote without being detected by either the voter or auditors.
[1] Technical and administrative requirements for electronic vote casting v 2.0 https://www.bk.admin.ch/dam/bk/en/dokumente/pore/Annex_of_the_Federal_Chancellery_Ordinance_on_Electronic_Voting_V2.0_July_2018.pdf.download.pdf/Annex_of_the_Federal_Chancellery_Ordinance_on_Electronic_Voting_V2.0_July_2018.pdf [2] Federal Chancellery Ordinance on Electronic Voting https://www.fedlex.admin.ch/eli/cc/2013/859/en
Riddhi Ghosal, Amit Sahai, Brent Waters
ePrint ReportBefore our work, the only object known to imply this challenging form of delegation was a SNARG/SNARK for $\mathcal{NP}$. This is because from the point of view of the user/verifier, the program $P$ is an unknown witness to the computation. However, constructing a SNARG for $\mathcal{NP}$ from standard assumptions remains a major open problem.
In our work, we show how to achieve delegation in this challenging context assuming only the hardness of the Learning With Errors (LWE) assumption, bypassing the apparent need for a SNARG for $\mathcal{NP}$.
Lichao Wu, Léo Weissbart, Marina Krček, Huimin Li, Guilherme Perin, Lejla Batina, Stjepan Picek
ePrint ReportThis work demonstrates a practical approach to dealing with the lack of profiling traces. Instead of learning from a one-hot encoded label, transferring the labels to their distribution can significantly speed up the convergence of guessing entropy. Besides, by studying the relationship between all possible key candidates, we propose a new metric, denoted augmented guessing entropy (AGE), to evaluate the generalization ability of the profiling model. We validate AGE with two common use cases: early stopping and network architecture search, and the results indicate its superior performance.
Sujaya Maiyya, Yuval Steinhart, Divyakant Agrawal, Prabhanjan Ananth, Amr El Abbadi
ePrint ReportNoemi Glaeser, Dimitris Kolonelos, Giulio Malavolta, Ahmadreza Rahimi
ePrint ReportIn this work, we propose a new approach to construct RBE, from well-studied assumptions in bilinear groups. Our scheme is black-box, and it is concretely highly efficient---a ciphertext is 866 bytes. To substantiate this claim, we implemented a prototype of our scheme, and we show that it scales to "millions of users". The public parameters of the scheme are in the order of kilobytes. The most expensive operation (registration) takes a handful of seconds, whereas the encryption and decryption runtimes are in the order of milliseconds. This is the first-ever implementation of an RBE scheme and demonstrates that the practical deployment of RBE is already possible with today's hardware.
Bar Alon, Olga Nissenbaum, Eran Omri, Anat Paskin-Cherniavsky, Arpita Patra
ePrint ReportWe study the feasibility of obtaining perfect security for deterministic symmetric two-party functionalities (i.e., where both parties obtain the same output) in the face of malicious adversaries. We explore both the plain model as well as the correlated randomness model. We provide positive results in the plain model, and negative results in the correlated randomness model. As a corollary, we obtain the following results. \begin{enumerate} \item We provide a characterization of symmetric functionalities with (up to) four possible outputs that can be computed with perfect security. The characterization is further refined when restricted to three possible outputs and to Boolean functions. All characterizations are the same for both the plain model and the correlated randomness model. \item We show that if a functionality contains an embedded XOR or an embedded AND, then it cannot be computed with perfect security (even in the correlated randomness model). \end{enumerate}
06 November 2022
Jeremiah Blocki, Blake Holman, Seunghoon Lee
ePrint ReportBalthazar Bauer, Pooya Farshim, Patrick Harasser, Adam O'Neill
ePrint ReportWe introduce a standard-model definition called pseudo-generic group (PGG), where we require exponentiations with base an (initially) unknown group generator to result in random-looking group elements. In essence, our framework delicately lifts the influential notion of Universal Computational Extractors of Bellare, Hoang, and Keelveedhi (BHK, CRYPTO 2013) to a setting where the underlying ideal reference object is a generic group. The definition we obtain simultaneously generalizes the Uber assumption family, as group exponents no longer need to be polynomially induced. At the core of our definitional contribution is a new notion of algebraic unpredictability, which reinterprets the standard Schwartz–Zippel lemma as a restriction on sources. We prove the soundness of our definition in the GGM with auxiliary-input (AI-GGM).
Our remaining results focus on applications of PGGs. We first show that PGGs are indeed a generalization of Uber. We then present a number of applications in settings where exponents are not polynomially induced. In particular we prove that simple variants of ElGamal meet several advanced security goals previously achieved only by complex and inefficient schemes. We also show that PGGs imply UCEs for split sources, which in turn are sufficient in several applications. As corollaries of our AI-GGM feasibility, we obtain the security of all these applications in the presence of preprocessing attacks.
Some of our implications utilize a novel type of hash function, which we call linear-dependence destroyers (LDDs) and use to convert standard into algebraic unpredictability. We give an LDD for low-degree sources, and establish their plausibility for all sources by showing, via a compression argument, that random functions meet this definition.
04 November 2022
Tokyo, Japan, 26 March 2023
Event CalendarTemasek Laboratories, National University of Singapore, Singapore
Job PostingA candidate will work in the area of post-quantum cryptography. The candidate will conduct research on analysis of post-quantum cryptography; the emphasis is on quantum analysis on symmetric cipher and PQC. The work requires to carry out some simulations.
Applicants are expected to have a PhD degree in Mathematics/Physics/Computer Science and a strong background in quantum algorithm, algebra, linear algebra or algebraic number theory.
Preferred candidates are expected to be proficient in Magma software or SAGEMATH software; or have knowledge on quantum software (eg. Qiskit, etc), a team worker and able to conduct independent research.
Interested candidates will kindly include their full CV and transcripts in their applications and send to Dr Chik How Tan, tsltch@nus.edu.sg. Deadline for applications is January 31st, 2023. We encourage early applications and review of applications will begin immediately. Only shortlisted applications will be notified.
Closing date for applications:
Contact: Dr Chik How Tan (tsltch@nus.edu.sg)
Florida Atlantic University
Job Posting- post-quantum cryptography
- lattice-based cryptography
- code-based cryptography
- cryptanalysis
- elliptic curves and isogenies
- zero-knowledge proofs
- ...
Closing date for applications:
Contact: Edoardo Persichetti (epersichetti@fau.edu); Shi Bai (sbai@fau.edu); Francesco Sica (sicaf@fau.edu)
Heliax, Remote
Job PostingClosing date for applications:
Contact: Christopher Goes
More information: https://heliax.dev/jobs/research-cryptographer-FHE/