1. 구어적 정의
어떤 암호화 방법이 완전비밀성(Perfect Secrecy)을 가진다는 것은 그 암호화 방법으로 암호화한 암호문에서 평문의 힌트를 전혀 찾을 수 없는 경우를 말한다. 이는 공격자의 계산능력과 무관하다. 따라서 무한한 계산능력을 가진 공격자를 상대로도 성립해야 한다. '힌트를 찾을 수 없다'는 말은, 그냥 찍어서 평문을 맞추는 경우와, 주어진 암호문으로 얻은 정보와 함께 평문을 맞추는 경우, 두 경우의 확률이 같은 경우를 말한다.완전비밀성을 가진 암호화를 완전 비밀 암호화 (Perfectly Secret Encryption, PSE)라고도 한다.
2. 수학적 정의
대문자 [math(M)], [math(C)], 그리고 [math(K)]는 랜덤변수이며, 각각 평문, 암호문, 그리고 암호에 사용할 키 값의 분포를 가진다.소문자 [math(m)], [math(c)], 그리고 [math(k)]는 각각 평문, 암호문, 그리고 키의 구체적인 값이다. [math(Pr(M=m))]은 사건 [math(\{ M = m \})]의 확률이다.
모든 [math(M)]과 [math(C)]의 분포와 [math(m)]과 [math(c)]에 대해 [math(Pr(M=m|C=c) = Pr(M=m))] 이 성립하는 경우 PSE이다.
위 정의에 조건부확률의 성질을 이용하여 다른 PSE의 정의를 얻을 수 있다.
예를 들어, [math(Pr(M=m|C=c) = Pr(M=m))]는 [math(Pr(C=c|M=m) = Pr(C=c))]와 동치이고, [math(\{ M=m \})]과 [math(\{ C=c \})]가 서로 독립임과도 동치이다.