디지털 서명의 정의

🚀

디지털 서명 개요 (Overview of Digital Signature) 🔗

✅

메시지 인증 과정에서 Bob이 Alice에게 메시지를 보낼 때, Alice는 메시지가 Bob에게서 온 것인지 확인해야 함

\rightarrow

디지털 서명

사용

Bob의 비밀 키가 없으면 누구도 Bob의 서명을 생성할 수 없음

출처(Bob)와 데이터 무결성(메시지) 측면에서 인증된다.

✅

디지털 서명 체계는 다음과 같은 세 가지 다항 시간 알고리즘으로 구성됨

KeyGen
( $\lambda$ $λ$ ) $\rightarrow$ $\to$ (pk, sk): 키 생성 알고리즘
- 보안 매개변수 $\lambda$ 를 입력으로 받아 공개키(pk)와 개인키(sk)를 생성
Sign
(sk, m) $\rightarrow$ $\to$ $\sigma$ $σ$ : 서명 알고리즘
- 개인키(sk)와 메시지(m)를 입력으로 받아 디지털 서명( $\sigma$ )을 생성
Verify
(pk, m, $\sigma$ $σ$ ) $\rightarrow$ $\to$ {0, 1}: 검증 알고리즘
- 공개키(pk), 메시지(m), 디지털 서명( $\sigma$ )을 입력으로 받아 디지털 서명이 유효한지 검증
- 유효하면 1, 그렇지 않으면 0을 반환

✅

정당성

: 검증 알고리즘은 다음을 만족해야 함

➡️

🚀

도전자

C

와 공격자

A

사이의 게임을 고려

Setup: $C$ 는 KeyGen( $\lambda$ )을 실행하여 $(pk, sk)$ 를 생성, 공개 키 $pk$ 를 $A$ 에게 전달
Signing Queries: $A$ $A$ 는 메시지 $M_i$ $M_{i}$ 에 대해 다항 횟수만큼 서명 쿼리를 요청
- 각 $M_i$ 에 대해 $C$ 는 $\text{Sign}(sk, M_i) → \sigma_i$ 를 실행하여 서명 $\sigma_i$ 를 생성, $A$ 에게 반환
Output: $A$ $A$ 는 $(M, \sigma)$ $(M, σ)$ 를 반환
- $M$ 은 $C$ 가 서명하지 않은 메시지이며, $A$ 가 서명을 요청한 메시지와 다름
- $A$ 가 $M$ 에 대한 유효한 서명 $\sigma$ 를 생성한 경우, $A$ 는 성공

A

의 성공 확률은 다음과 같이 정의

서명 체계는 적응적 선택 메시지 공격(Adaptive Chosen Message Attack)에 대해 강하게 위조 불가능

만약 다항 시간 공격자

A

가 위의 게임에서 성공할 확률이 무시할 만큼 작다면, 서명 체계는 강하게

위조 불가능

하다