무작위 자기 축소성

Random self-reducibility

RSR(Random Self-Redibility)은 평균 사례에 대한 양호한 알고리즘이 최악의 경우를 위한 양호한 알고리즘을 의미한다는 규칙이다.RSR은 많은 부분을 해결함으로써 문제의 모든 인스턴스를 해결할 수 있는 능력이다.

정의

임의의 인스턴스(instance)를 평가하는 함수의 경우, x를 한 개 이상의i 임의 인스턴스(y)에 대한 f의 평가로 다항 시간 내에 축소할 수 있는 경우, 이는 스스로 축소할 수 있다(비적응적 균일 자기 감소라고도 한다).임의의 자기 감소에서, f의 영역에 있는 임의의 최악의 경우 인스턴스 x는 임의의 인스턴스1 y, ..., y에k 매핑된다. 이것은 매핑, x, f(y1), ..., f(yk)의 코인-토스 시퀀스를 감안하여, f(x)를 다항 시간 내에 계산할 수 있도록 한다.따라서 y에i 대한 유도 분포에 관한 평균을 보면 f의 평균 사례 복잡성은 f의 최악의 무작위화 복잡성과 동일하다(다항식 요인 내에서).

하나의 특별한 경우로, 각 임의 인스턴스i y가 길이가 x인 f의 영역에 있는 요소들의 전체 집합에 걸쳐 균일하게 분포되어 있을 때 이다. 이 경우 f는 평균적으로 최악의 경우만큼 단단하다.이 접근방식은 두 가지 주요 제한을 포함한다.먼저1 y, ..., y의k 세대는 비적응적으로 수행된다.f(y1)가 알려지기 전에 y가2 선택된다는 뜻이다.둘째, 점 y1, ..., y를k 균일하게 분포시킬 필요는 없다.

암호 프로토콜의 응용 프로그램

데이터에서 어느 정도의 프라이버시가 필요한 문제(일반적으로 암호화 문제)는 프라이버시를 보장하기 위해 무작위화를 사용할 수 있다.실제로 유일하게 보안이 가능한 암호시스템(일회용 패드)은 시스템에 공급되는 핵심 데이터의 무작위성에 전적으로 의존하는 보안성을 가지고 있다.

암호학 분야는 특정 숫자-이론적 함수가 임의로 자체 축소 가능하다는 사실을 활용한다.이것은 확률론적 암호화와 암호화된 강한 유사성 숫자 생성을 포함한다.또한 인스턴스(instance-hiding scheme) 방식(약한 개인 기기가 데이터를 노출하지 않고 강력한 공용 장치를 사용하는 경우)은 무작위 자가 저감에 의해 쉽게 예시된다.

예

이산 로그 문제, 2차 잔류성 문제, RSA 반전 문제, 매트릭스의 영구적 계산 문제는 각각 무작위 자체 축소 가능한 문제들이다.

이산 로그

정리: G 크기의 주기 그룹 G를 부여한다. 결정론적 다항식 시간 알고리즘 A가 모든 입력의 1/poly(n) 부분에 대한 이산 로그(여기서 n = 로그 G는 입력 크기)를 계산한다면, 모든 입력에 대한 이산 로그에 대한 랜덤화 다항식 시간 알고리즘이 있다.

주기 그룹 G = { gi 0 ≤ i < G }}의 발생기 g와 x ∈ G에 대한 x의 이산 로그는 x = g를k 갖는 정수 k (0 ≤ k < G )이다.{0, ..., G - 1}에 균일하게 분포되도록 B를 택한 다음, xgB = g도k+B G에 균일하게 분포한다.따라서 xg는B x와 독립적이며, 그 로그는 다항식 시간에서 확률 1/폴리(n)로 계산할 수 있다.그런 다음 logxg ≡ logxggB - B (mod G )와 이산 로그는 자체 축소 가능하다.

행렬의 영구

행렬의 영구적 정의에 비추어 볼 때, 어떤 n-by-n 매트릭스 M에 대한 PERM(M)은 M의 항목에 대한 다변량 다항식 n의 도라는 것은 분명하다. 매트릭스의 영구적 계산은 어려운 계산 작업이다.PERM은 #P-완전(방증)으로 나타났다.더욱이 대부분의 행렬에 대해 PERM(M)을 계산하는 능력은 모든 행렬에 대해 PERM(M)을 계산하는 임의 프로그램의 존재를 암시한다.이것은 PERM이 무작위적으로 자기축소가 가능하다는 것을 보여준다.아래 논의에서는 일부 prime p에 대해 유한한 필드p F에서 행렬 입력이 도출되고, 그 필드에서 모든 산술화가 수행되는 경우를 고려한다.

X는 F의p 항목이 있는 임의의 n-by-n 행렬이 되게 하라.모든 행렬 M + kX의 모든 항목이 k의 선형 함수이기 때문에, 이러한 선형 함수를 PUM(M)을 계산하는 다변량 다항식(dippariate polyomial)로 구성함으로써 k에 대한 또 다른 n 다항식을 얻게 되는데, 이를 p(k)라고 한다.분명히 p(0)는 M의 영구와 같다.

대부분의 n-by-n 행렬에 대한 정확한 PERM(A) 값을 F-특정적으로p 1 - 1/3(3n)의 항목으로 계산하는 프로그램을 알고 있다고 가정합시다.그러면 대략 2/3 확률로 k = 1,2, ...,n + 1에 대한 PERM(M + kX)을 계산할 수 있다.일단 그러한 n + 1 값을 얻으면 보간법을 사용하여 p(k) 계수에 대해 해결할 수 있다(p(k)에 n도가 있다는 것을 기억하라).일단 p(k)를 정확히 알게 되면 PERM(M)과 같은 p(0)을 평가한다.

그렇게 하면 3분의 1이 틀릴 위험을 무릅쓰지만, 복수의 랜덤 X를 선택하고 위의 절차를 여러 번 반복해, 다수 승자만을 답으로 제시함으로써 오류율을 매우 낮게 몰아갈 수 있다.

결과들

  • NP-완전한 문제가 비적응적으로 무작위적인 임의적 자체 축소 가능한 경우 다항식 계층 구조는 σ으로3 축소된다.
  • CoNP-hard 문제가 O(log n/n)에서 임의로 자체 축소 가능한 경우, σ2 = π2.

참조