🔢 mathematics

Bent Functions and the Completed Maiorana-McFarland Class

이 논문은 불리언 벤트 함수(Boolean bent functions)의 설계 및 분석에 관한 근본적인 결과와 최근의 진보를 조사하며, 특히 완성된 마이오라나-맥팔랜드(completed Maiorana-McFarland) 클래스와의 관계에 초점을 맞춘다.

원저자: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

게시일 2026-08-25

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

현대 디지털 보안의 숨겨진 구조 속에는 벤트 함수(bent function)라고 알려진 특별한 종류의 수학적 객체가 존재한다. 이것들은 물리적인 장치나 생물학적 실체가 아니라, 모든 컴퓨터 통신의 기초가 되는 1과 0의 이진 데이터 문자열을 처리하기 위한 복잡한 규칙들이다. 가능한 규칙들의 광활한 풍경을 상상해 보라. 대부분의 규칙은 예측 가능하고 분석하기 쉽다. 벤트 함수는 이러한 단순하고 직선적인 패턴으로부터 최대한 멀리 떨어져 있는, 극도의 예측 불가능성의 정점에 자리 잡고 있다. 이러한 극단적인 불규칙성 때문에, 이들은 암호학 및 오류 정정 코드에서 데이터를 보호하는 데 매우 귀중한 도구로 사용되며, 도청자가 신호를 찾아내지 못하도록 막는 혼돈스러운 노이즈 역할을 한다. 수십 년 동안 수학자들은 이 함수들을 만드는 구체적이고 잘 이해된 특정 가계(family)를 구축하는 방법을 알고 있었으며, 이 그룹은 이를 처음 기술한 연구자들의 이름을 따서 명명되었다. 흔히 마이오라나-맥팔랜드(Maiorana-McFarland) 클래스라고 불리는 이 가계는, 마치 집을 짓기 위한 표준 건축 설계도처럼 벤트 함수를 생성하는 주요 청사진 역할을 해왔다. 그러나 하나의 잔류하는 질문이 이 분야를 괴롭혀 왔다. 과연 이러한 표준 설계도가 이러한 함수들을 만드는 유일한 방법인가, 아니면 우리가 아직 발견하지 못한 다른 더 기이한 설계들이 존재하는가?

한 연구팀은 이 질문에 대해 포괄적인 검토를 수행하며, 벤트 함수 전체의 지형을 조사하여 그것들이 해당 표준 가계와 어떻게 연관되는지 살펴보았다. 그들의 연구는 알려진 설계도들이 유용하기는 하지만, 전체 가능성의 아주 작은 부분만을 나타낸다는 점을 확인해 주었다. 8개의 변수를 가진 함수의 경우, 컴퓨터 탐색을 통해 벤트 함수의 총 개수가 대략 2의 106승에 달할 정도로 천문학적으로 크다는 것이 밝혀졌다. 이와 극명하게 대조적으로, 표준 마이오라나-맥팔랜드 청사법을 사용하여 구축할 수 있는 함수의 개수는 최대 2의 81승 정도로 추정된다. 이 거대한 격차는 대다수의 벤트 함수가 우리가 명시적으로 구축해 온 함수들과는 근본적으로 다르다는 것을 시사한다. 연구자들의 목표는 이 두 극단 사이의 영역을 지도화하여, 기존의 틀에 확실히 들어맞지 않는 새로운 벤트 함수 구축 방법을 식별하고, 왜 그것들이 그토록 다른지에 대한 구조적 이유를 이해하는 것이었다.

논문은 표준 청사법을 수정하기 위해 설계된 C 클래스와 D 클래스로 알려진 두 가지 특정 벤트 함수 가계를 조사하는 것으로 시작한다. 이 가계들은 표준 공식에 특정 패턴을 추가함으로써 의도적인 작은 변화를 도입한다. 연구진은 이러한 수정 사항들이 결과물을 표준 가계 밖으로 밀어내기에 충분한지 조사했다. 그들은 만약 구축에 사용된 치환(permutation)이 특정 대수적 성질을 갖는다면—즉, 특정한 숨겨진 대칭성이 결여되어 있다면—결과로 나타나는 벤트 함수가 표준 형태로 변환될 수 없음을 발견했다. 저자들은 어떤 함수가 이 새로운 이국적인 가계에 속하고, 어떤 함수가 여전히 기존의 틀 안에 갇혀 있는지 결정할 수 있는 명확하고 테스트 가능한 규칙들을 제공했다. 또한 그들은 다양한 수정 유형을 결합하는 '슈퍼클래스(superclasses)'를 탐구했는데, 어떤 조합은 작동하지만 어떤 조합은 벤트 함수를 전혀 생성하지 못한다는 것을 발견했으며, 이는 필요한 수준의 예측 불가능성을 유지하기 위해 요구되는 섬세한 균형을 드러냈다.

이러한 특정 가계들을 넘어, 연구진은 유한체의 곱셈 구조를 사용하여 구축된 함수들, 종종 트레이스(trace) 항을 사용하여 설명되는 함수들을 살펴보았다. 이 함수들은 특정 지수로 거듭제곱된 수의 합에 따라 출력이 결정되는 함수들이다. 본 연구는 특히 특정 지수에 기반한 많은 함수들이 표준 가계의 밖에 있음이 증명 가능하다는 점을 강조한다. 연구진은 2차 미분—함수의 변화율 자체가 어떻게 변하는지를 측정하는 방법—을 포함하는 특정 수학적 테스트를 사용하여, 이 함수들이 표준 클래스에서 발견되는 구조적 규칙성을 결여하고 있음을 증명했다. 또한 그들은 거의 완벽한 비선형(almost perfect nonlinear) 함수와 같은 다른 중요한 수학적 객체의 지표 역할을 하는 함수들을 조사했으며, 이러한 지표들이 종-종 알려진 가계의 밖에 있는 벤트 함수의 고유하고 비표준적인 특성을 지니고 있음을 보여주었다.

연구의 핵심 주제는 '선형성 지수(linearity index)'라는 개념인데, 이는 함수가 얼마나 단순한 선형 패턴과 닮았는지를 나타내는 척도로 생각할 수 있다. 표준 마이오라나-맥팔랜드 함수들은 높은 선형성 지수를 가지며, 이는 커다란 단순 아핀(affine) 조각들로 분해될 수 있음을 의미한다. 연구진은 이들이 가질 수 있는 최소한의 선형성 지수를 가진 새로운 범주의 함수들을 식별하였으며, 이를 '최적(optimal)'이라고 명명했다. 이 함수들은 표준적인 것들과 정반대이다. 즉, 너무나 불규칙하여 큰 아핀 블록들로 전혀 단순화될 수 없다. 논문은 이 최적 함수들을 구축하는 방법을 상세히 설명하고, 이들이 표준 클래스와 근본적으로 다르다는 것을 증명한다. 저자들은 함수의 도메인 내에 있는 특별한 기하학적 하부 구조인 'M-부분공간(M-subspaces)'을 연구함으로써, 이 최적 함수들이 표준 함수들은 갖지 못한 고유하고 최소한의 구조를 가지고 있음을 보여주었다.

이 조사는 '일반화된 마이오라나-맥팔랜드 클래스'라고 불리는 더 넓고 유연한 프레임워크를 다룬다. 이 프레임워크는 표준 클래스에서 사용하는 고정된 크기가 아닌, 다양한 크기의 아핀 조각들로부터 구축된 함수들을 허용한다. 연구진은 이 더 넓은 클래스에 속한 함수가 언제 표준 가계에 머무르고, 언제 그 밖으로 벗어나는지를 정확히 규명했다. 그들은 구성 요소를 신중하게 선택함으로써, 표준에 '거의' 가깝지만 여전히 구별되는 함수를 만들 수도 있고, 표준 가계와 완전히 이질적인 함수를 만들 수도 있다는 것을 발견했다. 논문은 몇 가지 미해결 문제들을 나열하며, 자신들이 수학적 영토의 상당 부분을 지도화했음에도 불구하고 모든 벤트 함수를 전수 조사하는 것은 여전히 미스터리로 남아 있음을 인정한다. 그들은 미래의 연구자들이 이러한 이국적인 함수들의 더 많은 무한 가계를 찾아내고, 이들이 가진 고유한 대수적 구조를 이해함으로써, 이 분야가 원래의 청사법이라는 한계를 넘어 계속 진화할 수 있도록 도전할 것을 촉구한다.

기술 요약: 벤트 함수(Bent Functions)와 완성된 마요라나-맥팔랜드(Maiorana-McFarland) 클래스

문제 정의
Rothaus가 도입한 불리언 벤트 함수는 짝수 개의 변수를 가진 함수 중 최대 비선형성(아핀 함수로부터의 최대 거리)을 달리는 근본적인 함수 클래스를 나타낸다. 마요라나-맥팔랜드(M) 클래스와 그 완성형( $M^\#$ )은 가장 철저하게 이해된 명시적 벤트 함수 가문이지만, 최근의 계산적 증거는 전체 벤트 함수의 수와 $M^\#$ 에 속하는 함수의 수 사이에 상당한 격차가 있음을 보여준다. 구체적으로, 차원 8에서 전체 벤트 함수의 수는 약 $2^{106}$ 인 반면, 마요라나-맥팔랜드와 동등한 함수의 수는 최대 $2^{81}$ 로 추정된다. 이러한 관찰은 본 조사 논문의 핵심 문제인, 완성된 마요라나-맥팔랜드 클래스( $M^\#$ ) 외부에 존재하는 벤트 함수를 특징짓고, 그들의 대수적 구조를 이해하며, 이러한 함수들을 위한 명시적 구성 방법을 개발하는 데 동기를 부여한다. 본 논문은 "배제 문제(exclusion problem)"—즉, 다양한 벤트 함수 클래스와 $M^\#$ 사이의 교집합을 결정하고, 함수가 이 클래스 밖에 있음을 증명할 수 있는 조건을 식별하는 것—에 초점을 맞춘다.

방법론
본 논문은 불리언 벤트 함수의 설계 및 분석에 관한 근본적인 결과와 최근의 진보를 종합하여 포괄적인 조사 방법론을 채택한다. 기술적 접근 방식은 다음 사항에 크게 의존한다:

대수적 특징 규명: $M^\#$ 멤버십을 특징짓기 위해 2차 도함수 기준(Lemma 1.2)을 활용한다. 함수가 $M^\#$ 에 속할 필요충분조건은 모든 $a, b \in U$ 에 대해 2차 도함수 $D_a D_b f$ 가 0이 되는 $m$ 차원 부분 공간 $U$ 가 존재하는 것이다.
선형성 지수와 M-부분 공간: "선형성 지수"($ind(f) $)를 분석한다. 이는 M-부분 공간(2차 도함수가 0이 되는 부분 공간)의 최대 차원으로 정의된다.$ ind(f) = n/2 $인 함수는$ M^# $에 속하며, 최소 지수($ ind(f)=1 $)를 갖는 함수는$ \ell$-최적(optimal)이라 불린다.
이차적 구성: 직접 합(direct sum), 간접 합(indirect sum), 연결(concatenations, 2- 및 4-연결), 그리고 트레이스 항(trace terms) 또는 지표(indicators)의 추가가 $M^\#$ 멤버십에 어떤 영향을 미치는지 조사한다.
일반화된 프레임워크: 고전적인 $M$ 클래스( $r=s=n/2$ )에서 일반화된 마요라나-맥팔랜드(GMM) 클래스( $Mr,s$ , 여기서 $f(x,y) = x \cdot \phi(y) + h(y)$ 이고 $x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s, r \neq s$ )로 분석을 확장한다.

주요 기여 및 결과

Carlet의 C 및 D 클래스: 본 논문은 벡터 부분 공간의 지표를 추가하여 마요라나-맥팔랜드 형태를 수정한 C 및 D 클래스를 상세히 다룬다.
- Class C: 함수 $x \cdot \pi(y) + 1_{L^\perp}(x)$ 형태의 함수들이다. 저자들은 $\pi$ 와 부분 공간 $L$ 에 대한 충분 조건(특히 성질 (C))을 요약하여, 해당 함수가 벤트 함수이면서 동시에 $M^\#$ 밖에 있음을 보장한다. 핵심 결과는 0이 아닌 선형 구조가 결여된 성분을 가진 치환(permutation)과 관련이 있다.
- Class D 및 $D_0$ : 함수 $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ 형태의 함수들과 그 하위 클래스인 $D_0$ ( $x \cdot \pi(y) + \delta_0(x)$ )를 다룬다. 본 논문은 이차 치환(quadratic permutations)에 대해, 멤버십이 치환이 아핀 하이퍼플레인 상에서 아핀인지 여부에 달려 있음을 보여줌으로써 $D_0 \cap M^\#$ 를 완전히 규명한다. 고차수의 경우, 함수들은 종종 $M^\#$ 밖에 존재한다.
- 상위 클래스(Superclasses): 지표들을 결합하여 형성된 상위 클래스(SC, CD, SD)를 조사한다. 저자들은 일부 조합(예: SC)은 $M^\#$ 밖의 벤트 함수를 생성하는 반면, 다른 조합(예: SD)은 벤트 함수 자체를 생성하지 못함을 확인한다.
트레이스 항과 $P_\tau$ 성질:
- 본 논문은 트레이스 항(예: Dillon 및 Kasami 지수)을 통해 정의된 단항식, 이항식 및 관련 벤트 함수들을 검토한다. 이를 통해 특정 니호(Niho) 지수를 가진 함수들을 포함한 많은 함수가 $M^\#$ 밖에 있음을 확인한다.
- 상당 부분은 벤트 함수에 트레이스 항의 다항식 조합을 더하는 것과 관련된 $P_\tau$ 성질에 할애된다. 본 논문은 듀얼 함수의 2차 도함수가 0이 되는 것으로 특징지어지는 $P_\tau$ 성질을 통해, C 또는 D 클래스에 의해 커버되지 않는 $M^\#$ 외부의 벤트 함수 무한 가문을 구성하는 방법을 상세히 설명한다.
일반화된 마요라나-맥팔랜드 (GMM) 클래스:
- 본 논문은 GMM 클래스( $Mr,s$ )와 그 완성형을 도입한다. 이 클래스에서의 벤트성을 "벤트 집합(bent sets)"과 "부분적으로 정의된 벤트 함수"를 사용하여 규명한다.
- Almost Maiorana-McFarland ( $k=1$ ): 선형성 지수가 $n/2 - 1$ 인 함수들을 분석한다. 본 논문은 도메인의 "자명한(trivial)", "비적절한(non-proper)", "적절한(proper)" 분할을 구분하며, 특정 적절한 분할이 $M^\#$ 밖의 벤트 함수를 생성함을 보여준다.
- $\ell$ -최적 함수: 최소 선형성 지수($ind(f)=1$)를 갖는 함수들을 논하며, 이들이 마요라나-맥팔랜드 함수의 "반대"임을 언급한다. 성질 (P1)(0이 아닌 2차 도함수)을 가진 치환을 이용한 구성법이 이러한 함수들을 생성하는 방법으로 강조된다.
M-부분 공간 및 이차적 구성:
- 본 논문은 M-부분 공간에 대한 심도 있는 대수적 및 조합론적 분석을 제공한다. 최대 M-부분 공간의 개수에 대한 경계값을 설정하고, 이를 벤트 함수의 분류와 연결한다.
- 이차적 구성(직접 합, 간접 합, 2- 및 4-연결)이 $M^\#$ 밖의 함수를 결과로 내기 위한 필요충분조건을 제시한다. 특히, $M^\#$ 밖의 벤트 함수와 임의의 벤트 함수를 4-연결하면 새로운 $M^\#$ 밖의 벤트 함수가 생성됨을 증명한다.

의의
본 논문은 잘 알려진 마요라나-맥팔랜드 클래스와 광대하고 미분류된 벤트 함수의 공간 사이의 간극을 메우는 포괄적인 조사로서 자리매김한다. 주요 의의는 다음과 같다:

배제의 체계화: 벤트 함수가 언제 $M^\#$ 밖에 떨어지는지를 결정하기 위해, 단순한 사례 제시를 넘어 선형성 지수와 M-부분 공간에 기반한 구조적 특징화를 바탕으로 한 통일된 프레임워크를 제공한다.
구성 방법의 확장: 고정된 차원에서 알려진 예시의 부족함을 해결하기 위해, $M^\#$ 외부의 벤트 함수 무한 가문을 생성하는 명시적 방법(C, D, $P_\tau$ , GMM)을 상세히 기술한다.
대수적 구조의 명확화: 선형성 지수와 M-부분 공간과 같은 개념을 도입하고 정교화하여, 벤트 함수의 대수적 성질과 일반화된 마요라나-맥팔랜드 계층 구조 간의 관계를 이해하기 위한 근본적인 도구로 사용한다.
미해결 문제 식별: 본 논문은 $M^\#$ 내의 EA-동치(EA-equivalence) 클래스의 정확한 열거, 이러한 이론의 $p$ -진 벤트 함수로의 확장, 그리고 맥파랜드 클래스 외부의 차집합(difference sets) 구성 등을 포함한 수많은 미해결 문제를 나열하며 마무리된다.

저자들은 $M^\#$ 외부의 함수를 식별하는 데 상당한 진전이 있었음에도 불구하고, 벤트 함수의 전체 열거와 그들의 대수적 구조에 대한 완전한 분류는 여전히 해결해야 할 과제로 남아 있음을 인정하며 겸허한 어조를 유지한다. 본 연구는 표준 마요라나-맥팔랜드 구성을 통해서는 포착할 수 없는 특정 비선형 특성을 가진 암호학적으로 중요한 불리언 함수를 설계하고자 하는 연구자들에게 기초적인 참고 자료 역할을 한다.

유사한 논문