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:
11 April 2022
-
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.
Véronique Cortier, Pierrick Gaudry, Quentin Yang
ePrint Report
Coercion-resistance is a security property of electronic voting, often considered as a must-have for high-stake elections. The JCJ voting scheme, proposed in 2005 by Juels, Catalon and Jakobsson, is still the reference paradigm when designing a coercion-resistant protocol. We highlight a weakness in JCJ that is also present in all the systems following its general structure. This comes from the procedure that precedes the tally, where the trustees remove the ballots that should not be counted. This phase leaks more information than necessary, leading to potential threats for the coerced voters. Fixing this leads to the notion of cleansing-hiding, that we apply to form a variant of JCJ that we call CHide. One reason for the problem not being seen before is the fact that the associated formal definition of coercion-resistance was too weak. We therefore propose a definition that can take into accounts more behaviors such as revoting or the addition of fake ballots by authorities. We then prove that CHide is coercion-resistant for this definition, and that JCJ is coercion-resistant for a slightly weakened version of our definition, that models the leakage of information in JCJ.
Jianfang "Danny" Niu
ePrint Report
Xifrat was a group-theoretic public-key cryptosystem based on a quasigroup with the special property of "restricted-commutativity". It was broken within half a month of its publication, due to a mistake made in the "mixing" function.
In this paper, we revisit the design decisions made, proposing new constructions, and attempt (again) to build secure digital signature schemes and key encapsulation mechanisms.
If the schemes can be proven secure, then this will be the most compact and the most efficient post-quantum cryptosystem ever proposed to date.
In this paper, we revisit the design decisions made, proposing new constructions, and attempt (again) to build secure digital signature schemes and key encapsulation mechanisms.
If the schemes can be proven secure, then this will be the most compact and the most efficient post-quantum cryptosystem ever proposed to date.
Adrián Ranea, Joachim Vandersmissen, Bart Preneel
ePrint Report
Since the first white-box implementation of AES published twenty years ago, no significant progress has been made in the design of secure implementations against an attacker with full control of the device. Designing white-box implementations of existing block ciphers is a challenging problem, as all proposals have been broken. Only two white-box design strategies have been published this far: the CEJO framework, which can only be applied to ciphers with small S-boxes, and self-equivalence encodings, which were only applied to AES.
In this work we propose implicit implementations, a new design of white-box implementations based on implicit functions, and we show that current generic attacks that break CEJO or self-equivalence implementations are not successful against implicit implementations. The generation and the security of implicit implementations are related to the self-equivalences of the non-linear layer of the cipher, and we propose a new method to obtain self-equivalences based on the CCZ-equivalence. We implemented this method and many other functionalities in a new open-source tool BoolCrypt, which we used to obtain for the first time affine, linear, and even quadratic self-equivalences of the permuted modular addition. Using the implicit framework and these self-equivalences, we describe for the first time a practical white-box implementation of a generic Addition-Rotation-XOR (ARX) cipher, and we provide an open-source tool to easily generate implicit implementations of ARX ciphers.
In this work we propose implicit implementations, a new design of white-box implementations based on implicit functions, and we show that current generic attacks that break CEJO or self-equivalence implementations are not successful against implicit implementations. The generation and the security of implicit implementations are related to the self-equivalences of the non-linear layer of the cipher, and we propose a new method to obtain self-equivalences based on the CCZ-equivalence. We implemented this method and many other functionalities in a new open-source tool BoolCrypt, which we used to obtain for the first time affine, linear, and even quadratic self-equivalences of the permuted modular addition. Using the implicit framework and these self-equivalences, we describe for the first time a practical white-box implementation of a generic Addition-Rotation-XOR (ARX) cipher, and we provide an open-source tool to easily generate implicit implementations of ARX ciphers.
Katarzyna Kapusta, Matthieu Rambaud, Ferdinand Sibleyras
ePrint Report
We consider threshold Computational Secret Sharing Schemes, i.e., such that the secret can be recovered from any $t+1$ out of $n$ shares, and such that no computationally bounded adversary can distinguish between $t$ shares of a chosen secret and a uniform string.
We say that such a scheme has Constant Size (CSSS) if, in the asymptotic regime of many shares of small size the security parameter, then the total size of shares reaches the minimum, which is the size of an erasures-correction encoding of the secret with same threshold.
But all CSSS so far have only maximum threshold, i.e., $t=n-1$.
They are known as All Or Nothing Transforms (AONT).
On the other hand, for arbitrary thresholds $t
Our first contribution is to show that the CSSS of [Des00, Crypto], which holds under the ideal cipher assumption, looses its privacy when instantiated with a plain pseudorandom permutation.
Our main contribution is a scheme which: is the first CSSS for any threshold $t$, and furthermore, whose security holds, for the first time, under any plain pseudorandom function, with the only idealized assumption being in the key-derivation function. It is based on the possibly new observation that the scheme of [Des00] can be seen as an additive secret-sharing of an encryption key, using the ciphertext itself as a source of randomness.
A variation of our construction enables to improve upon known schemes, that we denote as Encryption into Shares with Resilience against Key exposure (ESKE), having the property that all ciphertext blocks are needed to obtain any information, even when the key is leaked. We obtain the first ESKE with arbitrary threshold $t$ and constant size, furthermore in one pass of encryption. Also, for the first time, the only idealized assumption is in the key-derivation.
Then, we demonstrate how to establish fast revocable storage on an untrusted server, from any black box ESKE. Instantiated with our ESKE, then encryption and decryption both require only $1$ pass of symmetric primitives under standard assumptions (except the key-derivation), compared to at least $2$ consecutive passes in [MS18, CT-RSA] and more in [Bac+16, CCS].
We finally bridge the gap between two conflicting specifications of AONT in the literature: one very similar to CSSS, which has indistinguishability, and one which has not.
Our first contribution is to show that the CSSS of [Des00, Crypto], which holds under the ideal cipher assumption, looses its privacy when instantiated with a plain pseudorandom permutation.
Our main contribution is a scheme which: is the first CSSS for any threshold $t$, and furthermore, whose security holds, for the first time, under any plain pseudorandom function, with the only idealized assumption being in the key-derivation function. It is based on the possibly new observation that the scheme of [Des00] can be seen as an additive secret-sharing of an encryption key, using the ciphertext itself as a source of randomness.
A variation of our construction enables to improve upon known schemes, that we denote as Encryption into Shares with Resilience against Key exposure (ESKE), having the property that all ciphertext blocks are needed to obtain any information, even when the key is leaked. We obtain the first ESKE with arbitrary threshold $t$ and constant size, furthermore in one pass of encryption. Also, for the first time, the only idealized assumption is in the key-derivation.
Then, we demonstrate how to establish fast revocable storage on an untrusted server, from any black box ESKE. Instantiated with our ESKE, then encryption and decryption both require only $1$ pass of symmetric primitives under standard assumptions (except the key-derivation), compared to at least $2$ consecutive passes in [MS18, CT-RSA] and more in [Bac+16, CCS].
We finally bridge the gap between two conflicting specifications of AONT in the literature: one very similar to CSSS, which has indistinguishability, and one which has not.