이 부울 함수의 비선형 성이 다음과 같이 평가되는 이유는 무엇입니까? $\frac12$?
이 문서 에 제시된 방법을 사용 하여 함수의 비선형 성을 찾습니다.
$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$
진리표는 $f = [0 \space \space 1]$. 이제, 내가 읽어 테리 리터로 종이 그
비선형 성은 가장 가까운 아핀 함수에 도달하기 위해 부울 함수의 진리표에서 변경해야하는 비트 수입니다.
이는 비선형 성 값이 정수 여야 함을 의미합니다.
비선형 성을 계산하는 알고리즘은 먼저 Fast Walsh Transform을 사용하여 Walsh 스펙트럼을 찾은 다음 공식을 사용하는 것입니다.
$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$
여기서 Walsh 스펙트럼은 함수의 진리표에 해당 Hadamard 행렬을 곱하여 계산됩니다.
그래서 $k = 1$, 우리는 크기의 Hadamard 행렬을 사용합니다. $2^1$ 다음 Walsh 스펙트럼을 제공합니다.
$$ \begin{bmatrix}0 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} = \begin{bmatrix}1 & -1\end{bmatrix} \implies \max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| = |-1| = 1 $$
따라서
$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$
내가 무엇을 놓치고 있습니까?
링크가 끊어진 경우 링크 된 문서는 다음과 같습니다.
- Pedro Miguel Sosa의 Walsh-Hadamard 변환을 사용 하여 부울 함수의 비선형 성 계산
- Terry Ritter의 Walsh 변환 에 의한 부울 함수 비선형 성 측정
답변
이 공식에서 함수의 출력 범위를 다음으로 변환해야합니다. $\{-1,+1\}$ 통하다 $$f`(x)=(-1)^{f(x)}$$ Walsh Hadamard를 새 기능에 적용합니다. $f`(x)$. 제로원 공식을 사용하면 변수의 수에 따라 상수를 벗어난 것을 의미합니다.
$$ (-1)^u=1-2u $$ ...에 대한 $u\in \{0,1\}.$
부울 함수 및 암호화에 대한 아래의 답변을 참조하십시오. 최근 질문을 고려할 때 유용 할 수 있습니다.
부울 함수는 암호화에서 어떻게 사용됩니까?
kodlu의 답변에 더해 논문을주의 깊게 다시 읽어 본 결과 알아낼 수있었습니다. 주목해야 할 주요 사항 :
1. 부울 함수에 Fast Walsh Transform을 사용하는 경우 $\{0,1\}$ 비선형성에 대한 공식은 다음과 같습니다.
... 함수 비트 수의 절반, 예상치 못한 거리의 절대 값을 뺀 값입니다.
그건 $$ Nl(f) = \dfrac12 \cdot 2^k - \max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)|\\ = 2^{k-1} - \max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$
따라서 원래 게시물의 질문에 대해
$$Nl(f) = 2^{0} - |1| = 0$$
또는 여기 20 페이지 ( alt 링크 )에서 다음과 같이 진행할 것을 제안합니다. Fast Walsh 변환을 찾은 후
더하다 $2^{k-1}$첫 번째 항목을 제외하고 행의 각 항목에. 이것은 우리에게 새로운 행을 제공합니다.$FHT'$
항목이 미만인 경우 $2^{k-1}$변경되지 않습니다. 그렇지 않으면 항목이$FHT'$ 보다 큼 $2^{k-1}$ 그런 다음 그것을 빼십시오 $2^k$.
마지막으로, 비선형 성은 이러한 조정 된 요소 중 가장 작은 것입니다.
2. 다음으로 구성된 부울 함수에 Fast Walsh Transform을 사용하는 경우 $\{1,-1\}$ 비선형성에 대한 공식은 다음과 같습니다.
$$ Nl(f) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$
때문에
실제 값 사용 $\{1,-1\}$ 크기를 두 배로 늘리고 FWT 결과의 부호를 변경합니다.
출처