IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
26 June 2020
Leuven, Belgium, 7 July - 9 July 2020
Event Calendar24 June 2020
Naomi Ephraim, Cody Freitag, Ilan Komargodski, Rafael Pass
ePrint ReportWe use our (functional) non-malleable time-lock puzzles to give efficient multi-party protocols for desirable tasks such as coin flipping and auctions. Our protocols are (1) fair, meaning that no malicious party can influence the output, (2) optimistically efficient, meaning that if all parties are honest, then the protocol terminates immediately, and (3) publicly verifiable, meaning that from the transcript of the protocol anyone can quickly infer the outcome, without the need to perform a long computation phase. Our protocols support an unbounded number of participants and require no adversary-independent trusted setup. Our protocol is the first protocol that satisfies all of the above properties under any assumption. Security is proven assuming the repeated squaring assumption and in the auxiliary-input random oracle model. Along the way, we introduce a publicly verifiable notion of time-lock puzzles which is of independent interest. This notion allows the solver of the puzzle to compute the solution together with a proof which can be quickly verified by anyone.
Seyed Farhad Aghili, Amirhossein Adavoudi Jolfaei, Aysajan Abidin
ePrint ReportGiuseppe Vitto, Alex Biryukov
ePrint ReportDana Dachman-Soled, Ilan Komargodski, Rafael Pass
ePrint ReportWe present the first construction of a non-malleable code secure against $\textit{all}$ polynomial size tampering functions that have $\textit{bounded polynomial depth}$. This is an even larger class than all bounded polynomial $\textit{size}$ functions and, in particular, we capture all functions in non-uniform $\mathbf{NC}$ (and much more). Our construction is in the plain model (i.e., no trusted setup) and relies on several cryptographic assumptions such as keyless hash functions, time-lock puzzles, as well as other standard assumptions. Additionally, our construction has several appealing properties: the complexity of encoding is independent of the class of tampering functions and we obtain sub-exponentially small error.
Christof Beierle, Gregor Leander, Yosuke Todo
ePrint ReportMajid Khabbazian, Tejaswi Nadahalli, Roger Wattenhofer
ePrint ReportJohann Großschädl, Ben Marshall, Dan Page, Thinh Pham, Francesco Regazzoni
ePrint ReportAlex Lombardi, Vinod Vaikuntanathan
ePrint ReportIn this work, we consider the problem of compiling a different succinct interactive proof system: Pietrzak's proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly $2^{\lambda^{\epsilon}}$) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential ($2^{-n^{1-\epsilon}}$)-hardness of the $n$-dimensional learning with errors problem. (The latter follows from the worst-case $2^{n^{1-\epsilon}}$ hardness of lattice problems.) More generally, we extend the ``bad-challenge function'' methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable.
As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class $\mathbf{CLS}\subset \mathbf{PPAD}$ under the $2^{\lambda^\epsilon}$-hardness of the repeated squaring problem and the $2^{-n^{1-\epsilon}}$-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is ``inherently sequential'', we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption.
Xin Li, Fermi Ma, Willy Quach, Daniel Wichs
ePrint ReportWe first consider this problem in the symmetric-key setting, where the states of Alice and Bob include a shared secret as well as individual uniform randomness. However, since Eve gets leakage on these states, Alice and Bob need to perform privacy amplification to derive a fresh secret key from them. Prior solutions require Alice and Bob to sample fresh uniform randomness during the protocol, while in our setting all of their randomness was already part of their individual states a priori and was therefore subject to leakage. We show an information-theoretic solution to this problem using a novel primitive that we call a two-seed extractor, which we in turn construct by drawing a connection to communication-complexity lower-bounds in the number-on-forehead (NOF) model.
We then turn to studying this problem in the public-key setting, where the states of Alice and Bob consist of independent uniform randomness. Unfortunately, we give a black-box separation showing that leakage-resilient NIKE in this setting cannot be proven secure via a black-box reduction under any game-based assumption when the leakage is super-logarithmic. This includes virtually all assumptions used in cryptography, and even very strong assumptions such as indistinguishability obfuscation (iO). Nevertheless, we also provide positive results that get around the above separation: - We show that every key exchange protocol (e.g., Diffie-Hellman) is secure when the leakage amount is logarithmic, or potentially even greater if we assume sub-exponential security without leakage. - We notice that the black-box separation does not extend to schemes in the common reference string (CRS) model, or to schemes with preprocessing, where Alice and Bob can individually pre-process their random coins to derive their secret state prior to leakage. We give a solution in the CRS model with preprocessing using bilinear maps. We also give solutions in just the CRS model alone (without preprocessing) or just with preprocessing (without a CRS), using iO and lossy functions.
Akshima, David Cash, Andrew Drucker, Hoeteck Wee
ePrint ReportEduard Hauck, Eike Kiltz, Julian Loss, Ngoc Khanh Nguyen
ePrint ReportWe propose a new three-round lattice-based blind signature scheme whose security can be proved, in the random oracle model, from the standard SIS assumption. Our starting point is a modified version of the (insecure) BLAZE scheme, which itself is based Lyubashevsky's three-round identification scheme combined with a new aborting technique to reduce the correctness error. Our proof builds upon and extends the recent modular framework for blind signatures of Hauck, Kiltz, and Loss (EUROCRYPT '19). It also introduces several new techniques to overcome the additional challenges posed by the correctness error which is inherent to all lattice-based constructions.
While our construction is mostly of theoretical interest, we believe it to be an important stepping stone for future works in this area.
Peter Dixon, Sutanu Gayen, A. Pavan, N. V. Vinodchandran
ePrint Report1. A unconditional inclusion that NIPZK is in CoSBP.
2. Construction of a relativized world in which there is a distribution testing problem that lies in NIPZK but not in SBP, thus giving a relativized separation of NIPZK (and hence PZK) from SBP.
3. Construction of a relativized world in which there is a distribution testing problem that lies in PZK but not in CoSBP, thus giving a relativized separation of PZK from CoSBP. These results refine the landscape of perfect zero-knowledge classes in relation to traditional complexity classes.
Carsten Baum, Emmanuela Orsini, Peter Scholl, Eduardo Soria-Vazquez
ePrint ReportIn this work, we present the first efficient MPC protocols with identifiable abort in the dishonest majority setting, which run in a constant number of rounds and make only black-box use of cryptographic primitives. Our main construction is built from highly efficient primitives in a careful way to achieve identifiability at a low cost. In particular, we avoid the use of public-key operations outside of a setup phase, incurring a relatively low overhead on top of the fastest currently known constant-round MPC protocols based on garbled circuits. Our construction also avoids the use of adaptively secure primitives and heavy zero-knowledge machinery, which was inherent in previous works. In addition, we show how to upgrade our protocol to achieve public verifiability using a public bulletin board, allowing any external party to verify correctness of the computation or identify a cheating party.
Unai Rioja, Servio Paguada, Lejla Batina, Igor Armendariz
ePrint ReportJoseph Jaeger, Nirvan Tyagi
ePrint ReportWe apply our framework to give proofs of security for the BurnBox system for privacy in the face of border searches and the in-use searchable symmetric encryption scheme due to Cash et al. In both cases, prior analyses had bugs that our framework helps avoid.
Romain Gay, Aayush Jain, Huijia Lin, Amit Sahai
ePrint ReportNew Assumption: Previous to our work, all constructions of $i\mathcal{O}$ from simple assumptions required novel pseudorandomness generators involving LWE samples and constant-degree polynomials over the integers, evaluated on the error of the LWE samples. In contrast, Boolean pseudorandom generators (PRGs) computable by constant-degree polynomials have been extensively studied since the work of Goldreich (2000). We show how to replace the novel pseudorandom objects over the integers used in previous works, with appropriate Boolean pseudorandom generators with sufficient stretch, when combined with LWE with binary error over suitable parameters. Both binary error LWE and constant-degree Goldreich PRGs have been subject to extensive cryptanalysis since much before our work. Thus, we back the plausibility of our assumption with security against algorithms studied in context of cryptanalysis of these objects.
New Techniques: We introduce a number of new techniques: - We introduce a simple new technique for proving leakage resilience when polynomial-size noise is used to hide small secrets (for example, to hide LWE-based FHE decryption errors). - We show how to build partially-hiding \emph{public-key} functional encryption, supporting degree-2 functions in the secret part of the message, and arithmetic $\mathsf{NC}^1$ functions over the public part of the message, assuming only standard assumptions over asymmetric pairing groups. - We construct single-ciphertext secret-key functional encryption for all circuits with {\em linear} key generation, assuming only the LWE assumption.
Simplification: Unlike prior works, our new techniques furthermore let us construct public-key functional encryption for polynomial-sized circuits directly (without invoking any bootstrapping theorem, nor security amplification, nor transformation from secret-key to public-key FE), and based only on the polynomial hardness of underlying assumptions. The functional encryption scheme satisfies a strong notion of efficiency where the size of the ciphertext grows only sublinearly in the output size of the circuit and not its size. Finally, assuming that the underlying assumptions are subexponentially hard, we can bootstrap this construction to achieve $i\mathcal{O}$.
23 June 2020
École polytechnique, France
Job PostingDepending on her/his profile, the chosen candidate will become a member of the cryptography team («Grace», joint with INRIA) at the Department of Computer Science, or of the Department of Economics. Candidates must hold a Ph.D. in computer science or in Economics, and have demonstrated great ability in research and teaching. Candidates must present a scientific research project in relation to blockchains.
The mission of the accepted candidate will be to develop research, coordinate with PhD students and researchers, and also support the activities of the chair, by outreaching to the blockchain network in the Paris area, but also worldwide, and by supporting the communication and PR of the chair. If she/he wishes to, the candidate will be able to complement his or her activity by doing lectures, labs and student projects about blockchain platforms.
Through a fast and lightweight process the candidate will be hired from Winter 2020 for two years, which could be extended for two more years after a further review process. The complementary teaching activity, if any, may complement the base salary. Successful candidates will work at Ecole Polytechnique located in Palaiseau, Paris area, France.
Deadline for Application: July 23rd, 2020
Closing date for applications:
Contact: Daniel Augot, Senior researcher, INRIA and École polytechnique. Daniel.Augot@inria.fr
More information: https://blockchain-chair.io/
CryptoLux Group, University of Luxembourg
Job Posting- Design and cryptanalysis of symmetric cryptographic primitives
- Cryptocurrencies, blockchain
- Privacy enhancing technologies, Tor
- Side-channel attacks and countermeasures
- White-box cryptography
The University offers a two-year employment contract, which may be extended up to five years. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Alex Biryukov before August 1, 2020. The application should contain a brief cover letter explaining the candidate's research interests, CV with photo, a list of publications and the names and contacts of 3 references.
Closing date for applications:
Contact: Prof. Alex Biryukov
More information: https://www.cryptolux.org/index.php/Vacancies
New Jersey Institute of Technology
Job PostingCandidates are expected to mainly teach courses under the umbrella of Cybersecurity in support of our graduate and undergraduate programs. The successful candidate will also be involved in creating course content and materials with a focus on experiential and project-based learning.
Interested applicants should submit their CV and the names of at least two references by applying as soon as possible at https://njit.csod.com/ats/careersite/JobDetails.aspx?site=1&id=1961. Applications will be reviewed on a rolling basis until the position is filled.
Work environment and location:
The Computer Science department, part of the Ying Wu College of Computing Sciences, is the largest at NJIT, comprising one tenth of the student population. It is also the largest computer science department among all research universities in the New York metropolitan area. Located in Northern New Jersey, within the greater New York Metropolitan area, NJIT is part of a vibrant ecosystem of research universities and corporate research centers.
Closing date for applications:
Contact: Reza Curtmola
More information: https://njit.csod.com/ats/careersite/JobDetails.aspx?site=1&id=1961