약속 체계

커밋 체계는 나중에 커밋된 가치를 드러낼 수 있는 능력을 가지고, 다른 사람에게 숨기면서 선택된 값(또는 선택된 문장)에 커밋할 수 있도록 하는 암호 원시체다.^[1] 약속 체계는 당사자가 약속된 후 가치나 진술을 변경할 수 없도록 설계된다. 즉, 약속 체계는 구속력이 있다. 약속 체계는 보안 코인 플립, 제로 지식 증명, 안전한 계산을 포함한 다수의 암호화 프로토콜에서 중요한 응용 프로그램을 가지고 있다.

약속 계획을 시각화하는 방법은 발신인을 잠긴 상자에 메시지를 넣고 수신자에게 상자를 주는 것으로 생각하는 것이다. 자물쇠를 스스로 열 수 없는 수신기에 상자 속의 메시지가 숨겨져 있다. 수신기가 박스를 가지고 있기 때문에 내부의 메시지는 변경할 수 없다. 보낸 사람이 나중에 그들에게 키를 주겠다고 선택한다면 아주 잘 드러난다.

약속 체계에서 상호작용은 다음 두 단계로 이루어진다.

1. 값을 선택하고 커밋하는 커밋 단계
2. 송신자에 의해 값이 공개되고, 수신자가 그 진위를 확인하는 공개 단계

위의 은유에서 커밋 단계는 메시지를 상자에 넣고 잠그는 발신인이다. 공개 단계는 송신자가 수신자에게 키를 주는 것으로, 송신자는 수신기를 사용하여 상자를 열고 내용물을 확인하는 것이다. 자물쇠가 채워진 상자는 약속이고 열쇠는 증거다.

간단한 프로토콜에서 커밋 단계는 송신자가 수신자에게 보내는 단일 메시지로 구성된다. 이 메시지를 약속이라고 한다. 그 때 선택한 구체적인 가치를 수신자가 알 수 없는 것이 필수적이다(이를 은닉재산이라고 한다). 단순한 공개 단계는 송신자에서 수신기로 이어지는 하나의 메시지, 즉 개방으로 구성되며, 수신자에 의해 수행되는 점검으로 구성된다. 커밋 단계 중에 선택한 값은 송신자가 계산할 수 있고 공개 단계 동안 유효성을 검사할 수 있는 값(이를 바인딩 속성이라고 함)만 되어야 한다.

약속 체계의 개념은 아마도 1988년 길레스 브래서드, 데이비드 차움, 클로드 크레포에 의해 다양한 유형의 약속 체계에 기초하여 NP를 위한 다양한 제로 지식 프로토콜의 일부로 처음 공식화되었을 것이다(^[2]또한: 참조).^[3][4] 그러나 그 개념은 그 전에 정식으로 다루지 않고 사용되었다.^[5][6] 약속의 개념은 마누엘 블럼,^[7] 시몬 이븐,^[8] 샤미르 등의 작품에서 가장 일찍 나타났다.^[9] 이 용어는 약속 체계를 비트 약속 체계라고 상호 교환할 수 있지만, 때로는 커밋된 가치가 약간 있는 특별한 경우를 위해 유보되기도 하지만,^[6] Blum에 의해 유래된 것으로 보인다. 이에 앞서, 단방향 해시함수를 통한 약속(예: Lamport 시그니처, 원래 일회성 1비트 시그니처 방식)의 일부로서 검토되었다.

적용들

동전 던지기

앨리스와 밥이 동전 던지기를 통해 어떤 분쟁을 해결하고 싶다고 가정해보자. 그들이 물리적으로 같은 장소에 있는 경우, 일반적인 절차는 다음과 같다.

1. 앨리스는 동전 던지기를 "부르다"
2. 밥은 동전을 던져버린다.
3. 앨리스의 부름이 맞으면 그녀가 이기고, 그렇지 않으면 밥이 이긴다.

만약 앨리스와 밥이 같은 장소에 있지 않다면 문제가 발생한다. 일단 앨리스가 동전 던지기를 "부르다"고 하면, 밥은 그 "결과"를 그에게 가장 바람직한 것으로 규정할 수 있다. 마찬가지로 앨리스가 밥에게 '통화'를 알리지 않으면 밥이 동전을 던져 결과를 발표한 후 앨리스는 자신에게 가장 바람직한 결과가 무엇이든 전화를 걸었다고 신고할 수 있다. 앨리스와 밥은 둘 다 결과를 믿을 수 있는 절차에 약속을 사용할 수 있다.

1. 앨리스는 동전 던지기를 "전화"하지만 밥에게 자신의 전화에 대한 약속만을 전한다.
2. 밥은 동전을 던져 결과를 보고한다.
3. 앨리스는 자신이 무엇을 위해 헌신했는지 드러낸다.
4. 밥은 앨리스의 전화가 그녀의 헌신과 일치한다는 것을 확인했고
5. 만약 앨리스의 폭로가 밥이 보고한 동전 결과와 일치한다면 앨리스는 승리한다.

밥이 자신에게 유리하게 결과를 왜곡할 수 있으려면 앨리스의 헌신 속에 감춰진 부름을 이해할 수 있어야 한다. 만약 약속 계획이 좋은 것이라면 밥은 결과를 왜곡할 수 없다. 마찬가지로 앨리스는 자신이 약속하는 가치를 바꿀 수 없다면 결과에 영향을 줄 수 없다.^[5][7]

이 문제의 실제 적용은 사람들이 (흔히 언론에) 결정을 약속하거나 "봉인 봉투"로 대답을 할 때 존재하며, 그 후에 공개된다. 예를 들어 게임쇼에서 "후보자가 그렇게 대답했는지 알아보자"는 것이 이 제도의 모범이 될 수 있다.

영지식증거

한 가지 특별한 동기를 부여하는 예는 제로 지식 증명에서의 헌신적인 계획의 사용이다. 약속은 두 가지 주요 목적을 위해 제로 지식 증명에서 사용된다. 첫째, 검증자가 "잘라서" 검증에 참여할 수 있도록 하고 검증자는 검증자의 선택에 해당하는 것만을 공개한다. 약속 계획은 프로베러가 모든 정보를 미리 명시할 수 있게 하고, 나중에 증명에서 밝혀야 할 내용만 밝힐 수 있게 한다.^[10] 둘째로, 검증자는 종종 약속에서 미리 자신의 선택을 명시할 것이다. 이를 통해 제로 지식 증명서가 프로베라에게 추가 정보를 노출하지 않고 병렬로 구성될 수 있다.^[11]

서명 구성표

램포트 서명 체계는 두 세트의 비밀 데이터 패킷을 유지하고, 검증 가능한 데이터 패킷의 해시를 게시한 다음, 서명할 데이터에 특별히 부합하는 방식으로 부분 비밀 데이터 패킷을 선택적으로 공개하는 데 의존하는 디지털 서명 시스템이다. 이렇게 해서 비밀 가치에 대한 이전의 공공의 약속은 시스템의 기능에서 중요한 부분이 된다.

Lamport 서명 시스템은 두 번 이상 사용할 수 없기 때문에(자세한 내용은 관련 기사 참조), 한 사람에게 묶어 다른 사람이 검증할 수 있는 하나의 공적인 가치로 여러 Lamport Key-set을 결합하는 시스템을 개발했다. 이 시스템은 해시 트리를 사용하여 많은 게시된 lamport-key-commits 집합을 하나의 해시 값으로 압축하며 나중에 검증된 데이터의 미래 작성자와 연관될 수 있다.

검증 가능한 비밀 공유

약속의 또 다른 중요한 적용은 검증 가능한 비밀 공유, 즉 안전한 다중 작업 계산의 중요한 구성 요소다. 비밀 공유 계획에서, 여러 당사자들은 각각 모든 사람에게 감추어져야 할 가치의 "공유"를 받는다. 충분한 당사자가 모이면 그들의 몫을 이용해 비밀을 재구성할 수 있지만, 크기가 부족한 악의적인 카발이라도 아무것도 배우지 말아야 한다. 비밀 공유는 안전한 계산을 위한 많은 프로토콜의 근원에 있다: 어떤 공유된 입력의 기능을 안전하게 계산하기 위해 비밀 공유는 대신 조작된다. 그러나 악의적인 당사자가 주식을 생성하려면 그러한 주식의 정확성을 확인하는 것이 중요할 수 있다. 검증 가능한 비밀 공유 계획에서 비밀의 분배는 개별 주식에 대한 약속이 수반된다. 그 약속들은 부정직한 카발에게 도움이 될 수 있는 어떤 것도 드러내지 않지만, 그 주식들은 각각의 개별 당사자들이 그들의 지분이 올바른지 확인할 수 있도록 한다.^[12]

보안 정의

약속 체계의 형식적 정의는 표기법과 향미에서 크게 다르다. 첫 번째 그러한 맛은 약속 체계가 숨기기나 구속력 있는 속성과 관련하여 완벽한 또는 계산적 보안을 제공하는가 하는 것이다. 또 다른 그러한 풍미로는 커밋 단계가 쌍방향인지, 즉 커밋 단계와 공개 단계가 모두 암호 프로토콜에 의해 실행된 것으로 보일 수 있는지 또는 두 알고리즘 커밋과 CheckReval로 구성된 비 상호작용이 있는지 여부다. 후자의 경우, CheckReveal은 종종 Commit에 의해 사용되는 무작위성이 개방 정보를 구성하는 것으로 비논리화된 버전의 Commit으로 보일 수 있다.

값 x에 대한 C가 C로 계산되는 경우:=커밋(x,open)을 커밋 계산에 사용한 랜덤성으로 커밋한 다음, CheckReval(C,x,open)은 단순히 C=커밋(x,open) 등식 확인으로 구성된다.

이 표기법과 수학적 함수와 확률 이론에 대한 지식을 사용하여 우리는 약속의 구속력과 숨김 속성의 다른 버전을 공식화한다. 이러한 특성의 가장 중요한 두 가지 조합은 완벽하게 결합되고 계산적으로 약속 체계를 숨기는 것이며, 계산적으로 결합하고 완벽하게 약속 체계를 숨기는 것이다. 어떤 약속 체계도 완벽하게 결합되고 완벽하게 숨길 수 없다는 점에 유의하십시오. 계산적으로 결합되지 않은 상대는 단순히 x의 모든 값에 대해 커밋(x, open)을 생성하고 C를 출력하는 쌍을 찾을 때까지 열 수 있으며, 완벽하게 결합되는 체계에서 이것이 x를 고유하게 식별할 수 있다.

연산 바인딩

사이즈 ${\displaystyle 2^{}}$ k ${\$ 2$^{k$ 즉 k 비트 문자열로 나타낼 수 있도록 하고, ${\displaystyle {\text{커밋}}_{}}$ ${\displaystyle {}_{}}$ ${\$을(를) 해당 커밋 스키마가 되도록$$ 한다. k의 크기가 약속 체계의 보안을 결정함에 따라 그것을 security parameter라고 부른다.

Then for all non-uniform probabilistic polynomial time algorithms that output ${\displaystyle x,x'}$ and ${\displaystyle open,open'}$ of increasing length k, the probability that ${\displaystyle x\neq x'}$ and ${\$$displaystyle {\textCommit}_{k$}(x$,open)={\text{Commit}_{$k}(x',$open')}$은(는) k로 무시할 수 있는 함수다$.$

이것은 무증상 분석의 한 형태다. 또한 구체적인 보안을 이용하여 동일한 요구사항을 진술할 수도 있다. A commitment scheme Commit is ${\displaystyle (t,\epsilon )}$ secure, if for all algorithms that run in time t and output ${\displaystyle x,x',open,open'}$ the probability that ${\displaystyle x\neq x'}$ and ${\d$$isplaystyle {\textCommit}(x,open)={\text{Commit}(x',open')}$은(는) $최대{\displaystyle }$ ${\displaystyle \epsilon }$ 입니다$.$

완벽한, 통계적, 계산적 숨기기

$U{\displaystyle {}_{}}$ {\$displaystyle U_{k}}}$을(를) $보안{\displaystyle {\mathrm{}}^{}}$ 매개 변수 k에 ${\displaystyle {대한}^{}}$ 2$$k {\$displaystyle$2^{$k}$ 개방$$ 값에 대한 균일한 분포로 설정하십시오$$. A commitment scheme is respectively perfect, statistical, or computational hiding, if for all ${\displaystyle x\neq x'}$ the probability ensembles ${\displaystyle \{{\text{Commit}}_{k}(x,U_{k})\}_{k\in \mathbb {N} }}$ and ${$$\displaystyle \{\text{Commit}_{k}(x',U_{k})\}_{k\in \mathb{N}}}}}}}$은(는) 동일하거나 통계적으로 근접하거나 계산적으로 구분할 수 없다.

보편적으로 구성 가능한 약속 체계의 불가능성

범용 복합성(UC) 프레임워크에서는 약속 체계를 실현하는 것이 불가능하다. 그 이유는 카네티와 피슐린이^[13] 보여주고 아래에 설명했듯이 UC 헌신이 추출 가능해야 하기 때문이다.

여기에 F로 표시된 이상적인 약속 기능은 대략 다음과 같이 작동한다. 커밋터 C는 값 m을 F에 보내어 이를 저장하고 수신기 R에 "수신"을 보낸다. 이후 C는 F에 "열림"을 보내 R에 m을 보낸다.

자, 이 기능을 실현하는 프로토콜 π이 있다고 가정합시다. 커밋자 C가 손상되었다고 가정해 보십시오. UC 프레임워크에서, 그것은 본질적으로 C가 이제 이상적인 프로세스와 프로토콜 실행을 구별하려는 환경에 의해 제어된다는 것을 의미한다. 메시지 m을 선택한 다음 C에게 m에 전념한 것처럼 π에서 규정한 대로 행동하도록 지시하는 환경을 고려한다. 여기서 F를 실현하기 위해, 수신자는 약속을 받은 후에 "수신"이라는 메시지를 출력해야 한다는 점에 유의하십시오. 환경은 이 메시지를 보고 나서 C에게 약속을 열라고 말한다.

프로토콜은 기능성이 시뮬레이터 S와 상호 작용하는 이상적인 경우와 구별할 수 없는 경우에만 안전하다. 여기서 S는 C를 지배한다. 특히 R이 "수신"을 출력할 때마다 F도 마찬가지로 해야 한다. 그렇게 하는 유일한 방법은 S가 C에게 F에게 값을 보내라고 말하는 것이다. 그러나 이때까지 m은 S에게 알려져 있지 않다는 점에 유의한다. 따라서 프로토콜 실행 중에 약속이 열리면, R이 영수증을 출력하기 전에 환경으로부터 받은 메시지로부터 S가 m을 추출할 수 있지 않는 한, F가 m에 개방될 가능성은 낮다.

그러나 이런 의미에서 추출할 수 있는 프로토콜은 통계적으로 숨길 수 없다. 그러한 시뮬레이터 S가 존재한다고 가정하자. 이제 C를 부패시키는 대신 R을 부패시키는 환경을 생각해 보자. 게다가 그것은 S의 복사본을 운영한다. C로부터 받은 메시지는 S로 공급되고, S로부터의 회신은 C로 전달된다.

환경은 처음에 C에게 메시지 m에 커밋하라고 말한다. 교호작용의 어느 지점에서 S는 값 m³에 커밋한다. 이 메시지는 m³를 출력하는 R에게 전달된다. 가정으로 m' = m이며 확률이 높다는 점에 유의하십시오. 이제 이상적인 과정에서는 시뮬레이터가 m을 만들어 내야 한다. 그러나 이것은 불가능한데, 왜냐하면 이 시점에서 그 약속은 아직 열리지 않았기 때문에 R이 이상적인 과정에서 받을 수 있는 메시지는 "수신" 메시지뿐이기 때문이다. 그래서 우리는 모순을 가지고 있다.

건설

약속 체계는 완벽하게 구속력이 있거나(앨리스가 만든 후에 약속을 변경하는 것은 불가능하며, 비록 그녀가 한없는 계산 자원을 가지고 있더라도), 또는 완벽하게 은폐될 수 있다(밥이 한없는 계산 자원을 가지고 있더라도 앨리스가 그것을 밝히지 않고는 그 약속을 알아내는 것은 불가능하다), 또는 그것을 공식화할 수 있다.s 다른 문제에 대한 해결책에 따라 숨기거나 구속력이 있는 인스턴스(instance)-instance-instance) 약속 체계.^[14][15] 약속 체계는 숨기는 동시에 구속력을 가질 수 없다.

랜덤 오라클 모델의 비트 커밋

비트 커밋 체계는 랜덤 오라클 모델에서 구성하기에는 사소한 것이다. 3k 비트 출력으로 해시함수 H가 주어지고, k비트 메시지 m을 커밋하기 위해 앨리스는 임의 k 비트 문자열 R을 생성하여 Bob H(R m)를 보낸다. H(R′ m³) = H(R m)가 2인^−k m³ m에 존재하는 R′, m³의 확률. 그러나 메시지에서 추측을 테스트하기 위해 m Bob은 임의의 오라클에 2^k(잘못된 추측의 경우) 또는 2^k-1(평균적으로 정확한 추측의 경우) 쿼리를 해야 한다.^[16] 우리는 해시함수에 기반한 이전의 체계들은 본질적으로 이러한 해시함수의 이상화에 근거한 체계들을 랜덤 오라클로서 생각할 수 있다는 점에 주목한다.

모든 단방향 순열의 비트 커밋

주입식 단방향 함수에서 비트 커밋 체계를 만들 수 있다. 이 계획은 (주사 특성을 유지하면서) 계산적으로 하드코어 술어를 보유하도록 (골드레이히-레빈 정리를 통해) 모든 일방 함수를 수정할 수 있다는 사실에 의존한다. f는 하드코어 술어를 가진 주입식 단방향 함수가 되게 하라. 그리고 나서 비트 b에 커밋하기 위해 앨리스는 임의의 입력 x를 선택하고 3중으로 전송한다.

${\displaystyle(h,f(x),b\oplus h(x))}$

bob ${\displaystyle \oplus }$은(는) XOR, 즉 비트 추가 모듈로 2를 의미한다$$. 앨리스는 단지 x를 밥에게 보낸다. 밥은 f(x)를 계산하고 커밋된 값과 비교하여 확인한다. 밥이 b(x)를 회복하려면 h(x)를 회복해야 하기 때문에 이 계획은 은폐되고 있다. h는 계산적으로 하드코어 술어인 만큼 확률 1/2 이상인 f(x)에서 h(x)를 회복하는 것은 f를 뒤집는 것만큼 어렵다. 완벽한 결합은 f가 주입식이기 때문에 f(x)가 정확히 하나의 프리이미지를 가지고 있다는 사실에서 따른다.

의사 임의 생성기의 비트 커밋

단방향 함수에서 단방향 순열을 구성하는 방법을 모르기 때문에, 이 절은 비트 커밋 프로토콜을 구성하는 데 필요한 암호 가정 강도를 줄인다.

1991년 Moni Naor는 암호학적으로 안전한 가성수 생성기로부터 비트 커밋 체계를 만드는 방법을 보여주었다.^[17] 공사는 다음과 같다. G가 n비트를 3n비트로 가져오는 의사 임의 생성기인 경우 앨리스가 비트 b에 커밋하기를 원하는 경우:

• 밥은 임의의 3n비트 벡터 R을 선택해서 앨리스에게 R을 보낸다.
• 앨리스는 임의의 n비트 벡터 Y를 선택하고 3n비트 벡터 G(Y)를 계산한다.
• b=1 앨리스가 G(Y)를 밥에게 보내고, 그렇지 않으면 G(Y)와 R의 비트 배타적 배타적(B)을 밥에게 보낸다.

앨리스는 사용을 중지하기 위해 Y를 밥에게 보내고, 밥은 그가 처음에 G$({\displaystyle }$Y)를 받았는지 G(Y)$$or {\$displaystyle \oplus }$을 받았는지 확인할 수 있다.

이 계획은 통계적으로 구속력이 있는데, 이는 앨리스가 계산적으로 무한하다고 해도 2 이상의⁻ⁿ 확률로 부정행위를 할 수 없다는 것을 의미한다. 앨리스가 속이기 위해서는 G(Y') = G(Y) = G(Y) $\oplus {\displaystyle }$ ${\displaystyle \oplus }$과 같은 Y'를 찾아야 할 것이다. 만약 그녀가 그러한 값을 찾을 수 있다면 진실과 Y를 보내서 불매운동을 하거나, 정반대의 대답과 Y'를 보낼 수도 있다. 그러나 G(Y)와 G(Y')는 각각 2개의ⁿ 가능한 값(즉, 2)만²ⁿ 생성할 수 있고 R은 2개의³ⁿ 값 중에서 선택된다. 그녀는 R을 선택하지 않기 때문에 부정행위에 필요한 방정식을 만족시키는 Y'가 존재할 확률은 2²ⁿ/2³ⁿ = 2이다⁻ⁿ.

은폐 속성은 앨리스가 0을 범했는지 아니면 1을 범했는지 알 수 있다면, 밥이 사이비 무작위 발생기 G의 출력과 G의 암호 보안에 모순되는 참 무작위 생성기 G의 출력도 구별할 수 있다.

이산 로그 문제를 기반으로 한 완벽한 바인딩 방식 및 그 이상

앨리스는 g의 승수 발생기를 가진 primary order p의 고리를 선택한다.

앨리스는 0에서 p - 1까지의 비밀 값 x를 임의로 선택하여 c = g를^x 계산하여 c를 발행한다. 이산 로그 문제는 c로부터 계산적으로 x를 계산할 수 없기 때문에 이 가정 하에서 밥은 x를 계산할 수 없다. 반면에 앨리스는 g^x' = c와 같은 x' <> x를 계산할 수 없기 때문에 계획은 구속력이 있다.

이 계획은 만약 그가 별개의 로그 문제를 해결한다면 누군가가 약속을 찾을 수 있기 때문에 완벽하게 은폐되지 않는다. 사실, 이 계획은 표준 은닉 게임과 관련해서 전혀 숨기지 않고 있는데, 이 게임에서 적수는 자신이 선택한 두 개의 메시지 중 어떤 것을 선택했는지 추측할 수 있어야 한다 - 바로 IND-CPA 게임과 유사하다. 이것의 한 가지 결과는 x의 가능한 값의 공간이 작을 경우 공격자는 단순히 모든 값을 시도할 수 있고 그 약속이 숨겨져 있지 않을 것이라는 것이다.

완벽하게 바인딩된 약속 체계의 더 좋은 예로는, 완벽한 완성도를 가진 의미론적으로 안전한 공개키 암호화 체계 하에서 x의 암호화가 있고, 무제한화는 x를 암호화하는 데 사용되는 랜덤 비트의 문자열이다. 정보-이론적으로 숨기기 약속 체계의 예는 분리된 로그 가정 하에서 구속력이 있는 페더슨 약속 체계가 있다. 위의 계획 외에도, 그것은 프라임 그룹의 또 다른 발전기 h와 임의의 숫자 r을 사용한다. ${\displaystyle {커밋}^{}}$은${\displaystyle }$c = ${\displaystyle g^{}}$ x$$h r {\$displaystyle$ c$=g^{x}h^{$r}}}}"로 설정된다$.$^[18]

이러한 구조는 기초 집단의 대수적 특성과 밀접하게 관련되고 기초가 되며, 그 개념은 원래 대수와 매우 관련이 있는 것 같았다. 그러나 통계적으로 구속력이 있는 약정 체계를 일반적 구조화되지 않은 가정에 기초하는 것은 (특히 단방향 순열화에 기초하여) 일반적 복잡성 가정(특정적으로 그리고 원래)의 약정에 대한 쌍방향 해싱 개념을 통해 가능한 것으로 나타났다.^[19]

부분 공개

일부 약속 체계는 약속된 가치의 일부만 증명할 수 있도록 허용한다. 이러한 체계에서 비밀 값 $X{\displaystyle }$ ${\displaystyle X}$은(는) 개별적으로 분리할 수 있는 많은 값의 벡터다$$.

${\displaystyle X=(x_{1},x_{2},...,x_{n}}})$

커밋 $단계$의 $X{\displaystyle }$ ${\$$displaystyle C}$에서 커밋 C {\$displaystyle$ C$}$을(를) 계산한다$$. 일반적으로 공개 단계에서 프로베러는 $모든{\displaystyle }$ X ${\displaystyle X}$ 및$$ 일부 추가 증거 데이터(예: 단순$$ $비트{\displaystyle }$커밋의 R {\$displaystyle$ R$})$를 공개한다. 대신 프로베러는 $X{\displaystyle }$ ${\displaystyle X}$ 벡터에서$$ 단일 값을 나타낼 수 있으며, 약속 $C{\displaystyle }$ ${\displaystyle C}$을(를) 생성한 원래 벡터의 정통 $i{\displaystyle }$ ${\displaystyle$i$}$요소라는 효율적인 증거를 생성할 수 있다$.$ 증명에는 x$$ ${\displaystyle i_{}}$ ${\$ 이외의$$ X ${\displaystyle x_{$i}의 값을 밝힐 필요가 없으며, 실제 값과 $다른$ x ${\displaystyle i_{}}$ ${\$의 값을 나타내는 유효한 증명서를 만드는 것은 불가능하다.^[20]

벡터 해싱

벡터 해싱은 비트 커밋에 기반한 순진한 벡터 커밋 부분 노출 체계다. 값 $m{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$m ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle }$.${\displaystyle }$. .${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$$m_{n}}}$는 임의로 선택한다. 개별적인 약속은 $해싱{\displaystyle {}_{}}$ ${\displaystyle {y\mathrm{}}_{}}$1 = ${\displaystyle H}$( ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {m\mathrm{}}_{}}$1${\displaystyle }$) , ${\displaystyle {}_{}{2\mathrm{}}_{}}$ = ${\displaystyle H}$( ${\displaystyle {}_{}}$ 2 ${\displaystyle m{}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$)${\displaystyle }$,${\displaystyle }$.${\displaystyle }$. . . . $.\displaystyle y_{1}=H(x_{1} m_{1$}), $y_{2}=H(x_{2$} $m_{2$}), $...}$ . . 전체적인 약속은 다음과 같이 계산된다$.$

${\displaystyle C=H(y_{1} y_{2}... y_{n}}}$

벡터 $X{\displaystyle }${\$displaystyle X}$의 한 요소를 입증하기 위해 프로베르는 값을 표시한다$.$

${\displaystyle(i,y_{1},y_{2},...,y_{i-1},x_{i},m_{i},y_{i+1},...,y_{n}}}}}$

검증자는 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 및$$ ${\displaystyle m_{}}$ i ${\$에서 y ${\displaystyle i_{}}$ ${\$y}을$($를) 계산할 수 있으며$,$ 이후 모든 $y{\displaystyle }$ ${\displaystyle y}$ 값의$$ 해시가 약속 $C{\displaystyle }$ ${\displaystyty$ C$}$인지 확인할 수 있다$.$ 증명서가 크기 및 검증 ${\displaystyle \mathrm{시간}}$에서 O${\displaystyle }$($n$${\displaystyle }$) ${\디스플레이$ 스타일 $O(n)}$이기 때문에 이 계획은 비효율적이다. 또는 $C{\displaystyle }$ ${\displaystyle C}$이(가) $모든{\displaystyle }$ y ${\displaystyle y}$ 값의$$ 집합인 경우 ${\displaystyle \mathrm{커밋}}$은 O$$${\displaystyle }$( n${\displaystyle }$) ${\displaystyle$ O$(n)$이고, 증명서는 크기 및 검증 시간의$$ $O{\displaystyle }$( ${\displaystyle 1}$) ${\displaysty$ O$(1)}$이다. 어느 쪽이든 약속 또는 증명은 $O{\displaystyle (n}$) ${\displaystyle O(n)}$로 척도한다$.$

머클 트리

A common example of a practical partial reveal scheme is a Merkle tree, in which a binary hash tree is created of the elements of ${\displaystyle X}$. This scheme creates commitments that are ${\displaystyle O(1)}$ in size, and proofs that are ${\displaystyle O(\log _{2}{n})}$ in size and verificati정시에 트리의 루트 해시는 약속 $C{\displaystyle }$ ${\displaystyle C$ 공개된 ${\displaystyle x_{}}$ $i{\displaystyle {}_{}}$ ${\$가 원본$$ 트리의 일부임을 증명하려면 각 레벨에서 하나씩 트리의 해시$$ 값 ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}n}$ ${\$만 증거로 밝혀야 한다. 검증자는 청구된 리프 노드에서 루트까지의 경로를 따라갈 수 있으며, 각 수준에서 형제 노드에 해싱되며, $결국{\displaystyle }$ C ${\displaystyle C}$와 같아야 하는 루트 노드 값에 도달할 수 있다$.$^[21]

KZG 공약

Kate-Zaverucha-Goldberg 약속은 쌍을 이루는 기반 암호법을 사용하여 $O{\displaystyle }$( ${\displaystyle 1}$) ${\displaystyle O(1$) 약속$$ 크기, 증명 크기 및 증명 검증 시간을 가진 부분 공개 체계를 구축한다. 즉, $n{\displaystyle }$ ${\displaystyle n}$이$($가)$$증가함에 $따라$ X {\displaystyle $X$의 값 수가 증가하고, 약속과 증명이 커지지 않으며, 증명은 더 이상 검증에 노력을 기울이지 않는다.

KZG 커밋에는 페어링을 생성하기 위해 미리 결정된 매개변수 집합과 신뢰할 수 있는 트랩도어 요소가 필요하다. 예를 들어, 테이트 페어링을 사용할 수 있다. $G{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$,${\displaystyle {}_{}{\mathbb{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$}}이$$ 가법 $그룹$이고 ${\displaystyle {}_{}}$ T ${\$가 쌍의 승법 그룹이라고$$ 가정하자. In other words, the pairing is the map ${\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{T}}$. Let ${\displaystyle t\in \mathbb {F} _{p}}$ be the trapdoor element (if ${\displaystyle p}$ is the prime order of ${\displaystyle \mat$$hbb {G} _{1}$${\displaystyle {}_{}}$ $G{\displaystyle {\mathbb{}}_{}}$ 2 ${\$ $_$${2}}:$ 그리고 $G{\displaystyle }$ ${\displaystyle G}$과 H ${\displaystyle H}$을(를$)$ 각각 G ${\displaystyle {\mathrm{}}_{}}$ ${\$$displaystysty \mathb$ {$G} _{1}$의 생성자가 되도록$$ 한다. 매개변수 설정의 일부로서, 우리는 $G{\displaystyle }$ t i {\$displaystyle$G\$cdot$ t$^{i$$}$ 및 H${\displaystyle t^{}}$ t i$$${\displaystyle$ H$\cdot$ t$^{i$$}}$가 $임의$로 많은 i의 양의 정수 값에 대해 알려져 있고 공유된 값을 트랩도어 $값{\displaystyle }$ t$${\$displaysty t}$ 자체가$$ 폐기되고 아무도 알 수 없다고 가정한다$.$

커밋

KZG 공약은 다항식으로서 커밋될 값의 벡터를 개혁한다. 먼저, 벡터에 있는$$ ${\displaystyle x_{}}$ i ${\$$(i)=x_$${i}$의 모든 값에 $대해$ p${\displaystyle (}$ i${\displaystyle }$)${\displaystyle }$= ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$ ${\$ p(i)=x_{$i}}}$와 같은 다항식을 계산한다. 라그랑주 보간법으로 다항식 계산 가능

${\displaystyle p(x)=\sum _{i=0}^{n-1}x_{i}\prod _{0\leq j<n,j\neq i}{\frac {x-j}{i-j}}}}}}}$

Under this formulation, the polynomial now encodes the vector, where ${\displaystyle p(0)=x_{0},p(1)=x_{1},...}$. Let ${\displaystyle p_{0},p_{1},...,p_{n-1}}$ be the coefficients of ${\displaystyle p}$, such that $p(x)=\sum _{i=0}^{n-}$$\underset{}{\overset{}{}}{}_{}$ $i_{}$ ${}_{}{}^{}$ $i^{}$ ${\$ 약속은 다음과 같이 계산된다.

${\displaystyle C=\sum _{i=0}^{n-1}p_{i}Gt^{i}}}}$

이것은 단순히 미리 결정된 $값{\displaystyle }$ G ${\displaystyle \cdot }$ ${\displaystyle t^{}}$ i ${\$와 다항 계수 $p{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 사이에 도트 곱으로 계산된다$.$ ${\displaystyle {\mathrm{}}_{}}$ 1 ${\$1}는 연관성과$$ 동시성을 갖는 첨가 그룹이기 때문에 C ${\displaystytype C}$는 동일하다. $G{\displaystyle }$ ${\displaystyle G}$을(를) 사용한 모든 추가 및 승수는 평가에서 배포할 수 있으므로$$ 단순하게 ${\displaystyle G}$ ${\displaystyle \cdot }$ p${\displaystyle }$( ${\displaystyle t}$) ${\displaystyle$G$}$ {\$cdot p$(t$)\}.$ 트랩도어 값 $t{\displaystyle }$ ${\displaystyle t}$을(를) 알 수 없으므로$$, $약속{\displaystyle }$ C$${\$displaystyle C}$은(는) 그 결과가 G ${\displaystyle {\mathrm{}}_{}}$ ${\$1}의 불투명 요소로 난독화되면서 기본적으로 아무도 알 수 없는 숫자로 평가되는 다항식이다$.$

드러내다

KZG 증명서는 $C{\displaystyle }$ ${\displaystyle$ C$}$이(가) 계산되었을$$ 때 노출된 데이터가$$ $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 실제 값임을 입증해야 한다. let $y{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 우리가 증명해야 할 공개 값$.$ $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 벡터가 다항식으로 개편되었기$$ 때문에, $i{\displaystyle }$ ${\displaystyle i}$에서 평가했을 때$$다항식 $p{\displaystyle }$ ${\displaystyle$ y$}$의 $값$이 y ${\\displaystyle$ y}을(를) 차지한다는$$ 것을 정말로 증명해야 한다$.$ 단순하게, ${\displaystyle p}$( ${\displaystyle i}$)${\displaystyle }$= y = ${\displaysty)$ = {\$displaysty$o $p{\displaystyle }$ ${\displaystyle p}$에서 y ${\displaystyle y}$을(를) 빼면 $i{\displaystyle }$ ${\displaystyle i}$에서 0이 된다는 것을 입증함으로써$$ 이를 증명함$.$ 다항식 $q{\displaystyle }$ ${\displaystyle q}$을(를) 다음과$$ 같이 정의하십시오.

${\displaystyle q(x)={\frac {p(x)-y}{x-i}}}$

This polynomial is itself the proof that ${\displaystyle p(i)=y}$, because if ${\displaystyle q}$ exists, then ${\displaystyle p(x)-y}$ is divisible by ${\displaystyle x-i}$, meaning it has a root at ${\displaystyle i}$, so ${\displaystyle p(i)-y=0}$ (or, in other 단어, $p{\displaystyle }$( ${\displaystyle i}$)${\displaystyle }$= ${\displaystyle y}$ ${\displaystyle p(i)=y}$ $$. KZG 증명서는 $q{\displaystyle }$ ${\displaystyle q}$이(가) 존재하고$$ 이 속성을 가지고 있음을 증명할 것이다.

프로베러는 위의 다항식 구분을 통해$$ $q{\displaystyle }$ ${\displaystyle q}$을(를) 계산한 다음 KZG 증명 값 $\pi {\displaystyle }$ ${\displaystyle \pi }$을(를) 계산한다.

${\displaystyle \pi =\sum _{i=0}^{n-1}q_{i}Gt^{i}}}}}$

이는 위와 같이 $G{\displaystyle }$ ${\displaystyle \cdot }$ ${\displaystyle q}$( ${\displaystyle t}$) ${\displaystyle G\cdot q(t)}$과 같다$.$ 즉, 증명 값은 G $1{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle$ t$}$에서 다시 평가된$$ 다항식 $q{\displaystyle }$ ${\displaystyle t$$}$이며$,$ G $1$ {\$displaystyle$ G$}$의 생성기 $G{\displaystyle }$ ${\$$displaystyle$G}에 숨겨져 있다$.$

이 계산은 위의 다항식들이 균등하게 분할될 경우에만 가능하다. 그 경우에 지수 $q{\displaystyle }$ ${\displaystyle q}$은 합리적인 함수가 아니라 다항식이기 때문이다. 트랩도어의 구성으로 인해 트랩도어 값에서 합리적인 함수를 평가할 수 없으며, $다만{\displaystyle }$ G${\displaystyle t^{}}$ t i$${\$displaystyle G\cdot$ t$^{i}}$의 사전 계산된 알려진 상수의 선형 조합을 사용하여 다항식을 평가해야 한다$.$ $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 잘못된 값에 대한 증거를 만들 수 없는 이유다$.$

검증하다

증거를 검증하기 위해 쌍의 이선형 맵을 사용하여 증명 값 $\pi {\displaystyle }$ ${\displaystyle \pi }$이(가) 원하는 속성을 보여주는$$ 실제 다항식 $q{\displaystyle }$ ${\displaystyle q}$을(를) 요약하고, $p{\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$- ${\displaystyle y}$ ${\$$displaystyp$ $p(x)-$$y}$을 $x{\displaystyle }$-$$로 균등하게 나누었다$.$ 검증 계산은 동등성을 점검한다.

$#\displaystyle e(\pi ,H\cdot t-H\cdot i)\\\\stackrel {?}}{=}\ e(C-G\cdot y,H)}$

여기서 $e{\displaystyle }$ ${\displaystyle e}$은(는) 위와 같은 이선형 맵 함수다. ${\displaystyle H}$ ${\displaystyle \cdot }$ ${\displaystyle t}$ ${\displaystyle H\cdot$ $t$$}$은(는) 사전 계산된 ${\displaystyle \mathrm{상수}}$이고, $H{\displaystyle }$ ${\displaystyle \cdot }$ i ${\displaystyle H\cdot$ i$}$은(는) $i{\displaystyle }$ ${\displaysty i}$을(를) 기반으로 계산된다$.$

By rewriting the computation in the pairing group ${\displaystyle \mathbb {G} _{T}}$, substituting in ${\displaystyle \pi =q(t)\cdot H}$ and ${\displaystyle C=p(t)\cdot G}$, and letting ${\displaystyle \tau (x)=e(G,H)^{x}}$ be a helper function for lifting 페어링 그룹 내에서, 증명 검증은 더 명확하다.

${\displaystyle e(\pi ,H\cdot t-H\cdot i)=e(C-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot t-H\cdot i)=e(G\cdot p(t)-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot (t-i)=e(G\cdot (p(t)-y)),H)}$

${\displaystyle e(G,H)^{q(t)\cdot(t-i)}=e(G,H)^{p(t)-y}}$

$\displaystyle \tau(q(t)\cdot(t-i))=\tau(p(t)-y)}$

이선형 지도가 유효하게 구성되었다고 가정할 때, 이는 $검증자$가 p ${\displaystyle p$} 또는$$ $q{\displaystyle }${\$displaystyle q}$이(가) 무엇인지$$ 알 수 없는 $상태$에서${\displaystyle q}$($x$-${\displaystyle }$i${\displaystyle }$) =${\displaystyle p}$ ($x)$ - $y}$을$($가) 증명한다. 만약 $\tau {\displaystyle }$( ${\displaystyle q}$(${\displaystyle t}$ )${\displaystyle (}$ ( ${\displaystyle t}$-${\displaystyle i}$ )${\displaystyle }$=${\displaystyle (}$ ( ${\displaystyle p}$( ${\displaystyle t}$)${\displaystyle }$-${\displaystyle y}$ ) ${\displaystyle \tau (q(t)\cdot (t-i))$이면 검증자는 이를 확신할 수 있다.$=\tau(p(t)-y$ 그러면 다항식은 트랩도어 값 $x{\displaystyle }$= ${\displaystyle t}$ ${\displaystyle$ x$=t}$에서 동일한 출력으로 평가된다$.$ 이것은 매개변수가 유효하게 구성되었다면 트랩도어 값은 아무도 알 수 없기 때문에 (슈워츠-지펠 보조마사에 따르면) 트랩도어에서 특정 값을 가지도록 다항식을 엔지니어링하는 것은 불가능하기 때문에 다항식이 동일하다는 것을 보여준다. If ${\displaystyle q(x)(x-i)=p(x)-y}$ is now verified to be true, then ${\displaystyle q}$ is verified to exist, therefore ${\displaystyle p(x)-y}$ must be polynomial-divisible by ${\displaystyle (x-i)}$, so ${\displaystyle p(i)-y=0}$ due to the f배우의 정리 $이$는 커밋된 벡터의 i ${\displaystyle i$$}$ 값이$$ $i{\displaystyle }$ ${\displaystyle$i}에서 커밋된 다항식을 평가하는 출력이기 때문에 y ${\displaystyle y}$과 동일해야 함을 증명한다$.$

$또한{\displaystyle }$ KZG 확약을 확장하여 $X{\displaystyle }$ ${\displaystyle$ X$}($단 하나의 값이 아님)의 $임의{\displaystyle }$ k ${\displaystyle$ $k$$}$ 값을$$ 증명할 수 있으며,${\displaystyle \mathrm{교정}}$크기는 O$$( 1 ) {\$displaystyle$ O$(1$로 남아 있지만, 교정 $확인{\displaystyle }$ 시간은${\displaystyle O}$( k$$) {\$displaystystyle$ O$(k$)로 스케일된다$.$ 증거는 동일하지만 $상수{\displaystyle }$ y ${\displaystyle y}$을$($를) 빼는 대신, 우리는 증명하고자 하는 모든 위치에서 복수의 뿌리를 일으키는 다항식을 빼내고, $x{\displaystyle }$- i ${\displaystyle x-i}$로 나누는 대신, 동일한 위치에 대해$$ $\prod \underset{}{}$ $\underset{}{}$ - $i$ - i - i -$$\$textstyle \prod _{i}x-i}$로 나눈다.^[22]

양자 비트 약속

양자 레벨, 즉 계산 자원에 제한이 없더라도 (적어도 무증상적으로) 바인딩하고 은폐하는 프로토콜에 무조건적인 보안 비트 커밋 프로토콜이 존재한다면 양자암호학에서는 흥미로운 질문이다. 무조건적으로 안전한 키 분배를 위한 프로토콜에서처럼 양자역학의 본질적인 속성을 이용할 수 있는 방법이 있을지도 모른다고 기대할 수 있다.

그러나 도미니크 메이어스가 1996년에 보여줬듯이 (원래 증거를 보려면 참조) 이것은 불가능하다. 그러한 프로토콜은 앨리스가 커밋하고 싶은 비트에 따라 커밋 단계 이후 시스템이 두 개의 순수한 상태 중 하나에 있는 프로토콜로 축소될 수 있다. 만약 그 규약이 무조건 은폐된다면 앨리스는 슈미트 분해의 특성을 이용하여 이들 상태를 단위적으로 서로 변형시켜 결합 성질을 효과적으로 물리칠 수 있다.

증거에 대한 한 가지 미묘한 가정은 커밋 단계가 어느 시점에 끝나야 한다는 것이다. 이는 비트가 공개되거나 프로토콜이 취소될 때까지 지속적인 정보 흐름을 필요로 하는 프로토콜에 대한 여지를 남긴다. 이 경우 프로토콜은 더 이상 구속력이 없다.^[24] 보다 일반적으로 메이어스의 증거는 양자물리학을 이용하는 프로토콜에만 적용되지만 특수상대성이론에는 적용되지 않는다. 켄트는 정보가 빛보다 더 빨리 이동할 수 없다는 특수상대성이론의 원리를 이용하는 비트 약속에 대해 무조건적으로 안전한 프로토콜이 존재한다는 것을 보여주었다.^[25]

물리적 비클론적 기능에 기반한 약속

물리적 PUF(Clonnable Function)는 복제하거나 에뮬레이트하기 어려운 내부 무작위성을 가진 물리적 키의 사용에 의존한다. 전자, 광학 및 기타 유형의 PUF는^[26] 약속 체계를 포함한 잠재적 암호화 애플리케이션과 관련하여 문헌에서 광범위하게 논의되었다.^[27][28]

참고 항목

• 망각 전이
• 축전기(암호화)
• 키 서명파티
• 신뢰의 거미줄
• 제로코인

참조

외부 링크

• arxiv.org의 Quantum 비트 커밋
• 케이트-자베루차-골드버그(KZG) 일정 크기의 다항식 약속 - 알린 토메스쿠
• 케이트 다항식 공약