의미 보안

암호학에서 의미론적으로 안전한 암호 체계는 일반 텍스트에 대해 무시할 수 있는 정보만 암호 텍스트에서 타당하게 추출할 수 있는 것이다.구체적으로,$$ 특정 메시지 $m{\displaystyle }$ ${\displaystyle m}$의 암호문이 주어진 확률론적 다항식 시간 알고리즘(PPPTA)과 메시지 길이는 모두 Acceleration만 있는 다른 모든 PPTA보다 눈에 띄게 높은 확률로 메시지에 대한 부분 정보를 결정할 수 없다.ss를 메시지 길이(암호 텍스트가 아님)에 맞추십시오.^[1]이 개념은 섀넌의 완벽한 비밀 유지 개념과 유사하게 계산상의 복잡성이다.완벽한 비밀유지란 암호문이 일반 텍스트에 대한 정보를 전혀 공개하지 않는다는 것을 의미하며, 의미적 보안은 밝혀진 어떤 정보도 타당하게 추출할 수 없다는 것을 암시한다.^{[2][3]: 378–381}

역사

의미적 보안의 개념은 1982년 골드워서와 미칼리에 의해 처음 제시되었다.^[1]그러나 그들이 처음에 제안한 정의는 실제 암호 시스템의 보안을 증명할 수 있는 간단한 수단을 제공하지 않았다.골드워서/마이칼리는 이후 의미적 보안이 선택된-플레인텍스트 공격 하에서 암호문서의 식별 불가능성이라고 불리는 보안의 또 다른 정의와 동일하다는 것을 입증했다.^[4]이 후자의 정의는 의미 보안의 원래 정의보다 더 일반적이다. 왜냐하면 그것은 실제 암호 시스템의 보안을 더 잘 증명하기 때문이다.

대칭키암호법

대칭 키 알고리즘 암호 시스템의 경우, 적수는 암호문으로부터 일반 텍스트에 대한 정보를 계산할 수 없어야 한다.이는 길이가 같은 두 개의 일반 텍스트와 각각의 두 개의 암호 텍스트가 어떤 일반 텍스트에 속하는지 결정할 수 없는 경우 적수로 간주될 수 있다.

공개키암호법

이 섹션은 검증을 위해 추가 인용구가 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다.(2012년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

비대칭 키 암호화 알고리즘 암호 시스템이 의미론적으로 안전하려면, 암호화 텍스트와 해당 공개 암호화 키만 주어진 경우, 계산적으로 경계된 상대자가 메시지(플라인텍스트)에 대한 중요한 정보를 도출하는 것은 불가능해야 한다.의미적 보안은 "수동적" 공격자, 즉 그녀가 선택한 공개 키와 일반 텍스트를 사용하여 암호문을 생성하고 관찰하는 공격자의 사례만을 고려한다.다른 보안 정의와 달리 의미 보안은 공격자가 선택한 암호문의 해독을 요청할 수 있는 CCA(선택한 암호문 공격)의 경우를 고려하지 않으며, 의미론적으로 보안된 많은 암호화 체계가 선택한 암호문 공격에 대해 명백하게 안전하지 않다.따라서 의미적 보안은 이제 범용 암호화 체계를 확보하기 위한 불충분한 조건으로 간주된다.

선택적 일반 텍스트 공격(IND-CPA) 아래의 식별 불가능성은 일반적으로 다음 실험에 의해 정의된다.^[5]

1. 임의 쌍$({\displaystyle p}$ k${\displaystyle }$, ${\displaystyle s}$ k${\displaystyle }$) ${\displaystyle(pk,sk)}$은(는) $G{\displaystyle }$ ${\displaystyle e}$ n${\displaystyle }$( ${\displaystyle {1n}^{}}$) ${\displaystyle Gen(1^{n})$을$($를) 실행하여 생성된다.
2. 확률론적 다항식 시간 경계 상대에게 공개 키 ${\displaystyle p}$ k ${\displaystyle pk}$이(가) 주어지며,$$ 이 키를 사용하여 임의 수의 암호문을 생성할 수 있다(다항식 한계 내).
3. 상대방은 두 개의 동일한 길이의 메시지를 $m{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$과$$m ${\displaystyle {1\mathrm{}}_{}}$ ${\$}로 생성하여 공개 키와 함께 챌린지 Oracle로 전송한다.
4. 챌린지 오라클은 페어 코인을 플립하여 메시지 중 하나를 선택하고($$임의 비트 $b{\displaystyle \in \{0,}$ ${\displaystyle 1}$} {\$displaystyle$ b\in$\{0,1\}}) 공개$ 키 아래$$ 메시지 ${\displaystyle m_{}}$ ${\$을 암호화한 후, 결과 발생하는 도전 암호문 ${\displaysty c}$를 상대에게$$ 반환한다.

적수가 오라클이 선택한 두 메시지 중 어떤 메시지를 선택했는지 결정할 수 없는 경우 기본 암호 시스템은 IND-CPA(따라서 선택된 일반 텍스트 공격에 의미론적으로 안전함)이며, 확률은 $1{\displaystyle \mathrm{}}$/$2(임의$ 추측 $성공률)$보다 훨씬 크다.$$이 정의의 변형들은 선택된 암호문 공격과 적응적으로 선택된 암호문 공격(IND-CCA, IND-CCA2) 하에서 구별할 수 없는 가능성을 정의한다.

상대방이 위 게임에서 공용 암호화 키를 가지고 있기 때문에 의미론적으로 안전한 암호화 체계는 정의상 확률론적이어야 하며, 임의성의 구성요소를 소유해야 한다. 만약 그렇지 않다면 상대방은 ${\displaystyle {m\mathrm{}}_{}}$ $0{\displaystyle {}_{}}$ ${\$과 m ${\displaystyle {1\mathrm{}}_{}}$ ${\$}의$$ 결정론적 암호화를 간단하게 계산할 수 있다.$ystyle m_{1}:{$1}을$$(를) 사용하여 이러한 암호화를 반환된 암호 $텍스트{\displaystyle }$ c$${\$displaystyle c$}와$$ 비교하여 오라클의 선택을 성공적으로 추측하십시오.

의미론적으로 안전한 암호화 알고리즘에는 골드워서-미칼리, 엘가말, 파일리어 등이 있다.이러한 계획은 의미적 보안이 일부 어려운 수학 문제(예: 의사결정 디피-헬먼 또는 이차적 잔류성 문제)를 해결하는 것으로 축소될 수 있기 때문에 상당히 안전한 것으로 간주된다.RSA와 같은 의미론적으로 안전하지 않은 다른 알고리즘은 OAEP(Optimal Asymmetric Encryption Pading)와 같은 랜덤 암호화 패딩 방식을 사용함으로써 의미론적으로 안전하게 만들 수 있다(강력한 가정 하에서).

참조