Joseph Carolan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Joseph Carolan has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Alexander Poremba
Boston University
1 shared publication - Andrew M. Childs
Joint Center for Quantum Information and Computer Science
1 shared publication - Luke Schaeffer
University of Waterloo
1 shared publication - Mark Zhandry
Stanford University, Stanford, USA
1 shared publication - Matt Kovacs-Deak
University of Maryland College Park
1 shared publication
Latest Publications
- Open Access
- 3 August 2026
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 3 (2)
(Quantum) Indifferentiability and Pre-Computation
Indifferentiability is an important cryptographic paradigm for analyzing the security of ideal objects—both in a classical and quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction to be “as good as” an ideal object. A paradigmatic application of the framework is showing that a hash function does not have structural weaknesses, by proving it to be indifferentiable from a random oracle. Despite its generality, indifferentiability is not known to offer security against pre-processing attacks, in which the adversary gains access to classical or quantum advice that is relevant to the particular construction. In this work, we show that indifferentiability is generically insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable with pre-computation from a random oracle. This yields the first, and tight, quantum space-time trade-offs for one-round sponge inversion.
- 3 August 2026
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 3 (2)
Open Access(Quantum) Indifferentiability and Pre-Computation
Indifferentiability is an important cryptographic paradigm for analyzing the security of ideal objects—both in a classical and quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction to be “as good as” an ideal object. A paradigmatic application of the framework is showing that a hash function does not have structural weaknesses, by proving it to be indifferentiable from a random oracle. Despite its generality, indifferentiability is not known to offer security against pre-processing attacks, in which the adversary gains access to classical or quantum advice that is relevant to the particular construction. In this work, we show that indifferentiability is generically insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable with pre-computation from a random oracle. This yields the first, and tight, quantum space-time trade-offs for one-round sponge inversion.
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 150-161
Compressed Permutation Oracles
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 150-161
Open AccessCompressed Permutation Oracles
- Open Access
- 20 April 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 7 (3) , 1-29
Translation-Invariant Quantum Algorithms for Ordered Search are Optimal
Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses \(\lceil \log _{2}{n}\rceil\) queries for a list of length n . Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of \(\log _{2}{n}\) for exact quantum algorithms is only known to lie between \((\ln {2})/\pi \approx 0.221\) and \(4/\log _{2}{605} \approx 0.433\) . We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any bounded-error, k -query quantum algorithm for ordered search can be implemented by a k -query algorithm in this special class. Second, we use linear programming to show that the best exact 5-query quantum algorithm can search a list of length 7265, giving an ordered search algorithm that asymptotically uses \(5 \log _{7265}{n} \approx 0.390 \log _{2}{n}\) quantum queries.- 20 April 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 7 (3) , 1-29
Open AccessTranslation-Invariant Quantum Algorithms for Ordered Search are Optimal
Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses \(\lceil \log _{2}{n}\rceil\) queries for a list of length n . Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of \(\log _{2}{n}\) for exact quantum algorithms is only known to lie between \((\ln {2})/\pi \approx 0.221\) and \(4/\log _{2}{605} \approx 0.433\) . We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any bounded-error, k -query quantum algorithm for ordered search can be implemented by a k -query algorithm in this special class. Second, we use linear programming to show that the best exact 5-query quantum algorithm can search a list of length 7265, giving an ordered search algorithm that asymptotically uses \(5 \log _{7265}{n} \approx 0.390 \log _{2}{n}\) quantum queries.