○ 정보보호대학원 소속 이창민 교수팀 논문이 2026년 5월 18일-21일에 미국 샌프란시스코에서 개최되는 IEEE S&P 2026 발표 논문으로 선정됨. 이번에 선정된 논문은 현재 이창민 교수팀에서 박사과정으로 재학중인 홍가희, 이정환 학생과 함께 수행되었음
- 논문제목: From Perfect to Approximate Hints: Efficient LWE Secret Recovery Leveraging Low Hamming Weight
- 저자 정보: 홍가희(제1저자), 한민기, 김지승, 이정환, 이창민(교신저자)
- 학회 홈페이지: https://sp2026.ieee-security.org/index.html
○ IEEE Symposium on Security and Privacy(S&P)는 정보 보안 분야 세계 최고 권위의 국제학술대회로, IEEE가 직접 이 분야의 대표 학회로 소개하고 있음. 국내에서도 BK21 기준 최우수 학회(인정 IF 최고 등급 4)로 분류되는 권위 있는 학술대회임
○ S&P 2026 Cycle 2에는 총 1070 편의 논문이 제출되었으며, 이 중 135편만이 채택되어 약 13%의 채택률울 기록하였음. 본 논문은 이러한 치열한 경쟁을 뚫고 발표 논문으로 선정되었다는 점에서 큰 의의가 있음
○ 본 논문은 격자 기반 암호의 핵심 난제인 Learning With Errors (LWE)에서, 성능 향상을 위해 사용되는 sparse secret vector가 부채널 정보 유출에 얼마나 취약해질 수 있는지를 분석함. 특히 secret vector에 대한 선형 정보인 perfect hint 및 approximate hint와 secret vector의 낮은 Hamming Weight를 적극 활용하여 기존 기법보다 훨씬 적은 수의 힌트만으로도 비밀키 복구가 가능한 신규 공격 기법을 제시함. 기존에는 대략 격자의 차원 n에 대하여 n/2개의 perfect/modular hint가 필요했던 것과 달리, 제안 기법은 secret vector의 Hamming Weight h에 대해 O(h log_2 h)개의 힌트만으로 공격이 가능함. 또한, 다양한 동형암호 파라미터에 대한 실험을 통해 제안 기법의 실효성을 검증했음. 예를 들어 (n, h) = (2^15 , 32)일 때 기존 방식의 2^14개 수준보다 훨씬 적은 320개의 힌트만으로 비밀키 복구가 가능함을 확인함
○ 논문 초록: The Learning With Errors (LWE) problem is a cornerstone of lattice-based cryptography and underpins the security of numerous cryptographic schemes. To enhance efficiency, practitioners often employ sparse secrets in LWE, where the secret vector s has a significantly lower Hamming weight than its dimension n. While this approach improves performance, it raises security concerns, particularly against side-channel attacks that can leak partial information—or “hints”—about the secret key. In this paper, we revisit the LWE with side information framework on sparse ternary secrets, focusing on approximate/perfect hints of the form (v, l) satisfying l = ⟨v, s⟩ + e, where e is a small error term, or l = ⟨v, s⟩. While previous results needed about n/2 perfect or modular hints to break LWE in polynomial time, we show empirically, supported by a conservative lower-bound analysis under the Gaussian Approximation Assumption (GAA), that the task can be accomplished with only O(h log_2 h) hints, where h denotes the Hamming weight of s. We demonstrate the effectiveness of our algorithm on practical parameter sets used in Fully Homomorphic Encryption (FHE) schemes. For instance, for a sparse secret FHE bootstrapping regime with (n, h) = (2^15 , 32), our method requires only 320 approximate/perfect hints to recover the secret key, compared to the 2^14 perfect/modular hints required by previous methods. For the OpenFHE library with (n, h) = (2^15 , 192), we heuristically confirm secret-key recovery via O(h log_2 h) perfect hints; approximate hints have not yet been validated in this setting. After collecting the necessary hints, our algorithm recovers the secret key in polynomial time in dimension n.
