Peter Hall
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Peter Hall has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Eli Goldin
New York University
4 shared publications - Yevgeniy Dodis
New York University, New York, USA
3 shared publications - Bruno Cavalar
Department of Computer Science University of Oxford United Kingdom
2 shared publications - Matthew Gray
Department of Computer Science, University of Oxford, Oxford, UK
2 shared publications - Aggelos Kiayias
The University of Edinburgh
1 shared publication Alison Lin
Independent Contributor
1 shared publication
Latest Publications
- 28 April 2025
- Published by Springer Nature
- p. 82-107
A Meta-complexity Characterization of Quantum Cryptography
- 28 April 2025
- Published by Springer Nature
- p. 82-107
A Meta-complexity Characterization of Quantum Cryptography
- Open Access
- 27 March 2025
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 9, 1679
On the Computational Hardness of Quantum One-Wayness
There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that , which gives a lower bound on the necessary hardness.One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.We show that pseudorandom states compressing bits to qubits can be used to build one-way state generators and pseudorandom states compressing bits to qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than -qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a oracle.An interesting implication of our results is that a -copy one-way state generator exists unconditionally, for every . This contrasts nicely with the previously known fact that -copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments.- 27 March 2025
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 9, 1679
Open AccessOn the Computational Hardness of Quantum One-Wayness
There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that , which gives a lower bound on the necessary hardness.One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.We show that pseudorandom states compressing bits to qubits can be used to build one-way state generators and pseudorandom states compressing bits to qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than -qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a oracle.An interesting implication of our results is that a -copy one-way state generator exists unconditionally, for every . This contrasts nicely with the previously known fact that -copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments. - Open Access
- 13 January 2025
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (4)
HELP: Everlasting Privacy through Server-Aided Randomness
Everlasting (EL) privacy offers an attractive solution to the Store-Now-Decrypt-Later (SNDL) problem, where future increases in the attacker's capability could break systems which are believed to be secure today. Instead of requiring full information-theoretic security, everlasting privacy allows computationally-secure transmissions of ephemeral secrets, which are only "effective" for a limited periods of time, after which their compromise is provably useless for the SNDL attacker. In this work we revisit such everlasting privacy model of Dodis and Yeo (ITC'21), which we call Hypervisor EverLasting Privacy (HELP). HELP is a novel architecture for generating shared randomness using a network of semi-trusted servers (or "hypervisors"), trading the need to store/distribute large shared secrets with the assumptions that it is hard to: (a) simultaneously compromise too many publicly accessible ad-hoc servers; and (b) break a computationally-secure encryption scheme very quickly. While Dodis and Yeo presented good HELP solutions in the asymptotic sense, their solutions were concretely expensive and used heavy tools (like large finite fields or gigantic Toeplitz matrices). We abstract and generalize the HELP architecture to allow for more efficient instantiations, and construct several concretely efficient HELP solutions. Our solutions use elementary cryptographic operations, such as hashing and message authentication. We also prove a very strong composition theorem showing that our EL architecture can use any message transmission method which is computationally-secure in the Universal Composability (UC) framework. This is the first positive composition result for everlasting privacy, which was otherwise known to suffer from many "non-composition" results (Müller-Quade and Unruh; J of Cryptology'10).
- 13 January 2025
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (4)
Open AccessHELP: Everlasting Privacy through Server-Aided Randomness
Everlasting (EL) privacy offers an attractive solution to the Store-Now-Decrypt-Later (SNDL) problem, where future increases in the attacker's capability could break systems which are believed to be secure today. Instead of requiring full information-theoretic security, everlasting privacy allows computationally-secure transmissions of ephemeral secrets, which are only "effective" for a limited periods of time, after which their compromise is provably useless for the SNDL attacker. In this work we revisit such everlasting privacy model of Dodis and Yeo (ITC'21), which we call Hypervisor EverLasting Privacy (HELP). HELP is a novel architecture for generating shared randomness using a network of semi-trusted servers (or "hypervisors"), trading the need to store/distribute large shared secrets with the assumptions that it is hard to: (a) simultaneously compromise too many publicly accessible ad-hoc servers; and (b) break a computationally-secure encryption scheme very quickly. While Dodis and Yeo presented good HELP solutions in the asymptotic sense, their solutions were concretely expensive and used heavy tools (like large finite fields or gigantic Toeplitz matrices). We abstract and generalize the HELP architecture to allow for more efficient instantiations, and construct several concretely efficient HELP solutions. Our solutions use elementary cryptographic operations, such as hashing and message authentication. We also prove a very strong composition theorem showing that our EL architecture can use any message transmission method which is computationally-secure in the Universal Composability (UC) framework. This is the first positive composition result for everlasting privacy, which was otherwise known to suffer from many "non-composition" results (Müller-Quade and Unruh; J of Cryptology'10).
- Open Access
A Meta-Complexity Characterization of Quantum Cryptography
We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-complexity problem, initiated by Liu and Pass. Moreover, since the average-case hardness of Kolmogorov complexity over classically polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over which probability estimation is hard. We also observe that the oracle worlds of defined by Kretschmer et. al. rule out any relativizing characterization of one-way puzzles by the hardness of a problem in NP or QMA, which means that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem.
Open AccessA Meta-Complexity Characterization of Quantum Cryptography
We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-complexity problem, initiated by Liu and Pass. Moreover, since the average-case hardness of Kolmogorov complexity over classically polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over which probability estimation is hard. We also observe that the oracle worlds of defined by Kretschmer et. al. rule out any relativizing characterization of one-way puzzles by the hardness of a problem in NP or QMA, which means that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem.
- 16 August 2024
- Published by Springer Nature
- p. 113-146
Towards Permissionless Consensus in the Standard Model via Fine-Grained Complexity
- 16 August 2024
- Published by Springer Nature
- p. 113-146
Towards Permissionless Consensus in the Standard Model via Fine-Grained Complexity
- 9 August 2023
- Published by Springer Nature
- p. 514-546
Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance
- 9 August 2023
- Published by Springer Nature
- p. 514-546
Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance
- 1 January 2022
- Published by Springer Nature
- p. 353-383
Nonmalleable Digital Lockers and Robust Fuzzy Extractors in the Plain Model
- 1 January 2022
- Published by Springer Nature
- p. 353-383
Nonmalleable Digital Lockers and Robust Fuzzy Extractors in the Plain Model