IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
12 April 2022
Paola de Perthuis, David Pointcheval
ePrint Report
In this paper, we extend Inner-Product Functional Encryption (IPFE), where there is just a vector in the key and a vector in the single sender's ciphertext, to two-client ciphertexts. More precisely, in our two-client functional encryption scheme, there are two Data Providers who can independently encrypt vectors $\mathbf{x}$ and $\mathbf{y}$ for a data consumer who can, from a functional decryption key associated to a vector $\mathbf{\alpha}$, compute $\sum \alpha_i x_i y_i = \mathbf{x} \cdot \mathsf{Diag}(\mathbf{\alpha}) \cdot \mathbf{y}^\top$. Ciphertexts are linear in the dimension of the vectors, whereas the functional decryption keys are of constant size.
We study two interesting particular cases: - 2-party Inner-Product Functional Encryption, with $\mathbf{\alpha}= (1,\ldots,1)$. There is a unique functional decryption key, which enables the computation of $\mathbf{x}\cdot \mathbf{y}^\top$ by a third party, where $\mathbf{x}$ and $\mathbf{y}$ are provided by two independent clients; - Inner-Product Functional Encryption with a Selector, with $\mathbf{x}= \mathbf{x}_0 \| \mathbf{x}_1$ and $\mathbf{y}= \bar{b}^n \| b^n \in \{ 1^n \| 0^n, 0^n \| 1^n \}$, for some bit $b$, on the public coefficients $\mathbf{\alpha} = \mathbf{\alpha}_0 \| \mathbf{\alpha}_1$, in the functional decryption key, so that one gets $\mathbf{x}_b \cdot \mathbf{\alpha}_b^\top$, where $\mathbf{x}$ and $b$ are provided by two independent clients.
This result is based on the fundamental Product-Preserving Lemma, which is of independent interest. It exploits Dual Pairing Vector Spaces (DPVS), with security proofs under the \mathsf{SXDH} assumption. We provide two practical applications to medical diagnosis for the latter IPFE with Selector, and to money-laundering detection for the former 2-party IPFE, both with strong privacy properties, with adaptative security and the use of labels granting a Multi-Client Functional Encryption (MCFE) security for the scheme, thus enabling its use in practical situations.
We study two interesting particular cases: - 2-party Inner-Product Functional Encryption, with $\mathbf{\alpha}= (1,\ldots,1)$. There is a unique functional decryption key, which enables the computation of $\mathbf{x}\cdot \mathbf{y}^\top$ by a third party, where $\mathbf{x}$ and $\mathbf{y}$ are provided by two independent clients; - Inner-Product Functional Encryption with a Selector, with $\mathbf{x}= \mathbf{x}_0 \| \mathbf{x}_1$ and $\mathbf{y}= \bar{b}^n \| b^n \in \{ 1^n \| 0^n, 0^n \| 1^n \}$, for some bit $b$, on the public coefficients $\mathbf{\alpha} = \mathbf{\alpha}_0 \| \mathbf{\alpha}_1$, in the functional decryption key, so that one gets $\mathbf{x}_b \cdot \mathbf{\alpha}_b^\top$, where $\mathbf{x}$ and $b$ are provided by two independent clients.
This result is based on the fundamental Product-Preserving Lemma, which is of independent interest. It exploits Dual Pairing Vector Spaces (DPVS), with security proofs under the \mathsf{SXDH} assumption. We provide two practical applications to medical diagnosis for the latter IPFE with Selector, and to money-laundering detection for the former 2-party IPFE, both with strong privacy properties, with adaptative security and the use of labels granting a Multi-Client Functional Encryption (MCFE) security for the scheme, thus enabling its use in practical situations.
Jordi Ribes-González, Oriol Farràs, Carles Hernández, Vatistas Kostalabros, Miquel Moretó
ePrint Report
Cache side-channel attacks allow adversaries to learn sensitive information about co-running processes by using only access latency measures and cache contention. This vulnerability has been shown to lead to several microarchitectural attacks. As a promising solution, recent work proposes Randomization-based Protected Caches (RPCs). RPCs randomize cache addresses, changing keys periodically so as to avoid long-term leakage. Unfortunately, recent attacks have called the security of state-of-the-art RPCs into question.
In this work, we tackle the problem of formally defining and analyzing the security properties of RPCs. We first give security definitions against access-based cache side-channel attacks that capture security against known attacks such as Prime+Probe and Evict+Probe. Then, using these definitions, we obtain results that allow to guarantee security by adequately choosing the rekeying period, the key generation algorithm and the cache randomizer, thus providing security proofs for RPCs under certain assumptions.
In this work, we tackle the problem of formally defining and analyzing the security properties of RPCs. We first give security definitions against access-based cache side-channel attacks that capture security against known attacks such as Prime+Probe and Evict+Probe. Then, using these definitions, we obtain results that allow to guarantee security by adequately choosing the rekeying period, the key generation algorithm and the cache randomizer, thus providing security proofs for RPCs under certain assumptions.
Hanno Becker, Vincent Hwang, Matthias J. Kannwischer, Lorenz Panny, Bo-Yin Yang
ePrint Report
Conventional wisdom purports that FFT-based integer multiplication methods (such as the Schönhage-Strassen algorithm) begin to compete with Karatsuba and Toom-Cook only for integers of several tens of thousands of bits. In this work, we challenge this belief: Leveraging recent advances in the implementation of Number-Theoretic Transforms (NTT) stimulated by their use in Post-Quantum Cryptography, we report on implementations of NTT-based integer arithmetic on two Arm Cortex-M CPUs on opposite ends of the performance spectrum: Cortex-M3 and Cortex-M55. Our results indicate that NTT-based multiplication is capable of outperforming the big-number arithmetic implementations of popular embedded cryptography libraries for integers as small as 2048 bits. To provide a realistic case study, we benchmark implementations of the RSA encryption and decryption operations. Between Cortex-M3 and Cortex-M55, we observe a $\approx10\times$ performance improvement.
11 April 2022
University of Plymouth in Applied Cryptography
Job Posting
Would you like to have your impact on the elderly care? Gaining a PhD along the way? We are delighted to be offering the opportunities for PhD studentship at University of Plymouth, United Kingdom in the scope of the project “Privacy-preserving IoT-assisted Elderly Monitoring for Smart Health Community” (PEM)(https://lnkd.in/dBBQtaUp) and its collaborated project “Harnessing Wearables for Protection” (https://lnkd.in/dd4R3MXZ). The focus of the research (PEM) is to create privacy-preserving anomaly detection service for IoT and cloud computing and promote its use for the elderly care.
The studentship is supported for 3.5 years and includes full Home tuition fees (United Kingdom) plus a stipend of £16,062.00 per annum (2022/23 rate). Applicants should have a first or upper second class honours degree in an appropriate subject and preferably a relevant Masters qualification. Prospective applicant should have a mathematical inclination, good knowledge of applied cryptography, good development skills, problem-solving skills and an ability to work independently, interpersonal and collaborative skills.
Closing date for applications:
Contact: Dr. Hai-Van Dang
-
Event Calendar
Event date: to
Submission deadline: 2 May 2022
Notification: 1 December 2022
Submission deadline: 2 May 2022
Notification: 1 December 2022
University of Luxembourg
Job Posting
The Applied Crypto group of the University of Luxembourg is offering
a Ph.D. student and a post-doc position in cryptography. Possible topics of interests are fully homomorphic encryption, public-key cryptanalysis, and side-channel attacks and countermeasures.
We offer a competitive salary (about 37,000 euro/year gross for Ph.D, and 64,000 euro/year gros for post-doc). The duration of the position is 3 years (+ 1 year extension) for Ph.D., and 2.5 years for post-doc.
Profile:
We offer a competitive salary (about 37,000 euro/year gross for Ph.D, and 64,000 euro/year gros for post-doc). The duration of the position is 3 years (+ 1 year extension) for Ph.D., and 2.5 years for post-doc.
Profile:
- For Ph.D. position: MSc degree or equivalent in Computer Science or in Mathematics.
- For post-doc position: a PhD in cryptography, with publications in competitive cryptographic conferences
Closing date for applications:
Contact: Prof. Jean-Sebastien Coron - jean-sebastien.coron at uni dot lu
More information: http://www.crypto-uni.lu/vacancies.html
New Jersey Institute of Technology (NJIT), USA
Job Posting
Multiple fully-funded Ph.D. positions in the area of databases, secure data processing, IoT, cloud/edge computing, blockchain, and secure model learning.
Details: NJIT is a Rank 1 Research University, situated in New York Metropolitan area, and is about 7 miles away from the beautiful New York City. New York Metropolitan area is a key part of the US and is the hub of several major tech and research companies. The qualified candidates will have opportunities for research internships and joint projects with lead-industrial companies. The position is looking for highly motivated graduate students to explore, design, and implement algorithms for databases, secure computing, IoT, and blockchain.
Topics are as follows:
Multi-party computation (MPC) or secret-sharing based database systems
Requirements: 1. Adequate knowledge of cryptographic techniques/algorithms, programming, and relational database systems 2. Knowledge of Java, SQL, and C/C++ 3. Familiarity with development tools for managing and building software projects, version control systems (Git), and testing tools (JUnit) 4. You must be an Undergraduate/Master student in computer science or a related field
Additional Information:
1. Starting date: As soon as possible 2. Please send your CV and other information (e.g., github account, sample projects, etc.) to: Shantanu Sharma (shantanu.sharma[AT]njit[DOT]edu) 3. Please write a few sentences in the email to introduce yourself and your interest in the position
Thank you and I look forward to hearing from you!
Details: NJIT is a Rank 1 Research University, situated in New York Metropolitan area, and is about 7 miles away from the beautiful New York City. New York Metropolitan area is a key part of the US and is the hub of several major tech and research companies. The qualified candidates will have opportunities for research internships and joint projects with lead-industrial companies. The position is looking for highly motivated graduate students to explore, design, and implement algorithms for databases, secure computing, IoT, and blockchain.
Topics are as follows:
- Design and implementation of an end-to-end-secure database system using MPC or secret-sharing
- Algorithm development for side-channel attacks on MPC
Requirements: 1. Adequate knowledge of cryptographic techniques/algorithms, programming, and relational database systems 2. Knowledge of Java, SQL, and C/C++ 3. Familiarity with development tools for managing and building software projects, version control systems (Git), and testing tools (JUnit) 4. You must be an Undergraduate/Master student in computer science or a related field
Additional Information:
1. Starting date: As soon as possible 2. Please send your CV and other information (e.g., github account, sample projects, etc.) to: Shantanu Sharma (shantanu.sharma[AT]njit[DOT]edu) 3. Please write a few sentences in the email to introduce yourself and your interest in the position
Thank you and I look forward to hearing from you!
Closing date for applications:
Contact: Shantanu Sharma (shantanu.sharma[AT]njit[DOT]edu)
More information: https://web.njit.edu/~ss797/students.html
07 April 2022
Subspace Labs
Job Posting
Subspace Network is building a radically decentralized, next-generation blockchain which allows developers to easily run Web3 apps at Internet scale. Subspace is based on original research funded by the US National Science Foundation and plans to launch its Network later this year. Subspace Labs is an early-stage, venture-backed startup with a remote-first, globally distributed team.
We are seeking a Protocol Researcher to join our rapidly growing team of Blockchain and Cryptocurrency enthusiasts and engineers. As a Protocol Research you will be responsible for formally analyzing the security claims of the Subspace Network. Your goal is to formally prove these claims or suggest improvement to the protocol as needed to support them. This shall result in a series of formal specifications and peer-reviewed papers.
As a Protocol Researcher you will: Analyze and validate our solutions to some of the hardest problems in the blockchain space, as they relate to Nakamoto consensus, decentralized storage, decoupled execution, crypto-economic incentives, and the scaling trilemma; research and propose solutions to open problems or unsubstantiated claims; develop a series of formal specifications that codify and clarify our solutions; collaborate directly with our protocol engineering team to ensure that specifications are clearly understood and implemented correctly; iterate findings into research papers suitable for peer-reviewed publication; work directly with our university partners, academic advisors, and third party engineering security partners on formal security analyses and audits; present research finding at industry events and university conferences; distribute and discuss results in our open-source online research forum.
Position Requirements: A PhD in Computer Science, Cryptography or a related field, and a strong record of peer-reviewed publications in cryptography, distributed systems, or peer-to-peer network, as they relate to blockchain protocols.
Closing date for applications:
Contact: Sky McWilliams, Director of People
More information: https://jobs.lever.co/subspacelabs/95bd61e2-8aae-4109-89df-67b7350263c8?lever-origin=applied&lever-source%5B%5D=IACR
Input Output Global - remote work opportunity
Job Posting
Description
As a Principal Architect in Applied Cryptography at IOG, you must be an engineer, an architect, an applied cryptographer, and a leader - it’s a multifaceted role. You have the exciting challenge of working with bleeding-edge research and technology, always with a focus on the market's needs. You will be a leader of an exceptional team, working on everything from Post-Quantum prototypes to hand-optimization of existing primitives to completely new products. To support you on this challenge, we have software architects, product managers, project managers, formal methods specialists, and QA test engineers, with whom you must have high bandwidth communications.
Your mission
- Champion the applied cryptography team
- Captain end-to-end development and delivery of new products
- Spearhead prototyping of cryptographic products
- Translate research into rigorous engineering specifications and implementations
- Meticulously review cryptographic protocols and proposed primitives
- Contribute to industry standards and operational best practices
- Identify where the business needs to be next and get it there.
Closing date for applications:
Contact:
https://apply.workable.com/io-global/j/8D6CAEE7DD/
marios.nicolaides@iohk.io
More information: https://apply.workable.com/io-global/j/8D6CAEE7DD/
Subspace Labs
Job Posting
Subspace Network is building a radically decentralized, next-generation blockchain which allows developers to easily run Web3 apps at Internet scale. Subspace is based on original research funded by the US National Science Foundation and planning to launch its Network later this year. Subspace Labs is an early-stage, venture-backed startup with a remote-first, globally distributed team.
We are seeking a Director of Research to join our rapidly growing team of Blockchain and Cryptocurrency enthusiasts and engineers. As our Director of Research you will primarily be responsible for building and leading a team of protocol researchers. The research team will be responsible for analyzing the security of the Subspace Network, formalizing our specifications, and publishing relevant research results in the peer-reviewed setting.
Responsibilities: Collaborate directly with the CEO & CTO to translate our existing white paper, documentation, and protocol roadmap into a set of formal specifications; identify the key security challenges and develop a long-term research and publication roadmap which addresses them; ensure research findings are continuously fed back into the protocol design and implementation; recruit hire and lead our international protocol research team, consisting of research scientists, post-doctoral researchers, and graduate research interns; work directly with our university partners, academic advisors, and third party engineering security partners to facilitate formal security analyses and audits; design and administer an open-source online research forum and work to engage the global research community in the security analysis of our protocol.
Requirements: A PhD in Computer Science, Cryptography or a related field; strong record of peer-reviewed publications in cryptography, distributed systems, or peer-to-peer network, as they relate to blockchain technologies.
Closing date for applications:
Contact: CEO & Co-Founder, Jeremiah Wagstaff
More information: https://subspace.network/
Sunscreen; San Francisco, USA or remote
Job Posting
Sunscreen is building the privacy engine of the new web. We're bringing private computation to all by making advanced cryptographic primitives (e.g. fully homomorphic encryption, zero-knowledge proofs) easy to use.
What you'll accomplish your 1st year here...You'll help build the core infrastructure of a new cryptographic system
You’ll implement cryptographic primitives (e.g. zero-knowledge proof systems) and write robust, security-first code that will run in high-risk, adversarial environments
You'll become familiar with the latest advances in cryptography and determine their applicability to Sunscreen’s system
You'll have opportunities to present your work at conferences
You...Think technology should be frictionless (documentation is important to you!)
Have experience implementing cryptographic primitives (ideally efficient ZKP systems) in a performant and modular way
Are comfortable working with multiple programming languages
Are excited to get your hands dirty learning new math and cryptography
We offer...A highly flexible, remote-first working environment
Competitive compensation + significant equity
Homecomings where we gather in one spot to meet each other and work together
Annual health and wellness budget
Opportunity to travel to and present at conferences if desired (we hope you do!)
What you'll accomplish your 1st year here...
You...
We offer...
Closing date for applications:
Contact: Ravital Solomon (ravital@sunscreen.tech)
More information: https://www.notion.so/Jobs-at-Sunscreen-6966db120ec3425ead92f64b40d4cb17?p=6516320b644547c9b0ef4940684e2dc2
University of Neuchatel
Job Posting
The University of Neuchâtel announces a position of
Maître-assistant
(Lecturer — Senior Scientist)
Jointly at the Institute of Computer Science and the Institute of Mathematics
Full time 100%
Requirements:
• PhD in Computer Science or Mathematics (obtained up to 10 years ago)
• Good scientific knowledge in Computer Science and Mathematics
• Sustained teaching experience
• Strong interest in interdisciplinary approaches
Activities:
• Teaching in Computer Science and Mathematics: up to 4 hours per week at Bachelor and Master level in French and in English
• Student supervision
• Research development
• Participation in administrative tasks at the institutes
Start date: 01.08.2022 or to be agreed
Position duration: 4 years, renewable 2 years / legal treatment and obligations
The application of each candidate must include a letter of motivation, a curriculum vitae and a copy of the titles earned. A complete application file shall be sent in one PDF file to the address secretariat.iiun@unine.ch. The applications will be evaluated starting from May 1st 2022 until the position is filled.
The salary is defined according to the scale of the University of Neuchâtel, see http://www.unine.ch/srh/maitres-assistant-e-s-mer
Further information can be obtained by Prof. Pascal Felber pascal.felber@unine.ch and Prof. Elisa Gorla elisa.gorla@unine.ch, as well as on the page www.unine.ch/sciences
L'Université de Neuchâtel s'engage activement à la mise en oeuvre de sa responsabilité et offre des conditions de travail non discriminatoires, les candidatures féminines sont spécifiquement encouragées.
Jointly at the Institute of Computer Science and the Institute of Mathematics
Full time 100%
Requirements:
• PhD in Computer Science or Mathematics (obtained up to 10 years ago)
• Good scientific knowledge in Computer Science and Mathematics
• Sustained teaching experience
• Strong interest in interdisciplinary approaches
Activities:
• Teaching in Computer Science and Mathematics: up to 4 hours per week at Bachelor and Master level in French and in English
• Student supervision
• Research development
• Participation in administrative tasks at the institutes
Start date: 01.08.2022 or to be agreed
Position duration: 4 years, renewable 2 years / legal treatment and obligations
The application of each candidate must include a letter of motivation, a curriculum vitae and a copy of the titles earned. A complete application file shall be sent in one PDF file to the address secretariat.iiun@unine.ch. The applications will be evaluated starting from May 1st 2022 until the position is filled.
The salary is defined according to the scale of the University of Neuchâtel, see http://www.unine.ch/srh/maitres-assistant-e-s-mer
Further information can be obtained by Prof. Pascal Felber pascal.felber@unine.ch and Prof. Elisa Gorla elisa.gorla@unine.ch, as well as on the page www.unine.ch/sciences
L'Université de Neuchâtel s'engage activement à la mise en oeuvre de sa responsabilité et offre des conditions de travail non discriminatoires, les candidatures féminines sont spécifiquement encouragées.
Closing date for applications:
Contact: Prof. Pascal Felber pascal.felber@unine.ch and Prof. Elisa Gorla elisa.gorla@unine.ch
More information: http://www.unine.ch/sciences
06 April 2022
Benjamin Wesolowski
ePrint Report
We prove that isogenies between Drinfeld modules over a finite field can be computed in polynomial time. This breaks Drinfeld analogs of isogeny-based cryptosystems.
Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan
ePrint Report
We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021). This allows us to bring to bear the powerful machinery of LWE-based cryptography to the applications of CLWE. For example, we obtain the hardness of CLWE under the classical worst-case hardness of the gap shortest vector problem. Previously, this was known only under quantum worst-case hardness of lattice problems. More broadly, with our reductions between the two problems, any future developments to LWE will also apply to CLWE and its downstream applications.
As a concrete application, we show an improved hardness result for density estimation for mixtures of Gaussians. In this computational problem, given sample access to a mixture of Gaussians, the goal is to output a function that estimates the density function of the mixture. Under the (plausible and widely believed) exponential hardness of the classical LWE problem, we show that Gaussian mixture density estimation in $\mathbb{R}^n$ with roughly $\log n$ Gaussian components given $\mathsf{poly}(n)$ samples requires time quasi-polynomial in $n$. Under the (conservative) polynomial hardness of LWE, we show hardness of density estimation for $n^{\epsilon}$ Gaussians for any constant $\epsilon > 0$, which improves on Bruna, Regev, Song and Tang (STOC 2021), who show hardness for at least $\sqrt{n}$ Gaussians under polynomial (quantum) hardness assumptions. Our key technical tool is a reduction from classical LWE to LWE with $k$-sparse secrets where the multiplicative increase in the noise is only $O(\sqrt{k})$, independent of the ambient dimension $n$.
As a concrete application, we show an improved hardness result for density estimation for mixtures of Gaussians. In this computational problem, given sample access to a mixture of Gaussians, the goal is to output a function that estimates the density function of the mixture. Under the (plausible and widely believed) exponential hardness of the classical LWE problem, we show that Gaussian mixture density estimation in $\mathbb{R}^n$ with roughly $\log n$ Gaussian components given $\mathsf{poly}(n)$ samples requires time quasi-polynomial in $n$. Under the (conservative) polynomial hardness of LWE, we show hardness of density estimation for $n^{\epsilon}$ Gaussians for any constant $\epsilon > 0$, which improves on Bruna, Regev, Song and Tang (STOC 2021), who show hardness for at least $\sqrt{n}$ Gaussians under polynomial (quantum) hardness assumptions. Our key technical tool is a reduction from classical LWE to LWE with $k$-sparse secrets where the multiplicative increase in the noise is only $O(\sqrt{k})$, independent of the ambient dimension $n$.
Marc Rivinius, Pascal Reisert, Daniel Rausch, Ralf Küsters
ePrint Report
In recent years, lattice-based secure multi-party computation (MPC) has seen a rise in popularity and is used more and more in large scale applications like privacy-preserving cloud computing, electronic voting, or auctions. Many of these applications come with the following high security requirements: a computation result should be publicly verifiable, with everyone being able to identify a malicious party and hold it accountable, and a malicious party should not be able to corrupt the computation, force a protocol restart, or block honest parties or an honest third-party (client) that provided private inputs from receiving a correct result. The protocol should guarantee verifiability and accountability even if all protocol parties are malicious. While some protocols address one or two of these often essential security features, we present the first publicly verifiable and accountable, and (up to a threshold) robust SPDZ-like MPC protocol without restart. We propose protocols for accountable and robust online, offline, and setup computations. We adapt and partly extend the lattice-based commitment scheme by Baum et al. (SCN 2018) as well as other primitives like ZKPs. For the underlying commitment scheme and the underlying BGV encryption scheme we determine ideal parameters.
We give a performance evaluation of our protocols and compare them to state-of-the-art protocols both with and without our target security features: public accountability, public verifiability and robustness.
Frédéric Dupuis, Philippe Lamontagne, Louis Salvail
ePrint Report
We explore the cryptographic power of arbitrary shared physical resources. The most general such resource is access to a fresh entangled quantum state at the outset of each protocol execution. We call this the Common Reference Quantum State (CRQS) model, in analogy to the well-known Common Reference String (CRS). The CRQS model is a natural generalization of the CRS model but appears to be more powerful: in the two-party setting, a CRQS can sometimes exhibit properties associated with a Random Oracle queried once by measuring a maximally entangled state in one of many mutually unbiased bases. We formalize this notion as a Weak One-Time Random Oracle (WOTRO), where we only ask of the $m$-bit output to have some randomness when conditioned on the $n$-bit input.
We show that WOTRO with $n - m \in \omega(\lg n)$ is black-box impossible in the CRQS model, meaning that no protocol can have its security black-box reduced to a cryptographic game. We define a (inefficient) quantum adversary against any WOTRO protocol that can be efficiently simulated in polynomial time, ruling out any reduction to a secure game that only makes black-box queries to the adversary. On the other hand, we introduce a non-game quantum assumption for hash functions that implies WOTRO in the CRQS model (where the CRQS consists only of EPR pairs). We first build a statistically secure WOTRO protocol where $m = n$, then hash the output.
The impossibility of WOTRO has the following consequences. First, we show the black-box impossibility of a quantum Fiat-Shamir transform, extending the impossibility result of Bitansky et al. (TCC '13) to the CRQS model. Second, we show a black-box impossibility result for a strenghtened version of quantum lightning (Zhandry, Eurocrypt '19) where quantum bolts have an additional parameter that cannot be changed without generating new bolts.
We show that WOTRO with $n - m \in \omega(\lg n)$ is black-box impossible in the CRQS model, meaning that no protocol can have its security black-box reduced to a cryptographic game. We define a (inefficient) quantum adversary against any WOTRO protocol that can be efficiently simulated in polynomial time, ruling out any reduction to a secure game that only makes black-box queries to the adversary. On the other hand, we introduce a non-game quantum assumption for hash functions that implies WOTRO in the CRQS model (where the CRQS consists only of EPR pairs). We first build a statistically secure WOTRO protocol where $m = n$, then hash the output.
The impossibility of WOTRO has the following consequences. First, we show the black-box impossibility of a quantum Fiat-Shamir transform, extending the impossibility result of Bitansky et al. (TCC '13) to the CRQS model. Second, we show a black-box impossibility result for a strenghtened version of quantum lightning (Zhandry, Eurocrypt '19) where quantum bolts have an additional parameter that cannot be changed without generating new bolts.
Takashi Yamakawa, Mark Zhandry
ePrint Report
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1:
- There are NP search problems solvable by BQP machines but not BPP machines.
- There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.
- There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.
- Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.
By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
- There are NP search problems solvable by BQP machines but not BPP machines.
- There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.
- There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.
- Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.
By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
Nico Döttling, Lucjan Hanzlik, Bernardo Magri, Stella Wohnig
ePrint Report
Blockchain protocols have revolutionized the way individuals and devices can interact and transact over the internet. More recently, a trend has emerged to harness blockchain technology as a catalyst to enable advanced security features in distributed applications, in particular fairness. However, the tools employed to achieve these security features are either resource wasteful (e.g., time-lock primitives) or only efficient in theory (e.g., witness encryption). We present McFly, a protocol that allows one to efficiently ``encrypt a message to the future'' such that the receiver can decrypt the message almost effortlessly. Towards this goal, we design and implement a novel primitive we call signature-based witness encryption and combine it with a BFT blockchain (or a blockchain finality layer) in such a way that the decryption of the message can be piggybacked on the tasks already performed by the blockchain committee, resulting in almost-for-free decryption. To demonstrate the practicality of the McFly protocol, we implemented our signature-based witness encryption scheme and evaluated it on a standard laptop with Intel i7 @2,3 GHz. For the popular BLS12-381 curve, a $381$-bit message and a committee of size $500$ the encryption time is $9.8s$ and decryption is $14.8 s$. The scheme remains practical for a committee of size $2000$ with an encryption time of $58 s$ and decryption time of $218 s$.
Jiayu Zhang
ePrint Report
In the quantum computation verification problem, a quantum server wants to convince a client that the output of evaluating a quantum circuit $C$ is some result that it claims. This problem is considered very important both theoretically and practically in quantum computation [arXiv:1709.06984, 1704.04487, 1209.0449]. The client is considered to be limited in computational power, and one desirable property is that the client can be completely classical, which leads to the classical verification of quantum computation (CVQC) problem. In terms of the time complexity of server-side quantum computations (which typically dominate the total time complexity of both the client and the server), the fastest single-server CVQC protocol so far has complexity $O(poly(\kappa)|C|^3)$ where $|C|$ is the size of the circuit to be verified, given by Mahadev [arXiv:1804.01082]. This leads to a similar cubic time blowup in many existing protocols including multiparty quantum computation, zero knowledge and obfuscation [ia.cr/2021/964, arXiv:1902.05217, 2106.06094, 1912.00990, 2012.04848, 1911.08101]. Considering the preciousness of quantum computation resources, this cubic complexity barrier could be a big obstacle for taking protocols for these problems into practice.
In this work, by developing new techniques, we give a new CVQC protocol with complexity $O(poly(\kappa)|C|)$ (in terms of the total time complexity of both the client and the server), which is significantly faster than existing protocols. Our protocol is secure in the quantum random oracle model [arXiv:1008.0931] assuming the existence of noisy trapdoor claw-free functions [arXiv:1804.00640], which are both extensively used assumptions in quantum cryptography. Along the way, we also give a new classical channel remote state preparation protocol for states in $\{|+_\theta\rangle=\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta\pi/4}|1\rangle):\theta\in \{0,1\cdots 7\}\}$, another basic primitive in quantum cryptography. Our protocol allows for parallel verifiable preparation of $L$ independently random states in this form (up to a constant overall error and a possibly unbounded server-side isometry), and runs in only $O(poly(\kappa)L)$ time and constant rounds; for comparison, existing works (even for possibly simpler state families) all require very large or unestimated time and round complexities [arXiv:1904.06320, 1904.06303, 2201.13445, 2201.13430].
In this work, by developing new techniques, we give a new CVQC protocol with complexity $O(poly(\kappa)|C|)$ (in terms of the total time complexity of both the client and the server), which is significantly faster than existing protocols. Our protocol is secure in the quantum random oracle model [arXiv:1008.0931] assuming the existence of noisy trapdoor claw-free functions [arXiv:1804.00640], which are both extensively used assumptions in quantum cryptography. Along the way, we also give a new classical channel remote state preparation protocol for states in $\{|+_\theta\rangle=\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta\pi/4}|1\rangle):\theta\in \{0,1\cdots 7\}\}$, another basic primitive in quantum cryptography. Our protocol allows for parallel verifiable preparation of $L$ independently random states in this form (up to a constant overall error and a possibly unbounded server-side isometry), and runs in only $O(poly(\kappa)L)$ time and constant rounds; for comparison, existing works (even for possibly simpler state families) all require very large or unestimated time and round complexities [arXiv:1904.06320, 1904.06303, 2201.13445, 2201.13430].
Xinyu Mao, Noam Mazor, Jiapeng Zhang
ePrint Report
Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long and successful line of research studied these primitives, their optimal efficiency is not yet fully understood: there are gaps between the known upper bounds and the known lower bounds for black-box constructions.
Interestingly, the first construction of PRGs by H ̊astad, Impagliazzo, Levin, and Luby [SICOMP ’99], and the UOWHFs construction by Rompel [STOC ’90] shared a similar structure. Since then, there was an improvement in the efficiency of both constructions: The state of the art construction of PRGs by Haitner, Reingold, and Vadhan [STOC ’10] uses $O(n^4)$ bits of random seed and $O(n^3)$ non-adaptive calls to the one-way function, or alternatively, seed of size $O(n^3)$ with $O(n^3)$ adaptive calls (Vadhan and Zheng [STOC ’12]). Constructing a UOWHF with similar parameters is still an open question. Currently, the best UOWHF construction by Haitner, Holenstein, Reingold, Vadhan, and Wee [Eurocrypt ’10] uses $O(n^{13})$ adaptive calls and a key of size $O(n^5)$.
In this work we give the first non-adaptive construction of UOWHFs from arbitrary one-way functions. Our construction uses $O(n^9)$ calls to the one-way function, and a key of length $O(n^{10})$. By the result of Applebaum, Ishai, and Kushilevitz [FOCS ’04], the above implies the existence of UOWHFs in NC0, given the existence of one-way functions in NC1. We also show that the PRG construction of Haitner et al., with small modifications, yields a relaxed notion of UOWHFs. In order to analyze this construction, we introduce the notion of next-bit unreachable entropy, which replaces the next-bit pseudoentropy notion, used in the PRG construction above.
Interestingly, the first construction of PRGs by H ̊astad, Impagliazzo, Levin, and Luby [SICOMP ’99], and the UOWHFs construction by Rompel [STOC ’90] shared a similar structure. Since then, there was an improvement in the efficiency of both constructions: The state of the art construction of PRGs by Haitner, Reingold, and Vadhan [STOC ’10] uses $O(n^4)$ bits of random seed and $O(n^3)$ non-adaptive calls to the one-way function, or alternatively, seed of size $O(n^3)$ with $O(n^3)$ adaptive calls (Vadhan and Zheng [STOC ’12]). Constructing a UOWHF with similar parameters is still an open question. Currently, the best UOWHF construction by Haitner, Holenstein, Reingold, Vadhan, and Wee [Eurocrypt ’10] uses $O(n^{13})$ adaptive calls and a key of size $O(n^5)$.
In this work we give the first non-adaptive construction of UOWHFs from arbitrary one-way functions. Our construction uses $O(n^9)$ calls to the one-way function, and a key of length $O(n^{10})$. By the result of Applebaum, Ishai, and Kushilevitz [FOCS ’04], the above implies the existence of UOWHFs in NC0, given the existence of one-way functions in NC1. We also show that the PRG construction of Haitner et al., with small modifications, yields a relaxed notion of UOWHFs. In order to analyze this construction, we introduce the notion of next-bit unreachable entropy, which replaces the next-bit pseudoentropy notion, used in the PRG construction above.