기술 요약: PIVOT – 이소제니 군 작용으로부터의 프로액티브하고 검증 가능한 임계값 무관 난수 생성 함수 (Proactive and Verifiable Threshold Oblivious Pseudorandom Functions from Isogeny Group Actions)

1. 문제 정의

무관 의사 난수 생성 함수(OPRF)는 클라이언트가 서버에 자신의 입력을 드러내지 않고 키가 적용된 함수를 평가할 수 있게 한다. **임계값 OPRF(threshold OPRF)**에서는 비밀키가 $n$개의 서버에 분산되어 있으며, 평가를 위해 최소 $t$개의 서버가 협력해야 한다. 표준적인 임계값 스킴은 정적 부패(static corruption, 고정된 서버 집합이 침해되는 경우)로부터는 보호하지만, 모바일 적대자(mobile adversary) 모델에는 대응하지 못한다. 모바일 위협 모델에서 공격자는 시간에 따라 서로 다른 서버들을 침해하여 여러 에포크(epoch)에 걸친 쉐어(share)를 축적할 수 있다. 만약 쉐어가 정적으로 유지된다면, 공격자는 비록 동시에 $t$개의 서버를 제어하지 않더라도, 결국 동일한 공유 상태로부터 $t$개의 쉐어를 수집하여 마스터 키를 재구성할 수 있다.

기존의 이소제니 기반 임계값 OPRF는 주로 정적 부패 모델을 위해 설계되었다. 또한, 고전적 군(classical groups)에서의 기존 프로액티브 비밀 공유 메커니즘은 다항식 커밋먼트(스칼라 필드 내)와 이소제니 군 작용(타원 곡선 상)을 연결해야 하는 필요성 때문에 이소제니 설정으로 쉽게 전이되지 않는다. 따라서 다음을 동시에 제공하는 구성은 부재한 실정이다:

1. 양자 내성 보안 (이소제니 기반).
2. 검증 가능성 (서버가 올바른 키 하에 동작하는지 보장).
3. 프로액티브 보안 (모바일 적대자를 저지하기 위해 주기적으로 쉐어를 갱신).
4. 딜러리스 키 생성 (신뢰할 수 있는 설정/trusted setup 없음).
5. 커미티 마이그레이션 (애플리케이션 데이터를 재암호화하지 않고 서버 집합이나 임계값을 변경).

2. 방법론 및 구성

본 논문은 유효한 이소제니 군 작용(예: CSIDH)을 기반으로 구축된 PIVOT(Proactive Isogeny-based Verifiable Oblivious Threshold PRF) 프레임워크를 소개한다. 핵심 대수 구조는 이소제니 작용의 가환성(commutative property)인 $[a]([b]E) = [a+b]E$에 기초한다.

핵심 아키텍처

PIVOT은 단일 장기 마스터 키 $k$와 공개 키 $pk = [k]E_0$를 유지한다. 그러나 $k$의 표현 방식은 시간에 따라 변한다. 시스템은 에포크(epoch) 단위로 작동한다. 에포크 $e$에서 서버들은 $F_e(0) = k$를 만족하는 샤미르 다항식 $F_e(X)$의 쉐어 $s^{(e)}_i = F_e(i)$를 보유한다. 공개 계수 커밋먼트 벡터 $A^{(e)}$는 다항식 $F_e$를 인증한다.

프로토콜은 다섯 가지 주요 절차로 구성된다:

1. 딜러리스 분산 키 생성 (DKG):

   • 모든 서버는 검증 가능한 비밀 공유(VSS) 딜러로서 동작하며, 무작위 다항식을 샘플링하고 쉐어를 배포한다.
   • 자격을 갖춘 기여분들이 결합되어 초기 마스터 다항식 $F_0(X) = \sum f_j(X)$를 형성한다.
   • 링크 증명(Link Proofs): 핵심적인 혁신은 커밋된 다항식의 상수항(스칼라 쉐어)을 공개 키 $pk$를 생성하는 순차적 이소제니 작용 체인에서 사용된 지수와 연결하는 비대화형 영지식(NIZK) 증명을 사용하는 것이다. 이는 $k$를 재구성하지 않고도 공개 키가 공유된 비밀과 대응됨을 보장한다.

2. 임계값 평가 (Threshold Evaluation):

   • 클라이언트는 자신의 입력 $x$를 곡선 $X = H_1(ctx \| x)$로 매핑하고 무작위 작용 $[r]$을 적용하여 $B = [r]X$를 보냄으로써 블라인딩(blinding)한다.
   • $t$개의 쿼럼(quorum)은 라그랑주 가중치가 적용된 쉐어를 순차적으로 적용한다: $Q_h = [\lambda^I_{i_h} s^{(e)}_{i_h}] Q_{h-1}$.
   • 작용의 가법적 성질 덕분에, 최종 곡선은 $Q_t = [k]B$가 된다.
   • 클라이언트는 언블라인딩(unblinding)을 통해 $Y = [k]X$를 얻고 출력을 유도한다.
   • 검증: 각 서버는 자신이 수행한 작용이 현재 에포크의 공개 벡터 $A^{(e)}$에 커밋된 쉐어에 대응함을 인증하는 NIZK 증명($\pi_{eval}$)을 제공한다.

3. 프로액티브 쉐어 갱신 (Proactive Share Refresh):

   • 모바일 적대자에 대응하기 위해, 서버들은 $k$를 변경하지 않고 주기적으로 쉐어를 갱신한다.
   • 자격을 갖춘 "갱신 딜러(refresh dealers)"들은 $z_j(0)=0$을 만족하는 제로 쉐어링 다항식 $z_j(X)$를 샘플링한다.
   • 새로운 다항식은 $F_{e+1}(X) = F_e(X) + \sum z_j(X)$이다. 상수항의 합이 0이므로, $F_{e+1}(0) = k$가 유지된다.
   • 계수 커밋먼트는 동형적으로 업데이트된다. 전환 후 기존 쉐어는 안전하게 삭제된다.

4. 검증, 비난(Blame), 및 견고한 재시작:

   • 서버가 잘못된 증명이나 쉐어를 제출하면, 탐지된 당사자는 비난 인증서(실패에 대한 서명된 트랜스크립트)를 생성한다.
   • 비난받은 서버는 제거되며, 프로토콜은 새로운 쿼럼과 함께 재시작된다. 이는 식별 가능한 중단(identifiable aborts)을 보장한다.

5. 커미티 재공유 (Committee Resharing):

   • 새로운 서버 집합이나 새로운 임계값 $t'$로의 이주를 허용한다.
   • 기존 쿼럼은 자신들의 라그랑주 가중치 쉐어를 새로운 커미티에 배포될 새로운 다항식의 상수항으로 취급한다.
   • 결정적으로, 이는 $k$를 재구성하지 않고도 비밀을 전달하며, 기존의 공개 키와 이전에 생성된 모든 OPRF 출력을 보존한다.

해결된 기술적 과제

• 교차 도메인 위트 일관성 (Cross-Domain Witness Consistency): 본 논문은 필드 내에서 커밋된 스칼라와 이소제니 작용에 사용된 동일한 스칼라를 바인딩하는 결합된 NP 관계(예: $R_{link}, R_{eval}$)의 필요성을 정형화한다. 이들을 별도로 증명하는 것은 불충분하며, 위트(witness)는 두 도메인 간에 동일해야 한다.
• 에포크 일관성: 프로토콜은 쉐어의 혼합을 방지하기 위해 평가 체인이 반드시 단일 에포크 인증서를 사용하도록 강제한다.

3. 주요 기여

1. 정형화된 기능성: 저자들은 여러 에포크에 걸쳐 부패된 서버 집합이 변할 수 있는 모바일 적대자를 명시적으로 모델링하여, 장기 지속형 프로액티브 임계값 VOPRF를 위한 이상적 기능 $\mathcal{F}_{pTVOPRF}$를 정의한다.
2. 딜러리스 구성: 이소제니 군 작용과 샤미르 비밀 공유 및 가법 동형 커밋먼트를 결합하여, 마스터 키가 단일 참여자에 의해 재구성되지 않는 구성을 제시한다.
3. 프로액티브 유지보수: 마스터 키, 공개 키 및 모든 역사적 OPRF 출력을 보존하면서 모바일 적대자에 맞서 서버 쉐어를 갱신하는 메커니즘을 제공한다. 여기에는 조정된 에포크 전환 프로토콜이 포함된다.
4. 결합된 NP 관계: 비밀 공유 도메인(다항식 계수)과 이소제니 작용 도메인(곡선 변환)을 연결하는 데 필요한 특정 NIZK 관계를 식별하고 정형화한다.
5. 커미티 재공유: 기존의 암호화된 데이터베이스를 무효화하지 않고 새로운 커미티로 비밀을 이주하거나 임계값을 변경할 수 있게 한다.
6. 보안 분석: 벡터화(vectorization) 및 one-more hidden-group-action 가정을 바탕으로, 랜덤 오라클 모델에서 입력 프라이버시와 키 비밀성을 보장하는 시뮬레이션 기반 보안 증명을 제공한다.

4. 결과 및 성능

• 정확성: 본 논문은 DKG, 평가, 갱신 및 재공유 작업 전반에 걸쳐 마스터 키 $k$와 공개 키 $pk$가 일정하게 유지된다는 불변성을 증명한다.
• 보안성: 구성은 단일 에포크 내에서 $t$ 미만의 서버를 부패시키는 모바일 세미-혼리스트(semi-honest) 적대자에 대해 안전함이 증명된다. 보안은 쉐어의 안전한 삭제와 샤미르 공유의 정보 이론적 프라이버시에 의존한다.
• 효율성 트레이드오프:
  • 트랜스크립트 크기: 상수 크기의 클라이언트 트랜스크립트를 제공하는 MPC 기반 가상 서버 접근 방식과 달리, PIVOT은 $t$개의 부분 평가와 증명의 순차적 체인을 노출하므로 $O(t)$의 클라이언트 트랜스크립트를 가진다.
  • 지연 시간 (Latency): 평가는 $t$개의 순차적인 군 작용과 증명을 요구하며, 이는 임계값에 비례하는 선형적인 지연 시간 병목을 생성한다.
  • 유지보수: 프로액티브 갱신과 커미티 재공유는 점대점 쉐어 배포로 인해 $O(n^2)$의 통신을 수반하지만, 이소제니 작용을 필요로 하지 않으므로 장기간에 걸쳐 분할 처리(amortization)하기에 적합하다.
  • 응용 분야: 본 논문은 온라인 비용이 더 높음에도 불구하고, (프라이빗 룩업 서비스와 같이) 대규모 데이터베이스를 재암호화하지 않고도 쉐어를 갱신하고 커미티를 이주할 수 있는 능력이 장기 지속형 서비스를 위한 상당한 운영 효율성을 제공한다고 강조한다.

5. 의의 및 주장

본 논문은 프로액티브 보안을 제공하는 이소제니 군 작용 기반의 최초 임계값 VOPRF를 제시한다고 주장한다.

저자들은 PIVOT을 기존의 단일 서버 또는 MPC 기반 OPRF에 대한 성능 최적화 도구가 아니라, 기능적으로 완전한 프레임워크로 포지셔닝한다. 그 의의는 가상 서버 뒤에 임계값 구조를 숨기는 대신 이를 명시적으로 노출하는 아키텍처적 선택에 있다. 이러한 명시성은 다음을 가능하게 한다:

• 프로액티브 갱신(제로 쉐어링 다항식 추가)의 직접적인 적용.
• 개별 책임 추적(blame attribution).
• 기존의 암호화된 데이터를 무효화하지 않고의 원활한 커미티 마이그레이션.

결론적으로, 본 논문은 점진적인 침해가 존재하는 환경에서 수년간의 운영 수명이 필요한 서비스의 경우, $O(t)$ 트랜스크립트 비용은 기존의 암호화된 데이터나 종속된 데이터를 재암호화하지 않고도 시스템의 보안 상태를 주기적으로 갱신할 수 있는 능력에 대한 필수적인 트레이드오프라고 주장한다.