{"entities":{"Q1045033":{"pageid":1046881,"ns":120,"title":"Item:Q1045033","lastrevid":79905857,"modified":"2026-05-06T14:58:58Z","type":"item","id":"Q1045033","labels":{"en":{"language":"en","value":"On complexity of round transformations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5648088"}},"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":"Q1045033$8BED6261-8572-4EDE-AF18-04B80A9CAF87","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4925773131d7c41add63b02774af1a321cd05e8d","datavalue":{"value":{"text":"On complexity of round transformations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1045033$4DBC271B-76AF-4BB3-8422-192748EFB58E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7b62929aa94272b6ef8bd5b3d3aa1c8336cc8150","datavalue":{"value":"1190.94025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045033$17826973-FF7B-4157-967F-50812B8F7915","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e72502166e8d9a0cc947c65da832bc54cb32a5e","datavalue":{"value":{"entity-type":"item","numeric-id":420636,"id":"Q420636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$1016FFBF-5CDF-4A81-9E99-4A7AC95D6C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e71d1531addd3e751a7c2f29dcec31264ed06413","datavalue":{"value":{"entity-type":"item","numeric-id":215558,"id":"Q215558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$5AFF0CB0-B7D8-4353-891E-8AA8F1A2E9FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a9bcb5564a7e76a6a62cffa78830d30fe4b603d","datavalue":{"value":{"entity-type":"item","numeric-id":510447,"id":"Q510447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$85920308-E085-4DFD-9CCE-819B31D88FFD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$644DE2D2-E3D0-4FE2-A8A7-73C8E6DFFB1D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9d265d400060d2e7fb9c5c45adc5a5c7f5f7bbd7","datavalue":{"value":{"time":"+2009-12-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1045033$6B49F7DC-A6CC-43F8-A0ED-BB4823780A78","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87dc1878756258020be641a16f977ff14b404323","datavalue":{"value":"A block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). With respect to the hardware implementation, a good block cipher has to have a reasonable complexity. This paper studies complexity of round transformations satisfying some basic security criteria. It turns out, that it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. Assuming that the Boolean function \\(F\\) possesses some fundamental properties imposed on each block cipher for security reasons; namely that the function is a strictly non-linear bijection and that it has a good diffusion, the total number of variables in the normal algebraic form of the component functions of \\(F\\) is taken as its complexity. The minimum complexity of such functions is found, and this way a lower bound on complexity of all round transformations is established. To show that the lower bound is the best possible, a round transformation \\(F'\\) attaining the bound is constructed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045033$903FB3CF-339E-4336-B20E-EC5097778A31","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"278cb718fa512f840b9c5522dfe38ff5e946abf8","datavalue":{"value":{"entity-type":"item","numeric-id":589393,"id":"Q589393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$04CF38BE-03D7-4E6F-B181-C13B723720B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045033$68331808-9DB2-43C0-B1A4-EC4BA7D3B2C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045033$60EB1330-A5B0-4257-B171-A7646CD4CBB8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3a546a5856154a454dbbc35013eca2c9261bc954","datavalue":{"value":"5648088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045033$02377D0B-5F38-4FC6-8426-D27337466131","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"532eb17396fbdf767a0807d74978f220282a65f2","datavalue":{"value":"block ciphers design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045033$B700DE07-8E32-4D43-992B-033923280710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87da3b6dac32f1cff3310af6a8482a8aa787d012","datavalue":{"value":"round function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045033$D1C1977C-69BB-4EEF-AE1F-2BDE11B79278","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":"Q1045033$6EF198D4-1074-4E66-919A-B85D4D559F7A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8dbc8b26a9ee0efe1caeae83311baa7b88d01dab","datavalue":{"value":"https://doi.org/10.1016/j.disc.2008.03.020","type":"string"},"datatype":"url"},"type":"statement","id":"Q1045033$5309FCD5-D288-4B7F-B88B-38F2BA040054","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"94da6e1ad30534cda4d53974f01edd8b5707e517","datavalue":{"value":"W2089161071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045033$5F548D02-DB69-4ADA-BF0E-88A208D6B496","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8030ec86fdcd930f6cfcdb2c0bd519348141be19","datavalue":{"value":{"entity-type":"item","numeric-id":923056,"id":"Q923056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$3365EDF8-564E-4AF7-A391-ED60419F8BC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c2b177271dc2f55dd75a823aa964ec861952e0d","datavalue":{"value":{"entity-type":"item","numeric-id":4934726,"id":"Q4934726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$E56C0EFE-8C30-48E6-9714-7767316A9024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b073b70429536ef3ba0b0852f8badb2c326703a","datavalue":{"value":{"entity-type":"item","numeric-id":3998725,"id":"Q3998725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$B50F6E6F-FF21-449F-9026-42569A328F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e01ba75f44d99ac03fed4a3a414e3d7034ad0ff9","datavalue":{"value":{"entity-type":"item","numeric-id":2760977,"id":"Q2760977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$4D4D185F-5230-4D96-A663-8672002B3B6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b96c37287a25d3260f5ac19097db4dcc1994205e","datavalue":{"value":{"entity-type":"item","numeric-id":1272532,"id":"Q1272532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$1B5A80E6-0F7D-4C9F-A9ED-C9E9B559DB67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"815e32e79f46da70b103b197bf24a16265667a30","datavalue":{"value":{"entity-type":"item","numeric-id":3421463,"id":"Q3421463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$2FC48C4A-4F28-4331-A5B4-6826EDD505EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd2414bd2fc3236263cf5651dd5bc482b19621b3","datavalue":{"value":{"entity-type":"item","numeric-id":2784264,"id":"Q2784264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$1455DE5B-81D7-4125-BBF8-7C66BC986098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c540363d0796c9bf81f7e5b8b3135a1ad841043","datavalue":{"value":{"entity-type":"item","numeric-id":5202623,"id":"Q5202623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$C85CCD1C-E5B2-4F2C-87F1-E88A49C8BE4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8219b8caf64f58381971bc73c47456fa8a33f55a","datavalue":{"value":{"entity-type":"item","numeric-id":3645296,"id":"Q3645296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$C3CD617D-9418-45B1-B376-951E08B7DF09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be0af0ff634d24203092ee8f325c2327ac8b6ca5","datavalue":{"value":{"entity-type":"item","numeric-id":5318253,"id":"Q5318253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045033$D74094DB-4169-473C-846D-BFF7F2A6ED82","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"25d2aa98d07768b897d9c21e393bc32df56db8f0","datavalue":{"value":"10.1016/J.DISC.2008.03.020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045033$D1E4E000-A785-432D-A62D-335211CA0D54","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcdf1983a59519d7a62f8f9ae1423d765e47ebca","datavalue":{"value":{"entity-type":"item","numeric-id":775997,"id":"Q775997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44842aed2ee8ba171751b34ef59a26bbb6f2b334","datavalue":{"value":{"amount":"+0.87783766","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$37D0A5C8-C4AC-4BA7-8389-FFC5B021A23C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfb6776500fa18030bf2566eb31cbfffeb744591","datavalue":{"value":{"entity-type":"item","numeric-id":2352607,"id":"Q2352607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32b8fdbda249830519dcd6f1a483f12d8dcc8d7c","datavalue":{"value":{"amount":"+0.8648504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$E511952F-7223-4A3D-BA54-625A5FF86EF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73087ebc6b29fd7f7937ab30c1b6f186cbacb034","datavalue":{"value":{"entity-type":"item","numeric-id":2356497,"id":"Q2356497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1430ba54109c0e02532b5d5bc9dcdd1b346597f","datavalue":{"value":{"amount":"+0.85068697","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$30E4E000-5B43-41FE-91A7-E6951DFEEC91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bc9bcde0d2c249ad254464511d22797a0258824","datavalue":{"value":{"entity-type":"item","numeric-id":4809642,"id":"Q4809642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f1ff5bd9347cdac3ee2550f3bb091110c4fb45e","datavalue":{"value":{"amount":"+0.8452066","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$C3B445FF-922E-471D-AA1C-EFD466C2027F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9526070f4cd450ff2a0c11dadbd99a530a3a8d20","datavalue":{"value":{"entity-type":"item","numeric-id":4037694,"id":"Q4037694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a07a53fafb5ec6bb971bee633ef547c0167fdfe","datavalue":{"value":{"amount":"+0.84519625","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$8BFA3E1D-4C09-4B72-A87C-D8B6D2E4D7CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67ac63612927540e6d6c1c9534ac5302f5b2a188","datavalue":{"value":{"entity-type":"item","numeric-id":2722004,"id":"Q2722004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9098db3526a758574d09b72b81104fdcec4e9a6f","datavalue":{"value":{"amount":"+0.84062093","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$F1D852E5-1D80-45F1-8016-AE851DB7F23E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e354cf3d0b3f4ca8e25845258ac5d68753193394","datavalue":{"value":{"entity-type":"item","numeric-id":4950448,"id":"Q4950448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9582be29c84e3f47ccb064dcd5eb14bbcd8ce797","datavalue":{"value":{"amount":"+0.8400252","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$E48FBD51-4BE0-4FE7-B188-61AEF9C90304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f315ccdff3ded8ebd17f1f27d36b754be9bbbccd","datavalue":{"value":{"entity-type":"item","numeric-id":4252028,"id":"Q4252028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a517c2004aedb98751228a5ce0876f5a963ed90d","datavalue":{"value":{"amount":"+0.83511674","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$719586E9-AE6E-4871-8FC7-EDF1F832DC06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d33b5c0f07023955caa0797a79e4a60a9a3055e","datavalue":{"value":{"entity-type":"item","numeric-id":4212463,"id":"Q4212463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46904ae3fd44d9ced4f4b242eaf0b96d19148d75","datavalue":{"value":{"amount":"+0.834493","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1045033$AB1AABC2-F0AC-40E4-B7A7-19CE9321D0C0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On complexity of round transformations","badges":[]}}}}}