On the weight and nonlinearity of rotation symmetric boolean functions = 회전대칭 불함수의 해밍무게 및 비선형성 연구

Recently, rotation symmetric Boolean functions have taken strong attention and exhibited their usefulness. For example, important questions in coding theory were given answers by heuristic or theoretical searches in the function class. The functions are also applied to design an efficient hash algorithm. On the other hand, for quadratic rotation symmetric functions with single orbit, their exact weight and nonlinearity were formulated in [4, 21]. We improve parts of their results. It is observed that the n-variable quadratic boolean functions $f_{n,s} (x) := \sum^n_{i=1} x_i x_{i+s-1}$ for $2 \leq s \leq \lceil \frac{n}{2}\rceil$ , which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weight and nonlinearity are exactly characterized by the cyclic subgroup \langle{s-1} \rangle$ of $\Bbb{Z}_n$. If $\frac{n}{gcd(n,s-1)}$ , the order of $s-1$ , is even then the weight and nonlinearity of $f_{n,s}$ are the same and given by $2^{n-1} - 2^{\frac{n}{2}+gcd(n,s-1)-1}$. If the order is odd then $f_{n,s}$ is balanced and its nonlinearity is given by $2^{n-1} - 2^{\frac{n+gcd(n,s-1)}{2}-1}$. Enlarging it slightly, we also characterize the exact weight of $g_{n,s} (x) := f_{n,s} (x) + \sum_{i=1}^n x_i$ . Finally, we touch a conjecture, given in [24], of the nonexistence of bent functions which are homogeneous rotation symmetric of degree $\geq3$, and give a positive answer to it for a very limited case.
Advisors
Hahn, Sang-Geunresearcher한상근researcher
Publisher
한국과학기술원
Issue Date
2008
Identifier
303596/325007  / 020035822
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 수리과학과, 2008. 8., [ v, 38 p. ]

Keywords

Boolean function; rotation symmetric; Hamming weight; nonlinearity; 불함수; 회전대칭; 해밍무게; 비선형석; Boolean function; rotation symmetric; Hamming weight; nonlinearity; 불함수; 회전대칭; 해밍무게; 비선형석

URI
http://hdl.handle.net/10203/41905
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=303596&flag=t
Appears in Collection
MA-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 102
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0