Weight distributions of two classes of linear codes with few weights derived from Weil sums

기술 요약: 바일 합(Weil Sums)으로부터 유도된 두 종류의 선형 부호의 가중치 분포

문제 정의
적은 수의 가중치를 갖는 선형 부호는 비밀 공유 스킴, 인증 코드, 연관 스킴(association schemes), 그리고 강한 정규 그래프(strongly regular graphs) 분야에서의 응용 가능성 때문에 부호 이론에서 매우 중요한 관심을 받고 있다. 이 분야의 주요 과제는 특정 가중치 분포(즉, 적은 수의 서로 다른 비제로 가중치)를 갖는 새로운 선형 부호 패밀리를 구축하고, 그 파라미터(길이, 차원 및 최소 거리)를 결정하는 것이다. 이전 연구들은 트레이스 함수(trace functions)와 특정 다항식 형태에 기반한 정의 집합을 활용하여 이러한 부호를 구축해 왔으나, 다양한 가중치 구조를 생성하기 위해 이항 바일 합(binomial Weil sums)과 같은 고급 지수 합의 평가를 활용하는 새로운 정의 집합을 탐색할 필요가 남아 있다.

방법론
저자들은 $q = p^e$ ($p$와 $\ell$은 서로 다른 홀 소수, $e = \phi(\ell^k)$)인 유한체 $\mathbb{F}_q$ 상의 두 가지 구별되는 $p$-진 선형 부호를 구축한다. 이 구축은 정의 집합 접근 방식을 따르며, 여기서 선형 부호 $C_D$는 다음과 같이 정의된다:
$$C_D = \{c(\gamma, \delta) = (\text{Tr}_1^e(\gamma x + \delta y))_{(x,y) \in D} : \gamma, \delta \in \mathbb{F}_q\}$$
본 논문은 이전의 구축 방식과 달리 특정 이항 바일 합 구조를 포함하는 두 가지 특정한 정의 집합 $D_u$와 $D'$를 조사한다.

1. 정의 집합 $D_u$: $D_u = \{(x, y) \in \mathbb{F}_q^2 \setminus \{(0,0)\} : \text{Tr}_1^e(x + y^N) = u\}$로 정의되며, 여기서 $N = \frac{q-1}{2\ell^k}$이고 $u \in \mathbb{F}_p$이다.
2. 정의 집합 $D'$: $D' = \{(x, y) \in \mathbb{F}_q^2 \setminus \{(0,0)\} : f(x) + \text{Tr}_1^e(y^N) = 0\}$로 정의된다. 여기서 $f$는 특정 동차 조건(homogeneity conditions)을 만족하는 쌍의 듀얼(dual)을 가진 $\mathbb{F}_q$에서 $\mathbb{F}_p$로의 약한 정규 벤트 함수(weakly regular bent function)이다.

핵심 방법론은 이항 바일 합 $S_{2\ell^k}(a, b)$ 및 관련 사이클로토믹 체(cyclotomic fields) 상의 합에 대한 상세한 평가를 포함한다. 저자들은 다음을 활용한다:

• 정형적인 가법 및 이차 곱셈 캐릭터(canonical additive and quadratic multiplicative characters)의 성질.
• Cheng, Gao, Sheng의 최근 연구들에 의한 가우스 합(Gauss sums) 및 바일 합의 평가.
• 약한 정규 벤트 함수와 그 듀얼의 이론.
• 트레이스 조건을 처리하기 위해 원소의 곱셈군 내 차수(order)에 따른 인덱스 집합의 분할.

다양한 $(\gamma, \delta)$ 쌍에 대한 정의 방정식의 해의 개수를 계산함으로써, 저자들은 부호어(codewords)의 해밍 가중치와 그에 대응하는 빈도를 도출한다.

주요 기여 및 결과
본 논문은 $p, \ell, k, u$에 대한 다양한 조건 하에서 구축된 부호의 파라미터와 가중치 분포에 대한 완전한 특성화를 제공한다.

1. $D_u$로부터의 부호:

   • 저자들은 $u$의 값과 $\ell \pmod p$의 합동 관계에 따라 다섯 가지 별개의 경우에 대한 가중치 분포를 결정한다.
   • 결과적으로 생성된 부호들은 두 개, 네 개 또는 여섯 개의 비제로 가중치를 나타낸다.
   • 특히, $u \neq 0$이고 특정 이차 비잔여(quadratic non-residue) 조건이 충족될 때, 이 구축은 **두 가지 가중치(two-weight)**를 갖는 무한한 부호 패밀리를 생성한다.
   • 특정 조건(최소 가중치와 최대 가중치의 비율이 $\frac{p-1}{p}$를 초과하는 경우) 하에서, 이 부호들은 **최소(minimal)**임이 증명되어 비밀 공유 응용에 적합하다.

2. $D'$로부터의 부호:

   • 약한 정규 벤트 함수 $f$를 포함함으로써, 저자들은 더 복잡한 가중치 구조를 갖는 부호를 구축한다.
   • $p \pmod 4$의 합동 관계와 $\ell$과 $p$의 관계에 따라, 이 부호들은 여섯 개, 여덟 개 또는 아홉 개의 비제로 가중치를 갖는 것으로 나타난다.
   • 가중치 분포는 $f$의 월시 변환(Walsh transform)의 부호와 이차 캐릭터 평가에서 유도된 항들을 포함하여 모든 경우에 대해 명시적으로 표로 정리되었다.

3. 최적성(Optimality):

   • 중요한 결과 중 하나는 $D_u$ 구축으로부터 유도된 두 가지 가중치 최적(two-weight optimal) 선형 부대의 무한한 패밀리를 식별한 것이다. 이 부호들은 차원과 최소 거리가 주어졌을 때 선형 부호의 길이에 대한 근본적인 하한인 **그리스머 경계(Griesmer bound)**를 만족한다.

의의
본 논문은 다음 분야에서 의의를 갖는다:

• 정의 집합의 참신함: 본 연구에서 사용된 정의 집합은 이전의 구축 방식(예: 단순 트레이스 함수나 특정 거듭제곱 맵을 사용하는 방식)과 차별화되는 새로운 이항 바일 합($S_{2\ell^k}(a, b)$) 구조를 도입한다.
• 가중치 분포의 다양성: 본 연구는 2, 4, 6, 8, 9개의 비제로 가중치를 갖는 부호를 명시적으로 구축함으로써, 적은 수의 가중치를 갖는 선형 부호의 알려진 영역을 확장한다.
• 최적성 및 최소성: 그리스머 경계를 만족하는 최적의 두 가지 가중치 부호 패밀리를 구축한 것은 효율적인 오류 정정 부호를 찾는 데 있어 주목할 만한 기여이다. 또한, 특정 조건 하에서 최소 부호임을 확인한 것은 비밀 공유와 같은 암호학적 응용에서의 유용성을 강화한다.
• 방법론적 엄밀성: 본 논문은 가중치 분포 결정 문제를 해결하기 위해 바일 합과 사이클로토믹 체 이론을 엄격하게 적용하는 방법을 보여주며, 이는 유사한 부호 구축을 분석하는 데 있어 템플릿을 제공한다.

저자들은 자신들의 연구가 기존의 방법들을 성공적으로 일반화하였으며, 이론적 연구와 실질적 응용 모두에 바람직한 특성을 가진 새로운 선형 부호의 풍부한 원천을 제공한다고 결론짓는다.