On complexity of round transformations

DOI10.1016/J.DISC.2008.03.020MaRDI QIDQ1045033zbMATH OpenOpenAlexFDO

Authors Otokar Grošek, Peter Horák, Pavol Zajac

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2008.03.020

zbMATH Keywords

block ciphers designround function

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Review text

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.

Recommendations

• On the round complexity of OT extension
• Arithmetic complexity of certain linear transformations
• The arithmetic computational complexity of linear transforms
• On the complexity of unitary transformations
• Rounds in Communication Complexity Revisited
• scientific article; zbMATH DE number 1617281
• scientific article; zbMATH DE number 1426192
• scientific article; zbMATH DE number 1305086
• scientific article; zbMATH DE number 1206797

Cites work

• Combinatorial matrix theory
• Communication Theory of Secrecy Systems*
• scientific article; zbMATH DE number 1682693 (Why is no real title available?)
• scientific article; zbMATH DE number 1731748 (Why is no real title available?)
• scientific article; zbMATH DE number 4195885 (Why is no real title available?)
• Is Rijndael really independent of the field polynomial?
• Minimal oriented graphs of diameter 2
• On Almost Perfect Nonlinear Permutations
• On perfect nonlinear functions
• The structured design of cryptographically good s-boxes

Cited in

(1)

• scientific article; zbMATH DE number 1962150 (Why is no real title available?)

This page was built for publication: On complexity of round transformations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045033)