Creating quantum-resistant classical-classical OWFs from quantum-classical OWFs

Wei Zheng Teo, Marco Carmosino, Lior HoresharXiv 2022 · DOI · arXiv

Abstract

One-way functions (OWFs) are fundamental primitives in cryptography, yet many classical constructions are vulnerable to quantum-era attacks. This paper explores the bridge between quantum-input/classical-output (Q-C) functions and purely classical (C-C) functions. By developing a "domain shifting" technique, the authors demonstrate that the existence of Q-C OWFs implies the existence of quantum-resistant classical OWFs, providing a theoretical framework to secure classical infrastructure using quantum primitives.

Introduction

One-way functions (OWFs) serve as the bedrock of modern cryptography, enabling the construction of digital signatures, pseudorandom generators, and private-key encryption. Formally, an OWF $f$ is easy to compute but hard to invert. However, the rise of quantum computing threatens this foundation; algorithms such as Shor’s and Grover’s can efficiently invert many functions previously thought to be secure.

While researchers have proposed quantum-classical (Q-C) OWFs—functions that take a quantum state as input and produce a classical bit string—these primitives are not directly compatible with the current classical internet infrastructure. This research addresses a pivotal question: Can we leverage the security properties of quantum-input functions to construct the classical-input functions required for a quantum-secure future?

Bridging the Quantum-Classical Gap

The authors propose a methodology to transform a Q-C OWF into a C-C OWF through a process of composition and deterministic wrapping.

1. Composition and Reduction

The core construction follows the form $f(x) = f_2(f_1(x))$, where:

  • $f_1$ is a classical-to-quantum function.
  • $f_2$ is a quantum-to-classical function.

The paper proves that if $f_2$ is a one-way function, the resulting composite function $f$—which maps classical inputs to classical outputs—retains one-wayness against quantum adversaries. This reduction ensures that any adversary capable of breaking the classical function could, by extension, break the underlying quantum primitive.

2. Formalizing Quantum Equality

A significant challenge in quantum cryptography is that quantum states cannot be compared as easily as classical bit strings. To define Q-C OWFs rigorously, the authors utilize the Swap Test, a quantum procedure used to determine the similarity between two states. They introduce a "no cheating" property to ensure that an adversary cannot succeed by providing a quantum state outside the intended domain that happens to yield the correct classical output.

3. Algorithm 1: Deterministic Wrapping

To make these functions practical for classical systems, the authors developed Algorithm 1. This algorithm encodes quantum states and circuit configurations into binary strings. By utilizing a seeded pseudorandom number generator (PRNG), the authors ensure that the quantum circuit generation is deterministic for any given classical input, effectively "wrapping" a quantum process within a classical interface.

Key Theoretical Results

The paper establishes several landmark theorems that validate this approach:

  • Theorem 1: Formally proves that the existence of a Q-C OWF is a sufficient condition for the existence of a quantum-resistant C-C OWF.
  • Theorem 3: Applies this framework to a specific candidate Q-C OWF based on GCH states and CNOT circuits. The authors demonstrate that this candidate can be successfully transformed into a deterministic C-C OWF using their encoding method.

Implications and Limitations

The "Domain Shifting" technique suggests that we can hide classical information within quantum states to leverage the inherent hardness of quantum inversion. However, the research highlights several areas for future exploration:

  • Security Assumptions: The construction's security is tied to the underlying Q-C OWF. Currently, many Q-C candidates are only proven resistant to random guessing; a rigorous proof against all quantum polynomial-time (QPT) adversaries remains a high priority.
  • Primitive Scarcity: There are currently very few candidate Q-C OWFs available. The authors call for the development of more robust quantum primitives to populate this framework.
  • The C-Q to C-C Gap: While Q-C functions can be transformed into C-C functions, the authors note that the reverse—building C-C OWFs from classical-to-quantum (C-Q) functions—is significantly more complex and remains an open theoretical question.

Conclusion

By creating a formal bridge between quantum-input functions and classical outputs, this work provides a new pathway for developing quantum-resistant cryptography. It shifts the focus toward developing robust quantum primitives that can be "wrapped" for use in classical environments, ensuring that the security of the classical web can be maintained even in the post-quantum era.

Summary updated

BibTeX
@misc{teo2022creating,
  author = {Wei Zheng Teo and Marco Carmosino and Lior Horesh},
  title = {{Creating quantum-resistant classical-classical OWFs from quantum-classical OWFs}},
  year = {2022},
  eprint = {2209.10146},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.10146},
}
Figure