근사 동형암호(HE)에서 반올림 오차는 잡음 수준과 달성 가능한 정밀도를 결정하는 핵심 요소다. 통상 계수 기저에서 좌표별로 반올림하지만, 정준 임베딩에서 격자 기반 반올림을 수행하는 대안도 있으며 이 둘은 2의 거듭제곱(PoT) 원분체에서는 일치하지만 비PoT 원분체에서는 달라질 수 있어 새로운 파라미터 절충의 여지를 연다. 이 논문은 임의 차수의 원분 격자에서 최근접벡터문제(CVP)의 반올림 오차를 연구해 새로운 최악·평균 경우 경계를 도출했고, 비PoT 원분체가 PoT 원분체보다 반올림이 개선됨을 보였다. 효율적인 반올림을 위해 정확한 최근접점 반올림의 근사로서 바바이의 최근접평면 알고리즘을 분석하면서도 폭넓은 원분 차수군에서 효율적인 환 연산을 유지했다. 개선된 경계와 PoT의 희소한 차수를 벗어난 유연성을 결합해, 동일한 출력 정밀도와 목표 보안 수준에서 PoT 대비 더 작은 격자 차원과 암호문 모듈러스를 갖는 파라미터를 실제로 도출했다.
- •정준 임베딩에서의 격자 기반 반올림이 계수별 반올림과 비PoT 원분체에서 달라짐을 발견
- •임의 차수 원분 격자의 CVP 반올림 오차에 대한 새로운 최악·평균 경계 도출
- •비PoT 원분체가 PoT보다 반올림이 개선됨을 입증
- •동일 정밀도·보안수준에서 PoT보다 작은 격자 차원과 암호문 모듈러스 파라미터 도출
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
The Closest-Vector Problem over Cyclotomics and its Application to Homomorphic Encryption
- 1.근사 준동형암호(HE)의 반올림 오차를 비power-of-two(PoT) 원분환으로 확장해 분석
- 2.Babai의 최근접 평면 알고리즘으로 격자 기반 반올림을 근사하는 새 오차 상하한을 도출
- 3.동일 정밀도·보안수준에서 비PoT 파라미터가 PoT보다 격자 차원과 암호문 모듈러스를 모두 줄일 수 있음을 실증
왜 중요한가?
CKKS 계열 근사 HE의 파라미터 선택 폭을 power-of-two 제약 밖으로 넓혀, 더 작고 빠른 준동형암호 구현의 이론적 근거를 제공한다.
본문 미리보기
Rounding error plays a key role in approximate homomorphic encryption (HE), as it determines the noise level and affects the achievable precision. While rounding is typically performed coordinate-wise in the coefficient basis, an alternative is to perform lattice-based rounding in the canonical embedding. These two approaches coincide for power-of-two (PoT) cyclotomics, but can differ for non-PoT cyclotomics. This difference opens the possibility of new parameter tradeoffs for approximate HE ove
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
