안전성 증명

암호학에서, 어떤 시스템이 다음과 같은 조건을 만족하면 증명가능한 안전성(provable security)을 가지고 있다면 한다.

• 공격자 모형을 이용하여 안전성의 조건을 명시하고
• 환원이라고 하는 방식으로 널리 알려진 암호학적 성질(예를 들어 RSA에 관련된 성질)이 안전하다는 가정하에 이와 같은 안전성의 조건이 만족되는 것을 증명했을 때

안전성 증명의 한계

이와 같은 방식으로 증명하는 것을 안전성 증명(安全性 證明)이라 부르지만, 엄밀한 의미에서 이것은 증명이 아니다. 증명과정이 기껏 '증명되지 않은' 가설로 환원하는 정도거나 혹은 랜덤 오라클 모델처럼 실제로는 존재하지 않는 가상의 이론적 모형을 사용하기 때문이다.

이론전산학의 관점에서 본다면, 안전성 증명에는 다음과 같은 두 가지 문제점이 있다.

• 대부분의 암호학적 성질이 P ≠ NP(계산 복잡도 이론의 기본적 가정)로 환원할 수 있는지도 제대로 알려지지 않았다.
• P ≠ NP 자체도 증명되지 않았다.

이런 이유로, 안전성 증명은 제대로 된 증명과 두 단계나 떨어져 있다고 할 수 있다.

오늘날 암호학이 이론적인 연구에서 그치는 것이 아니라 실제로 널리 사용되면서, 안전성 증명에 대한 관심이 더욱 늘어나고 있다. 무한에 가까운 큰 값을 사용하여 증명하는 점근적인 증명보다 작은 변수값에 대한 안전성 증명을 더욱 중요하게 여기고 있고, 그런 이유로 많은 사람들이 안전성 증명을 '정확한 안전성'(exact security)이나 '구체적 안전성'(concrete security)라는 이름으로 더욱 의미있는 것으로 생각하고 있다.

외부 링크

• Another Look at "Provable Security" - 닐 코블리츠와 Alfred Menezes가 안전성 증명에 대해 가볍게 분석한 논문