축전기(암호화)

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오. (2021년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

암호학에서 축전지는 단방향 멤버십 해시함수다. 그것은 사용자가 세트의 개별 구성원을 밝히지 않고 잠재 후보자가 특정 세트의 구성원임을 인증할 수 있도록 한다. 이 개념은 1993년 조시 베날로와 마이클 드 마레에 의해 정식으로 소개되었다.^[1][2]

형식 정의

문헌에는 몇 가지 형식적인 정의가 제시되어 있다. 이 절에는 제안자별로 대략 연대순으로 나열되어 있다.^[2]

베날로와 데 마레(1993)

Benaloh와 de Mare는 ^[1][2]단방향 해시함수를 함수 h ${\displaystyle h_{}{}_{}}$: ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\ell }_{}}$→ Z ${\displaystyle {\ell }_{}}$ ${\${\ell }\time Y_${\ell }\to Z_{\ell$ }\ell$$$$}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

1. For all ${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y\in Y_{\ell }}$, one can compute ${\displaystyle h_{\ell }(x,y)}$ in time ${\displaystyle {\text{poly}}(\ell , x , y )}$. (Here the "poly" symbol refers to an unspecified, but fix에드, 다항식)
2. No probabilistic polynomial-time algorithm will, for sufficiently large ${\displaystyle \ell }$, map the inputs ${\displaystyle \ell \in \mathbb {Z} ,(x,y)\in X_{\ell }\times Y_{\ell },y'\in Y_{\ell }}$, find a value ${\displaystyle x'\in X_{\ell }}$ such 그 $h{\displaystyle {}_{}}$ ${\displaystyle \ell {}_{}}$( x${\displaystyle }$, ${\displaystyle y}$)${\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {}^{}{}_{}}$( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$, y ${\displaystyle {\prime }^{}}$) ${\displaystyle h_{\ell }(x,y)=h_{\ell }}(x',y')}}$이(가) 무시해도 될 정도의 확률이다$$.
3. For all ${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y_{1},y_{2}\in Y_{\ell }}$, one has ${\displaystyle h(h(x,y_{1}),y_{2})=h(h(x,y_{2}),y_{1})}$. (A function that satisfies this property is called quasi-com돌연변이)

(처음 두 개의 속성으로, 암호 해시함수의 정상적인 정의를 회복한다.)

From such a function, one defines the "accumulated hash" of a set ${\displaystyle \{y_{1},\dots ,y_{m}\}}$ w.r.t. a value ${\displaystyle x}$ to be ${\displaystyle h(\dots h(h(x,y_{1}),y_{2}),\dots ,y_{m})}$. (This does not depend on the order of e$h{\displaystyle }$ ${\displaystyle h}$이(가) 준법률이기 때문에 임대.^[1][2]

바리치와 피츠만(1997)

준확정 해시함수의 기본 기능성은 정의에서 바로 나오는 것이 아니다. 이를 해결하기 위해 바리치와 피츠만은 약간 더 일반적인 정의를 정의했는데, 이는 축전지 체계의 개념으로 다음과 같은 구성요소로 구성된다.^[2][3]

1. Gen: $두{\displaystyle }$ 개의 매개 변수 ${\displaystyle ▼,}$ ${\displaystyle N}$ ${\displaystyle \lambda, N}($각각 보안 매개 변수와 안전하게 누적될 수 있는 값 수)를 취하여 적절한 $키{\displaystyle }$ k ${\displaystyk}$를 반환하는 확률 알고리즘$.$
2. Eval: a probabilistic algorithm that takes in a key ${\displaystyle k}$ and accumulation set ${\displaystyle Y:=\{y_{1},\dots ,y_{N'}\}}$, where ${\displaystyle N'\leq N}$, and returning an accumulated value ${\displaystyle z}$ and auxiliary information ${\displayst$$yle aux}$. 우리는 Eval이 $z{\displaystyle }$ ${\displaystyle z}$에 대한 결정론적이어야 한다고 주장한다$.$
3. Witt: $키{\displaystyle }$ k$${\$displaystyle k$ 값 $y{\displaystyle }$${\$$displaystyle$$$y$\},$ 일부 $세트{\displaystyle }$ Y의$$ $누적{\displaystyle }$값 z {\$displaystyle$ $z}$$$및 일부 보조 $정보$는 ${\displaystyle u}$ x ${\displaystyle$ $aux$$\}$을(으)로 가져와서 $w{\displaystyle }$ ${\displaystystyle$ w$}$ 또는$$ 특수 공모를 반환하는 확률 알고리즘l $\perp {\displaystyle \mathrm{}}$ ${\displaystyle \bot$ $\}.$ 우리는 만약 ${\displaystyle y}$ ${\displaystyle \in }$ L ${\displaystyle y\in L}$이$($가) 있다면, Witt가 증인을 반환하고, 그렇지 않으면 Witt가 $\perp {\displaystyle \mathrm{}}$ ${\displaysty \bot }$을(가) 반환한다고 주장한다$.$
4. Ver: 키 $k{\displaystyle }$ ${\displaystyle$ $k$$\},$ $값{\displaystyle }$ y ${\displaystyle$ y$\},$ $감시{\displaystyle }$ w ${\displaystyle w},$ 누적 $값{\displaystyle }$ z ${\displaysty$ z$}$을$($를) 취하여 Yes/No 값을 반환하는 결정론 알고리즘. We insist that if ${\displaystyle w}$ was generated from running Wit on a tuple ${\displaystyle (k,y,z,aux)}$, where ${\displaystyle z,aux}$ were generated from running Eval on some ${\displaystyle k,L}$, and where ${\displaystyle L}$ was chosen arbitrarily and ${\displ$$aystyle k}$은(는) 실행 중인 Gen에서 선택되었으며$$ Ver는 항상 Yes를 반환한다.

위에 나타낸 기법을 사용하여 어떤 준확정 해시함수에서도 축전기 방식을 정의할 수 있다는 것을 비교적 쉽게 알 수 있다.^[2]

카메니슈·리시얀스카야(2002)

하나는 많은 응용 프로그램의 경우 누적된 값 집합이 여러 번 변경될 것이라고 관측한다. Naïvely는 매번 축전지 계산을 완전히 다시 할 수 있지만, 특히 우리 세트가 매우 크고 변화가 매우 작을 경우, 이것은 비효율적일 수 있다. 이러한 직관을 공식화하기 위해 카메니쉬와 라이산스카야는 일반적인 축전지 계획의 4가지 구성 요소와 3가지 더 많은 구성 요소로 구성된 동적 축전지 체계를 정의했다.^[2][4]

1. 추가: 키 $k{\displaystyle }$ ${\displaystyle$ k$\},$ 누적 $값{\displaystyle }$ z ${\$$displaystyle$ z$}$$$및 다른 값을 입력하여 $y{\displaystyle }$ {\$displaystyle$ y}을$($를) 누적하고 새 누적 $값{\displaystyle {}^{}}$ z ${\displaystyle {\prime }^{}}$ ${\$과 보조 정보를 ${\displaystyle u}$ ${\displaystystyle o}$을(가)하는 (확률적으로) 알고리즘$.$ $우리$는 z ${\displaystyle$ z$}$이(가) 어떤 세트 $L{\displaystyle }$ ${\displaystyle L}$을$($를) 누적하여 생성된 경우$$, $z{\displaystyle {}^{}}$′ ${\$z'}은$($는) $세트{\displaystyle }$ L${\displaystyle }$∪${\displaystyle }${ ${\displaystyle y\}}$ ${\displaystyle L\cup$\cup \{$y\}}}}}}$을 누적하여 생성된 것과 같아야 한다고$$ 주장한다$.$
2. 델: 키 $k{\displaystyle }$ ${\displaystyle k$ 누적 $값{\displaystyle }$ z ${\displaystyle z$$}$$$및 다른 $값$을 입력하여$$y {\$displaystyle$ y}을(를$)$ 누적하고 새 누적 $값{\displaystyle {}^{}}$ z ${\displaystyle {\prime }^{}}$ ${\$과 보조 정보를 ${\displaystyle u}$ ${\displaystystyle o}$을(가)하는 (확률적으로) 알고리즘$.$ $우리$는 z ${\displaystyle$ z$}$이(가) 어떤 세트 $L{\displaystyle }$ ${\displaystyle L}$을$($를) 누적하여 생성된 경우$$, $z{\displaystyle {}^{}}$′ ${\$은(는) $세트{\displaystyle }$ L${\displaystyle \mathrm{}}$∖${\displaystyle }${ ${\displaystyle y\}}$ ${\displaystyle L\backslash \{y\}}$을 누적하여 생성된 것과 같아야 한다고$$ 주장한다$.$
3. Updates: $키{\displaystyle }$$$k {\$displaystyle$$$k}, $값{\displaystyle }$y {\$displaystyle$ y$\},$ $목격자{\displaystyle }$ $w{\displaystyle }$ ${\displaystyle$ $w$$\},$ 누적 값$$z {\$displaystyle$ z$\},$ 보조 ${\displaystyle \mathrm{정보}}$$u{\displaystyle {}^{}}$ ${\displaystyle x}$ $displaysty$$$aux$},$ 그리고 if의 새로운 증인을 반환해야 함$.$${\displaystyle k}$ ${\displaystyle k}$은(는) Gen에 의해 생성되었으며, $y{\displaystyle }$ ${\$$displaystyle y$$}$은(는) $집합{\displaystyle }$ L$$${\$displaystyle $L$$}$의 $일부분$이며$,$ w$${\$displaystyle$$$w$}$은(는) L$${\$displaystystyle$$$L$\}$의 $멤버$인$$y {\$d$의 $증인$이며, z$}$의 누적 값이다$.$$isplaystyle aux}$은(는) Add 또는 Del을 실행하여 생성된 다음 $w{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ w$'}$이(가) 새 집합의 $멤버$인 y ${\displaystyle y}$의 증인이 된다.

Fazio와 Nicolosi는 Add, Del, Upd는 Eval과 Wit를 다시 실행하여 시뮬레이션할 수 있으므로 이 정의는 근본적으로 새로운 기능을 추가하지 않는다고 언급한다.^[2]

예

하나의 예는 큰 소수보다 곱하기입니다. 이것은 암호 축전지로, 복합수를 인자화하는 데는 초폴리놀리컬 시간(최소한 추측에 따라)이 걸리지만, 프라임을 인자의 하나인지 확인하고/또는 인자를 인자화하는 데 있어서 정수로 나누는 데는 소량의 시간(규모의 폴리놀리컬)밖에 걸리지 않는다. 새로운 구성원은 각각 숫자를 곱하거나 인수하여 요인 집합에 추가 또는 감산할 수 있다. 이 시스템에서 단일 공유 프라이밍을 축적한 두 축전지는 프라이밍에 대한 사전 지식이 없어도(그렇지 않으면 축전지의 프라이밍 인자화가 필요함) GCD를 계산하여 사소한 발견을 할 수 있다.^{[citation needed]}

보다 실용적인 축전지는 준확정 해시함수를 사용하므로 축전지의 크기가 회원수와 함께 커지지 않는다. 예를 들어, Benaloh와 de Mare는 RSA에서 영감을 받은 암호 축전지를 제안한다: 준확정 함수 $h{\displaystyle (}$ x${\displaystyle }$, ${\displaystyle y}$) ${\displaystyle :=}$ ${\displaystyle {}^{}}$ ${\displaystyle y^{}{}^{}}$(${\displaystyle mod}$ n$){\$$=x^{y}{\pmod{n}$ 일부 복합 번호 $n{\displaystyle }$ ${\displaystyle$ n$}$의 경우$$ $.$ 그들은 $n{\displaystyle }$ ${\displaystyle n}$을(를) 경직된 정수(즉, 두 개의 안전한 프라임의 산물로 선택할 것을 권장한다.^[1] 바리치와 피츠만은 $y{\displaystyle }$ ${\displaystyle y}$이(가) prime으로 제한되고$$ 최대 ${\displaystyle n\mathrm{}}$/ 4 ${\displaystyle n/4}($이 상수는 $\varphi {\displaystyle }$ ${\displaystyle (n}$)$$${\displaysty$ $\phi ($$n)}$에 매우 가깝지만 $n$의 primary factorization에 대한 정보를 누설하지 않는 변형을 제안했다.$$^[2][3]

David Naccache는 ${\displaystyle {\mathrm{1993년}}_{}}$에 e $n{\displaystyle {}_{}}$, c${\displaystyle {}_{}}$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle :=}$ x ${\displaystyle y^{}}$ ${\displaystyle y^{}}$ -${\displaystyle 1^{}{}^{}}$(${\displaystyle \mathrm{모드}}$ ${\displaystyle n}$) ${\$$=x^{y}c^{y-1}{\pmod{n}}}$은(는) 모든 상수 $c{\displaystyle }$, ${\displaystyle n}$ ${\displaystyle c,n}$에 대한 준 커맨티브로$$$,$ 이전 RSA에서 영감을 받은 암호화 축전지를 일반화한다. 나카체도 딕슨 다항식들이 정도에서는 준확정적이라는 점에 주목했지만, 이 함수 계열이 일방통행인지는 알 수 없다.^[1]

1996년에 Nyberg는 임의의 오라클 모델에서 이론적으로 안전한 정보로 축적기를 건설했다. Choosing some upper limit ${\displaystyle N=2^{d}}$ for the number of items that can be securely accumulated and ${\displaystyle \lambda }$ the security parameter, define the constant ${\displaystyle \ell :\approx {\frac {e}{\log _{2}(e)}}\lambda N\log _{2}(N)}$ to는 $d{\displaystyle }$ ${\dapplaystyle d}$의 정수 배수가 되고($$그러므로 $\ell {\displaystyle }$= r ${\displaystyle d}$ ${\d$ 디스플레이style $\ell =rd$ H${\displaystyle }$:${\displaystyle }${ 0${\displaystyle ,}$ 1${\displaystyle {}^{\ast }}$→${\displaystyle }${$0,$1\}^{*}\$to$\,{0$,1$\}^{\ell$}}}}}}}$은 암호화된 보안 해시함수가 되도록$$ 한다. 키 $k{\displaystyle }$ ${\displaystyle$k}을$($를) 임의 $r{\displaystyle }$ ${\displaystyle r}$ -비트$$ 비트 문자열로$$ 선택하십시오. 그런 다음 Nyberg의 체계를 사용하여 축적하려면 준확정 해시함수 $h{\displaystyle (}$ ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle :=}$ x${\displaystyle {}_{}}$ ${\displaystyle r_{}}$ (${\displaystyle {}_{}}$H${\displaystyle }$( $){\displaystyle h(x,y$)를 사용하십시오$.$$=x\odot \alpha _{r}(H(y))}$, where ${\displaystyle \odot }$ is the bitwise and operation and ${\displaystyle \alpha _{r}:\{0,1\}^{\ell }\to \{0,1\}^{r}}$ is the function that interprets its input as a sequence of ${\displaystyle d}$-bit bitstrings of length ${\displaystyle r}$$$는 모든 0의 비트 문자열을 단일 0으로, 다른 모든 비트 문자열을 1로 교체하고 결과를 출력한다.^[2][5]

적용들

이 구간은 확장이 필요하다. 덧셈으로 도움도 된다(2021년 5월)

하버와 스토르넷타는 1990년에 암호 체인을 통해 축적기를 사용하여 문서의 타임스탬프를 기록할 수 있다는 것을 보여주었다. (이 개념은 암호 블록체인의 현대적 개념을 예상한다.)^[1][2][6] 베날로와 드 마레는 1991년 회진에서의 시간 단축에 기초한 대체 계획을 제안했다.^[1][7]

베날로와 드 마레는 축전지를 사용하여 나중에 많은 사람들이 서로를 알아볼 수 있다는 것을 보여주었다(파지오와 니콜로시는 이것을 "ID 에스크로" 상황이라고 부른다). 각 사람은 자신의 정체성을 $나타내는$ y ${\displaystyle y}$을(를) 선택하고, 그룹은 집단적으로 공공 축전조 $h{\displaystyle }${\$displaystyle h}$와 비밀 x$${\$displaysty x}$을(를) 선택한다$.$ 그런 다음, 그룹은 비밀 x$${\$displaystyle$ $}$ 및 공공 축전지와$$ 함께 그룹 전체의 모든 ID에 대한 해시함수와 누적 해시를 게시하거나 저장한다. 동시에 그룹의 각 구성원은 ID 값 $y{\displaystyle }$ ${\displaysty$y}와$$ 그룹 전체의 ID에 대한 누적 해시를 모두 유지한다. 회원. (대규모의 사람들이 서로를 신뢰하지 않거나, 축전지에 RSA에서 영감을 받은 축전지의 경우와 같이 암호화 트랩도어가 있다면, 그들은 안전한 다중작업 계산을 통해 축적된 해시를 계산할 수 있다.) 청구된 구성원이 나중에 실제로 그룹에 속했는지 확인하기 위해, 그들은 자신의 정체성과 개인 축적된 해시(또는 그것들의 제로 지식 증명)를 제시한다. 청구된 구성원의 신원을 축적하고 그룹 전체의 축적된 해시와 대조하여 확인함으로써, 누구든지 그룹의 구성원을 확인할 수 있다.^[1][2] 동적 축전지 체계를 사용하면 이후에 구성원을 추가하거나 제거하는 것이 추가로 쉽다.^[2][4]

암호화 축전기는 다른 암호화된 보안 데이터 구조를 구성하는 데도 사용될 수 있다.

• 바리치와 피츠만은 압축 속성을 악용해 일정한 공간만으로 페일스톱 서명을 구성할 수 있다는 것을 보여준다.^[2][3]
• Goodrich 등은 크기가 확실하고 효율적이며 동적으로 인증된 사전(신뢰할 수 없는 디렉토리가 멤버십 질의에 암호화된 검증 가능한 답변을 제공할 수 있도록 허용)을 구성했다.^[2][8]
• Papamantou 등에서는 암호화된 보안 해시 테이블을 구성했는데, 이 테이블의 기능은 원격으로 저장하면 인증할 수 있다.^[9]

비트코인 블록체인의 추적 가능한 연계를 없애기 위해 암호축적기를 사용하는 비트코인에 제로코인이 추가되면서 이 개념은 새롭게 관심을 받게 되었고, 이는 거래를 익명하고 더 사적인 것으로 만들 것이다.^[10][11][12] 구체적으로는 제로코인을 민트(생성)하기 위해, 은밀한 임의의 값을 가진 일련번호(모든 사용자가 정확한 포맷을 하는 한)에 대한 코인과 암호약속을 발행하고, 제로코인을 소비(재청구)하기 위해, 제로코인의 일련번호를 그들이 크노라는 비인터랙티브 영지식 증명서와 함께 발행한다.청구된 일련 번호와 관련된 일부 게시된 약속 중 w는 코인을 청구한다(NIZKP가 유효하고 일련 번호가 이전에 나타나지 않은 한 모든 사용자가 이를 수락함).^[10][11] 제로코인의 초기 제안 이후 제로카시 의정서에 의해 계승되어 현재는 완전한^{[weasel words]} 디지털 화폐인 제라코시로 발전하고 있다.^[13][14]

참고 항목

• 암호학
• 영지식증거

참조