노이즈 플러딩은 근사 동형암호(FHE)의 복호화 공격 방어를 위한 표준 기법이지만, 그 안전성 증명은 여러 번의 적응형 질의를 합성할 때 손실이 커지는 문제가 있다. 통상적인 하이브리드 논증은 질의 횟수 q에 비례해 선형적으로 손실되지만, 조건부 KL(쿨백-라이블러) 비용을 누적한 뒤 한 번에 통계적 거리로 변환하면 제곱근 손실로 줄일 수 있다. 이 논문은 이 증명을 Rocq와 SSProve로 기계 검증했으며, 근사적으로 정확하고 IND-CPA 안전한 모든 FHE 스킴에 대해 q-질의 IND-CPAD 적대자를 위한 환원을 형식화하고 제곱근 경계를 증명했다. 조건부 KL 예산을 통계적 거리로 변환하지 않고 합성하는 새로운 관계형 프로그램 논리와 검증된 트레이스 컴파일러를 제시했다.
- •노이즈 플러딩 안전성 증명의 손실을 질의횟수 선형에서 제곱근으로 줄이는 KL 누적 기법 제시.
- •Rocq와 SSProve로 IND-CPAD 안전성 환원을 기계 검증.
- •조건부 KL 예산을 합성하는 새로운 관계형(피타고라스) 프로그램 논리 개발.
- •검증된 트레이스 컴파일러로 국소 오라클 규칙을 임의의 적응형 프로그램으로 확장.
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption
- 1.근사 동형암호의 복호화 공격 방어책인 노이즈 플러딩의 안전성 증명을 Rocq와 SSProve로 기계 검증
- 2.조건부 KL 비용을 누적한 뒤 한번에 통계적 거리로 변환, 파라미터 결정적 제곱근 손실 유도 증명
- 3.근사적으로 올바르고 IND-CPA 안전한 모든 FHE 스킴에 대해 q번 질의 IND-CPAD 적대자의 성공확률 상한을 공식화
- 4.SSProve 의미론 위에 새 관계형 로직(피타고라스 판단) 구성, 검증된 컴파일러로 지역 오라클 규칙 확장
왜 중요한가?
근사 동형암호의 핵심 방어기법인 노이즈 플러딩의 보안증명이 기존에는 표준 하이브리드 논증으로 질의 수에 선형 손실이 생겼던 것을, 기계검증된 새 증명기법으로 제곱근 손실까지 개선함으로써 실제 FHE 배포에서 더 타이트한 파라미터 선택을 가능케 한다.
본문 미리보기
arXiv:2608.13846v1 Announce Type: new Abstract: Noise flooding is a standard defense against decryption attacks on approximate homomorphic encryption, but its security proof is unusually sensitive to composition. Replacing each of $q$ adaptive decryption answers with a statistically close simulation and applying an ordinary hybrid argument loses linearly in $q$. The cryptographic proof instead accumulates conditional Kullback-Leibler (KL) costs and converts to statistical distance once, giving
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:23AI 초안
