06 March 2021
Justin Holmgren, Alex Lombardi, Ron D. Rothblum
Leveraging a connection observed by Dwork, Naor, Reingold, and Stockmeyer (FOCS '99), our negative result is obtained by making positive progress on a related fundamental problem in cryptography: securely instantiating the Fiat-Shamir heuristic for eliminating interaction in public-coin interactive protocols. A recent line of works has shown how to instantiate the heuristic securely, albeit only for a limited class of protocols.
Our main result shows how to instantiate Fiat-Shamir for parallel repetitions of much more general interactive proofs. In particular, we construct hash functions that, assuming LWE, securely realize the Fiat-Shamir transform for the following rich classes of protocols:
- The parallel repetition of any ``commit-and-open'' protocol (such as the GMW protocol mentioned above), when a specific (natural) commitment scheme is used. Commit-and-open protocols are a ubiquitous paradigm for constructing general purpose public-coin zero knowledge proofs.
- The parallel repetition of any base protocol that (1) satisfies a stronger notion of soundness called round-by-round soundness, and (2) has an efficient procedure, using a suitable trapdoor, for recognizing ``bad verifier randomness'' that would allow the prover to cheat.
Our results are obtained by establishing a new connection between the Fiat-Shamir transform and list-recoverable codes. In contrast to the usual focus in coding theory, we focus on a parameter regime in which the input lists are extremely large, but the rate can be small. We give a (probabilistic) construction based on Parvaresh-Vardy codes (FOCS '05) that suffices for our applications.
Amos Beimel, Hussien Othman, Naty Peter
We define and study two additional classes of polynomial secret-sharing schemes: (1) schemes in which for every authorized set the reconstruction of the secret is done using polynomials and (2) schemes in which both sharing and reconstruction are done by polynomials. For linear secret-sharing schemes, schemes with linear sharing and schemes with linear reconstruction are equivalent. We give evidence that for polynomial secret-sharing schemes, schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction. We also prove lower bounds on the share size for schemes with polynomial reconstruction. On the positive side, we provide constructions of secret-sharing schemes and conditional disclosure of secrets (CDS) protocols with polynomials of degree-$2$ sharing and reconstruction. We extend a construction of Liu et al. (CRYPTO'17) and construct a degree-$2$ $k$-server CDS protocols for a function $f:[N]^k\rightarrow \{0,1\}$ with message size $O(N^{(k-1)/3})$. We also show how to transform our degree-$2$ $k$-server CDS protocol to a robust CDS protocol, and use the robust CDS protocol to construct degree-$2$ secret-sharing schemes for arbitrary access structures with share size $O(2^{0.716n})$; this is better than the best known share size of $O(2^{0.762n})$ for linear secret-sharing schemes and worse than the best known share size of $O(2^{0.637n})$ for general secret-sharing schemes.
Christof Ferreira Torres, Antonio Ken Iannillo, Arthur Gervais, Radu State
Carsten Baum, Bernardo David, Tore Frederiksen
Péter Kutas, Simon-Philipp Merz, Christophe Petit, Charlotte Weitkämper
Alessandro Chiesa, Eylon Yogev
In this work, we provide a new construction that achieves a smaller argument size. This is the first progress on the Micali construction since it was introduced over 25 years ago.
A SNARG in the ROM is *(t,ε)-secure* if every t-query malicious prover can convince the verifier of a false statement with probability at most ε. For (t,ε)-security, the argument size of all known SNARGs in the ROM (including Micali's) is Õ((log (t/ε))^2) bits, *even* if one were to rely on conjectured probabilistic proofs well beyond current techniques. In practice, these costs lead to SNARGs that are much larger than constructions based on other (pre-quantum and costly) tools. This has led many to believe that SNARGs in the ROM are inherently quadratic.
We show that this is not the case. We present a SNARG in the ROM with a sub-quadratic argument size: Õ(log (t/ε) ∙ log t). Our construction relies on a strong soundness notion for PCPs and a weak binding notion for commitments. We hope that our work paves the way for understanding if a linear argument size, that is O(log (t/ε)), is achievable in the ROM.
Jelle Don, Serge Fehr, Christian Majenz, Christian Schaffner
The technical core of our result is a new commutator bound that bounds the operator norm of the commutator of the unitary operator that describes the evolution of the compressed oracle (which is used to simulate the random oracle above) and of the measurement that extracts $x$.
We show two applications of our generic online extractability result. We show *tight* online extractability of commit-and-open $\Sigma$-protocols in the quantum setting, and we offer the first non-asymptotic post-quantum security proof of the *textbook* Fujisaki-Okamoto transformation, i.e, without adjustments to facilitate the proof.
04 March 2021
Anna-Lena Horlemann, Sven Puchinger, Julian Renner, Thomas Schamberger, Antonia Wachter-Zeh
Ivan Damgård, Boyang Li, Nikolaj I. Schwartzbach
The second lower bound applies to the perfect maliciously secure setting with $n=3t+1$ parties. We show that for any $n$ and all large enough $S$, there exists a reactive functionality $F_S$ taking an $S$-bit string as input (and with short output) such that any protocol implementing $F_S$ with perfect malicious security must communicate $\Omega(nS)$ bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any $n$ and all large enough $g \in \mathbb{N}$ there exists a reactive functionality $F_C$ doing computation specified by a Boolean circuit $C$ with $g$ gates, where any perfectly secure protocol implementing $F_C$ must communicate $\Omega(n g)$ bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor $\log n$ off for Boolean circuits).
Both results also extend to the case where the threshold $t$ is suboptimal. Namely if $n=kt+s$ the bound is weakened by a factor $O(s)$, which corresponds to known optimizations via packed secret-sharing.
Julien Devevey, Amin Sakzad, Damien Stehlé, Ron Steinfeld
We describe the first polynomial-time average-case reductions for the search variant of $\mathsf{I-PLWE}^f$, proving its computational equivalence with the search variant of its counterpart problem $\mathsf{PLWE}^f$. Our reductions apply to a large class of defining polynomials $f$. To obtain our results, we employ a careful adaptation of Rényi divergence analysis techniques to bound the impact of the integer ring arithmetic carries on the error distributions. As an application, we present a deterministic public-key cryptosystem over integer rings. Our cryptosystem, which resembles $\mathsf{ThreeBears}$, enjoys one-way (OW-CPA) security provably based on the search variant of $\mathsf{I-PLWE}^f$.
Amril Syalim, Takashi Nishide, Kouichi Sakurai
Zhengyuan Shi, Gangqiang Yang, Hailiang Xiong, Fudong Li, Honggang Hu
Lawrence Roy, Jaspal Singh
Stanislaw Jarecki, Hugo Krawczyk, Jiayu Xu
However, this protocol requires two variable-base exponentiations on the client, while a more efficient multiplicative blinding scheme replaces one or both client exponentiations with fixed-base exponentiation, leading to the decrease of the client's computational cost by a factor between two to six, depending on pre-computation. We analyze the security of the above OPRF with multiplicative blinding, showing surprising weaknesses that offer attack avenues which are not present using exponential blinding. We characterize the security of this OPRF implementation as a "Revised OPRF" functionality, a relaxation of UC OPRF functionality used in prior work. On the positive side, we show that the Revised OPRF suffices for the security of OPAQUE, the asymmetric PAKE protocol, hence allowing OPAQUE the computational advantages of multiplicative blinding. Unfortunately, we also show examples of other OPRF applications which become insecure when using such blinding. The conclusion is that usage of multiplicative blinding for F_k(x) defined as above, in settings where correct value g^k (needed for multiplicative blinding) is not authenticated, and OPRF inputs are of low entropy, must be carefully analyzed, or avoided all together. We complete the picture by showing a simple and safe alternative definition of function F_k(x) which offers (full) UC OPRF security using either form of blinding.
Geovandro C. C. F. Pereira, Paulo S. L. M. Barreto
Dakshita Khurana, Brent Waters
We study the following question: Is every CPA-compatible key generation algorithm also CCA-compatible? We obtain the following answers:
- Every sub-exponentially CPA-compatible KeyGen algorithm is CCA1-compatible, assuming the existence of hinting PRGs and sub-exponentially secure keyless collision resistant hash functions. - Every sub-exponentially CPA-compatible KeyGen algorithm is also CCA2-compatible, assuming the existence of non-interactive CCA2 secure commitments, in addition to sub-exponential security of the assumptions listed in the previous bullet.
Here, sub-exponentially CPA-compatible KeyGen refers to any key generation algorithm for which there exist encryption and decryption algorithms that result in a CPA-secure public-key encryption scheme {\em against sub-exponential adversaries}.
This gives a way to perform CCA secure encryption given any public key infrastructure that has been established with only (sub-exponential) CPA security in mind. The resulting CCA encryption makes black-box use of the CPA scheme and all other underlying primitives.
Pedro Hecht
CryptoLux Group, University of Luxembourg
The CryptoLux group of the University of Luxembourg has a vacancy for a post-doctoral researcher in the area of symmetric cryptography. The successful candidate will contribute to a research project entitled Analysis and Protection of Lightweight Cryptographic Algorithms (APLICA), which is funded by the Luxembourgish Fonds National de la Recherche and the German Research Foundation. Starting in 2021, APLICA will run over a period of 3 years as a joint research project between the CryptoLux group and the Workgroup for Symmetric Cryptography of Ruhr-University Bochum. The mission of the APLICA project is to develop new cryptanalytic techniques for lightweight authenticated encryption algorithms and hash functions, and to design and implement new countermeasures against side-channel attacks that are suitable for constrained devices.
Candidates must have a Ph.D. degree in symmetric cryptography or a closely related field. Preference will be given to candidates with a strong publication record that includes at least one paper at an IACR conference/workshop or one of the top-4 security conferences. Experience in software development for embedded systems or mounting side-channel attacks is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:
- Cryptanalysis of authenticated encryption algorithms or hash functions
- Leakage resilience or leakage reduction by design (e.g. modes of operation)
- Security evaluation of leakage-resilient primitives or constructions
The position is available from Jan. 2021 on basis of a fixed-term contract for 3 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 Apr. 1, 2021 (early submission is strongly encouraged, applications will be processed upon receipt). The application material should contain a cover letter explaining the candidate's research interests, a CV (incl. photo), a list of publications, scans of diploma certificates, and contact details of 3 references.
Closing date for applications:
Contact: Prof. Alex Biryukov (alex.biryukov@uni.lu)
More information: https://www.fnr.lu/projects/analysis-and-protection-of-lightweight-cryptographic-algorithms/
Fujitsu Laboratories of America
This is a remote position; we are accepting applications from exceptional graduate students based in USA, UK or Japan. The selected candidate will closely work with researchers based in Sunnyvale, California. We offer attractive remuneration and typical length of internship is 12 weeks. Start date is flexible.
Closing date for applications:
Contact: Avradip Mandal (amandal at fujitsu dot com)
More information: https://www.fujitsu.com/us/about/businesspolicy/tech/rd/research/computer-security/cryptography-and-privacy/
IMDEA Software Institute, Madrid, Spain
The IMDEA Software Institute offers a postdoc position in the area of security and privacy in blockchain. The work may involve a combination of (i) identification of security threats and privacy leakages in cryptocurrencies (e.g., hardware wallets, layer-2 scalability solutions, cross-chain protocols, cybercrime operations), (ii) design and evaluation of cryptographic protocols to enhance the security, privacy, scalability and interoperability of current cryptocurrencies. The postdoc will work under the supervision of Pedro Moreno-Sánchez and Juan Caballero.
Who should apply?Applicants should have a PhD in computer science or a related discipline with an excellent track-record and an interest in privacy-enhancing technologies, applied cryptography, and data analysis. Good command of English both spoken and written is required.
Working at IMDEA SoftwareThe position is based in Madrid, Spain where the IMDEA Software Institute is situated. Salaries are internationally competitive and include attractive conditions such as access to an excellent public healthcare system. The working language at the institute is English. Knowledge of Spanish is not required.
DatesThe position is for 2 years. The preferred starting date is June 2021 with some flexibility.
How to apply?Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2021-03-postdoc-spblockchain. Review of applications will begin immediately and close when the position is filled or on April 2nd, 2021.
Closing date for applications:
Contact: pedro.moreno(at)imdea.org and/or juan.caballero(at)imdea.org
More information: https://software.imdea.org/open_positions/2021-03-postdoc-spblockchain.html