Boolean functions are accepted to be cryptographically strong if they satisfy some
common pre-determined criteria. It is expected that any design criteria should remain invariant under
a large group of transformations due to the theory of similarity of secrecy
systems proposed by Shannon. One of the most important design criteria for
cryptographically strong Boolean functions is the nonlinearity criterion. Meier and
Staffelbach studied nonlinearity preserving transformations,
by considering the invertible transformations acting on the arguments of
Boolean functions, namely the pre-transformations. In this thesis, first, the
results obtained by Meier and Staffelbach are presented. Then, the invertible
transformations acting on the truth tables of Boolean functions, namely the post-transformations,
are studied in order to determine whether they keep the nonlinearity
criterion invariant. The equivalent counterparts of Meier and Staffelbach&rsquo / s
results are obtained in terms of the post-transformations. In addition, the existence
of nonlinearity preserving post-transformations, which are not equivalent
to pre-transformations, is proved. The necessary and sufficient conditions for an
affine post-transformation to preserve nonlinearity are proposed and proved. Moreover, the sufficient conditions
for an non-affine post-transformation to keep nonlinearity invariant are proposed. Furthermore,
it is proved that the smart hill climbing method, which is introduced to
improve nonlinearity of Boolean functions by Millan et. al., is equivalent to applying
a post-transformation to a single Boolean function. Finally, the necessary and
sufficient condition for an affine pre-transformation to preserve the strict avalanche
criterion is proposed and proved.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12605183/index.pdf |
| Date | 01 June 2004 |
| Creators | Sertkaya, Isa |
| Contributors | Doganaksoy, Ali |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.002 seconds