International Association for Cryptologic Research

International Association
for Cryptologic Research


Da Lin


Optimizing Implementations of Linear Layers 📺
In this paper, we propose a new heuristic algorithm to search efficient implementations (in terms of Xor count) of linear layers used in symmetric-key cryptography. It is observed that the implementation cost of an invertible matrix is related to its matrix decomposition if sequential-Xor (s-Xor) metric is considered, thus reducing the implementation cost is equivalent to constructing an optimized matrix decomposition. The basic idea of this work is to find various matrix decompositions for a given matrix and optimize those decompositions to pick the best implementation. In order to optimize matrix decompositions, we present several matrix multiplication rules over F2, which are proved to be very powerful in reducing the implementation cost. We illustrate this heuristic by searching implementations of several matrices proposed recently and matrices already used in block ciphers and Hash functions, and the results show that our heuristic performs equally good or outperforms Paar’s and Boyar-Peralta’s heuristics in most cases.
The Design Principle of Hash Function with Merkle-Damg{\aa}rd Construction
The paper discusses the security of hash function with Merkle-Damg{\aa}rd construction and provides the complexity bound of finding a collision and primage of hash function based on the condition probability of compression function $y=F(x,k)$. we make a conclusion that in Merkle-Damma{\aa}rd construction, the requirement of free start collision resistant and free start collision resistant on compression function is not necessary and it is enough if the compression function with properties of fix start collision resistant and fix start preimage resistant. However, the condition probability $P_{Y|X=x}(y)$ and $P_{Y|K=k}(y)$ of compression function $y=F(x,k)$ have much influence on the security of the hash function. The best design of compression function should have properties of that $P_{Y|X=x}(y)$ and $P_{Y|K=k}(y)$ are both uniformly distributed for all $x$ and $k$. At the end of the paper, we discussed the block cipher based hash function, point out among the the 20 schemes, selected by PGV\cite{Re:Preneel} and BPS\cite{Re:JBlack}, the best scheme is block cipher itself, if the block cipher with perfect security and perfect key distribution.