"quantum algorithms" .
.
_:N9a64a9b237d6469ab1968c88ec712cd4 "Steven" .
"complexity" .
"Computation Theory and Mathematics" .
"Simon" .
"2022-12-01T06:48" .
"follow" .
"symmetric construction" .
"extremes" .
_:N25c51b3f0b134d5bb0ed9c95ccab258c .
"previous results" .
"theoretical analysis" .
.
.
"effect" .
_:Nc316f873e51f42de853330047be06e3e .
"At Eurocrypt\u00A02017 a tweak to counter Simon\u2019s quantum attack was proposed: replace the common bitwise addition with other operations, as a modular addition. The starting point of our paper is a follow up of these previous results:First, we have developed new algorithms that improves and generalizes Kuperberg\u2019s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE\u00A02005, widely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the hidden problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes.In order to verify our theoretical analysis, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak. We concluded that the tweak does not seem to be efficient." .
"TWEAK" .
"point" .
"true"^^ .
_:N6deb41950b0c452ba73647dec8dd0e96 "doi" .
"improved algorithm" .
"attacks" .
"Inria, Paris, France" .
.
.
"2018-10-27" .
_:Nd90311f057ef421f9b956dc86dea0e63 .
_:N31602018f9694b7e8b37a96c960f2e54 "Peyrin" .
"first time" .
"paper" .
"Inria, Paris, France" .
"Hidden Shift Quantum Cryptanalysis and Implications" .
_:Nc316f873e51f42de853330047be06e3e "Springer Nature - SN SciGraph project" .
_:N02f742276a1b49a4a4116567a4a1ed78 .
"560-592" .
.
"algorithm" .
_:N6deb41950b0c452ba73647dec8dd0e96 .
"estimates" .
"chapters" .
"thanks" .
"parameters" .
"operation" .
.
_:Ne6c4b0bd4be848c399d0137b3016dfa5 _:N61951ee122af40399105ab0da25c740b .
_:N358163eacdeb4eb8828289539048479e "978-3-030-03326-2" .
_:Nf38cc8197ef842428af7e29c24c8e63f .
_:N31602018f9694b7e8b37a96c960f2e54 .
"Xavier" .
_:N02f742276a1b49a4a4116567a4a1ed78 "pub.1107870546" .
.
.
"results" .
_:N31602018f9694b7e8b37a96c960f2e54 "Thomas" .
.
_:N358163eacdeb4eb8828289539048479e "Advances in Cryptology \u2013 ASIACRYPT 2018" .
"superposition model" .
_:Nd90311f057ef421f9b956dc86dea0e63 _:N9a64a9b237d6469ab1968c88ec712cd4 .
_:N358163eacdeb4eb8828289539048479e .
"implications" .
"time" .
"problem" .
_:N358163eacdeb4eb8828289539048479e "978-3-030-03325-5" .
"Eurocrypt" .
"cryptanalysis" .
_:N61951ee122af40399105ab0da25c740b .
"shift problem" .
_:N6deb41950b0c452ba73647dec8dd0e96 "10.1007/978-3-030-03326-2_19" .
.
_:Nf38cc8197ef842428af7e29c24c8e63f _:Nd90311f057ef421f9b956dc86dea0e63 .
.
"construction" .
"Poly1305" .
"https://scigraph.springernature.com/explorer/license/" .
"model" .
.
"quantum attacks" .
"impact" .
_:N25c51b3f0b134d5bb0ed9c95ccab258c .
"open problem" .
_:N9a64a9b237d6469ab1968c88ec712cd4 "Galbraith" .
"order" .
"Bonnetain" .
"modular addition" .
"security" .
"Sorbonne Universit\u00E9, Coll\u00E8ge Doctoral, F-75005, Paris, France" .
_:N9a64a9b237d6469ab1968c88ec712cd4 .
_:N61951ee122af40399105ab0da25c740b .
"analysis" .
.
_:Nf38cc8197ef842428af7e29c24c8e63f _:N31602018f9694b7e8b37a96c960f2e54 .
"concrete parameters" .
_:N358163eacdeb4eb8828289539048479e .
"addition" .
"Naya-Plasencia" .
"quantum cryptanalysis" .
"concrete estimates" .
.
"https://doi.org/10.1007/978-3-030-03326-2_19" .
_:Ne6c4b0bd4be848c399d0137b3016dfa5 .
"Mar\u00EDa" .
"FSE" .
_:Nc316f873e51f42de853330047be06e3e .
_:Ne6c4b0bd4be848c399d0137b3016dfa5 .
"Kuperberg" .
_:N02f742276a1b49a4a4116567a4a1ed78 "dimensions_id" .
"Information and Computing Sciences" .
"bitwise addition" .
"cost" .
"FX construction" .
.
"2018-10-27" .
_:N25c51b3f0b134d5bb0ed9c95ccab258c "Springer Nature" .
"chapter" .
.
"new algorithm" .
_:N6deb41950b0c452ba73647dec8dd0e96 .
"practicality" .
"starting point" .
_:N02f742276a1b49a4a4116567a4a1ed78 .