네트워크 코딩을 위한 동형체 서명

네트워크 코딩은 정보 흐름을 극대화하는 네트워크 대역폭을 최적으로 사용하는 것으로 나타났지만, 그 계획은 네트워크 내 악의적인 노드에 의한 오염 공격에 본질적으로 매우 취약하다.쓰레기를 주입하는 노드는 많은 수신기에 빠르게 영향을 줄 수 있다.네트워크 패킷의 오염은 (한 개라도) 정직한 노드의 출력이 적어도 하나의 수신 패킷이 손상되면 손상되기 때문에 빠르게 확산된다.

공격자는 서명을 위조하거나 해시함수에 따라 충돌을 발생시켜 암호화해도 패킷을 쉽게 손상시킬 수 있다.이렇게 하면 공격자가 패킷에 액세스할 수 있고 패킷을 손상시킬 수 있는 능력을 갖게 된다.Denis Charles, Kamal Jain, Kristin Lauter는 오염 공격을 방지하기 위해 네트워크 코딩과 함께 사용할 새로운 동형 암호화 서명 체계를 설계했다.^[1]

서명의 동형성 속성은 노드가 서명 당국에 연락하지 않고 들어오는 패킷의 어떤 선형 조합에도 서명할 수 있게 한다.이 체계에서 노드가 패킷 생성에 어떤 선형 결합이 사용되었는지를 밝히지 않고 패킷의 선형 결합에 서명하는 것은 계산상 불가능하다.더욱이, 우리는 서명 체계가 이산 로그 문제와 계산된 타원곡선 Diffie–의 경도에 대한 잘 알려진 암호 가정 하에서 안전하다는 것을 증명할 수 있다.헬맨.

네트워크 코딩

Let $G{\displaystyle }$=${\displaystyle }$( V${\displaystyle }$, ${\displaystyle E}$) ${\displaystyle$ G$=(V,E)}$은 $V{\displaystyle }$ ${\displaystyle V}$이(가) 세트인 방향 그래프로서, 이 요소를 정점 또는 노드라고 하며, $E{\displaystyle }$ ${\displaystyle E}$은 순서가 지정된 정점 쌍의 집합으로, 호, 방향 에지 또는 화살표라고 한다.소스 $s{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle V}$ ${\displaystyle s\in V}$이(가) 파일 $D{\displaystyle }$ ${\displaystyle$ $D$$}$을(를) 정점의 세트$$ $T{\displaystyle }$ ${\displaystyle V}$ {\$displaystyle$ T\$subseteq V}$에 전송하려고$$ 한다.One chooses a vector space ${\displaystyle W/\mathbb {F} _{p}}$(say of dimension ${\displaystyle d}$), where ${\displaystyle p}$ is a prime, and views the data to be transmitted as a bunch of vectors ${\displaystyle w_{1},\ldots ,w_{k}\in W}$. The source then creates the augmented vectors ${\displaystyle v_{1},\ldots ,v_{k}}$ by setting ${\displaystyle v_{i}=(0,\ldots ,0,1,\ldots ,0,w_{i_{1}},\ldots ,w{i_{d}})}$ where ${\displaystyle w_{i_{j}}}$ is the ${\displaystyle j}$-th coordinate of the벡터 ${\displaystyle w_{}}$ $i{\displaystyle {}_{}}$ ${\$첫 ${\displaystyle {번째}_{}}$ '1$'$이 v i {\$displaystyle$ v_{$i}$에 나타나기 전에${\displaystyle }$(${\displaystyle \mathrm{i}}$- 1${\displaystyle }$) ${\displaystyle (i-1)$0이$$ 존재하며$,$ 벡터 $v{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$이(가) 선형적으로 독립되어 있다고$$ 가정할 수 있다.We denote the linear subspace (of ${\displaystyle \mathbb {F} _{p}^{k+d}}$ ) spanned by these vectors by ${\displaystyle V}$ . Each outgoing edge ${\displaystyle e\in E}$ computes a linear combination, ${\displaystyle y(e)}$, of the vectors entering the vertex ${\displays$즉, 가장자리가 발원하는 곳에$$ $v=in(e)}$을(를) $붙인다$.

${\displaystyle y(e)=\sum _{f:\mathrm {out}(f)=v}(m_{e}(f)y(f)}}$

where ${\displaystyle m_{e}(f)\in \mathbb {F} _{p}}$. We consider the source as having ${\displaystyle k}$ input edges carrying the ${\displaystyle k}$ vectors ${\displaystyle w_{i}}$. By induction, one has that the vector ${\displaystyle y(e)}$ on any edge is a linear combination $y{\displaystyle }$( ${\displaystyle e}$)${\displaystyle }$= ${\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{1\mathrm{}}}$ ${\displaystyle \underset{}{\le }}$ ${\displaystyle \underset{}{i}}$ ${\displaystyle \underset{}{\le }}$ k${\displaystyle \underset{}{}}$( ${\displaystyle g_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle e}$) ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle$ y$(e)=\sum _{1\leq$ i$\leq k}(g_{i}(e)v_{i}}}}}}}}$의 벡터로서 $V{\displaystyle }$ ${\displaystystylek$ V$}$에 있다.$$The k-dimensional vector ${\displaystyle g(e)=(g_{1}(e),\ldots ,g_{k}(e))}$ is simply the first k coordinates of the vector ${\displaystyle y(e)}$. We call the matrix whose rows are the vectors ${\displaystyle g(e_{1}),\ldots ,g(e_{k})}$, where ${\displaystyle e_{}}$ ${\$은(는$)$ ${\displaystyle \mathrm{꼭지}}$ $t{\displaystyle }$ ${\displaystyle \in }$T {\$displaystyle t}$에 대한 수신$$$에지$로서$,$$$t {\$displaystyle G_{$t$\}\}$에 대한 전역 인코딩 매트릭스 벡터는 ${\displaystyle {무작위}_{}}$로 선택되므로 실제로 매트릭스 $G{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$는 반전된다$$.개연성이 높은따라서, $y{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle y_{}}$ k ${\$를 수신할 때, 어떤 수신기라도 ${\displaystyle {풀어서\mathrm{}}_{}}$${\displaystyle {}_{}}$w 1,${\displaystyle }$… ,${\displaystyle }$w ${\displaystyle k_{}}$ ${\$를 찾을$$ 수 있다.

${\displaystyle {\begin{bmatrix}y'\\y_{2}'\\\vdots \\\\nd{bmatrix}}=G_{t}{\gin{bmatrix}w_\{1}\2}\vdots \\\w_{bmats}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}ndataxt}}}}}}}}}}}}}}}}$

${\displaystyle {여기}_{}^{}}$서 $y{\displaystyle {}_{}^{}}$ $′{\$는 벡터 ${\displaystyle y_{}}$ i ${\$ $y_${$i}$의$$첫 번째 $k{\displaystyle }$ ${\displaystyle$ k} 좌표를$$ 제거하여 형성된 벡터다$$.

수신기에서 디코딩

${\displaystyle {각}_{}}$ 수신기, $t{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle T}$ ${\displaystyle t\in T}$에는$$$v{\displaystyle {}_{}}$ i ${\$ $y_{1},\ldots,y_{k}}$의 임의 선형 조합인 $k{\displaystyle }$ ${\displaystyle k}$ 벡터$$ $y{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle {}_{}}$ ${\$displaystystyle $v_{i$s를 얻는다.사실, 만약

${\displaystyle y_{i}=(\displaystyle _{i_{1}=(\readots _{1},\ldots, {i_{d})}}$

그때

${\displaystyle y_{i}=\sum _{1\leq j\leq k}(\properties _{ij}v_{j}).}$

따라서 선형 변환을 반전시켜 높은 확률로$$$v{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$s를 찾을 수 있다.

역사

Krohn, Freedman, Mazieres는 2004년에 우리가 해시함수${\displaystyle }$H : ${\displaystyle Vg}$ G$${\$displaystyle H:V\longrightarrow G}$를 가지고 있다면 다음과 같은$$ 이론을^[2] 제안했다.

• ${\displaystyle H}$ ${\displaystyle H}$은(는) 충돌에 내성이 있음 – $H{\displaystyle (x}$) = ${\displaystyle H(}$ ${\displaystyle y)}${\$displaystyle$ H$(x)=$와$$ 같은 $x{\displaystyle }${\$displaystyle$ $y$$}$ 및$$ $y{\displaystyle }$ ${\displaystystyle$ y$}$을(를) 찾기가 어려움$H(y)}$;
• ${\displaystyle H}$ ${\displaystyle H}$은 ${\displaystyle \mathrm{동형상}}$ – H(${\displaystyle x}$+ y${\displaystyle }$)${\displaystyle }$= ${\displaystyle H(}$ ${\displaystyle x}$)${\displaystyle }$+ ${\displaystyle H(}$ ${\displaystyle y}$) ${\displaystyle H(x+y)=H(x)++++$이다.$H(y)}$.

그러면 서버는 각 수신기에$$ $H{\displaystyle }$( ${\displaystyle v_{}}$i${\displaystyle {}_{}}$) {\$displaystyle H$(v_${i}})$를 안전하게 배포하고, 이를 확인할 수 있다.

${\displaystyle y=\sum _{1\leq i\leq k}(\reason _{i}v_{i}}})$

우리는 확인할 수 있다

${\displaystyle H(y)=\sum _{1\leq i\leq k}(\alpha _{i_{i})}$

이 방법의 문제는 서버가 각각의 수신자에게 보안 정보를 전송해야 한다는 것이다.해시함수 $H{\displaystyle }$ ${\displaystyle H}$는 별도의 보안 채널을 통해 네트워크의 모든 노드로 전송될 필요가$$ 있다.${\displaystyle }$$H{\displaystyle }$ ${\displaystyle H}$은(는) 계산 비용이 많이 들고 H ${\displaystyle$ H$}$의 안전한 전송도 경제적이지 않다$$.

동형 서명의 장점

1. 오염 검출 외에 인증확인을 확립한다.
2. 보안 해시 다이제스트를 배포할 필요 없음.
3. 일반적으로 비트 길이가 작으면 충분하다.길이 180비트의 서명은 1024비트 RSA 서명에 버금가는 보안성을 가진다.
4. 이후 파일 전송 시 공용 정보는 변경되지 않는다.

서명 방식

서명의 동형성 속성은 노드가 서명 당국에 연락하지 않고 들어오는 패킷의 어떤 선형 조합에도 서명할 수 있게 한다.

한정된 영역에 걸친 타원 곡선 암호화

유한분야에 걸친 타원곡선 암호화는 유한분야에 걸친 타원곡선의 대수적 구조에 기초한 공개키 암호화에 대한 접근법이다.

$F{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$는 q ${\displaystyle q}$이(가) 2 또는 3의 검정력이 아닐$$ 정도로 유한한 필드가 되도록$$ 한다.그러면 $F{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$ 위에$$ 있는 타원 곡선 $E{\displaystyle }$ ${\displaystyle E}$은 형태의 방정식에 의해 주어진 곡선이다.

${\displaystyle y^{2}=x^{3}+ax+b,\,}$

$여기$서${\displaystyle ,}$ a , ${\displaystyle b}$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$ ${\displaystyle {}^{}}$ a${\displaystyle {}^{}}$+ ${\displaystyle 27}$ ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle 0}$ ${\displaystyle 4a^{3}+27b^{2}\not =0}$

$K{\displaystyle }$ ${\displaystyle \supseteq }$ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$을(를) 다음으로 한다.

${\displaystyle E(K)=\{(x,y) y^{2}=x^{3}+ax+b\}\빅컵 \{O\}}}$

정체성을 O로 하여 아벨 그룹을 형성하다.그룹 작업은 효율적으로 수행될 수 있다.

웨일 페어링

Weil pairing은 $E{\displaystyle }$ ${\displaystyle E}$의 비틀림 부분군에서 쌍(승수 표기법 포함)을 구성하는 방법으로$$타원 $곡선{\displaystyle }$ E ${\displaystyle$ E$}$에 대한 함수에 의한 통일의 뿌리의 구성이다$.$ $Let{\displaystyle }$ E${\displaystyle }$/ ${\displaystyle F{\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$는 c 타원형이어야$$ 한다.urve and let ${\displaystyle \mathbb {\bar {F}} _{q}}$ be an algebraic closure of ${\displaystyle \mathbb {F} _{q}}$. If ${\displaystyle m}$ is an integer, relatively prime to the characteristic of the field ${\displaystyle \mathbb {F} _{q}}$, then the group of ${\displaystyle m}$$$-torsion points, ${\displaystyle E}$[ m ${\displaystyle ]}$= ${\displaystyle P}$ ${\displaystyle \in }$ E${\displaystyle }$(${\displaystyle {\stackrel{\mathbb{}}{\mathbb{}}q}_{}}$)${\displaystyle }$: ${\displaystyle m}$ ${\displaystyle P}$= O ${\$ {F$} _{q}):mP=O$

$E{\displaystyle }$/ ${\displaystyle F{\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$ E$/\mathb {F} _{q}}$이(${\displaystyle 가}$) 타원 곡선 및 ${\displaystyle gcd}$(m${\displaystyle }$,${\displaystyle q}$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle \gcd(m,q)=1}$인 경우$$

${\displaystyle E[m]\cong(\mathb {Z} /m\mathb {Z} )*(\mathb {Z} /m\mathb {Z} )}$

지도 $e{\displaystyle {}_{}}$: ${\displaystyle E}$[ ${\displaystyle m}$ ${\displaystyle ]}$ ${\displaystyle \ast }$ ${\displaystyle E}$[ ${\displaystyle m}$ ${\displaystyle ]}$→ ${\displaystyle {}_{}}$ ${\displaystyle m_{}}$(${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle e_{m:$$E$$[m]*E[m]\오른쪽$ 화살표 $\mu _{m}(\mathb {F} _{q$})를 참조하십시오$.$

1. (Bilinear) ${\displaystyle e_{m}(P+R,Q)=e_{m}(P,Q)e_{m}(R,Q){\text{ and }}e_{m}(P,Q+R)=e_{m}(P,Q)e_{m}(P,R)}$.
2. (비감속) ${\displaystyle e_{}}$m (${\displaystyle P}$ ,${\displaystyle Q}$) = 1 모든 P에 대한$$ ${\displaystyle 1}$ ${\displaystyle e_{m}(P,Q)=1}$은 $Q{\displaystyle }$= O ${\displaystyle Q=O}$을 의미한다$.$
3. (대체) $e{\displaystyle {}_{}}$ ${\displaystyle m_{}}$( ${\displaystyle P}$, P${\displaystyle }$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle e_{m}(P,P)=1$

또한 ${\$을(를) 효율적으로 계산할 수 있다$$.^[3]

동형체 서명

$p{\displaystyle }$ ${\displaystyle p}$을(를) 프라임으로 하고$$ $q{\displaystyle }$ ${\displaystyle q}$을 프라임으로 한다.Let ${\displaystyle V/\mathbb {F} _{p}}$ be a vector space of dimension ${\displaystyle D}$ and ${\displaystyle E/\mathbb {F} _{q}}$ be an elliptic curve such that ${\displaystyle P_{1},\ldots ,P_{D}\in E[p]}$. Define ${\displaystyle h:V\$$다음$과 같은$$ $Longrightarrow E[p]}:$ h (${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle u_{}}$ D${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{1\mathrm{}}}$ ${\displaystyle \underset{}{\le }}$ ${\displaystyle \underset{}{i}}$ ${\displaystyle \underset{}{\le }}$ D${\displaystyle \underset{}{}}$(${\displaystyle {}_{}{}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle h(u_{1},\ldots,u_{D}}}=\sum$_{$1\leq$ i$\leq$ d$}(u_{i}P_{i$}}}}}}}}}}}}}}{i$\}\}\}\}\}\}\})\}\}\}\}\}\}).$$h$ ${\displaystyle$ h}$함수$는 $V{\displaystyle }$ ${\displaystyle V}$에서 $E$ [ p ${\displaystyle E[p]}$까지 임의의$$동형상이다.

The server chooses ${\displaystyle s_{1},\ldots ,s_{D}}$ secretly in ${\displaystyle \mathbb {F} _{p}}$ and publishes a point ${\displaystyle Q}$ of p-torsion such that ${\displaystyle e_{p}(P_{i},Q)\not =1}$ and also publishes ${\dis$$playstyle (P_{i},s_{i}Q)}$ for ${\displaystyle 1\leq i\leq D}$. The signature of the vector ${\displaystyle v=u_{1},\ldots ,u_{D}}$ is ${\displaystyle \sigma (v)=\sum _{1\leq i\leq D}(u_{i}s_{i}$$P_{i}}}$ 참고$$:h의 계산이 동형이기 때문에 이 서명은 동형이다.

서명확인

$v{\displaystyle }$= ${\displaystyle {u\mathrm{}}_{}}$ 1,${\displaystyle }$… ,${\displaystyle u_{}}$ D ${\$ 및$$ 해당 시그니처 $\sigma {\displaystyle }$ ${\displaystyle \sigma}$이$($가) 지정되었는지 확인하십시오.

${\displaystyle {\begin}e_{p}(\sigma ,Q)&=e_{p}\좌(\sum _{1\leq i\leq D}(u_{i}s_{i}s_{i}})P_{i}),Q\right)\\&=\prod _{i}e_{p}(u_{i}s_{i}})P_{i}}\&=\&=\prod _{i}e_{p}(u_{i}P_{i}Q)\end{aigned}}}}$

그 검증은 위일페어링의 이단성을 결정적으로 이용한다.

시스템 설정

The server computes ${\displaystyle \sigma (v_{i})}$ for each ${\displaystyle 1\leq i\leq k}$. Transmits ${\displaystyle v_{i},\sigma (v_{i})}$. At each edge ${\displaystyle e}$ while computing ${\displaystyle y(e)=\sum _{f\in E:\mathrm{o}\mathrm{u}\mathrm{t}(f)=\mathrm{i}\mathrm{n}(e)}(m_e(f)y(f))}$${\displaystyle y(e)=\sum _{f\in E:\mathrm {out} (f)=\mathrm {in} (e)}(m_{e}(f)y(f))}$ also compute ${\displaystyle \sigma (y(e))=\sum _{f\in E:\mathrm {out} (f)=\mathrm {in} (e)}(m_{e}(f)\sigma (y(f)))}$ on the elliptic curve ${\displaystyle E}$$$.

서명은 타원곡선의 점이며, $좌표$는 F ${\displaystyle {}_{}}${\$displaystyle \mathb {F$} $_{$q$\}.$ 따라서 서명의 크기는 $2{\displaystyle \mathrm{}}$ ${\displaystyle \log q}${\$displaystyle 2\log$$q$}$비트{\displaystyle }$(일부 일정한 $시간{\displaystyle }$ l ${\displaystyle o}$g (${\displaystyle p}$$){\displaystystystyle$ $log($$p)}$비트$$$$)이다.$전송$ 오버헤드 입니다$.$The computation of the signature ${\displaystyle h(e)}$ at each vertex requires ${\displaystyle O(d_{in}\log p\log ^{1+\epsilon }q)}$ bit operations, where ${\displaystyle d_{in}}$ is the in-degree of the vertex ${\displaystyle in(e)}$.서명을 검증하려면 $O{\displaystyle ((d}$+ ${\displaystyle k}$) ${\displaystyle {로그\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$+ ${\displaystyle {ϵ}^{}}$q ${\displaystyle q}$) ${\displaystyle O(d+k)\log ^{2+\epsilon }q)}$비트$$ 작업이 필요하다.

담보증거

공격자는 해시함수 아래서 충돌을 일으킬 수 있다.

If given ${\displaystyle (P_{1},\ldots ,P_{r})}$ points in ${\displaystyle E[p]}$ find ${\displaystyle a=(a_{1},\ldots ,a_{r})\in \mathbb {F} _{p}^{r}}$ and ${\displaystyle b=(b_{1},\ldots ,b_{r})\in \$$mathbb {F} _{p}^{r}}}}$

${\displaystyle \ne }$ $[\displaystyle a\not =b$$]$ 및

${\displaystyle \sum _{1\leq i\leq r}(a_{i}P_{i}}=\sum _{1\leq j\leq r})(b_{j}P_{j}}).}$

제안:타원형 곡선의$$ $순서{\displaystyle }$ p$${\$displaystyle p}$의 주기적 그룹에 있는 이산 로그에서 해시-Colision까지 다항식 시간 단축이 있다.

$r{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle r=2$이면 $x{\displaystyle }$ ${\displaystyle P}$+ ${\displaystyle y}$ ${\displaystyle Q}$= ${\displaystyle u}$ P${\displaystyle }$+ ${\displaystyle v}$ ${\displaystyle Q}$ ${\displaystyle xP+yQ=uP+vQ}$을(를) 얻는다$.$Thus ${\displaystyle (x-u)P+(y-v)Q=0}$. We claim that ${\displaystyle x\not =u}$ and ${\displaystyle y\not =v}$. Suppose that ${\displaystyle x=u}$, then we would have ${\displaystyle (y-v)Q=0}$, but ${\displaystyle Q}$ is a point of order ${\displaystyle p}$${\displaystyle p}$ $$(prime) $따라서{\displaystyle }$ y -${\displaystyle u}$ ${\displaystyle \equiv }$ ${\displaystyle 0}$ ${\displaystyle mod}$ p ${\$ $y-u$$\equiv 0{\bmod$${p$$\}\}\}.$ 즉, $y{\displaystyle }$= $F{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$This contradicts the assumption that ${\displaystyle (x,y)}$ and ${\displaystyle (u,v)}$ are distinct pairs in ${\displaystyle \mathbb {F} _{2}}$. Thus we have that ${\displaystyle Q=-(x-u)(y-v)^{-1}P}$, where the inverse is taken as modulo ${\displays$$tyle p}$.

r > 2가 있으면 두 가지 중 하나를 할 수 있다.를 나는 을{\displaystyle 나는}우리는)}와 P2)Q{\displaystyle P_{2}=Q}전에 및 P을 세웠다 나는 O{\displaystyle P_{나는}=O원};2(때 r2{\displaystyle r=2게 국가 주의적 관점에서 서술 이 사건에서 증거는 사건으로 줄어든다.}), 또는 우리가)P1을 가져갈 수 있{\displaysty P1P{\displaystyle P_{1}=P r1P을 가져갈 수 있다.르$P_{1}=r_{1}P}$ and ${\displaystyle P_{i}=r_{i}Q}$ where ${\displaystyle r_{i}}$ are chosen at random from ${\displaystyle \mathbb {F} _{p}}$. We get one equation in one unknown (the discrete log of ${\displaystyle Q}$). It is quite possible that the equation we get does not involve t그는 알지 못한다.그러나, 이것은 다음에 우리가 논쟁할 때 아주 작은 확률로 일어난다.해시-콜렉션 알고리즘이 우리에게 그런 걸 줬다고 가정해봅시다.

${\displaystyle ar_{1}P+\sum _{2\leq i\leq r}(b_{i}r_{i}Q)=0.}$

그렇다면 $\sum {\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{2\mathrm{}}}$ ${\displaystyle \underset{}{\le }}$ ${\displaystyle \underset{}{i}}$ ${\displaystyle \underset{}{\le }}$ ${\displaystyle \underset{}{r}}$ ${\displaystyle {}_{}{}_{}}$ ≢ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ 0 ${\displaystyle mod}$ p ${\$ i$\leq r}b_{i}r_{i}\not \equiv 0{\bmod{p}}}}}$만 하면 Q의 이산 로그에 대해 해결할 수 있다$.$그러나 $r{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$은$($는) 해시-콜ision의 오라클에는 알려져 있지 않으므로 이 프로세스가 발생하는 순서를 서로 교환할 수 있다.In other words, given ${\displaystyle b_{i}}$, for ${\displaystyle 2\leq i\leq r}$, not all zero, what is the probability that the ${\displaystyle r_{i}}$’s we chose satisfies ${\displaystyle \sum _{2\leq i\leq r}(b_{i}r_{i})=0}$? It is clear that the latter확률은 $1\frac{{\displaystyle \mathrm{}}}{}$ $\frac{}{}$ $[\displaystyle$1$\over p}$ 입니다.$$따라서 $Q{\displaystyle }$ ${\displaystyle Q}$의 이산 로그에 대해 높은 확률로 해결할 수 있다$.$

우리는 이 계획에서 해시 충돌의 발생이 어렵다는 것을 보여주었다.적들이 우리의 시스템을 저지할 수 있는 다른 방법은 서명을 위조하는 것이다.이 서명 체계는 본질적으로 Boneh-Lynn-Shacham 서명 체계의 Aggregate Signature 버전이다.^[4]여기서 서명을 위조하는 것은 적어도 타원 곡선 Diffie–를 푸는 것만큼 어렵다는 것을 보여준다.헬맨 문제.타원곡선에서 이 문제를 해결하는 유일한 방법은 이산 로그 계산을 통해서이다.따라서 서명을 위조하는 것은 적어도 계산적 공동 Diffie를 푸는 것만큼 어렵다.타원형 곡선에 헬맨이 있고 개별 로그를 계산하는 것만큼 어려울 겁니다.

참고 항목

• 네트워크 코딩
• 동형 암호화
• 타원곡선암호법
• 웨일 페어링
• 타원곡선 디피-헬먼
• 타원 곡선 DSA
• 디지털 서명 알고리즘

참조

외부 링크

1. Live Network Coding P2P 시스템의 종합적인 보기
2. 네트워크 코딩(표시) CISS 2006, Princeton
3. 버팔로 대학교 코딩 이론 강의 노트 - 닥터아트리 루드라