계산적으로 경계된 적수

정보이론에서 계산적으로 묶여 있는 상대적 문제는 시끄러운 채널을 통해 데이터를 전송하는 문제를 바라보는 다른 방법이다.이전 모델에서는 최대 d/2 오류에 대해 정확한 디코딩을 보장하는 것이 가장 좋았고, 여기서 d는 코드의 해밍 거리였다.이렇게 하는 것의 문제는 상대가 이용할 수 있는 실제 컴퓨팅 파워의 양을 고려하지 않는다는 것이다.오히려 주어진 코드 워드의 몇 비트가 변화할 수 있고 여전히 메시지 디코딩이 제대로 되어 있는지 그것 자체만을 걱정한다.연산적으로 경계된 상대 모델에서 채널(상대방)은 코드 워드의 어떤 비트를 변경해야 할지를 결정하기 위해 합리적인 양의 연산만 수행할 수 있는 것으로 제한된다.즉, 이 모델은 얼마나 많은 오류를 처리할 수 있는가를 고려할 필요가 없고, 단지 얼마나 많은 오류가 상대편에서 합리적인 양의 계산력을 부여할 수 있는가에 대해서만 도입될 수 있는 것이다.일단 채널에 이러한 제한이 주어지면, 많은 수의 오류를 처리할 수 있는 이전의 방법에 비해 인코딩과 디코딩이 모두 더 빠른 코드를 구성할 수 있게 된다.

다른 모델과의 비교

최악의 경우 모형

언뜻 보기에 최악의 경우 모델은 직관적으로 이상적으로 보인다.물론 어떤 알고리즘이 고도로 유혹되어도 성공할 수 있다는 보장.하지만, 그것은 너무 많은 것을 요구한다.현실의 적수는 알고리즘이 고전할 한 가지 오류 패턴을 찾기 위해 메시지를 검토하는 데 무한정 많은 시간을 할애할 수 없다.

비교로 Quicksort 알고리즘을 고려하십시오.최악의 경우 Quicksort는 O(n²) 비교를 하지만 그러한 경우는 드물다.Quicksort는 거의 변함없이 O(n log n) 비교를 하고 O(n log n) 동작을 보장할 수 있는 다른 알고리즘을 능가하기도 한다.적이 퀵소트 알고리즘을 강제로 O²(n) 비교하게 하고 싶다고 가정해 봅시다.그런 다음 입력 문자열의 n! 순열 모두를 검색하고 알고리즘이 상당히 느리게 실행되는 알고리즘을 찾을 때까지 각각에 대해 알고리즘을 테스트해야 한다.그러나 이것은 시간이 걸릴 것이기 때문에, 적들이 이것을 하는 것은 분명히 불가능하다.마찬가지로, 가장 효과적인 오류 패턴을 찾기 위해 모든 오류 패턴을 테스트할 수 있는 인코딩 및 디코딩 시스템의 적수를 가정하는 것은 불합리하다.

확률형 소음 모델

확률적 소음 모델은 일종의 "덤프" 소음 모델이라고 설명할 수 있다.즉, 「지능형」위협에 대처할 수 있는 적응력을 갖추지 못하고 있다.비록 공격자가 경계가 있다고 해도, 그들이 약간의 영리함으로 확률론적 모델을 극복할 수 있을 가능성이 여전히 있다.확률적 모델은 이런 종류의 공격에 대항할 실질적인 방법을 가지고 있지 않으며, 따라서 그러한 모델은 방어력을 갖추는 것이 더 바람직한 일종의 "지능적" 위협에 대처하는 데 적합하지 않다.

---

따라서, 계산적으로 경계된 대립적 모델은 둘 사이의 타협으로 제안되었다.^[1]이것은 메시지가 의식적이고 심지어 악의적인 방법으로 왜곡될 수 있다는 것을 고려하도록 강요하지만 알고리즘 설계자가 결코 일어날 것 같지 않은 희귀한 사례에 대해 걱정하도록 강요하지 않는다.

적용들

확률적 소음 채널과 비교

연산적으로 바인딩된 적수는 O(n)시간 내에 각 비트에 대해 동전을 휙휙 던질 수 있으므로, 이 적에 대해 작동할 수 있는 인코딩 및 디코딩 시스템도 확률적 소음 모델에서 작동해야 한다는 것은 직관적으로 분명하다.역방향은 덜 단순하지만, 확률적 소음 모델에서 작동하는 시스템은 계산적으로 경계된 적에 대해 효율적으로 인코딩 및 해독할 수 있으며, 오직 n의 다항식인 추가 비용만 들 수 있다는 것을 보여줄 수 있다.^[1]이를 달성하기 위한 다음과 같은 방법은 딕 립톤에 의해 설계되었으며, 다음 방법에서 취한다.^[1]

$E{\displaystyle }$(${\displaystyle }$) ${\displaystyle$ E$()}$을(를) 확률형 소음 모델의 인코더로 하고$$ $D{\displaystyle }$(${\displaystyle }$) ${\displaystyle D()}$을(를) 같은 것에 대한 단순한 디코더로 두며$$, 각각 다항식으로 실행된다.또한 송신자와 수신자 모두 일부 임의 순열 함수 $\pi {\displaystyle }$ ${\displaystyle \pi }$ 및 임의$$ 패턴 $R{\displaystyle }$ ${\displaystyle R}$을(를) 공유하도록 하십시오$.$

인코딩의 경우: 1.$X{\displaystyle }$= ${\displaystyle E}$( ${\displaystyle M}$) ${\displaystyle X=E(M)}$을(를) 놓으십시오$.$

2. $Y{\displaystyle }$= ${\displaystyle \pi }$ (${\displaystyle X}$) ${\displaystyle \oplus }$ ${\displaystyle R}$ ${\displaystyle$ Y$=\pi (X)\oplus$ R$\}.$

3. $전송{\displaystyle }$ Y ${\디스플레이$ 스타일 $Y}$

디코딩의 경우: 1.$수신{\displaystyle }$ Y${\displaystyle {}^{}}${$${\$displaystyle$ Y$'}.$ 계산 ${\displaystyle {}^{}}$= $.$ - ${\displaystyle 1^{}}$(${\displaystyle {}^{}{}^{}{-}^{}}$ ) {\$displaystyle$ Z$=\pi ^{-1}(Y'\oplus$ R$)}$.

2. $M{\displaystyle }$= ${\displaystyle D}$( ${\displaystyle Z}$) ${\displaystyle$ M$=D(Z$)} 계산$.$

위의 Quicksort 비교와 유사하게, 채널이 스마트한 무언가를 하고 싶다면, 먼저 모든 순열을 테스트해야 한다.그러나 이는 계산적으로 구속되어 있는 상대에게는 불가능한 일이므로 임의의 $오류$ 패턴 $N$을 $만드는$ 것이 가장 효과적이다$.$ 그러나 그 다음:

${\displaystyle Z=\pi ^{-1}(Y'\oplus R)=\pi ^{-1}(Y\oplus N\oplus R),}$

$Y{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$= ${\displaystyle Y}$ ${\displaystyle \oplus }$ ${\displaystyle N}$ ${\displaystyle$ Y$'=Y\oplus N}$을(를) 정의하기$$ 때문에.

${\displaystyle =}$ ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$( ${\displaystyle Y}$ ${\displaystyle \oplus }$ ${\displaystyle R}$) ${\displaystyle \oplus }$ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ R$)\oplus N$ 여기서 $N{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$= ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ (${\displaystyle {}^{}N}$)${\displaystyle }$, ${\displaysty$ N$'=\pi ^{-1},}$

모든 순열은 XOR에 대해 선형이기 때문에,

${\displaystyle =X\oplus N',}$

$위$의 Y ${\displaystyle Y}$의 정의에 따라

$\pi {\displaystyle }$ ${\displaystyle \pi}$은(는) $랜덤$이므로 N ${\displaystyle {\prime }^{}}$ ${\$ N$'}$은(는) 랜덤 노이즈일 뿐이며, 간단한 디코더를 사용하여 수신된 $메시지$를 디코딩하고 M ${\displaystyle M}$을(를) 다시 받을 수 있다$.$

특정 응용 프로그램

계산적으로 경계된 적수를 가정하면, 효율적이면서도 거의 최적에 가까운 로컬로 해독 가능한 코드를 설계할 수 있으며, 오류 확률은 무시할 수 있다.이러한 코드는 자가 교정 연산, 확률적으로 확인 가능한 증명 시스템, 의사 무작위 생성기 구성에서 최악의 경우에서 평균까지의 경도 감소와 같은 것에 대해 복잡성 이론에 사용된다.그것들은 개인 정보 검색 프로토콜과의 연결로 암호화에 유용하다.그것들은 또한 내결함성 데이터 스토리지와 같은 다수의 데이터베이스 애플리케이션에 있다.^[2]

또한 최악의 경우 코드에 대해 알려진 경계를 초과하는 코드($특히{\displaystyle \mathrm{}}$ 1${\displaystyle }$- ${\displaystyle R}$ ${\displaystyle 1-R}$ 오류율을$$ 가진 고유 디코딩)를 구성할 수 있다.^[3]이것은 타임스탬프된 디지털 서명을 메시지에 연결함으로써 이루어질 수 있다.계산적으로 경계된 채널은 서명을 위조할 수 없으며, 유효한 과거 서명을 가지고 있는 동안 수신자는 디코딩 목록을 사용할 수 있으며 서명에 올바른 타임스탬프가 있는 경우에만 메시지를 선택할 수 있다.

참조