A Totient Function Associated with Variants of Groups

1. 연구 배경 및 문제 제기 (Problem)

이 논문은 이산 로그 문제 (Discrete Log Problem, DLP) 와 관련된 암호화 시스템의 보안성을 강화하기 위해 새로운 수학적 도구를 도입합니다.

• 배경: 현대 암호학에서 이산 로그 문제는 공개키 암호 시스템의 핵심입니다. 기존 시스템은 '변형된 군 (variants of groups)'을 사용하여 보안성을 높일 수 있음을 시사합니다. 변형된 군 $G_x$에서는 암호문을 $c = (gx)^{e-1}g$ 형태로 생성하며, 여기서 $x$는 비밀 키의 일부입니다.
• 문제: 공격자가 평문 $g$와 암호문 $c$를 알고 있을 때, 키 $(x, e)$를 찾기 위해 '브루트 포스 (brute force)' 공격을 수행하면, $G$의 모든 원소 $y$와 $U_n$ (정수 $n$에 대한 곱셈군) 의 모든 원소 $f$에 대해 $(gy)^{f-1}$을 계산하여 $c$와 비교해야 합니다.
  • 이때, 올바른 키 $(x, e)$ 외에도 방정식 $(gy)^{f-1} = c$를 만족하는 '거짓 긍정 (false positive)' 쌍 $(y, f)$가 존재할 수 있습니다.
  • 이러한 거짓 긍정의 수가 많을수록 공격자가 올바른 키를 식별하기가 더 어려워지므로, 시스템의 보안성이 높아집니다.
• 목표: 이 거짓 긍정 쌍의 수를 정확히 계산하고 하한을 구할 수 있는 새로운 오일러 함수 (Totient Function) $T(n)$를 정의하고, 그 성질을 분석하여 암호 시스템의 안전성 평가에 활용하는 것입니다.

2. 방법론 (Methodology)

저자는 다음과 같은 수학적 접근법을 사용합니다.

• 새로운 함수 정의:
  새로운 오일러 함수 $T: \mathbb{N} \to \mathbb{N}$를 다음과 같이 정의합니다.
  $$T(n) = |\{1 \le m \le n \mid \gcd(m, n) = 1, \gcd(\frac{m-1}{2}, n) = 1\}|$$
  즉, $n$과 서로소인 홀수 $m$ 중에서 $(m-1)/2$ 또한 $n$과 서로소인 경우의 수를 세는 함수입니다. (단, $n=1$인 경우 $T(1)=0$으로 정의).

• 기존 함수와의 비교:

  • 오일러 피 함수 ($\phi$): $n$ 이하의 $n$과 서로소인 수의 개수.
  • 스케멜 함수 ($S_r(n)$): $n$과 서로소인 $r$개의 연속된 수의 개수. 특히 $S(n) = S_2(n)$은 $n$과 서로소인 연속된 두 수 $(m, m+1)$의 개수를 의미하며, $S(n) = n \prod_{p|n} (1 - \frac{2}{p})$로 표현됩니다.
  • 저자는 $T(n)$이 $S(n)$과 밀접한 관련이 있음을 증명하고, $T(n)$을 $S(n)$을 기반으로 한 근사식과 오차 범위로 표현합니다.

• 수학적 분석 도구:

  • 포함 - 배제 원리 (Inclusion-Exclusion Principle): $n$의 소인수 분해를 바탕으로 조건을 만족하지 않는 수들을 제거하여 $T(n)$의 정확한 값이나 상/하한을 유도합니다.
  • 디오판토스 방정식 (Diophantine Equations): $px = 1 + qy$ 형태의 방정식 해의 개수와 그 홀짝성 (parity) 을 분석하여 교집합의 크기를 추정합니다.
  • 군론 (Group Theory): 변형된 군 $G_x$의 구조와 이산 로그 문제의 해의 존재성을 분석합니다.

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

논문은 $n$의 형태 (홀수, 짝수, 소수 거듭제곱 등) 에 따라 $T(n)$의 값을 계산하거나 근사하는 정밀한 정리들을 제시합니다.

A. $T(n)$의 계산 공식 및 근사식

1. 홀수 소수 거듭제곱 ($n=p^e$):
   • $T(p^e) = \frac{p^e - 2p^{e-1} - 1}{2} = \frac{S(p^e) - 1}{2}$가 성립합니다.
2. 일반적인 홀수 $n$:
   • $n$이 $\omega$개의 서로 다른 소인수를 가질 때, $T(n)$은 $S(n)$과 매우 가깝습니다.
   • 정리 3: $|T(n) - \frac{S(n)-1}{2}| \le \frac{3^\omega - 2^{\omega+1} + 1}{2}$로 오차 범위가 제한됩니다.
3. 짝수 $n$ ($n=2^e m$):
   • $e \ge 2$인 경우: $T(2^e m) = 2^{e-2} S(m)$.
   • $e = 1$인 경우 ($n=2m$): $T(2m)$은 $\frac{S(m)-1}{2}$와 매우 가깝습니다. 소수 $p \equiv 1 \pmod 4$ 또는 $p \equiv 3 \pmod 4$에 따라 정확히 $\frac{S(m) \pm 1}{2}$가 됩니다.
   • $e = 0$인 경우 ($n=m$, 홀수): 위와 유사한 오차 범위를 가집니다.

B. 암호학적 적용 및 정리

• 정리 1 (핵심 정리): 유한군 $G$의 크기가 $n$ (짝수) 일 때, 주어진 $g, x, e$에 대해 $(gy)^{f-1} = (gx)^{e-1}$을 만족하는 서로 다른 쌍 $(y, f)$의 개수는 적어도 $T(n)$입니다.
  • 특히 $p=2q+1$이 안전 소수 (Safe Prime) 인 경우, 해의 개수는 $q \equiv 1 \pmod 4$일 때 $\frac{p-3}{4}$ 이상, $q \equiv 3 \pmod 4$일 때 $\frac{p-7}{4}$ 이상입니다.
• 보안성 함의: 이 결과는 공격자가 $O(n^2)$개의 후보를 검사해야 하지만, 그중 $T(n)$개의 후보가 모두 '잠재적 해'로 보일 수 있음을 의미합니다. 올바른 키는 이 중 하나일 뿐이므로, $T(n)$이 클수록 올바른 키를 찾는 것이 훨씬 어려워집니다 (Haystack metaphor: 많은 바늘 중에서 진짜 바늘 찾기).

C. 추가적 통찰

• Proposition 15: $G=U_p$ ($p=2q+1$) 인 경우, 방정식 $w^{f-1}=c$의 해는 정확히 $p-5$개 존재함을 보였습니다.
• 일반화 가능성: $(m-1)/r$이 단위수 (unit) 인 경우를 세는 함수 $T_r(n)$의 연구가 향후 암호학적으로 유익할 수 있음을 제안했습니다.

4. 의의 및 결론 (Significance)

1. 새로운 수학적 함수의 정립: 오일러 함수와 스케멜 함수를 일반화하고 변형한 새로운 함수 $T(n)$을 정의하고, 그 산술적 성질을 체계적으로 규명했습니다. 이는 순수 수론 (Number Theory) 에 새로운 기여를 합니다.
2. 암호 시스템 설계의 이론적 기반: '변형된 군 (Group Variants)'을 이용한 암호 시스템에서 발생할 수 있는 거짓 긍정 해의 수를 정량화했습니다. 이는 시스템 설계 시 $n$을 선택할 때 $T(n)$이 충분히 큰 값을 가지도록 하여, 브루트 포스 공격에 대한 저항성을 수학적으로 보장할 수 있음을 보여줍니다.
3. 실용적 보안성 증대: 기존 이산 로그 문제의 복잡도 $O(n)$에서 변형된 군을 사용하면 $O(n^2)$의 검색 공간을 가지게 되며, 여기에 $T(n)$개의 가짜 해가 존재함으로써 실제 공격 난이도를 기하급수적으로 높일 수 있음을 입증했습니다.
4. 미래 연구 방향 제시: $T_r(n)$과 같은 일반화된 함수 연구와, 유클리드 알고리즘을 통해 구한 정수 $a, b$의 홀짝성 예측 문제 등 흥미로운 수론적 문제들을 제시하여 후속 연구를 유도합니다.

요약하자면, 이 논문은 암호학의 난이도 문제를 해결하기 위해 새로운 오일러 함수 $T(n)$을 도입하고, 이 함수를 통해 변형된 군 기반 암호 시스템의 보안 강도를 수학적으로 분석 및 증명했다는 점에서 이론적, 실용적 가치를 모두 지닙니다.