dorsal/arxiv
View SchemaBreaking Classical Public Key Cryptosystems by Using a Novel Ensemble Search Algorithm
| Authors | Chien-Yuan Chen |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0407126 |
| URL | https://arxiv.org/abs/quant-ph/0407126 |
Abstract
In this paper, we improve Bruschweiler's algorithm such that only one query is needed for searching the single object z from N=2^n unsorted elements. Our algorithm construct the new oracle query function g(.) satisfying g(x)=0 for all input x, except for one, say x=z, where g(z)=z. To store z, our algorithm extends from one ancillary qubit to n ancillary qubits. We then measure these ancillary qubits to discover z. We further use our ensemble search algorithm to attack classical public key cryptosystems. Given the ciphertext C=Ek(m, r) which is generated by the encryption function Ek(), a public key k, a message m, and a random number r, we can construct an oracle query function h(.) satisfying h(m', r')=0 if Ek(m', r')!=C and h(m', r')= (m', r') if Ek(m', r')=C. There is only one object, say (m, r), can be discovered in decryption of C. By preparing the input with all possible states of (m', r'), we can thus use our ensemble search algorithm to find the wanted object (m, r). Obviously, we break the classical public key cryptosystems under the ciphertext attack by performing the oracle query function only one time.
{
"annotation_id": "0bae76b5-5eaa-41cf-9348-e6fde3f936b2",
"date_created": "2026-03-02T18:02:10.191000Z",
"date_modified": "2026-03-02T18:02:10.191000Z",
"file_hash": "f30231bf8c26f5f01622c55af93babb9b7142c55c20c102fe9b7caf3f57033ee",
"private": false,
"record": {
"abstract": "In this paper, we improve Bruschweiler\u0027s algorithm such that only one query\nis needed for searching the single object z from N=2^n unsorted elements. Our\nalgorithm construct the new oracle query function g(.) satisfying g(x)=0 for\nall input x, except for one, say x=z, where g(z)=z. To store z, our algorithm\nextends from one ancillary qubit to n ancillary qubits. We then measure these\nancillary qubits to discover z. We further use our ensemble search algorithm to\nattack classical public key cryptosystems. Given the ciphertext C=Ek(m, r)\nwhich is generated by the encryption function Ek(), a public key k, a message\nm, and a random number r, we can construct an oracle query function h(.)\nsatisfying h(m\u0027, r\u0027)=0 if Ek(m\u0027, r\u0027)!=C and h(m\u0027, r\u0027)= (m\u0027, r\u0027) if Ek(m\u0027,\nr\u0027)=C. There is only one object, say (m, r), can be discovered in decryption of\nC. By preparing the input with all possible states of (m\u0027, r\u0027), we can thus use\nour ensemble search algorithm to find the wanted object (m, r). Obviously, we\nbreak the classical public key cryptosystems under the ciphertext attack by\nperforming the oracle query function only one time.",
"arxiv_id": "quant-ph/0407126",
"authors": [
"Chien-Yuan Chen"
],
"categories": [
"quant-ph"
],
"title": "Breaking Classical Public Key Cryptosystems by Using a Novel Ensemble Search Algorithm",
"url": "https://arxiv.org/abs/quant-ph/0407126"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e50ffde1-306b-447f-99b1-f3129f823f61",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}