완벽한 비밀 정의

Question

내 질문에 우리는 완벽한 비밀이 균일 한 분포의 메시지로 달성된다는 것을 알고있다. 그러나 메시지 배포가 일정하지 않은 경우에는 어떻게됩니까? 그러면 우리는 어떻게 완벽한 기밀을 어떻게 정의 할 것입니까?

Answer 1

설득력있는 대답을 얻으려면 보안을 정의하는 몇 가지 가능한 방법을 논의하는 것이 가장 좋습니다. 정확한 정의는 분명하지 않고 역사적으로 많은 연구와 그것을 반복하기위한 반복이 필요했습니다.

"일회성 패드"가 매우 강하게 의미가 있다고 생각하는 대부분의 사람들은 동의합니다. 일회용 패드는 매우 오래된 기술이며, 2 차 세계 대전 전에 알려졌습니다.

아이디어는 다음과 같습니다. 당신은 스파이이며, 나는 당신의 spymaster 처리자입니다. 나는 비밀을 모으고 그들을 나에게 돌려 보내기 위해 너를 해외로 보내고 싶다. 우리가 의사 소통을 할 수 있도록 먼저 난수로 가득 찬 전체 책을 만듭니다. (일부 기계는 기계적으로 동전을 뒤집어서 0 또는 1을 인쇄합니다.) 사본이 있고 사본이 있으며 그 외의 사람은 없습니다.

k 바이트의 메시지를 보내려는 경우 책에서 k 바이트를 가져와 바이트로 XOR합니다. (그런 다음 북마크를 k 바이트 씩 앞당겨줍니다.) k 바이트를 받으면 북에서 다음 k 바이트로 XOR 한 다음 내 북마크를 진행합니다.

적군이 모든 메시지를 가로채는 경우에도 책에서 (임의의) 비트의 기능으로 보이는 방식을 고려하면 상대방이받는 메시지는 독립적 인 동전 뒤집기로 배포됩니다. 실제로 보낸 고정 메시지의 경우 book이 임의 인 경우 message xor book은 완전히 무작위입니다.

따라서이 구성표는 완벽하게 안전합니다. 암호문은 통계적으로 일반 텍스트와 독립적이므로 공격자는 메시지에 대해 아무 것도 알 수 없습니다.

이 문제는 공개적으로 교환 할 때 수작업으로 많은 바이트를 개인적으로 교환해야한다는 것입니다. 예를 들면. 신용 카드 판매 온라인으로, 당신은 열쇠 물자의 개인 교환이 미리다는 것을 추측 할 수 없다. 따라서 필요한 핵심 자료의 양을 줄일 수 있어야합니다.

한편, k 바이트 메시지의 경우 키 재료를 k 바이트 미만으로 줄이면이 ​​보안 수준을 달성 할 수 없습니다. 암호 텍스트 배포는 서로 다른 메시지에 대해 달라야합니다. 심지어 바이트 수가 적어지면서 메시지 사이에 큰 통계적 거리가 있음을 보여줄 수도 있습니다.

현대의 암호화에서 정의를 완화하는 일반적인 방법은주의를 제한적으로 으로 제한하려고 시도하는 것입니다.. 두 분포 D1 및 D2 통계적 거리를 공식화

한가지 방법은, 거리가 모든 테스트 기능 기대 E_{x ~ D_2} [ T(x) ] 대 E_{x ~ D_1} [ T(x) ]의 차이 T : { strings } -> { 0, 1 } 위에 최대 것을 말하는 것이다.

다음, 우리는 다항식 시간 또는 subexponential 시간, 뭔가, 말,효율적으로 계산할 수있는 테스트 기능 T에만 초점을 맞춤으로써 정의를 수정할 수 있습니다. (일반적으로 뭔가가 "보안 매개 변수"입니다.D1 및 D2의 통계적 거리가 계산 경계 원수에 대한 작은 경우)

, 우리는 때때로 D1 및 D2이 구별이다,라고.

임의의 고정 메시지 m에 대해 임의 시드/키의 확률에 대해 암호문의 분포가 균일 분포와 구별 될 수없는 경우 암호화 프로토콜이 안전하다고 말할 수 있습니다.

합리적 인 암호화 가정 하에서, 이것은 메시지보다 훨씬 짧은 키에 대해서조차도 달성 될 수 있다고 널리 알려져있다. 그러나 이것은 P! = NP 및 많은 다른 어려운 일들을 증명하지 않고서도 사실임을 입증 할 수 없습니다. 예를 들어 발전기가 아직 알려지지 않은 적보다 계산 비용이 더 높은 경우에도 의사 랜덤 생성기의보다 엄격한 구조가 필요할 것입니다.

이 형식주의에서 메시지 배포가 무엇인지는 중요하지 않습니다. 메시지를 가져 와서 압축 한 다음 암호화하거나 일반 영어 텍스트를 암호화하는 경우 목표는 고정 메시지 문자열 인 경우 시드/키의 임의성이 우연한 배포판을 생성하기에 충분합니다. 너의 적이다.

보안을 공식화 할 수있는 다른 방법이 있지만 이것이 좋은 방법이라고 생각합니다.

---

요점 : 보안 상태가 어떤 고정 메시지를 보유

경우, 그것은 또한 평균 인수로, 메시지의 고정 유통을 위해 보유하고 있습니다. 따라서이 정의는 매우 강력합니다.