1. 서론 및 안전성 개념

공개키 암호(PKC)의 안전성은 단일 방향성(One-wayness)을 넘어, 암호문으로부터 평문에 대한 어떠한 정보도 유추할 수 없는 의미론적 안전성(Semantic Security)을 요구한다. 본 글에서는 부분군 소속 문제(Subgroup Membership Problem, SMP)의 계산적 난해성에 기반한 새로운 공개키 암호 체계를 제시한다. 이 체계는 표준 모델(Standard Model)에서 의미론적 안전성이 수학적으로 증명되며, 다중 부분군 구조를 활용해 효율적인 암호화 및 복호화 연산을 제공한다.

2. 수학적 배경 및 가정

소수 $P = 2N + 1$을 고려하자. 여기서 $N = r_0 r_1$이며 $r_0, r_1$은 서로 다른 소수이다. $\mathbb{Z}_P^*$의 부분군을 각각 $\mathbb{G}_N$, $\mathbb{G}_{r_0}$, $\mathbb{G}_{r_1}$라 정의하며, 이들의 위수는 $N$, $r_0$, $r_1$이다.

사실 1: $\mathbb{G}_N$의 임의의 원소 $Y$에 대해, $Y = Y_0 Y_1 \bmod P$를 만족하는 유일한 쌍 $(Y_0, Y_1) \in \mathbb{G}_{r_0} \times \mathbb{G}_{r_1}$이 존재한다.

이러한 구조를 바탕으로 두 가지 계산 문제를 정의한다.

• 투영 문제 (Projection Problem, PP): $\mathbb{G}_N$의 원소 $Y$가 주어졌을 때, 이를 만족하는 부분군 성분 $(Y_0, Y_1)$을 찾는 문제.
• 부분군 소속 문제 (Subgroup Membership Problem, SMP): 주어진 원소가 특정 부분군 $\mathbb{G}_{r_0} \times \mathbb{G}_{r_1}$에 속하는지 판별하는 문제.

두 문제 간의 다항 시간 귀환(Reduction) 관계에 의해 $SMP \le_P PP$가 성립하며, PP는 정수 인수분해 문제(IFP)와 이산 로그 문제(DLP)로 귀환될 수 있음이 알려져 있다.

3. 암호 시스템 구성

3.1 키 생성

보안 매개변수 $k$에 대해 각 사용자는 다음 절차를 통해 키 쌍을 생성한다.

1. $P = 2r_0 r_1 + 1$ 형태의 소수를 선택한다.
2. $\mathbb{G}_{r_i}$의 생성자 $u_i$를 무작위 선택한다.
3. 비공개 지수 $\gamma_i = r_{1-i}(r_{1-i}^{-1} \bmod r_i)$를 계산한다.
4. 공개키 $PK = \{P, u_0, u_1\}$와 비공개키 $SK = \{\gamma_0, \gamma_1\}$를 설정한다.

3.2 암호화

메시지 $M \in \mathbb{G}_N$을 암호화하기 위해 다음 연산을 수행한다.

1. 난수 $x_0, x_1 \in \mathbb{Z}_N$을 선택한다.
2. 부분군 원소 $v_i = u_i^{x_i} \bmod P$를 계산한다.
3. 암호문 $W = (w_0, w_1)$를 구성한다. 단, $w_i = M \cdot v_{1-i} \bmod P$ 이다.

3.3 복호화

암호문 $W = (w_0, w_1)$를 수신하면 비공개키 $SK$를 사용해 다음 절차로 평문을 복원한다.

1. 투영 연산 $m_i = w_i^{\gamma_i} \bmod P$를 수행한다.
2. 최종 메시지 $M = m_0 m_1 \bmod P$를 도출한다.

이 체계는 Paillier 암호와 유사하게, 암호문의 형태를 변경하면서도 동일한 평문을 유지하는 준동형(Homomorphic) 특성을 일부 제공한다.

graph TD;
    KeyGen[키 생성] --> Params[모수 설정: P, r0, r1];
    Params --> Gen[생성자 u0, u1 및 지수 γ0, γ1 도출];
    Gen --> Pub[공개키 PK = {P, u0, u1}];
    Gen --> Priv[비공개키 SK = {γ0, γ1}];
    Enc[암호화] --> Rand[난수 x0, x1 선택];
    Rand --> CalcV[v0 = u0^x0, v1 = u1^x1 연산];
    CalcV --> CalcW[w0 = M*v1, w1 = M*v0 연산];
    CalcW --> Ctx[암호문 W = {w0, w1}];
    Dec[복호화] --> Proj[m0 = w0^γ0, m1 = w1^γ1 투영];
    Proj --> Rec[M = m0 * m1 복원];
    Pub --> Enc;
    Ctx --> Dec;
    Priv --> Dec;

4. 안전성 증명

단방향성: 투영 문제(PP)가 난해하다는 가정 하에, 암호문 $(w_0, w_1)$로부터 원본 메시지 $M$을 추출하는 것은 다항 시간 내에 불가능하다. 만약 암호문을 해독할 수 있다면, 이를 이용해 임의 원소의 부분군 성분을 효율적으로 찾아낼 수 있기 때문이다.

의미론적 안전성: 부분군 소속 문제(SMP)가 난해하다는 가정 하에, 공격자는 암호문을 관찰하더라도 평문에 대한 어떠한 정보도 얻지 못한다. 이는 암호문이 특정 부분군에 속하는지 판별하는 것조차 계산적으로 불가능함을 의미한다.

5. 영지식 증명 기반 신원 확인 프로토콜

제시된 암호 체계의 비공개키 $SK$ 소유권을 증명하기 위해 3-라운드 영지식 증명(Zero-Knowledge Proof) 프로토콜을 설계한다. 이 프로토콜은 증명자(Prover)와 검증자(Verifier) 간에 진행되며, 피셔-지랄(Fiat-Shamir) 휴리스틱을 통해 디지털 서명 방식으로 변환 가능하다.

1. 증명자: 난수 $\rho \in \mathbb{Z}_N$을 선택하고 $\rho_i = \rho \bmod r_i$를 계산한 뒤, $y_i = u_i^{\rho_i} \bmod P$를 검증자에게 전송한다.
2. 검증자: 무작위 도전값 $c_i \in \{0, \dots, 2^t - 1\}$를 선택하여 증명자에게 전송한다.
3. 증명자: 응답값 $\zeta = \rho_0 c_0 \gamma_0 + \rho_1 c_1 \gamma_1 \bmod N$을 계산하여 전송한다.
4. 검증자: 모든 $i \in \{0, 1\}$에 대해 $y_i = u_i^{\zeta c_i^{-1}} \bmod P$ 등식이 성립하는지 확인한다.

graph TD;
    P[증명자 Prover] --> Rnd[난수 ρ 선택 및 ρ0, ρ1 계산];
    Rnd --> Commit[y0 = u0^ρ0, y1 = u1^ρ1 전송];
    Commit --> V[검증자 Verifier];
    V --> Chal[도전값 c0, c1 생성 및 전송];
    Chal --> P;
    P --> Resp[응답값 ζ = ρ0*c0*γ0 + ρ1*c1*γ1 mod N 전송];
    Resp --> V;
    V --> Verify[y0 = u0^(ζ*c0^-1), y1 = u1^(ζ*c1^-1) 검증];