Deterministic Johnson--Lindenstrauss Projections from Pisot $\beta$-Transformations for Zero-Knowledge Private Routing

기술 요약: 제로 지식 프라이빗 라우팅을 위한 피소트(Pisot) $\beta$-변환 기반 결정론적 존슨-린덴스트라우스(Johnson–Lindenstrauss) 투영

1. 문제 정의

프라이빗 라우팅을 위한 제로 지식(Zero-Knowledge, ZK) 증명 시스템에서, 증명자(prover)는 메시지 임베딩 $v \in \mathbb{R}^d$가 공개된 센트로이드 집합 $C = \{c_1, \dots, c_N\}$으로 정의된 허용된 의미론적 클래스에 속함을 인증해야 한다. 이는 통상적으로 최근접 센트로이드 테스트를 통해 수행되며, 이 과정에는 $O(Nd)$의 산술 제약 조건이 필요하다. 현대의 임베딩 차원($d \in [768, 4096]$)을 고려할 때, 이러한 제약 조건의 수는 증명의 크기와 증명자의 연산 시간을 지배하는 핵심 요소가 된다.

표준적인 해결책은 차원을 $m \ll d$로 줄이는 존슨-린덴스트라우스(JL) 투영이다. 그러나 고전적인 JL 행렬은 무작위적이다. ZK 문맥에서 무작위 행렬을 사용하면 회로가 해당 행렬을 커밋(commit)하고 그 샘플링을 증명해야 하므로, 투영을 통해 제거하려 했던 바로 그 계산 비용이 다시 발생하게 된다. 또한, 무작위 행렬은 샘플링 과정을 증명해야 하며, 이는 정보 누출(leakage)의 위험을 초래한다. 따라서 본 연구의 과제는 다음을 만족하는 공개적이고, 결정론적이며, 고정된 투영 행렬을 구축하는 것이다:

1. 거리 보존성을 증명 가능하게 유지할 것.
2. 회로의 유한체(finite field)에 네이티브할 것.
3. 회로 내의 무작위성이나 샘플링 증명을 요구하지 않을 것.

2. 방법론

저자들은 피소트(Pisot) $\beta$-변환의 표준화된 궤도(orbit)로부터 투영 행렬 $A$를 구성하는 방법을 제안한다.

• 맵(Map): $\beta$-변환 $T_\beta x = \beta x - \lfloor \beta x \rfloor$는 단위 구간에서의 맵이며, 여기서 $\beta > 1$은 피소트 수(갈루아 공액이 단위 원 내부의 디스크에 위치하는 대수적 정수, 예: 황금비)이다.
• 역학(Dynamics): 이 맵은 결정론적인 "신축 및 접기(stretch-and-fold)" 카오스 시스템이며, 고유한 파리 측도(Parry measure) $\mu$를 갖는다. 결정적으로, $\beta$가 피소트 수이기 때문에, 이 맵의 전이 연산자(transfer operator)는 **스펙트럼 갭(spectral gap)**을 가지며, 이로 인해 관측량 간의 상관관계는 기하급수적으로 감소한다($|r_k| \le C\theta^k$).
• 행렬 구축:
  • 공개된 시드(seed) $x_0$를 선택한다.
  • 샘플링 간격 $g$를 고정하여 샘플이 상관 시간(correlation time) 너머에서 채취되도록 보장한다.
  • 행렬 엔트리 $A_{ij}$를 정규화된 궤도 값 $z_p = \psi(T_\beta^{pg} x_0)$로 순차적으로 채운다.
  • 투영은 $\Phi(v) = Av/\sqrt{m}$이다.
• 유한체 재현성: 일반적인 카오스 맵과 달리, 피소트 성질은 궤도가 유한체 내에서 정확하게 재현될 수 있음을 보장한다. $k$ 단계를 생성하는 비용은 $k$에 선형적($O(k \log_2 \beta)$ 비트)인 반면, 일반적인 카오스 맵(예: 로지스틱 맵)은 정확한 산술을 유지하기 위해 지수적인 비트 성장($O(2^k)$)이 필요하다.

3. 주요 기여

본 논문은 네 가지 주요 이론적 및 실무적 기여를 제시한다:

1. 차원 독립적 편향 및 분산 경계:

   • 편향(Bias): 저자들은 제곱 노름 추정기의 편향이 차원 $d$와 무관하게 샘플링 간격 $g$에 따라 기하급수적으로 감소하는 항에 의해 제한됨을 증명한다(Lemma 의 보조정리 1). 이는 $\beta$-맵의 스펙트럼 갭으로부터 유도되며, 표준적인 균등 분포 논의보다 더 강력한 보장을 제공한다.
   • 분산(Variance): 추정기의 분산이 $V_0/m$에 비례함을 보여준다. 결정적으로, 명시된 집중 가설(concentration hypothesis) 하에서 상수 $V_0$는 차원 독립적이다(즉, $d^2$에 따라 증가하지 않는다). 이는 조잡한 경계값이 $O(d^2)$를 시사하는 것과 대조적이다. 이는 $d$가 아무리 커지더라도 고정된 투영 차원 $m$이 충분함을 의미한다.

2. 단일 공개 시드의 존재성:

   • 정리 1은 모든 $\binom{N}{2}$ 쌍의 센트로이드 간 거리를 $(1 \pm \varepsilon)$ 내로 보존하는 단일 공개 시드 $x_0$가 존재함을 증명한다.
   • 이 시드는 효율적인 오프라인 탐색을 통해 찾을 수 있다. 일단 발견되면, 행렬은 고정되고 공개되며, ZK 증명 중에 무작위성 커밋을 요구하지 않는다.

3. 피소트 성질을 통한 정확한 재현성:

   • 본 논문은 ZK 배포를 위해 피소트 성질(단순히 일반적인 카오스 성질이 아님)이 필수적임을 식별했다. 이는 궤도가 고정된 유한체 내에서 선형적인 계산 비용($\log_2 \beta$ 비트)으로 정확하게 재현될 수 있음을 보장한다. 일반적인 카오스 맵은 부동 소수점 발산을 피하기 위해 필요한 정밀도(분모)가 지수적으로 증가하기 때문에 여기서 실패한다.

4. 강건성 및 탐색:

   • 쿼리가 센트로이드의 근접성을 변경하지 않고 견딜 수 있는 최대 섭동(perturbation) 범위를 정의하는 폐쇄형(closed-form) 인증 가능 강건성 반경이 제공된다(Proposition 1).
   • 시드 탐색은 무조건적(unconditional)이지만, 특정 스펙트럼 갭 맵에 대한 집중 부등식이 성립한다면 $N$에 대한 로그 의존성으로 개선될 수 있다.

4. 실험 결과

본 구조는 여섯 가지 표준 투영 방식(Gaussian, Rademacher, Achlioptas sparse, SRHT, 그리고 Yu 등의 카오스 시퀀스 행렬)과 비교 평가되었다.

• 통계적 품질: 피소트 투영은 무작위 투영의 통계적 품질과 일치한다.
  • 분산율: 추정기 분산은 $1/m$ 법칙을 따르며, Gaussian JL의 $2/m$ 참조값과 중첩된다.
  • 차원 독립성: $d$가 64에서 1024로 증가함에 따라 $V_0$가 2 근처에서 평탄하게 유지되는 것을 확인하였으며, 이는 차원 독립적 이론적 예측을 뒷받침한다.
  • 왜곡(Distortion): 모든 센트로이드 쌍에 대한 최악의 경우 상대적 왜곡은 Gaussian JL 베이스라인을 추종한다.
• 태스크 성능: $d=256$인 24-클래스 최근접 센트로이드 라우팅 태스크에서, 피소트 투영은 $m=32$에서(8배 압축) 다른 방법들과 동일하게 100% 정확도를 회복했다.
• 재현성: 시뮬레이션 결과, 부동 소수점 구현은 약 50-70단계 이후에 실제 궤도에서 벗어나는 것(Lyapunov 예측과 일치)을 확인했으나, 피소트 $\beta$-진법 표현은 200단계에서도 139비트만으로 정확하고 컴팩트하게 유지되었다(로지스틱 맵의 경우 $1.66 \times 10^6$ 비트 필요).

5. 의의 및 주장

본 논문은 이 구조가 ZK 프라이빗 라우팅을 위한 세 가지 핵심 요구사항을 동시에 만족하는 유일한 방법이라고 주장한다:

1. 회로 내 무작위성이 없음: 무작위 행렬의 샘플링을 커밋하거나 증명할 필요가 없다.
2. 고정된 유한체에서 정확하게 재현 가능: 피소트 성질을 통해 단계당 $\log_2 \beta$의 비용으로 달성하며, 일반적인 카오스 맵의 $O(2^k)$ 비용을 피한다.
3. 무작위 투영과 통계적으로 동등함: 표준 JL 행렬의 분산율 및 왜곡 특성을 일치시킨다.

저자들은 통계적 품질은 증명되었으나, 무조건적인 $O(N^2)$ 시드 탐색 경계를 조건부 $O(\log N)$ 경계로 업그레이드하는 이론적 단계는 전이 연산자에 대한 특정 집중 부등식에 의존하며, 이는 여전히 미해결 과제로 남아 있다고 언급한다. 실무적으로, 이 방법은 증명 생성 시간을 분/기가바이트 단위에서 초/메가바이트 단위로 전환하여, 고차원 임베딩에 대한 검증 가능한 프라이빗 라우팅을 가능하게 한다.