계산 경도 가정

계산 복잡성 이론에서 계산적 경도 가정은 특정 문제를 효율적으로 해결할 수 없다는 가설이다(여기서는 효율적으로 "다항식 시간"을 의미한다).본질적으로 어떤 유용한 문제에 대해 어떻게 경도를 증명할지는 알려져 있지 않다.대신에, 컴퓨터 과학자들은 새롭거나 복잡한 문제의 경도를 더 잘 이해되는 문제에 대한 계산적 경도 가정과 공식적으로 연관시키기 위해 감축에 의존한다.

계산 경도 가정은 암호학에서 특히 중요하다.암호학의 주요 목표는 입증 가능한 보안으로 암호 원형을 만드는 것이다.암호 프로토콜은 정보 이론적 보안을 가지고 있는 경우가 있는데, 일회용 패드가 일반적인 예다.그러나, 정보 이론적 보안이 항상 달성될 수 있는 것은 아니다. 그러한 경우, 암호학자는 컴퓨터 보안에 다시 의존한다.대략적으로 말하면, 이는 모든 적들이 실제로 존재하듯이, 어떤 적들이든 계산적으로 제한된다고 가정할 때 이 시스템들이 안전하다는 것을 의미한다.

연산 경도 가정은 알고리즘 설계자에게도 유용하다. 단순한 알고리즘이 P p NP와 같이 잘 연구된 연산 경도 가정을 반박할 가능성은 낮다.

경도 가정 비교

컴퓨터 과학자들은 어떤 경도 가정이 더 신뢰할 수 있는지를 평가하는 다른 방법을 가지고 있다.

경도 가정 강도

우리는 $가정{\displaystyle }$ $A{\displaystyle }$ {\$displaystyle A}$이(가) $B{\displaystyle }$ ${\displaystyle B}$을(를) 암시할$$ 때 가정$$ $B{\displaystyle }$ ${\displaystyle B}$보다 강하다고 말한다($$그 반대는 거짓이거나 알 수 없음).즉, 가정 $A{\displaystyle }$ ${\displaystyle A}$이(가) 거짓이라 하더라도 가정 $B{\displaystyle }$ ${\displaystyle B}$은(는) 여전히 참일 수 있으며$$ 가정 $B{\displaystyle }$ ${\displaystyle B}$에 기초한 암호 프로토콜은 여전히 사용하기에 안전할 수 있다$$.그러므로 암호 프로토콜을 고안할 때, 사람들은 가능한 가장 약한 가정을 사용하여 보안을 증명할 수 있기를 희망한다.

평균 사례 대 최악의 경우 가정

평균 사례 가정은 특정 문제가 어떤 명시적 분포로부터 대부분의 경우에 어렵다고 말하는 반면, 최악의 경우 어떤 경우에는 문제가 어렵다고만 말한다.주어진 문제의 경우, 평균 사례 경도는 최악의 경우 경도를 의미하므로, 평균 사례 경도 가정은 동일한 문제에 대한 최악의 경우 경도 가정보다 강하다.더욱이 비교할 수 없는 문제에 대해서도 지수적 시간 가설과 같은 가정은 흔히 심어진 종파적 추측과 같은 평균 사례 가정보다 선호되는 것으로 간주된다.^[1]그러나 대부분의 암호 애플리케이션에서 문제가 어떤 하드 인스턴스(즉, 최악의 경우 문제가 어려움)를 가지고 있다는 것을 아는 것은 우리에게 하드 인스턴스를 생성하는 방법을 제공하지 않기 때문에 무용지물이라는 점에 유의한다.^[2]다행히 암호화에 사용되는 많은 평균 사례 가정(RSA, 이산 로그 및 일부 격자 문제 포함)은 최악의 사례 대 평균 사례 축소를 통해 최악의 사례 가정에 기초할 수 있다.^[3]

변위성

계산 경도 가정의 원하는 특성은 위조 가능성이다. 즉, 가정이 거짓이라면 그것을 증명할 수 있을 것이다.특히 Naor(2003)는 암호의 위변위성에 대한 정식 개념을 도입했다.^[4]대략 계산적 경도 가정은 도전적과 효율적인 검증자 사이의 대화형 프로토콜로 공식화될 수 있는 경우, 효율적인 적성이 검증자를 설득하여 가정이 거짓인 경우에만 이를 받아들일 수 있다고 한다.

공통암호경도 가정

많은 암호 경도 가정이 사용되고 있다.이것은 가장 일반적인 것들과 그것들을 사용하는 몇몇 암호 프로토콜들의 목록이다.

정수 인자화

복합 번호 $n{\displaystyle }$ ${\displaystyle$ n$}$과$($와) 두 개의 큰 $소수점{\displaystyle }$ n${\displaystyle }$= p${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle n=p=$p\$cdot$q$}$의 산물인 정수 인수 문제는 p ${\$$displaystyle p$$}$과$($으로 $소수점{\displaystyle {}_{}}$ p1,${\displaystyle {}_{},}$ ${\displaystyle {}_{}}$ ${\$)를 찾는 것이다$.$$s,p_{k}}$과 같은$$ $n{\displaystyle }$=${\displaystyle \underset{}{}}$∏ ${\displaystyle i_{}}$ ${\$표현 크기(${\displaystyle \log }$ ${\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle \log(n)})$에서 시간 다항식으로 실행되는 정수 인자화를 위한 알고리즘을 찾는 것은 주요한 개방적인 문제다.$$많은 암호 프로토콜의 보안은 정수 인수화가 어렵다는 가정(즉, 다항식 시간으로는 해결할 수 없다)에 의존한다.이러한 가정과 동일한 보안성을 가진 암호체계에는 라빈 암호체계와 오카모토 암호체계가 포함된다.우치야마 암호 체계.더 많은 암호 시스템은 RSA, 잔류성 문제, 피히딩과 같은 더 강력한 가정에 의존한다.

RSA 문제

복합 번호 $n{\displaystyle }$ ${\displaystyle$ n$\},$ $지수{\displaystyle }$ e ${\displaystyle e}$ 및$$ $숫자{\displaystyle }$ c ${\displaystyle :=m^{}}$ e${\displaystyle {}^{}m\mathrm{}}$ ${\displaystyle \mathrm{o}}$ ${\displaystyle d}$ )${\displaystyle c:=m^{e}(\mathrm {mod}\n$ RSA 문제는 $m{\displaystyle }$ ${\displaystystym m}$을 찾는 것이다$.$문제는 어렵지 않을 것으로 추측되지만, $n{\displaystyle }${\$displaystyle n$}의 인수화를 감안하면 쉬워진다$.$ RSA 암호체계에서 $({\displaystyle }$n${\displaystyle ,e}$ )$${\$displaystyle(n,e)$은 공개키, $c{\displaystyle }$ ${\displaystyle c$}은 $메시지{\displaystyle }$ m$${\$displaystym$m}의 암호화$$$,$ $n{\displaystyle }${\$disc}$의 인수화는 비밀이다$$.암호 해독에 사용되는 키.

잔류성 문제

복합 $번호{\displaystyle }$n {\$displaystyle$n$$}과${\displaystyle }$정수 y , d ${\displaystyle y,d$}을$($를) 지정하면 잔존도 문제는 다음과 같은$$ (대체로, a) $x{\displaystyle }$ ${\displaystyle x}$이(가) 존재하는지 여부를 결정하는 것이다.

${\displaystyle x^{d}\equiv y{\pmod {n}}.}$

중요한 특별한 경우로는 2차적 잔류성 문제와 의사결정 복합적 잔류성 문제가 있다.RSA의 경우와 마찬가지로 이 문제(및 그 특수한 경우)는 추측하기 힘들지만, $n{\displaystyle }$ ${\displaystylen}$의 인자를 감안하면 쉬워진다$.$ 잔류성 문제의 경도에 의존하는 암호체계로는 다음과 같은 것이 있다.

• Goldwasser-Micali 암호 시스템(정확한 재반복성 문제)
• 블럼 블럼 슈브 발전기(정량적 재등도 문제)
• Paillier 암호 시스템(결정적 복합 잔류성 문제)
• Benaloh 암호 시스템(높은 잔류성 문제)
• Naccache-Stern 암호 시스템(높은 잔류성 문제)

피히딩 가정

복합 숫자 $m{\displaystyle }$ ${\displaystyle m}$의 경우$,$ ${\displaystyle \mathrm{오일러}}$의 전체 함수 $\varphi {\displaystyle }$ (${\displaystyle }$m$){\displaystyle \phi (m)}$을(를) 효율적으로 계산하는 방법을 알 수 없다$.$피히딩 가정은 ${\displaystyle \varphi }$( m${\displaystyle }$) ${\displaystyle \pi (m$을(를) 계산하기 어렵다고 가정하며, 더욱이 $\varphi {\displaystyle }$(${\displaystyle m}$) ${\displaysty \pi (m)}$의 어떤 주요 요소도 계산하기 어렵다고$$ 가정한다.이 가정은 Cachin-Micali-Stadler PIR 프로토콜에서 사용된다.^[5]

이산 로그 문제(DLP)

그룹 $G{\displaystyle }$ ${\displaystyle G}$에서 $요소{\displaystyle }$ a ${\displaystyle a}$ 및 b ${\displaystyle b}$을(를) 지정하면${\displaystyle }이산{\displaystyle }$ ${\displaystyle {}^{}}$ ${\displaystyle {문제}^{}}$는 a$$= b k {\$displaystyle$a=$b^{$k$$}와$$같은 정수 k {\$displaystystyle k}$를 요구한다$.$이산 로그 문제는 정수 인자화에 비견될 만한 것으로 알려져 있지 않지만, 이들의 계산 복잡성은 밀접하게 관련되어 있다.

이산 로그 문제와 관련된 대부분의 암호 프로토콜은 실제로 더 강한 Diffie-에 의존한다.헬만 가정: g 그룹 요소 $g{\displaystyle }$, ${\displaystyle {}^{}}$ ${\displaystyle a^{}{}^{}}$, ${\displaystyle {}^{}}$ ${\$ $여기$서 g ${\displaystyle g}$은(는) 발생기이고$$ $a{\displaystyle ,}$ ${\displaystyle b}$ ${\$$displaystyle a,b}$은 임의의 정수인$$ 경우 $g{\displaystyle {}^b}$ b${\$disposition을 사용하는 프로토콜의 예가 포함된다$.$Fie-Hellman 키 교환 및 ElGamal 암호화(그러나 더 강력한 Decisional Diffie-에 의존함)헬만(DDH) 변종.

다중선 지도

다중선 지도는 함수 $e{\displaystyle }$: ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle G_{}}$ n${\displaystyle {}_{}}$→ ${\displaystyle G_{}}$ ${\displaystyle {}_{}}$ ${\$$G_{1},\dots ,G_{n}\rightarrow G_{T}}$ (where ${\displaystyle G_{1},\dots ,G_{n},G_{T}}$ are groups) such that for any ${\displaystyle g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}}$ and ${\displaystyle a_{1},\dots ,a_{n}}$,

${\displaystyle e}$( g ${\displaystyle {}_{}^{}}$ ${\displaystyle {{a\mathrm{}}_{}}_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$,${\displaystyle }$… ,${\displaystyle {g_{}}_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$)${\displaystyle }$= ${\displaystyle e}$( ${\displaystyle {g\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle g_{}}$ ${\displaystyle {}_{}{}^{}}$) ${\displaystyle {{1\mathrm{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{}}$ a ${\displaystyle {n_{}}^{}}$ ${\$

For cryptographic applications, one would like to construct groups ${\displaystyle G_{1},\dots ,G_{n},G_{T}}$ and a map ${\displaystyle e}$ such that the map and the group operations on ${\displaystyle G_{1},\dots ,G_{n},G_{$$T}$은(는) 효율적으로 계산할 수 있지만$$, $G{\displaystyle {}_{}}$ 1${\displaystyle }$, … ,${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$의 이산 로그 문제는 여전히 어렵다$$.^[6]일부 애플리케이션은 더 강력한 가정을 요구한다. 예를 들어 Diffie-Hellman 가정의 다중 선 아날로그.

$n{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle n=2}$의 특별한 경우를 위해$,$ 신뢰할 수 있는 보안을 가진 바이린어 맵은 Weil 페어링과 Tate 페어링을 사용하여 구성되었다.^[7]> $[\디스플레이스타일 n]2}$의 경우, 최근 몇 년 동안 많은 건설이 제안되었지만, 그 중 많은 건설도 부숴졌고, 현재 안전한 후보에 대한 공감대가 형성되어 있지 않다.^[8]

다중경도 가정에 의존하는 일부 암호체계에는 다음이 포함된다.

• Boneh-Franklin 계획(블린어 디피-헬먼)
• 본-린-샤캄(블린어 디피-헬먼)
• Garg-Gentry-Halevi-Raykova-Sahai-Waters 후보, 불식성 난독화 및 기능 암호화(다층 지그소 퍼즐)^[9]

격자 문제

lattices에 가장 근본적인 계산 문제는 최단 벡터 문제(부사장):격자 L{L\displaystyle}지정된, L{\displaystylev\in L}∈ 가장 짧은 0이 아니벡터 v를 찾는다. 대부분의 cryptosystems 부사장의 최단 독립 벡터와 같은 변종들에 더 강한 가정이 필요한 problem(SIVP), GapSVP,[10]또는 Uniq.ue-S부사장.^[11]

암호학에서 가장 유용한 격자 경도 가정은 오류가 있는 학습(LWE) 문제에 대한 것이다.$({\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle (x,$${\displaystyle y}$$)}$에 샘플을 주면$,$ ${\displaystyle \mathrm{여기}}$서 일부 선형함수 $f{\displaystyle }$ (${\displaystyle \cdot }$) ${\displaystyle y$$=f(x$$)}$에 $대해$ 선형대수를 사용하여 f$$ (${\displaystyle \cdot }$) ${\displaystystyle$ f$(\cdot )$를 쉽게 배울 수 있다$.$LWE 문제에서 알고리즘에 대한 입력은 오류가 ${\displaystyle \mathrm{있다}}$. 즉, 각 쌍 $y{\displaystyle }$ ${\displaystyle \ne }$ f${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle y\neq f(x)}$에 대해 약간의 작은 확률을 가진다$$.이 오류는 문제를 다루기 어렵게 만들 것으로 생각되며(적절한 매개변수에 대해), 특히 SVP 변종에서 최악의 경우에서 평균 사례의 감소로 알려져 있다.^[12]

양자컴퓨터의 경우 팩토링과 이산 로그 문제는 쉽지만 격자문제는 어려울 것으로 추측된다.^[13]이것은 일부 격자 기반 암호 시스템이 후분위 암호화에 적합하게 만든다.

격자 문제의 경도에 의존하는 일부 암호체계에는 다음이 포함된다.

• NTRU(NTRUEncrypt 및 NTRUSign 둘 다)
• 대부분의 완전 동형 암호화 대상

비결정적 경도 가정

그들의 암호 응용뿐만 아니라 경도 가정도 계산 복잡성 이론에 사용되어 무조건적으로 증명하기 어려운 수학적 진술에 대한 증거를 제공한다.이러한 적용에서, 경도 가정은 진술 자체가 사실이라는 것을 증명하는 대신에 원하는 복잡성-이론적 진술을 함축한다는 것을 증명한다.이러한 유형의 가장 잘 알려진 가정은 P ≠ NP라는 가정이지만,^[14] 다른 가정에는 기하급수적인 시간 가설,^[15] 심어진 패거리 추측, 독특한 게임 추측 등이 있다.^[16]

${\displaystyle C}$ ${\displaystyle C}$ -hard$$ 문제

일부 복잡성 $등급{\displaystyle }$ C ${\displaystyle$ C$\},$ 특히 NP-hard(그러나 종종 PSPACE-hard, PPAD-hard 등)에 대해 많은 최악의 계산 문제가 어렵거나 심지어 완전한 것으로 알려져 있다.이는 최소한 C $등급$의 문제만큼 어렵다는 것을 의미한다$.$ 문제가 C $등급{\displaystyle }$${\$$displaystyle C}$ -hard$$(다항식 시간 감소와 관련)인 경우, 계산 $경도{\displaystyle }$ ${\displaystyle \mathrm{가정}}$ P${\displaystyle }${$$C {\$displaystyle P\neq$ C$}$가 거짓이$$ 아니면 다항식 시간 알고리즘으로 해결할 수 없다.

지수 시간 가설(ETH) 및 변종

지수 시간 가설(ETH)은 $P{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle N}$ ${\displaystyle P}$ ${\displaystyle P\neq NP}$ 경도$$ 가정을 강화한 것으로, 부울 만족도 문제가 다항 시간 알고리즘을 가지고 있지 않을 뿐만 아니라 지수 시간(${\displaystyle {2\Omega \mathrm{}}^{}}$($){\$ 2$^{\Oomega (n)}$을 필요로 한다고 추측한다.$$^[17]An even stronger assumption, known as the Strong Exponential Time Hypothesis (SETH) conjectures that ${\displaystyle k}$-SAT requires ${\displaystyle 2^{(1-\varepsilon _{k})n}}$ time, where ${\displaystyle \lim _{k\rightarrow \infty }\varepsilon _{k}=0}$. ETH, SETH, and related 계산적 경도 가정은 다항 시간과 준 다항 시간을 구별하는 결과,^[1] $또는{\displaystyle {}^{}}$ n${\displaystyle {\mathrm{}1}^{}}$.${\displaystyle {99}^{}}$ ${\$ n$^{1.99}$ $대$ n ${\displaystyle {2\mathrm{}}^{}}${\$디스플레이 스타일$ n$^{2}}.$ 이러한 가정은 파라메트릭화된 복잡성에서도 유용하다$.$^[18][19]

평균 사례 경도 가정

일부 계산 문제는 특정 인스턴스 분포에 대해 평균적으로 어려운 것으로 가정한다.For example, in the planted clique problem, the input is a random graph sampled, by sampling an Erdős–Rényi random graph and then "planting" a random ${\displaystyle k}$-clique, i.e. connecting ${\displaystyle k}$ uniformly random nodes (where ${\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}}$), and심은 $k{\displaystyle }$ ${\displaystyle k}$ -clike$$(유일한 w.h.p.)^[20]를 찾는 것이 목표다.또 다른 중요한 예는 3-SAT의 무작위 인스턴스에 대한 계산 경도 가정(변수에 대한 절의 특정 비율을 유지하기 위해 표본 추출)인 Feige의 가설이다.^[21]평균 사례 계산 경도 가정은 입력값보다 자연 분배가 있는 통계와 같은 응용 프로그램에서 평균 사례 경도를 입증하는 데 유용하다.^[22]또한, 심어진 집단 경도 가정은 지수 시간 가설과 ^[23]유사하게 다른 문제의 다항식 및 준폴리문식 최악의 시간 복잡성을 구별하기 위해 사용되었다.

유니크 게임스

Unique Label Cover 문제는 제약조건 만족도 문제인데, 여기서 각 $제약조건{\displaystyle }$C {\$displaystyle C}$은(는)${\displaystyle 두}$ 변수 x ,$$y {\$displaystyle x,y$을(를$)$ 포함하며,$$x {\$displaystyle$ x}의 각 값에 대해 y ${\displaystyty$$$y}의 고유한 값이 있다$$$.$ 모든$$값을 만족하는지 여부를 결정한다.그 제약 조건 만족할 수는 없지만, 독특한 게임 Conjecture이 거의 모든 제약에 어떤 상수 ε 을, 0{\displaystyle \varepsilon>0})또는 그들 중 거의 없다가(ε{\displaystyle \varepsilon}만족할 수도{\displaystyle(1-\varepsilon)}-fraction((1− ε)을 결정하는 공준(UGC) 쉽다.-fraction)은 NP-hard로 만족될 수 있다.^[16]근사적 문제는 종종 UGC를 가정하여 NP-hard로 알려져 있다. 그러한 문제를 UG-hard라고 부른다.특히, UGC를 가정하면 많은 중요한 문제에 대해 최적의 근사치 보증을 달성하는 반피니트 프로그래밍 알고리즘이 있다.^[24]

스몰 세트 확장

Unique Label Cover 문제와 밀접하게 관련되어 있는 것은 SSE(Small Set Expansion) 문제다.그래프 $G{\displaystyle }$=${\displaystyle }$( V${\displaystyle }$, ${\displaystyle E}$) ${\displaystyle$ G$=(V,E)}$을$($를) 지정하면 에지 확장이 최소인 정점 집합($n{\displaystyle }$/ ${\displaystyle \log }$ ${\displaystyle }$(${\displaystyle n}$ )${\displaystyle n/\log(n$을 찾으십시오.SSE의 근사치가 어렵다면 Unique Label Cover도 마찬가지인 것으로 알려져 있다.따라서 SSE가 근사치라고 가정하는 스몰 세트 확장 가설은 유니크 게임 추측보다 더 강력하지만 밀접하게 연관되어 있다고 가정한다.^[25]일부 근사치 문제는 SSE-hard^[26](즉, 적어도 근사치 SSE만큼)인 것으로 알려져 있다.

3SUM 추측

$n{\displaystyle }$ ${\displaystyle n}$개의$$ 숫자로 구성된 경우, 3SUM 문제는 합이 0인 세 개의 숫자가 있는지 여부를 묻는다.에는 3SUM에 대한quadratic-time 알고리즘과 게 없알고리즘"정말 시간sub-quadratic"에 3SUM를 해결할 수 있습니다. 그 3SUM Conjecture은 계산적 경도 가정이 없다는 주 있3SUM에 대한 상수 ε 을(;0{\display에{O(n^{2-\varepsilon})\displaystyle}-time 알고리즘(n2− ε) 것으로 추측하고 있었다는 것이다.세인트$yle \varepsilon >0}$ )이 추측은 주로 컴퓨터 기하학에서 나오는 몇 가지 문제에 대해 거의 2분위수적인 하한을 입증하는데 유용하다.^[27]

참고 항목

• 보안 수준

참조