with Jung Hee Cheon, Alain Passelègue, Damien Stehlé, and Elias Suvanto,
In this paper, we address the IND-CPAD insecurity of exact FHE schemes,
which was previously believed to apply only to approximate FHEs.
We identify vulnerabilities arising from non-negligible incorrectness, where the
probability of incorrect evaluation is not exponentially small.
Our attacks efficiently recover secret keys from BFV/BGV, DM/CGGI, and the exact variant of
CKKS, exposing vulnerabilities in current parameter choices.
This paper received the Grand prize at the Korean National Cryptography Contest
in 2024.
이 논문은 Exact FHE 스킴들의 IND-CPAD 안전성에 대해 다루며, 기존에는 Approximate FHE
스킴에만 적용된다고 여겨졌던 IND-CPAD 공격을 Exact FHE 스킴에도 적용한 연구입니다.
우리는 스킴의 정확성, 특히 non-negligible한 부정확성이 안전성을 심각하게 위협한다는 점을 발견하였으며,
실제로 BFV/BGV, DM/CGGI, Exact CKKS 스킴에서 작은 파라미터들을 바탕으로, 비밀 키를 효율적으로 복구하는 공격을 구현하였습니다.
이러한 취약점은 실제 쓰이는 파라미터로도 자연스럽게 확장되며, 지수적으로 작은 부정확도를 보장하는 파라미터를 사용함으로써 해결될 수 있습니다.
이 논문은 2024년 한국국가암호공모전에서 대상을 수상하였습니다.