공개 키 암호화 개요

🚀

공개 키 암호화란? (What is Public Key Cryptography?)🔗

암호화에 사용되는 키와 복호화를 위한 키는 다르다.

RSA, ElGamal, NTRU 등이 있다.

장점: 키 공유가 쉽고, 키의 수가 적다.

단점: 대칭키 암호화보다 느리다.

🚀

정의: 공개 키 암호화 PKE는 다음과 같은 알고리즘들로 구성된다.

정확성

공개 키 암호화 PKE는 다음이 성립할 때 정확하다고 한다. 보안 파라미터 λ와 모든 평문 M에 대해,

👨‍💻

Dec(sk, Enc(pk, M)) = M

여기서 (pk, sk)는 KeyGen(λ)의 출력이다.

🚀

도전자 C와 적대자 A 사이의 게임을 고려하자

A의 목표는 공개 키 암호화를 해독하는 것이다. - 즉, 암호문에서 평문 M을 찾는 것이다.

Setup : 도전자 C는 보안 파라미터 λ를 입력으로 받아 (pk, sk)를 출력한다.

그 중, 공개 키 pk를 A에게 전달한다.
Phase1: A는 C에게 복호화 쿼리 요청을 보낸다.

즉, A는 임의의 암호문 $C_i$ 를 C에게 보내고, C는 $Dec(sk, C_i) = M_i$ 을 반환한다.
Challenge: A는 두 평문 $M_0, M_1$ 을 선택하고, C는 둘 중 하나를 선택해( $b \in \{1, 2\}$ ) $Enc(pk, M_b) = C_b$ 를 반환한다.

이때, A는 어떤 평문에 해당하는 암호문인지 $b$ 를 추측한다.
Phase2: A는 C에게 복호화 쿼리 요청을 보낸다.

즉, A는 임의의 암호문 $C_i$ 를 C에게 보내고, C는 $Dec(sk, C_i) = M_i$ 을 반환한다.

Adv_{PKE}(\lambda) = Pr[b = b'] - \frac{1}{2}

👍

공개 키 암호화 체계는 적이 보안 파라미터에서 중요하지 않은 이점을 가질 수 없을 때 IND-XXX 안전하다.

XXX: 적대자에게 허용된 복호화 오라클에 의해 결정된다.