# 디지털 서명(Schnorr) {% hint style="warning" %} **목표 : 디지털 서명의 기본 원리를 이해하고, 이를 바탕으로 Schnorr 서명 스킴의 작동 과정과 강력한 보안 속성을 분석한다.** {% endhint %} zkp의 내부 구조는 Schnorr 서명과 같은 디지털 서명과 상당히 유사하다. Schnorr 서명은 원래 상호작용적인 식별 프로토콜을 Fiat-Shamir 변환을 통해 **비상호작용적인 지식 증명**으로 바꾼 결과이다. 많은 zkp 프로토콜 역시 같은 아이디어 위에서 설계된다. 이 글에서는 먼저 디지털 서명과 Schnorr 서명 스킴을 살펴보고, 이러한 구조가 이후 zkp를 이해하는 데 어떤 직관을 주는지 연결해서 본다. ### Digital Signature란? Digital Signature는 디지털 문서의 진정성(authenticity)과 무결성(integrity)을 암호학적으로 보장하기 위한 기술로, 비대칭 키 암호(Public Key Encryption) 환경에서 핵심적인 역할을 한다. 대칭키 암호(Symmetric key Encryption) 방식에서는 MAC(메시지 인증 코드)을 통해 이 두 가지 속성을 보장하지만, 비대칭키 방식(Asymmetric key Encryption)은 공개키가 누구에게나 공개되어 있어 송신자의 신원을 바로 보장할 수 없다. 따라서 디지털 서명은 이러한 환경에서 송신자의 신원을 확인하고 메시지 변조를 방지하는 역할을 수행한다. ### Digital Signature의 과정

Digital signature의 과정

그림처럼 두 당사자가 있을 때, 발신자가 pk(공개키)를 공개된 저장소에 올려서 누구나 접근할 수 있게 한다. 발신자와 통신하고 싶은 사람은 누구나 pk를 얻을 수 있다. 발신자가 수신자에게 메시지 m을 보내려고 할 때, 발신자는 본인이 해당 m을 만들었다는 것을 증명하기 위해 본인의 개인키 sk로 메시지 m에 서명하여 서명값 $$Sign\_{sk}(m)=σ$$를 함께 보낸다. Bob은 *σ*에 대해서 서명 검증 알고리즘인 $$Verify\_{pk}(m,σ)$$을 통해 $$σ$$가 발신자 Alice로부터 왔고 중간에 변조되지 않았음을 검증할 수 있다. ### Comparison to MACs? Digital signatures(전자서명)의 방법은 MACs(메시지 인증 코드)의 운용방식과 매우 유사해보인다. 그렇다면 둘의 차이점은 무엇일까? Digital signatures(전자서명) 대신 MACs의 알고리즘을 이용하여 σ를 생성해보자. \| Method 1 : 동일한 키를 모두 공유하는 경우
위 그림에서 모든 사람들은 동일한 키 k를 공유한다. 발신자 Alice는 $$t=MAC\_k(patch)$$를 이용하여 key k에 대한 tag를 생성하여 Bob에게 전달한다. 그러나 위 방법은 결함이 있다. 위처럼 수신자 Bob은 key k를 알고 있기 때문에, $$MAC\_k(patch')$$를 통해 새로운 tag를 만들어낼 수 있다. 만약 수신자들 중 한 명이 악의적인 목적으로 이상한 패치 patch′와 이에 해당하는 tag t′를 전송한다면, 이를 전송받은 수신자는 이상한 tag t′를 올바른 패치로 인식할 수 있다. \| Method 2 : 각각 다른 키를 공유하고, 이를 통해서 MAC을 보내는 경우 위 문제는 모든 수신자가 동일한 key k를 공유하고 있기 때문에 발생한다. 이를 해결하기 위해 이번엔 수신자마다 서로 다른 key들을 Alice와 공유하도록 해보자.
위 그림처럼 tag를 생성하여 전송하면, 수신자들 간에 악의적인 공격을 충분히 막아낼 수 있다. 하지만 Alice 입장에선 수신자들마다 서로 다른 key를 이용하여 tag를 만들어야하기 때문에, 수신자가 많아질수록 많은 키를 배포하고 관리해야 한다는 문제가 생긴다. Digital Signature는 공개키 암호화(Public-key Cryptography) 방식을 사용하며, MAC이 해결하지 못하는 중요한 보안 속성들을 제공한다. * **Public verifiability(공개검증가능성)**: 누구나 서명을 검증(verify)할 수 있어야 한다. MAC은 키를 공유하지 않는 제3자는 MAC의 유효성을 확인할 수 없다. * **Transferability(양도가능성)**: 다른 사람에게 서명을 양도할 수 있다. 물론 MAC도 그냥 중간에서 사람이 넘길 수 있긴하지만 키를 공유하지 않는 제3자는 MAC의 유효성을 독립적으로 검증할 수단이 없다. 그런데 signature는 가능하다. * **Non-repudiation(부인방지성)**: 송신자는 수신자에게 보낸 정보를 부인할 수 없다. MAC과 non-repuditation에 대한 성질을 비교해보면, MAC은 송신자가 동일한 key를 공유하기 때문에 3자 입장에선 메시지를 만든 주체가 누군지 확신할 방법이 없다. 따라서 MAC은 메시지 인증에는 적합하지만 부인방지까지 만족하지는 못한다. ### **Signature schemes** Digital signature의 signature scheme을 정의해보면, Signature scheme은 세 개의 PPT 알고리즘으로 구성되어 있다. * $$Gen(1^n)$$ : output pk, sk (키 생성)(input : $$1^n$$, output : pk,sk) * *σ* ← $$Sign\_{sk}(m)$$ : output *σ* (서명 생성) (input : sk, m output : *σ)* * $$Vrfy\_{pk}(m,σ)$$ : output 1 or 0 (증명) (input : pk, m, *σ output : 1 or 0)* 이때 모든 메시지 *m*과 *Gen* 알고리즘을 거친 키 *pk*,*sk*에 대하여, 아래 식을 만족한다. $$ Vrfy\_{sk}(m,Sign\_{sk}(m))=1 $$ #### Hash-and-sign paradigm Hash-and-sign paradigm은 디지털 서명에서 메시지 전체가 아닌, 메시지를 해시 함수에 넣어 얻은 해시 다이제스트 H(m)에만 서명하는 기법이다. 기본적인 서명 알고리즘은 보통 특정 길이 n의 짧은 입력(메시지)에 대해서만 효율적으로 작동하도록 설계되어 있었다. 따라서 서명해야 할 실제 메시지 m이 이보다 길거나 임의의 길이를 가질 때, 서명을 직접 적용하는 것은 비효율적이거나 불가능했다. 이 패러다임은 임의의 길이 메시지 m을 고정된 짧은 길이 n의 해시 다이제스트 H(m)로 변환하는 해시 함수 H:{0,1}\* →{0,1}n의 특성을 활용하여 이러한 문제를 해결한다. 서명 생성은 $$σ ← Sign\_{sk}(H(m))$$로, 검증은 $$Vrfy'*{pk}(m,σ)=Vrfy*{pk}(H(m),σ)$$로 정의된다. 이 방식을 통해 메시지 입력 길이를 맞출 필요 없이 임의의 긴 메시지에 대해 효율적으로 디지털 서명을 생성하고 검증할 수 있다. ### Identification Scheme 디지털 서명의 기반이 되는 중요한 개념인 식별 체계(Identification Scheme)에 대해 알아보자. Digital Signature는 메시지의 무결성과 서명자의 신원 인증을 보장하는 암호학적 기법이다. 이러한 디지털 서명의 기저에는 '자신만이 아는 비밀 정보(예: 개인키)를 소유하고 있음을 증명하는' 원리가 깔려 있으며, 바로 이 '비밀 정보 소유 증명' 과정을 상호작용적으로 다루는 것이 Identification Scheme이다. Identification Scheme은 '나는 이 비밀 정보를 알고 있다는 것을 상대방에게 보여주고 싶지만, 그 비밀 정보 자체는 노출하고 싶지 않을 때' 사용하는 상호작용적인 프로토콜이다.

Identification Scheme 과정

**과정** **Key 공유** 1. Prover가 pk,sk인 key pair를 생성하고, 자신의 pk를 공개적으로 배포하거나 접근 가능하게 한다 2. Verifier는 prover의 pk에 접근한다. **Identification** 1. Prover가 A라는 commitment 메시지를 생성하고 Verifier에게 보낸다. 2. Verifier는 임의의 challnege를 생성하고 이를 Prover에게 보낸다. 3. Prover는 A와 sk를 기반으로 s를 만들고 Verifier에게 보낸다. 4. Verifier는 pk, c, s를 이용해서 검증한다. #### Fiat-Shamir Transform Identification scheme이 상호작용적이라고 했는데, 디지털 서명은 보통 "비상호작용적(Non-Interactive)"이어야 한다. 즉, 서명자가 서명을 만들어서 보내면 검증자가 혼자서 검증할 수 있어야 한다는 것이다.. 그렇다면 어떻게 상호작용적인 식별 체계를 비상호작용적인 서명으로 만들 수 있을까? 바로 이때 등장하는 것이 Fiat-Shamir Transform이다. Fiat-Shamir Transform은 상호작용적인 식별 체계를 비상호작용적인 디지털 서명 스킴으로 변환하는 일반적인 방법이다. 방법은 다음과 같다. 원래 상호작용적인 식별 체계에서는 Verifier가 무작위 'Challenge'을 생성하여 Prover에게 보내야 한다.하지만 Fiat-Shamir Transform은 이 Challenge를 암호학적 해시 함수를 사용하여 생성하도록 한다.

Fiat-Shamir Transform

다시 말해, Prover가 서명할 메시지와 커밋먼트를 해시 함수에 넣어 스스로 챌린지 값을 만들고, 그 챌린지에 대한 응답을 계산하여 서명으로 제출하는 방식이다. 이렇게 하면 검증자가 직접 챌린지를 보낼 필요가 없어지므로, 한 번의 전송으로 서명과 검증이 모두 가능해진다.(커밋먼트가 랜덤하게 생성되므로 challenge도 랜덤) 이렇게 Fiat-Shamir Transform을 통해서 Identification을 하면서 Digital Signature가 가능해졌다. ### Schnorr Signature Schnorr identification scheme은 앞선 identification scheme에서 DLog가 hard problem임에 착안해 만든 프로토콜이다.

Shnorr 서명 과정

**과정** 1. 먼저 prover가 Group-generation 알고리즘을 이용해 *G*와 *q*, 그리고 generator *g*를 생성한다. 그룹 내에 랜덤한 값 x를 뽑아 자신의 private key로 세팅한다. 그리고 *h*를 $$g^x$$로 만들어, G, q, g, h를 public key로 만든다. 2. 이제 interaction proof protocol을 본격적으로 진행한다. Verifier에게 $$A = g^r$$ (r은 랜덤한 값)을 전달한다. 3. Prover는 Fiat-Shamir Transform을 활용해서 서명할 메시지 M과 자신의 A를 해시 함수에 넣어 c를 직접 생성한다. 4. *c*와 자신의 private key, 그리고 메시지에 대한 정보 *r*을 이용해 서명 *s*를 만든다. 이때 *s*는 $$s=\[cx+r \mod q]$$를 만족한다. 5. *s*를 전송받은 verifier는 public key에 존재하는 g와 자신이 랜덤하게 준 값 *c*, 그리고 서명 *s*를 이용해 인증이 됐는지 확인한다. 이때 아래 식에 의해 $$g^sh^{−c}=A$$가 성립해야 한다.

최종적으로 확인하는 식

이제 해당 scheme을 Prover와 Verifier가 malicious한 경우를 가정해서 Schnorr 서명의 안정성을 살펴보자. **Prover가 malicious한 경우**

Prover가 malicious한 경우(두번의 서명 시도를 한경우)

이 그림은 증명자가 만약 비밀키 x를 모른 채로도 두 번의 서명 시도(Fiat-Shamir 변환에서 c와 c’ 두 가지 challenge에 대한 s와 s’응답)를 통해 검증을 통과한다면, 이는 이산 로그 문제(DLP)를 풀 수 있음을 의미한다. 만약 악의적인 증명자가 커밋먼트 $$A$$에 대해

g^sh^{-c}=A, g^{s'}h^{-c'}=A

와 같은 두 가지 유효한 등식을 만들어낼 수 있다면, 이 두 등식을 결합하여

g^sh^{-c} = g^{s'}h^{-c'}

이라는 관계가 성립하게 된다. 이 관계를 조작하면 결국 x를 알아낼 수 있는 수식이 도출된다. 따라서 만약 악의적인 Prover가 비밀키 x를 모르면서 검증을 통과한다면, 그들은 DLP라는 매우 어려운 암호학적 문제를 풀 수 있다는 것을 의미한다. 이는 현재까지 알려진 효율적인 방법이 없기 때문에, 이러한 상황은 발생하기 어렵다고 가정하며, 이는 곧 “증명자가 실제로 비밀키 x를 알고 있어야만 이 증명 과정을 성공시킬 수 있다”는 soundness(건전성)를 강력하게 뒷받침한다. **Verifier가 malicious한 경우**

Verifier가 malicious한 경우(기존의 Schnorr 서명과 순서를 달리 c,s를 먼저 제공받고 A를 유추하는 경우)

그림의 왼쪽은 정직한 증명자(Prover)와 정직한 검증자(Verifier) 간의 실제 프로토콜 상호작용을 나타낸다. 1. 증명자는 자신의 비밀키 x와 랜덤 값 r을 사용하여 첫 메시지 $$A=g^r$$를 계산하여 검증자에게 보낸디. 2. 검증자는 이에 대한 무작위 도전값(Challenge) c를 생성하여 증명자에게 보낸다. 3. 증명자는 이 c와 자신의 비밀키 x, 그리고 r을 사용하여 응답 s=cx+r를 계산하여 보낸다. 4. 검증자는 최종적으로 $$g^sh^{-c}=A$$가 성립하는지 확인한다 (여기서 $$h=g^x$$는 증명자의 공개키이다). 이제 그림의 오른쪽은 공격자(악의적인 검증자)가 증명자의 비밀키 x를 전혀 모르는 상태에서 transcript(A, c, s)를 스스로 시뮬레이션하는 과정을 보여준다. 여기서 중요한 점은, 공격자는 x를 모른 채로도 다음 순서로 값을 생성한다. 1. 먼저, 공격자는 도전값 c를 $$Z\_q$$에서 균등하게 선택하고, 응답 값 s 또한 $$Z\_q$$에서 균등하게 선택한다. 2. 그런 다음, 이 두 값을 사용하여 프로토콜의 첫 메시지 A를 $$A=g^sh^{-c}$$로 역으로 계산한다. 오른쪽에서 공격자가 임의로 만들어낸 (A,c,s) 세 값의 transcript는 왼쪽에서 정직한 증명자와 검증자가 실제로 상호작용한 (A,c,s) transcript와 동일한 분포를 가진다. 이 결론이 의미하는 바는 매우 중요하다. 만약 공격자가 비밀키 x를 전혀 모르는 상태에서 정직한 프로토콜과 구별할 수 없는 성공적인 transcript를 스스로 생성할 수 있다면, 이는 공격자가 프로토콜의 정직한 실행을 관찰하더라도 비밀키 x에 대한 어떠한 정보도 추가적으로 얻을 수 없다는 것을 의미한다. 검증자는 프로토콜을 관찰함으로써 얻는 정보가, 자신이 x 없이 임의로 생성할 수 있는 정보와 동일하기 때문이다. (DLP를 풀 수 있으면 비밀키를 구할 수 있는데 DLP를 풀 수 없음으로 안전하다.) 따라서 이 그림은 Schnorr Identification이 zero knowledge(영지식성)이라는 강력한 보안 속성을 가지고 있음을 증명하는 핵심적인 개념이며, 이는 비밀 정보를 노출하지 않고도 신원을 증명할 수 있게 해주는 기초가 된다. 이처럼 Schnorr identification scheme은 악의적인 Prover와 Verifier 모두로부터 비밀값(x)을 안전하게 지킬 수 있다. ### Reference 1. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-0/prerequisite/schnorr.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.