부정할 수 없는 서명

거부할 수 없는 서명은 서명자가 서명을 검증할 수 있는 사람을 선택할 수 있도록 하는 디지털 서명 체계다. 이 계획은 명시적인 서명 거부를 추가하며, 서명자가 나중에 누락에 의해 서명 확인을 거부하는 것을 방지한다. 즉, 확인자가 보기에 서명을 평가절하할 수 있는 상황이다. 1989년 데이비드 차움, 한스 반 앤트워펜에 의해 발명되었다.^[1]

개요

이 계획에서 개인 키를 가진 서명인은 메시지의 서명을 발행할 수 있다. 그러나 서명은 메시지 및 서명의 수신자/검증자에게 다음 두 가지 대화형 프로토콜 중 하나에 참여하지 않고서는 아무것도 드러내지 않는다.

후보자가 공개 키로 식별된 서명자가 발행한 메시지의 유효한 서명임을 확인하는 확인 프로토콜.
후보자가 서명인이 발행한 메시지의 유효한 서명이 아님을 확인하는 디스어바운스 프로토콜.

그 계획의 동기는 서명자가 서명을 검증할 사람을 선택할 수 있도록 하기 위함이다. 그러나 서명자가 나중에 검증에 참여하지 않음으로써 서명이 무효라고 주장할 수 있다는 것은 서명이 검증자에게 평가절하될 것이다. 이항 프로토콜은 이러한 경우를 구분하여 서명자의 그럴듯한 반항을 제거한다.

확인과 불복 교환이 이체되지 않는 것이 중요하다. 그들은 제로 지식의 속성을 가지고 있기 때문에, 양 당사자는 구별할 수 없는, 제3자에게, 올바른 교환의 확인과 불복 모두의 녹취록을 작성할 수 있다.

지정된 확인 서명 체계는 각 서명마다 서명자의 상호 작용 부분을 지정된 확인체인 다른 당사자에게 오프로딩하여 서명자의 부담을 줄임으로써 부정 서명 시 개선된다.

영지식 프로토콜

다음의 의전은 데이비드 차움(David Chaum)이 제안했다.^[2]

그룹 G는 이산 로그 문제가 난치될 수 있는 그룹으로 선택되며, 계획의 모든 작업이 이 그룹에서 이루어진다. 일반적으로, 이것은 Z/nZ에 포함된 유한 주기적 순서 p 그룹이 될 것이며, p는 큰 소수일 것이다. 이 그룹은 정수 곱셈모듈로 n의 그룹 운영을 갖추고 있다. G의 임의의 원시 요소(또는 발생기) g를 선택한다. g의 계산된 힘은 고정 공리를 준수하는 것을 결합한다.

앨리스는 키 쌍을 생성하고 임의로 개인 키 x를 선택한 다음 공개 키 y = g를 도출하여^x 게시한다.

메시지 서명

앨리스는 메시지 m에 서명하여 서명 z = m을^x 계산하고 발행한다.

확인(예: 포기) 프로토콜

밥은 열쇠 밑에 있는 앨리스에 의해 m의 서명인 z를 확인하기를 원한다.

밥은 두 개의 임의의 숫자 a와 b를 골라서, 이 숫자들을 이용해서 메시지를 블라인드 해 앨리스에게 보낸다.
c = m^ag^b.
앨리스는 무작위 번호인 q를 골라 블라인드, c에 사용하고, 자신의 개인 키인 x를 사용하여 서명하여 밥에게 보낸다.
s₁ = cg^q 및
s₂ = s₁^x.
참고:
s₁^x = (sv^q)^x = (mg^a^b)^xg^qx = (m^x)(^ag^x)^b+q = zy^a^b+q.
밥은 a와 b를 드러낸다.
앨리스는 a와 b가 올바른 블라인드 값인지 검증한 다음, 그렇다면 q를 드러낸다. 이러한 블라인드를 노출하면 교환에 대한 지식이 0이 된다.
밥은 s₁ = cg를^q 확인하고, q가 부정직하게 선택되지 않았음을 증명한다.
s₂ = z^ay^b+q,
증명 z는 앨리스의 키로 발급된 유효한 서명이다. 참고:
zy^a^b+q = (m^x)(^ag^x)^b+q

앨리스는 무작위로 s를₂ 추측해 2단계에서 부정행위를 할 수 있다.

이절규약서

앨리스는 밥에게 z가 키 아래^x m의 유효한^x 서명이 아니라는 것을 납득시키기를 원한다. 앨리스와 밥은 앨리스의 계산적 부담과 그녀가 우연히 성공할 가능성을 설정하는 정수인 k에 동의했다.

밥은 임의의 값, s ∈ {0, 1, ..., k} 및 a를 선택하고 다음을 전송한다.
v₁ = mg^s^a 및
v₂ = z^sy^a,
여기서 a에 의한 지수를 사용하여 전송된 값을 블라인드한다. 참고:
v₂ = z^sy^a = (m^x)^s(g^x)^a = v₁^x.
앨리스는 자신의 개인 키를 사용하여₁^x v를 계산하고 그 다음 인용구를 계산한다.
v₁^xv₂⁻¹ = (m^sg^a)^x(z^sg^xa)⁻¹ = m^sxz^−s = (m^xz⁻¹)^s.
따라서 z = m이 아닌^x 경우 vv₁^x₂⁻¹ = 1이다.
그런 다음 앨리스는 vv에서₁^x₂⁻¹ 다음과 같은 값에 대한 동등성을 테스트한다.
(mz^x⁻¹)ⁱ i ∈ {0, 1, …, k}의 경우,
이 값은^x⁻¹ mz의 반복 곱하기(각 i에 대한 지수보다 큰 값)로 계산된다. 시험이 성공하면 앨리스는 관련된 i를 추측하고, 그렇지 않으면 그녀는 임의의 값을 추측한다. 여기서^x z = m, (mz^x⁻¹)ⁱ = 모든 i에 대해 vv₁^x₂⁻¹ = 1인 경우 s는 복구할 수 없다.
앨리스는 나에게 약속한다: 그녀는 임의의 r을 선택하고 해시(r, i)를 밥에게 보낸다.
밥은 a를 드러낸다.
앨리스는 a가 올바른 블라인드(즉, v와₁ v는₂ 그것을 사용하여 생성될 수 있음)라는 것을 확인한 다음, 그렇다면 r이 드러난다. 이 블라인드를 노출시키면 교환은 전혀 알지 못한다.
밥은 해시(r, i) = 해시(r, s)를 확인하여 앨리스가 s를 알고 있음을 증명하고, 따라서 z ≠ m^x.

앨리스가 무작위로 s를 추측하여 3단계에서 부정행위를 시도한다면 성공할 확률은 1/(k + 1)이다. 그래서 k = 1023이고 프로토콜이 10번 실시된다면 그녀의 가능성은 1대¹⁰⁰ 2이다.

참고 항목

참조

^ Chaum, David; van Antwerpen, Hans (1990). "Undeniable Signatures". LNCS. 435: 212–216.
^ Chaum, David (1991). "Zero-Knowledge Undeniable Signatures". Advances in Cryptology EUROCRYPT '90 Proceedings: 458–462. doi:10.1007/3-540-46877-3_41.

[1] Chaum, David; van Antwerpen, Hans (1990). "Undeniable Signatures". LNCS. 435: 212–216.

[2] Chaum, David (1991). "Zero-Knowledge Undeniable Signatures". Advances in Cryptology EUROCRYPT '90 Proceedings: 458–462. doi:10.1007/3-540-46877-3_41.

[1]

[2]

Search