{"entities":{"Q2414939":{"pageid":2425682,"ns":120,"title":"Item:Q2414939","lastrevid":74217828,"modified":"2026-04-14T19:01:25Z","type":"item","id":"Q2414939","labels":{"en":{"language":"en","value":"Using Bernstein-Vazirani algorithm to attack block ciphers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7056604"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$97235816-DA27-4B5D-898C-31BA585BD92B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4bdc2a16d84680836a2e96fe23c0a24721474350","datavalue":{"value":{"text":"Using Bernstein-Vazirani algorithm to attack block ciphers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2414939$8C835FEC-3101-4435-B4A1-20584C8E86BE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7cef05400af64afd9f61e2976d16374c90637951","datavalue":{"value":"1445.94029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2414939$62C0F25C-A3BF-4997-834A-5371B32E15AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"48389a07d30cce8312c33bbec2fe606bccaacd04","datavalue":{"value":{"entity-type":"item","numeric-id":2414938,"id":"Q2414938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$379FCF65-C8BF-4DBF-89D4-278A1E64621D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6a5e67eea63385624dda9dfa1e8873ea073c218","datavalue":{"value":{"entity-type":"item","numeric-id":331900,"id":"Q331900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$DAA75058-E110-4EDF-8764-CD5B5296938C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fb34abbf39f11094509111953e4c62a22b1e3897","datavalue":{"value":{"entity-type":"item","numeric-id":115940,"id":"Q115940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$0F0D59BF-EFBA-4E7E-9AB8-574DB55AF2DA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ff447296bef390af9bbc2815788c2e74961068e5","datavalue":{"value":{"time":"+2019-05-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2414939$A2077EC9-5A1E-4A5B-BF8C-65CEB418ABEF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"49e14d7feba70087eed9cc8a6d34bafd2ec1478b","datavalue":{"value":"https://arxiv.org/abs/1711.00853","type":"string"},"datatype":"url"},"type":"statement","id":"Q2414939$034E3345-B793-4E08-BE16-818211F48EBD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"93fbb7f624f943e020f52d6344369f1b08828c78","datavalue":{"value":"A series of block cipher attacks is introduced based on the quantum algorithm of Bernstein and Vazirani. In the style of Deutsch algorithm, given a linear map \\(\\phi: \\mathrm{GF}_2^n\\to\\mathrm{GF}_2^n\\), where \\(\\mbox{GF}_2\\) is the primitive field of characteristic 2, Bernstein-Vazirani algorithm finds in an efficient way a vector \\(\\mathbf{x}\\in\\mathrm x{GF}_2^n\\) such that \\(\\phi(\\mathbf{y}) = \\langle\\mathbf{y}|\\mathbf{x}\\rangle\\). As usual, \\(\\mathrm{GF}_2\\) can be represented by the set of bits \\(Q=\\{0,1\\}\\). For a Boolean map \\(f: Q^n\\to Q\\), a ``linear structure'' is a point \\(\\mathbf{x}\\in Q^n\\) such that \\(\\forall\\mathbf{y}\\in Q^n\\), \\(f(\\mathbf{y}+\\mathbf{x}) + f(\\mathbf{y}) = f(\\mathbf{x}) + f(\\mathbf{0})\\). The authors show that, by sampling a Boolean map a number of times polynomial with respect to \\(n\\), a linear structure is obtained using Bernstein-Vazirani algorithm. Besides, through a rather direct iteration, linear structures may be obtained for vector Boolean maps. With respect to block ciphers, given a one-to-one map \\(P:Q^n\\to Q^n\\), the corresponding \\textit{Feistel round} is the map \\(Q^{2n}\\to Q^{2n}\\), \\(\\mathbf{z}_L\\mathbf{z}_R\\mapsto (P(\\mathbf{z}_L)+\\mathbf{z}_R)\\mathbf{z}_L\\). Given three permutations, provided by a cryptographically secure pseudorandom function, the corresponding 3-round Feistel is a secure pseudorandom permutation \\(Q^{2n}\\to Q^{2n}\\). The authors introduce a polynomial time quantum distinguisher for 3-round Feistel maps using Bernstein-Vazirani algorithm. Indeed, given two permutations \\(P_1,P_1\\) a linear structure of the map \\(\\varepsilon\\mathbf{x}\\mapsto P_2(P_1(\\mathbf{w}_{\\varepsilon} + \\mathbf{x})+\\mathbf{w}_{\\varepsilon})\\), with \\(\\mathbf{w}_0\\not=\\mathbf{w}_1\\), may allow to distinguish a 3-round Feistel involving \\(P_1,P_2\\). This is a different approach to a former quantum attack given by \\textit{H. Kuwakado} and \\textit{M. Morii} [Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), 2682--2685 (2010; doi:10.1109/ ISIT.2010.5513654]. Also, by recognition of linear structures, the introduced method may recover partial keys in the Even-Mansour construction of block-ciphers. Finally, the authors use thier method to render efficient differential cryptanalysis attacks, illustrating indeed the strength of quantum computing attacks.   The paper is very well structured but the chosen pseudocode style used by the authors is hard to read.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2414939$F8838F8F-43AB-4BB9-AD53-C04D40862C23","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2c051c55f89b8148a4dc64dba4569555d5561281","datavalue":{"value":{"entity-type":"item","numeric-id":590981,"id":"Q590981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$3136C65D-2C19-46D1-AAAA-037836B2C732","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2414939$6C75A0A5-2F7C-41E5-9836-BA608326EBF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7b959e36e52c7b395683dbe2d4c658b32b677b86","datavalue":{"value":"81P94","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2414939$ECC3A03F-2663-4761-83E1-3DB1A76F7CCB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2a10e53f0ed4a9ee339355cabe4b28eb4017c062","datavalue":{"value":"7056604","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2414939$696AE340-CE9F-43C9-9A99-5254A7F44AC9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"481277e4c76970eb4da1327a9bc96f387bc77c10","datavalue":{"value":"quantum cryptanalysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2414939$6DB6AB3F-5F2C-4E59-B589-22B9D1831D8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"408a6554e3e74524bca3562397a68fdf5580ebe5","datavalue":{"value":"differential cryptanalysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2414939$40A8A47E-9C29-4AFC-8F5B-4329363736FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97bcf90e5191a24f32d0c3ea19dcae9229d105f0","datavalue":{"value":"breaking block ciphers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2414939$94E9B511-3AD6-494F-8E47-CDC411839054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8858b8cb63065bc66c53dc02bc7cd9b9ec114fd8","datavalue":{"value":"post-quantum cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q2414939$0B586C48-7938-476E-8A2B-BD344B2C88E0","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"241e21b1625b5e055e4b0d10d5cac313a7c08063","datavalue":{"value":"Q123361145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2414939$5EE0C908-F31C-4321-81F6-81107F43441D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$D20388A9-0459-4B78-A955-93236615057A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1cd03976b813463139e961fb305e1ea442d6909b","datavalue":{"value":"W2963351393","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2414939$5839E263-BD7C-435D-9725-E7BF9460145D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9132eb582bb0cb94a8e9effdadcd521c87a3a155","datavalue":{"value":{"entity-type":"item","numeric-id":477162,"id":"Q477162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$A5EA736C-5F69-4441-841D-A33943C8A9D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b157b02484e4595fbaef25c02de6a19894a7dd7","datavalue":{"value":{"entity-type":"item","numeric-id":4376183,"id":"Q4376183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$1FC766DB-90CE-4831-AB77-201EFD79D02C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62ee767364b761528016c1f88346b42ee17afe3d","datavalue":{"value":{"entity-type":"item","numeric-id":2849406,"id":"Q2849406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$BB7E4E9E-A028-49AA-B4B5-92970E2AB742","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d07e6e240c94f7de982812abcf3d8de68cb6fde4","datavalue":{"value":{"entity-type":"item","numeric-id":2948260,"id":"Q2948260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$955C7084-13D0-443C-988C-9F1A13F88BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26800d6afecd349b1db599be13490dc7f3093fca","datavalue":{"value":{"entity-type":"item","numeric-id":1841525,"id":"Q1841525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$9ECF0B33-9A14-4B57-8CB2-A76B3CDC4A08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0238a6c1c77ed3605cc2bcf15fbfeb45f4a17b5","datavalue":{"value":{"entity-type":"item","numeric-id":1364898,"id":"Q1364898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$262EE441-F3CB-4CE8-B844-FAE16158B20B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b026c1e649ef1a4b49f6ce8a5f26bcb05279b9f","datavalue":{"value":{"entity-type":"item","numeric-id":4917194,"id":"Q4917194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$B6BFCCF7-958F-4956-862A-AAE8182A45A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b467eb2c74c68ea0eec4b3ddfa49552a12a509c","datavalue":{"value":{"entity-type":"item","numeric-id":2829943,"id":"Q2829943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$ECD48538-970B-499F-84C7-E670AF062F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e84f9dacdd0cb94a1a2cfe25af60e77d55bdf19","datavalue":{"value":{"entity-type":"item","numeric-id":2829216,"id":"Q2829216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$939EAA91-3A3A-4FFC-B7D6-20ABDF2B9AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c342c6f1e36ef1ac289a32bf1cf1a89bf8cbf00","datavalue":{"value":{"entity-type":"item","numeric-id":4941805,"id":"Q4941805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$56F0B122-E46A-46A2-B985-8018D1BD5A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c41a8abdfae52898c226a67049b7d90233853bec","datavalue":{"value":{"entity-type":"item","numeric-id":4599610,"id":"Q4599610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$91F353B7-5E79-4491-9155-EB61EAF47F66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d893bf6936768bc689fcbb0ae75e34fb68c6b758","datavalue":{"value":{"entity-type":"item","numeric-id":3787920,"id":"Q3787920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$2427BAF5-942A-4F09-B23D-FA1207AD39E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7eb94579414a875ab836b7feb8c110d6d7c380c","datavalue":{"value":{"entity-type":"item","numeric-id":4036866,"id":"Q4036866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$FEA4E950-86A9-44CF-8F7F-B5018CBF96C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6922e04481def5430210636d02e583e8dff1f2bf","datavalue":{"value":{"entity-type":"item","numeric-id":4934708,"id":"Q4934708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$F4F2D8FF-CB4F-4790-9792-FB1DB6A61EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf854375ef6a956c526c0de5e533214f6344181a","datavalue":{"value":{"entity-type":"item","numeric-id":4376181,"id":"Q4376181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$3467F3EC-8CC3-4786-A265-DA0B87CC3B9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97bf2c438c5820aa6b6fab5901d75408f9fd24e2","datavalue":{"value":{"entity-type":"item","numeric-id":2355614,"id":"Q2355614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$56F67FBE-AF7F-41C1-8245-9FA0FEB25A2D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec81238e23c35c5be6b38e1b4f6f0068449ad270","datavalue":{"value":"10.1007/S10623-018-0510-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2414939$B914370F-89D0-498E-BC73-C5E8E3033075","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e73a493789a10f8284f19294a788b643117de13","datavalue":{"value":{"entity-type":"item","numeric-id":2110996,"id":"Q2110996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0869d6580ea2f2aa259f4e0e20b4a5c218ff0fde","datavalue":{"value":{"amount":"+0.8872557282447815","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2414939$B5771B4B-56FF-47F7-B702-BC22FFCC3DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48140e779c41b5ac350f94945e66acf85d21631d","datavalue":{"value":{"entity-type":"item","numeric-id":2681588,"id":"Q2681588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eddce9b487e6b1d5f610a8c6db87fdb7eb84d193","datavalue":{"value":{"amount":"+0.8300127983093262","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2414939$61B901C8-1E3E-4BE9-AB5B-BCE5E8D36492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ed5db6cb093992c8fa2ef4164b9ff87f0a99034","datavalue":{"value":{"entity-type":"item","numeric-id":2685637,"id":"Q2685637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"353dd629f175181a64785c4bc7a350001d79a05b","datavalue":{"value":{"amount":"+0.8178072571754456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2414939$F6BBEF17-A0E0-46FA-A25E-BC9FBA52259F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c799986ed5bf9ad950719d35638b3028e2137ec8","datavalue":{"value":{"entity-type":"item","numeric-id":5071474,"id":"Q5071474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a019779c4b792064c7527eaccc73b5756191716","datavalue":{"value":{"amount":"+0.8013018369674683","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2414939$59047CA3-AACF-4EAA-89C2-09508ED3A9BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdfc7b2e7a9c823baba6c720013fef58dcfe7138","datavalue":{"value":{"entity-type":"item","numeric-id":2355614,"id":"Q2355614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35d29eca15a3729f3daf68a2362636b2bf8a9b52","datavalue":{"value":{"amount":"+0.7836088538169861","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2414939$3B641C0C-C8C4-4D6D-A865-C2D7E5B868F2","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2414939$FD685B83-1656-436C-B93D-50FF2983EE63","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Using Bernstein-Vazirani algorithm to attack block ciphers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Using_Bernstein-Vazirani_algorithm_to_attack_block_ciphers"}}}}}