의사결정 선형 가정

의사결정 선형(DLIN) 가정은 타원 곡선 암호화에 사용되는 계산적 경도 가정이다.특히 DLIN 가정은 의사결정 Diffie-가 있는 환경에서 유용하다.헬맨 가정은 (페어링 기반 암호법에서 흔히 그렇듯이) 유지되지 않는다.결정 선형 가정은 Boneh, Boyen, Shacham에 의해 도입되었다.^[1]

Informally the DLIN assumption states that given ${\displaystyle (u,\,v,\,h,\,u^{x},\,v^{y})}$, with ${\displaystyle u,\,v,\,h}$ random group elements and ${\displaystyle x,\,y}$ random exponents, it is hard to distinguish ${\displaystyle h^{x+y}}$ from an$독립{\displaystyle }$ 랜덤 그룹 요소 ${\displaystyle \eta$ $\}.$

동기

대칭$$ 쌍 구성 기반 암호화에서 $그룹{\displaystyle }$ G ${\displaystyle$ G$}$에는 쌍 구성 $e{\displaystyle }$: ${\displaystyle G}$ ${\displaystyle \times }$ ${\displaystyle G}$→ T ${\displaystyle e:$$G$$\time G\to$ T$}$은(는) 이선형이다.이 지도는 의사결정 Diffie-Hellman 문제를 해결하기 위한 효율적인 알고리즘을 제공한다.^[2] 입력$({\displaystyle g}$, ${\displaystyle g{}^{}}$ ${\displaystyle a^{}}$ ,${\displaystyle {}^{}{g}^{}}$ ${\displaystyle b{}^{}}$, ${\displaystyle h}$) ${\displaystyle (g,\,g^{a},\,g^{b},\,h)}$을$($를) 지정하면 $h{\displaystyle }$ ${\displaystyle h}$이(가) ${\displaystyle g^{}}$ ${\$과 동일한지 여부를 쉽게 확인할 수 있다$.$페어링을 사용하여 다음 사항을 확인하십시오.

${\displaystyle e(g^{a},g^{b}}=e(g,g)^{ab}=e(g,g^{ab}).}$

따라서 $h{\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle a^{}}$ ${\$인 경우 $e{\displaystyle ({}^{}}$ ${\displaystyle {}^{}}$,${\displaystyle {}^{}{g}^{}}$) ${\displaystyle e(g^{a},g^{b})$와 $e{\displaystyle (g,}$ ${\displaystyle h}$) ${\displaystystyle e(g,h)}$이 같게 된다$$.

ElGamal 암호화와 서명을 작성하는 데 필수적인 이 암호 가정은 이 경우 성립되지 않기 때문에 대칭 이선형 그룹에서 암호화를 구축하기 위해서는 새로운 가정이 필요하다.DLIN 가정은 위의 공격을 좌절시키기 위해 Diffie-Hellman 유형 가정을 수정하는 것이다.

형식 정의

$G{\displaystyle }$ ${\displaystyle G}$을(를) 프라임 $순서{\displaystyle }$ p ${\displaystyle$ $p$$}$의 순환 그룹이 되게$$ 하라$.$${\displaystyle <img\; alt="G"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b"\; style="vertical-align:\; -0.338ex;\; width:1.827ex;\; height:2.176ex;"\; papago-attr-id="74">}$$u{\displaystyle }$ ${\displaystyle$ $u$$\},$ $v{\displaystyle }$ ${\displaystyle$ $v$$\},$ ${\displaystyle h\mathrm{}}$ ${\displaystyle$ $h$$}$은(를${\displaystyle )}$의 균일하게 임의 생성자로${\displaystyle \mathrm{한다}.}$${\displaystyle \{1,\,2,\,\dots,\,\,p-1\}$분포 정의

${\displaystyle D_{1}=(u,\,v,\,h,\,u^{x},v^{y},\,h^{x+y}).}$

$\displaystyle \eta }$을(를) G$${\$displaystyle$G}의 다른 균일한 임의 요소가 되게 두십시오$$$.$ 다른 분포를 정의하십시오.

${\displaystyle D_{2}=(u,\,v,\,h,\,u^{x},\,v^{y},\eta).}$

의사결정 선형 가정에서는 ${\displaystyle {D\mathrm{}}_{}}$ 1 ${\$ 스타일 $D_{1$}와$$ $D{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ 스타일 $D_{2$}}은$$ 계산적으로 구별할 수 없다고 명시한다.

적용들

선형 암호화

Boneh, Boyen, Shacham은 ElGamal 암호화와 유사하게 공개 키 암호화 방식을 정의한다.^[1]이 구성표에서 공용 키는 생성자 $u{\displaystyle ,}$ ${\displaystyle v,}$ ${\displaystyle h}$, h ${\displaystyle u,$${\displaystyle v}$$,h$ 개인 키는 ${\displaystyle u^{}}$ x${\displaystyle {}^{}}$=${\displaystyle {}^{}{h}^{}}$ ${\displaystyle u^{x}=v^{y}=h}$와 같은 두 개의 지수다$.$ 암호문을 생성하기 위해 암호화 메시지 $m{\displaystyle }$∈ G ${\displaystysty$ m$\in$ G$}$을 조합한다.

${\displaystyle c}$ ${\displaystyle :=({c\mathrm{}}_{}}$ 1,${\displaystyle {}_{}c{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}}$c ${\displaystyle {3\mathrm{}}_{}}$)${\displaystyle }$= (${\displaystyle {}^{}}$ ${\displaystyle a^{}}$ ${\displaystyle v{}^{}}$ ${\displaystyle b^{}}$ ${\displaystyle m^{}}$ ${\displaystyle \cdot }$ h ${\displaystyle a^{}}$+ b${\displaystyle {}^{}}$) ${\displaystyle c:==(c_{1},\,c_{2},\c_{3}}=(u^{a},\,v^{b},m\cdot$ h$^{a+b$

암호문을 해독하려면 개인 키를 사용하여 계산하십시오.

${\displaystyle m':=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y}^{1}^{-1}).}$

이 암호화 체계가 올바른지 확인하려면(예: $m{\displaystyle {}^{}=}$ = ${\displaystyle m}$ ${\displaystyle m'=m})$ 양 당사자가 프로토콜을 따를 때 유의하십시오$$.

${\displaystyle m'=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{a})^{x}\cdot (v^{b})^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{x})^{a}\cdot (v^{y})^{b})^{-1}.}$

그런 다음 ${\displaystyle u^{}}$ x${\displaystyle {}^{}}$= ${\displaystyle {}^{}}$ ${\displaystyle y^{}}$= ${\displaystyle h}$ ${\displaystyle u^{x}=v^{y}=h}$ 산출량을$$ 사용

${\displaystyle m'=m\cdot h^{a+b}\cdot h^{a}\cdot h^{b}^{1}=m\cdot (h^{a+b}\cdot h^{-a-b}=m)=m.}$

또한, 이 계획은 DLIN 가정이 유지된다고 가정할 때 IND-CPA 안전하다.

짧은 그룹 서명

Boneh, Boyen, Shacham도 그룹 서명을 위한 계획에 DLIN을 사용한다.^[1] 서명은 표준 보안 수준으로는 250바이트로만 나타낼 수 있기 때문에 "단기 그룹 서명"이라고 불린다.

그들의 프로토콜은 특별한 유형의 영지식 증명을 정의하기 위해 먼저 선형 암호화를 사용한다.그 다음, 피아트-샤미르 휴리스틱스를 적용하여 증명 시스템을 디지털 서명으로 변환한다.그들은 이 서명이 그룹 서명에 필요한 용서할 수 없는, 익명성 및 추적가능성의 추가 요건을 충족함을 증명한다.

그들의 증거는 DLIN 가정뿐만 아니라 $q{\displaystyle }$ ${\displaystyle q}$ -strong$$ Diffie-Hellman 가정이라고 불리는 또 다른 가정에 의존한다.그것은 랜덤 오라클 모델에서 증명되었다.

기타 응용 프로그램

2004년 그것의 정의 이후, 의사결정 선형 가정은 다양한 다른 응용 프로그램을 보아왔다.여기에는 Naor-Reingold 구성을 일반화하는 유사 함수의 구축, 속성 기반 암호화 방식, 비 상호 작용 제로 지식 증명의 특수 등급이 포함된다.^[5]

참조