🔢 mathematics

The combinatorial structure and value distributions of plateaued functions

이 논문은 암호학에서 중요한 역할을 하는 플래티어드 함수의 와일시 변환, 선형성, 미분적 성질 및 값 분포 간의 상호작용을 연구하며, 특히 '거의 균형' 플래티어드 함수와 플래티어드 APN 함수에 대한 존재 조건, 선형성, 미분 균일성 경계 등을 규명합니다.

원저자: Lukas Kölsch, Alexandr Polujan

게시일 2026-03-26

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Lukas Kölsch, Alexandr Polujan

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

이 논문은 암호학의 핵심이 되는 **'평탄한 함수 (Plateaued Functions)'**라는 수학적 개념을 연구한 것입니다. 조금 어렵게 들릴 수 있지만, 일상적인 비유를 통해 쉽게 설명해 드리겠습니다.

🏔️ 산악 지형과 암호의 비밀

상상해 보세요. 암호학자들은 데이터를 안전하게 지키기 위해 **'산악 지형'**과 같은 수학적 함수를 만듭니다.

완벽한 평지 (Affine functions): 너무 평평해서 누구나 쉽게 예측할 수 있어 암호로 쓰면 안 됩니다.
완벽한 절벽 (Bent functions): 너무 급하고 예측 불가능해서 암호로 쓰기엔 좋지만, 만들기가 매우 어렵습니다.
평탄한 고원 (Plateaued functions): 이 논문에서 연구하는 주인공입니다. 산의 정상은 평평한 고원처럼 넓고, 그 주변은 완만하게 내려가는 형태입니다. 이 '고원' 구조가 암호 시스템에서 가장 이상적인 균형을 이룹니다.

이 함수들은 AES, Keccak(블록체인 해시 함수) 같은 현대 암호 시스템의 핵심 부품으로 쓰입니다.

🔍 이 논문이 해결한 3 가지 큰 질문

연구자들은 이 '고원 함수'들이 어떻게 생겼는지, 그리고 그 모양이 암호의 안전성에 어떤 영향을 미치는지 분석했습니다.

1. "물 분포"의 비밀 (Value Distribution)

함수는 입력값을 받아 출력값을 만들어냅니다. 이때 출력값이 얼마나 고르게 퍼져 있는지가 중요합니다.

균형 잡힌 상태 (Balanced): 모든 출력값이 똑같은 수의 입력값을 받습니다. 마치 물을 고르게 퍼뜨린 것처럼 이상적입니다.
거의 균형 잡힌 상태 (Almost Balanced): 대부분의 출력값은 고르게 퍼지지만, 하나만 유독 많거나 적게 받는 상태입니다.

이 논문은 **"어떤 함수가 '거의 균형 잡힌' 상태가 될 수 있는가?"**를 수학적으로 증명했습니다. 마치 "어떤 산의 정상은 평평하지만, 한쪽 면만 유독 가파를 수 있다"는 규칙을 찾아낸 것과 같습니다.

2. "한 번만" vs "여러 번" (d-to-1 함수)

어떤 함수는 입력을 넣으면 정확히 1 개의 출력만 나옵니다 (일대일 대응). 하지만 어떤 함수는 d 개의 입력이 같은 출력을 만들어냅니다 (d-to-1).

예를 들어, 3-to-1 함수는 3 개의 다른 입력이 같은 결과를 내는 경우입니다.

연구자들은 **"평탄한 고원 함수가 d-to-1 형태가 되려면 d 는 어떤 숫자여야 하는가?"**를 발견했습니다.

결과: d 는 무작위 숫자가 될 수 없습니다. 오직 **특정 규칙 (예: $p^t + 1$ 형태)**을 가진 숫자일 때만 가능합니다.
비유: 마치 "고원 지형의 산꼭대기에 3 명이 동시에 서 있을 수는 있지만, 5 명이 동시에 서 있을 수는 없다"는 법칙을 발견한 것입니다. 이는 암호 설계자가 실수하지 않도록 중요한 가이드가 됩니다.

3. "APN"이라는 특수한 산 (APN Functions)

암호학에서 APN (Almost Perfect Nonlinear) 함수는 가장 강력한 방어막으로 불립니다. 해커가 암호를 뚫으려 할 때 가장 견고한 방패입니다.

이 논문은 APN 함수 중에서도 '평탄한 고원' 형태인 것들을 집중 분석했습니다.
주요 발견: APN 함수가 가진 '출력 분포'에는 매우 제한적인 패턴만 존재합니다. 특히, 우리가 알고 있던 어떤 특정 패턴 (두 번째 경우) 은 평탄한 고원 함수에서는 절대 나올 수 없다는 것을 증명했습니다.
의미: "이런 형태의 산은 존재하지 않는다"고 말해주면, 암호 설계자는 그 길을 포기하고 다른 안전한 길을 찾을 수 있습니다.

💡 왜 이것이 중요한가요? (일상적인 비유)

이 연구는 마치 건축가에게 "어떤 형태의 기둥은 건물을 지탱할 수 없다"는 설계 도면을 주는 것과 같습니다.

안전한 암호 설계: 암호학자들은 이 논문의 결과를 바탕으로 해커가 뚫기 어려운 새로운 암호 알고리즘을 설계할 수 있습니다.
불필요한 시도 제거: "이런 숫자 조합으로는 평탄한 고원 함수를 만들 수 없다"는 것을 알면, 수천 가지의 시도를 하지 않아도 되어 시간과 에너지를 아낄 수 있습니다.
새로운 발견: 특히 제로지식증명 (Zero-Knowledge Proof) 같은 최신 블록체인 기술에서 쓰이는 함수들의 구조를 더 깊이 이해하는 데 기여합니다.

📝 한 줄 요약

이 논문은 암호학의 핵심 부품인 '평탄한 고원 함수'의 모양과 규칙을 완벽하게 분석하여, **"어떤 모양은 존재할 수 없고, 어떤 모양은 반드시 이 규칙을 따라야 한다"**는 법칙을 찾아냈습니다. 이는 더 안전하고 효율적인 암호 시스템을 만드는 데 필수적인 지도가 됩니다.

논문 개요

이 논문은 암호학에서 중요한 역할을 하는 **평탄 함수 (Plateaued functions)**의 조합론적 특성과 값 분포 (Value distribution) 를 연구합니다. 평탄 함수는 2 차 함수, 벤트 (Bent) 함수, 그리고 대부분의 알려진 APN (Almost Perfect Nonlinear) 함수를 포함하는 광범위한 클래스로, 비선형성, 복원성, 낮은 가법 자기상관 등 우수한 암호학적 성질을 가집니다. 저자들은 평탄 함수의 왈시 변환 (Walsh transform), 선형성 (Linearity), 미분 성질 (Differential properties) 및 값 분포 (이미지 및 전상 집합의 크기) 간의 상호작용을 규명하는 새로운 이론적 도구를 개발했습니다.

1. 연구 문제 (Problem)

배경: 암호학에서 사용되는 함수 (선형, 2 차, 벤트, APN 등) 는 대부분 평탄 함수의 특수한 경우이거나 그 부분집합입니다. 특히 APN 함수는 차분 분석에 대한 저항성을 위해 필수적입니다.
핵심 질문: 평탄 함수의 조합론적 구조, 특히 **값 분포 (Value distribution)**는 어떻게 결정되며, 이는 왈시 변환 및 불균형 (Imbalance) 과 어떤 관계가 있는가?
구체적 목표:
- 평탄 함수가 가질 수 있는 전상 집합 (Preimage set) 크기의 범위를 왈시 변환을 통해 규명.
- "거의 균형 (Almost balanced)" 상태인 평탄 함수 (전상 집합 크기가 두 가지 값만 가지는 경우) 의 존재 조건 및 구조 분석.
- 평탄 APN 함수의 조합론적 구조와 그 값 분포의 제약 조건 규명.

2. 방법론 (Methodology)

저자들은 함수의 미분 성질에 의존하기보다, 왈시 변환 (Walsh transform) 의 0 지점 ( $a=0$ ) 에서의 값에 기반한 새로운 분석 기법을 도입했습니다.

왈시 변환과 전상 집합의 연결:
- 직교성 (Orthogonality) 을 이용하여 전상 집합의 크기 $|F^{-1}(\beta)|$ 와 왈시 계수 $W_F(b, 0)$ 사이의 관계를 유도했습니다.
- 특히, 전상 집합 크기의 제곱합과 왈시 변환의 2 차 모멘트 사이의 관계를 Proposition 3.1 을 통해 정립했습니다.
불균형 (Imbalance) 의 도입:
- $N_bF = \frac{1}{p^m} \sum_{b \neq 0} |W_F(b, 0)|^2$ 로 정의된 불균형 지표를 사용하여 함수가 균형 (Balanced) 상태로부터 얼마나 벗어났는지 정량화했습니다.
부등식 및 경계 도출:
- 코시 - 슈바르츠 부등식 (Cauchy-Schwarz inequality) 을 활용하여 전상 집합 크기의 상하한을 불균형과 이미지 집합 크기의 함수로 표현하는 Theorem 3.3을 증명했습니다.
대수적 및 조합론적 분석:
- 평탄 함수의 왈시 계수가 $\{0, \pm p^{(n+t)/2}\}$ 의 값을 가진다는 성질을 활용하여, $d$ -to-1 함수 (특정 $d$ 에 대해 전상 집합 크기가 1 또는 $d$ 인 함수) 가 평탄 함수가 되기 위한 필요충분조건을 유도했습니다.
- 순환체 (Cyclotomic fields) 이론을 사용하여 홀수 소수 $p$ 에 대한 정수성 조건을 검증했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

가. 거의 균형 (Almost Balanced) 함수의 일반화 및 특성 규명

정의 확장: 기존에 벤트 함수 등에 국한되었던 '거의 균형' 함수의 개념을 비전사 (Non-surjective) 인 평탄 함수로 확장했습니다.
Theorem 4.1: 전사적인 거의 균형 평탄 함수의 경우, 모든 비영 벡터 $b$ 에 대해 $W_F(b, 0)$ 의 크기가 일정하며, 이는 왈시 변환의 특정 값을 통해 전상 집합 크기를 정확히 결정할 수 있음을 보였습니다.
Theorem 4.6: 출력 차원 $m \le n/2$ 인 경우, 모든 함수는 적절한 가법 사상을 더하면 전사 함수가 됨을 증명하여, 평탄 함수 연구의 범위를 확장했습니다.

나. $d$ -to-1 평탄 함수의 구조적 제약 (Theorem 5.2)

핵심 결과: 평탄 함수가 $d$ $d$ -to-1 (단, $d > 2$ $d > 2$ ) 일 수 있는 $d$ $d$ 의 값은 매우 제한적입니다.
- $d$ 는 반드시 $p^t + 1$ 형태 ( $t \ge 1, t|n/2$ ) 여야 합니다.
- 이러한 함수는 $n$ 이 짝수여야 하며, 구성 요소 함수 (Component functions) 들은 벤트 함수와 진폭이 $p^{n/2+t}$ 인 평탄 함수로 구성됩니다.
단항식 (Monomial) 함수 적용 (Corollary 5.4):
- 평탄 단항식 함수 $x^d$ 는 순열 (Permutation, $d=1$ ) 이거나 $(p^t+1)$ -to-1 함수여야 합니다.
- 이는 0 지식 증명 시스템 (Poseidon, Rescue-Prime 등) 에서 사용되는 단항식 함수의 구조적 한계를 명확히 했습니다.

다. 미분 균일성 (Differential Uniformity) 과의 관계

Theorem 5.5 & 5.6: $(p^t+1)$ $(p^{t} + 1)$ -to-1 평탄 함수의 미분 균일성 $\delta$ $δ$ 는 최소 $p^t$ $p^{t}$ 임을 증명했습니다.
- $\delta = p^t$ 가 되려면 함수는 미분적으로 2-값 (Differentially 2-valued, 즉 $F(x+a)-F(x)=b$ 의 해가 0 또는 $p^t$ 개) 이어야 합니다.
- 이는 평탄 함수의 비선형성 (진폭) 과 미분 성질 간의 강한 상관관계를 보여줍니다.

라. 평탄 APN 함수의 조합론적 구조 (Section 6)

불균형의 하한 및 상한 (Proposition 6.3): 평탄 APN 함수의 불균형 $N_bF$ $N_{b} F$ 는 $(2^{n+1}-2)/3 \le N_bF \le 2^{n+1}-2$ $(2^{n + 1} - 2) /3 \leq N_{b} F \leq 2^{n + 1} - 2$ 범위에 있어야 합니다.
- 하한은 벤트 성분 함수가 $2(2^n-1)/3$ 개일 때 달성됩니다.
- 상한은 균형 성분 함수가 하나도 없을 때 달성됩니다.
Theorem 6.7 (중요한 부정 결과): 최소 이미지 크기를 갖는 APN 함수의 가능한 값 분포 중, "두 개의 전상 집합 크기가 2 이고 나머지가 3 인 경우"는 평탄 APN 함수에서는 존재할 수 없음을 증명했습니다. 이는 기존 APN 함수 연구의 미해결 문제를 평탄 함수 클래스 내에서 해결한 것입니다.
Theorem 6.8: 최소 이미지 크기를 갖는 평탄 APN 함수는 균형 성분 함수를 가질 수 없음을 보였습니다.

4. 의의 및 중요성 (Significance)

이론적 통합: 평탄 함수, 벤트 함수, APN 함수, 2 차 함수 등 다양한 암호학적 함수 클래스를 하나의 통일된 프레임워크 (왈시 변환과 불균형 기반) 하에서 분석할 수 있는 강력한 이론적 도구를 제공했습니다.
구현 및 설계 가이드: 단항식 함수 및 Maiorana-McFarland 구성을 이용한 평탄 함수의 생성 시, 어떤 파라미터 ( $d$ , $t$ 등) 가 유효한지 명확한 조건을 제시하여 암호 알고리즘 설계 (예: 0 지식 증명 시스템) 에 직접적인 도움을 줍니다.
APN 함수의 한계 규명: 평탄 APN 함수가 가질 수 있는 값 분포의 종류를 제한함으로써, "Big APN" 문제 (짝수 변수에서의 APN 순열 존재성) 와 같은 난제에 대한 새로운 통찰을 제공했습니다. 특히, 특정 값 분포의 불가능성을 증명하여 탐색 공간을 축소했습니다.
새로운 연구 방향 제시: 평탄 APN 함수의 벤트 성분 개수에 대한 더 엄격한 상한선 설정 및 새로운 구성 방법론 개발을 위한 기초를 마련했습니다.

결론

이 논문은 평탄 함수의 조합론적 구조를 왈시 변환의 관점에서 깊이 있게 분석하여, 함수의 값 분포와 미분 성질 사이의 본질적인 연결고리를 규명했습니다. 특히, 평탄 함수가 가질 수 있는 $d$ -to-1 구조의 제한성과 평탄 APN 함수의 값 분포에 대한 부정적 결과 (Non-existence) 는 암호학 이론 연구에 중요한 이정표가 될 것입니다.