Expansive permutation on $F_2^n$

Abstract

This thesis consists of three chapters. Chapter 1 is general introduction to information theory, cryptology, coding theory. Let $F_n^2$ be the n-dimensional vector space over $\text{GF}(2).$ Chapter 2 deals with expansive permutation on $F_2^n$ that is used to be the cryptographic function in S-box of DES. In Section 2 of the Chapter 2, we define a permutation P on $F_2^n$ to be the locally expanding permutation if P satisfies the following condition: For Hamming distance d and positive integers r,s, if the elements x,y in $F_2^n$ satisfies d(x,y)=r, then d(p(x),p(y))≥s.(See Definition 2.2.1.) And we show some simple properties of the locally expanding permutation. In Section 3 of the Chapter 2, we define a permutation P of $F_2^n$ to be maximally separating permutation if P satisfies the following condition: For Hamming distance d and non-negative integer k, we first define the metric $d_k^P$ on $F_2^n$ as $d_k^P(x,y)=max_{0≤i≤k}{d(P^i(x),P^i(y))}$ for x,y in $F_2^n$, where $P^i$ means i-times composition of P. If there exists integer $k≥0$ such that for all x,y in $F_2^n$ with x≠y, $d_k^P(x,y)=n$, we define P to be maximally separating permutation on $F_2^n.$(See Definition 2.3.1.) In Theorem 2.3.3, we show that the only two kinds of permutations can be maximally separating permutation. But, in view of Definition, a locally expanding permutation seems to be strong candidate for maximally separating permutation. However, in the last Remark of Section 3 of the Chapter 2, we show that there is no strong relationship between locally expanding permutation and maximally separating permutation. Chapter 3 deals with the decoding algorithm of a syndrome-distribution decoding of mols $L_p$ codes. Let P be an odd prime number. We introduce simple and useful decoding algorithm for orthogonal Latin square codes of order p. Let H be the parity check matrix of orthogonal Latin square code. For any x∈ GF$(p)^n,$ we call $xH^T$ the syndrome of x. This method is based on th...