Grover's algorithm - DES circuit as oracle? The 2019 Stack Overflow Developer Survey Results...
Is this wall load bearing? Blueprints and photos attached
What do you call a plan that's an alternative plan in case your initial plan fails?
Match Roman Numerals
Can withdrawing asylum be illegal?
How to pronounce 1ターン?
How does this infinite series simplify to an integral?
Why can't wing-mounted spoilers be used to steepen approaches?
The variadic template constructor of my class cannot modify my class members, why is that so?
Who or what is the being for whom Being is a question for Heidegger?
What aspect of planet Earth must be changed to prevent the industrial revolution?
How do I add random spotting to the same face in cycles?
In horse breeding, what is the female equivalent of putting a horse out "to stud"?
Is there a writing software that you can sort scenes like slides in PowerPoint?
Sort list of array linked objects by keys and values
Does Parliament hold absolute power in the UK?
Why not take a picture of a closer black hole?
Python - Fishing Simulator
Why don't hard Brexiteers insist on a hard border to prevent illegal immigration after Brexit?
He got a vote 80% that of Emmanuel Macron’s
How many people can fit inside Mordenkainen's Magnificent Mansion?
How to delete random line from file using Unix command?
How did passengers keep warm on sail ships?
Still taught to reverse oxidation half cells in electrochemistry?
First use of “packing” as in carrying a gun
Grover's algorithm - DES circuit as oracle?
The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithmCompact encoding of Boolean formula as oracleQuantum attack on hash functionsPointer to related research (paper)Grover algorithm for more than one elementGrover's algorithm oracle matrixPossible results from Shor's algorithm in practiceN&C quantum circuit for Grover's algorithmGrover's algorithm: number of searches
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$begingroup$
In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|xranglerightarrow(-1)^{f(x)}|xrangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.
My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?
I would be very interested in what you think about it!
algorithm grovers-algorithm cryptography
$endgroup$
add a comment |
$begingroup$
In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|xranglerightarrow(-1)^{f(x)}|xrangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.
My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?
I would be very interested in what you think about it!
algorithm grovers-algorithm cryptography
$endgroup$
add a comment |
$begingroup$
In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|xranglerightarrow(-1)^{f(x)}|xrangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.
My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?
I would be very interested in what you think about it!
algorithm grovers-algorithm cryptography
$endgroup$
In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|xranglerightarrow(-1)^{f(x)}|xrangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.
My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?
I would be very interested in what you think about it!
algorithm grovers-algorithm cryptography
algorithm grovers-algorithm cryptography
edited 5 hours ago
Sanchayan Dutta♦
6,64141556
6,64141556
asked 5 hours ago
QuantaMagQuantaMag
1726
1726
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:
- AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965
- MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377
- SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383
A general programmatic framework to express general oracles, synthesize them into quantum circuits, and perform cost analyses does not exist to the best of my knowledge.
Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^{64}$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^{86}$ in the first paper above).
In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "694"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f5907%2fgrovers-algorithm-des-circuit-as-oracle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:
- AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965
- MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377
- SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383
A general programmatic framework to express general oracles, synthesize them into quantum circuits, and perform cost analyses does not exist to the best of my knowledge.
Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^{64}$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^{86}$ in the first paper above).
In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.
$endgroup$
add a comment |
$begingroup$
In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:
- AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965
- MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377
- SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383
A general programmatic framework to express general oracles, synthesize them into quantum circuits, and perform cost analyses does not exist to the best of my knowledge.
Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^{64}$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^{86}$ in the first paper above).
In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.
$endgroup$
add a comment |
$begingroup$
In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:
- AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965
- MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377
- SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383
A general programmatic framework to express general oracles, synthesize them into quantum circuits, and perform cost analyses does not exist to the best of my knowledge.
Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^{64}$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^{86}$ in the first paper above).
In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.
$endgroup$
In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:
- AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965
- MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377
- SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383
A general programmatic framework to express general oracles, synthesize them into quantum circuits, and perform cost analyses does not exist to the best of my knowledge.
Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^{64}$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^{86}$ in the first paper above).
In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.
answered 59 mins ago
MartinQuantumMartinQuantum
46029
46029
add a comment |
add a comment |
Thanks for contributing an answer to Quantum Computing Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f5907%2fgrovers-algorithm-des-circuit-as-oracle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown