Public Key Encryption from High-Corruption Constraint Satisfaction Problems

1. 문제 정의 및 배경 (Problem & Background)

• 배경: 공개키 암호 (PKE) 는 주로 수론적 문제 (RSA, DH) 나 격자/부호 이론 문제에 기반합니다. 그러나 양자 컴퓨터의 등장으로 수론적 문제가 무너질 수 있으며, 격자/부호 이론 문제도 수학적으로 붕괴될 위험이 있습니다. 따라서 **기존과 다른 새로운 난제 (Hardness Assumption)**를 기반으로 PKE 를 구축하는 연구가 필요합니다.
• 기존 접근법의 한계: 이전의 고오염 CSP 기반 PKE 제안들 (예: ABW10, YZ16) 은 보안 수준이 **준다항식 (Quasi-polynomial, $\lambda^{O(\log \lambda)}$)**에 그쳤습니다. 이는 암호문을 해독할 때 숨겨진 구성 요소를 브루트포스 (Brute-force) 방식으로 탐색해야 하기 때문입니다.
• 목표: 고오염 CSP 를 활용하면서도 준지수 (Quasi-exponential, $\exp\{2^{\log^{\Omega(1)} \lambda}\}$) 수준의 보안을 달성하는 PKE 를 설계하는 것입니다.

2. 핵심 가정 (Key Hardness Conjectures)

이 논문은 두 가지 새로운 CSP 난제에 대한 가정을 기반으로 합니다. 두 문제 모두 오염 비율이 $1-o(1)$ (즉, 거의 모든 제약 조건이 무작위로 바뀜) 인 환경에서 정의됩니다.

1. 고오염 LARP-CSP (Large Alphabet Random Predicate CSP):

   • 정의: 임의의 강하게 확장성 (Strongly Expanding) 을 가진 팩터 그래프 (Factor Graph) 위에서 정의되며, 대문자 (Large Alphabet) 와 무작위 예측자 (Random Predicate) 를 사용합니다.
   • 특징: 제약 조건의 vast majority(대부분) 가 무작위 출력으로 대체됩니다. Goldreich 의 의사난수 생성기 (PRG) 와 planted hypergraph 문제와 관련이 깊습니다.
   • 가정: 무작위 예측자의 거대한 엔트로피 때문에, $1-o(1)$ 오염 비율에서도 planted solution(숨겨진 해) 을 찾는 것이 계산적으로 불가능하다는 가정입니다.

2. 고오염 Random kXOR:

   • 정의: 무작위 팩터 그래프 위에서 정의된 표준 kXOR 문제입니다.
   • 차이점: 기존 암호학에서 사용되던 kXOR 은 오염 비율이 역다항식 (inverse polynomial) 이었던 반면, 여기서는 $1-o(1)$로 설정됩니다.

3. 방법론 및 기술적 기여 (Methodology & Contributions)

3.1. 새로운 트랩도어 (Trapdoor) 심기 기법

• Label Extended Factor Graph 활용: 저자들은 CSP 의 'Label Extended Factor Graph'를 사용하여 다른 CSP 에 트랩도어를 심는 새로운 기법을 고안했습니다. 이는 평균 사례 복잡도 (Average-case Complexity) 이론에서는 흔하지만, 암호학적 트랩도어 구축에 적용된 것은 처음입니다.
• 작동 원리:
  • 키 생성: LARP-CSP 문제를 사용하여 공개키 (무작위 행렬 $H$) 와 비밀키 (트랩도어 $\zeta$) 를 생성합니다. 이때 $H$는 원래의 확장 행렬 $G$의 일부 행을 삭제하고 무작위 행을 추가하여 생성되므로, 외부 관찰자에게는 완전히 무작위로 보입니다.
  • 암호화: kXOR 문제를 사용하여 암호문을 생성합니다. 비트 0 은 "식별 가능한" kXOR 인스턴스로, 비트 1 은 완전히 무작위한 벡터로 암호화됩니다.
  • 복호화: 비밀키 $\zeta$를 사용하여 암호문에서 원래의 코드 $G$에 해당하는 부분 벡터를 추출합니다. 추출된 벡터는 일부는 삭제 (Erasure), 일부는 오염 (Corruption) 되었지만, 특수한 디코딩 알고리즘을 통해 원래 비트를 복원할 수 있습니다.

3.2. 새로운 오류 정정 코드 (Error-Correcting Code) 구성

• 확장성 및 저밀도 생성 행렬 (Expanding, Low-Density Generator Matrix): $1-o(1)$ 비율의 오류 (오염 및 삭제) 를 효율적으로 정정할 수 있는 균일 (Uniform) 구성의 오류 정정 코드를 최초로 제시했습니다.
  • 기존 연구 (OST18) 는 그러한 코드의 존재성만 증명했을 뿐, 구체적인 구성 방법을 제시하지 못했습니다.
  • 이 논문은 Reed-Muller 코드의 부분 코드를 기반으로 하여, 확장을 보장하는 생성 행렬 $G$를 효율적으로 샘플링하는 알고리즘을 제공합니다.
  • Saptharishi, Shpilka, Volk 의 알고리즘을 변형하여, $1-o(1)$ 오류율에서도 효율적으로 디코딩 (또는 식별) 할 수 있는 알고리즘을 구현했습니다.

4. 주요 결과 (Results)

1. 준지수 보안 달성: 제안된 PKE 는 준지수 (Quasi-exponential) 보안 수준 ($\exp\{2^{\log^{\Omega(1)} \lambda}\}$) 을 달성합니다. 이는 기존 고오염 CSP 기반 schemes 의 준다항식 보안보다 훨씬 강력하며, 부분 지수 (Sub-exponential) 보안에 근접합니다.
2. 하한 (Lower Bound) 증명: LARP-CSP 가치에 대한 다양한 공격 기법들을 배제하는 하한을 증명했습니다.
   • Low Complexity Embedding Attacks: Oliveira, Santhanam, Tell (OST18) 이 Goldreich PRG 에 대해 사용한 공격 기법을 일반화하여, LARP-CSP 에서는 무작위 함수의 엔트로피 때문에 이러한 공격이 실패함을 증명했습니다.
   • Low Degree Polynomial Algorithms: 저차 다항식 알고리즘 (Sum-of-Squares 등) 이 문제를 해결할 수 없음을 보였습니다.
   • Polynomial Calculus Refutations: 다항식 계산 (Polynomial Calculus) 증명 시스템으로도 문제를 반증 (Refute) 할 수 없음을 보였습니다.
3. 보안성 증명: LARP-CSP 와 kXOR 두 가지 가정이 모두 성립한다면, 제안된 PKE 는 의미론적 보안 (Semantic Security) 을 가진다는 것을 증명했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 새로운 암호학적 기반: 수론이나 격자 문제 외에, 평균 사례 복잡도 (Average-case Complexity) 의 CSP를 기반으로 한 PKE 를 성공적으로 구축했습니다. 이는 암호학의 "Win-Win" 시나리오 (암호 시스템이 안전하거나, 수학적 난제가 해결됨) 를 확장합니다.
• 알고리즘 및 복잡도 이론에의 기여: 고오염 CSP 에 대한 새로운 하한 증명과 효율적인 오류 정정 코드 구성은 암호학을 넘어 알고리즘 이론과 부호 이론 분야에도 중요한 기여를 합니다.
• 미래 연구 방향:
  • LARP-CSP 에 대한 더 많은 하한 증명 필요.
  • Goldreich PRG 에 대한 공격을 포괄하는 통합 프레임워크 개발.
  • 다항식 확장 (Polynomial Stretch) regime 에서의 확장 코드 구성 가능성 탐구.

요약하자면, 이 논문은 매우 높은 오류율을 가진 CSP 문제를 이용해, 기존보다 훨씬 강력한 보안 수준을 가진 공개키 암호 체계를 최초로 구성했습니다. 이를 위해 새로운 트랩도어 심기 기법과 효율적인 오류 정정 코드를 개발했으며, 제안된 난제에 대한 강력한 계산적 하한을 증명하여 그 타당성을 뒷받침했습니다.