dorsal/arxiv
View SchemaA classical one-way function to confound quantum adversaries
| Authors | Cristopher Moore, Alexander Russell, Umesh Vazirani |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0701115 |
| URL | https://arxiv.org/abs/quant-ph/0701115 |
Abstract
The promise of quantum computation and its consequences for complexity-theoretic cryptography motivates an immediate search for cryptosystems which can be implemented with current technology, but which remain secure even in the presence of quantum computers. Inspired by recent negative results pertaining to the nonabelian hidden subgroup problem, we present here a classical algebraic function $f_V(M)$ of a matrix $M$ which we believe is a one-way function secure against quantum attacks. Specifically, inverting $f_V$ reduces naturally to solving a hidden subgroup problem over the general linear group (which is at least as hard as the hidden subgroup problem over the symmetric group). We also demonstrate a reduction from Graph Isomorphism to the problem of inverting $f_V$; unlike Graph Isomorphism, however, the function $f_V$ is random self-reducible and therefore uniformly hard. These results suggest that, unlike Shor's algorithm for the discrete logarithm--which is, so far, the only successful quantum attack on a classical one-way function--quantum attacks based on the hidden subgroup problem are unlikely to work. We also show that reconstructing any entry of $M$, or the trace of $M$, with nonnegligible advantage is essentially as hard as inverting $f_V$. Finally, $f_V$ can be efficiently computed and the number of output bits is less than $1+\epsilon$ times the number of input bits for any $\epsilon > 0$.
{
"annotation_id": "0689b16d-e8f5-45cf-86c7-8a1fafb3f75e",
"date_created": "2026-03-02T18:02:34.236000Z",
"date_modified": "2026-03-02T18:02:34.236000Z",
"file_hash": "e811502b4d9ec90f860bfd20d971e04455a15c9b2b5c65775cc7551f58efe430",
"private": false,
"record": {
"abstract": "The promise of quantum computation and its consequences for\ncomplexity-theoretic cryptography motivates an immediate search for\ncryptosystems which can be implemented with current technology, but which\nremain secure even in the presence of quantum computers. Inspired by recent\nnegative results pertaining to the nonabelian hidden subgroup problem, we\npresent here a classical algebraic function $f_V(M)$ of a matrix $M$ which we\nbelieve is a one-way function secure against quantum attacks. Specifically,\ninverting $f_V$ reduces naturally to solving a hidden subgroup problem over the\ngeneral linear group (which is at least as hard as the hidden subgroup problem\nover the symmetric group). We also demonstrate a reduction from Graph\nIsomorphism to the problem of inverting $f_V$; unlike Graph Isomorphism,\nhowever, the function $f_V$ is random self-reducible and therefore uniformly\nhard.\n These results suggest that, unlike Shor\u0027s algorithm for the discrete\nlogarithm--which is, so far, the only successful quantum attack on a classical\none-way function--quantum attacks based on the hidden subgroup problem are\nunlikely to work. We also show that reconstructing any entry of $M$, or the\ntrace of $M$, with nonnegligible advantage is essentially as hard as inverting\n$f_V$. Finally, $f_V$ can be efficiently computed and the number of output bits\nis less than $1+\\epsilon$ times the number of input bits for any $\\epsilon \u003e\n0$.",
"arxiv_id": "quant-ph/0701115",
"authors": [
"Cristopher Moore",
"Alexander Russell",
"Umesh Vazirani"
],
"categories": [
"quant-ph"
],
"title": "A classical one-way function to confound quantum adversaries",
"url": "https://arxiv.org/abs/quant-ph/0701115"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "3a00d674-2509-4fc5-9164-eff6839cf948",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}