하드코어 술어

암호학에서 단방향 함수 f의 하드코어 술어는 (x의 함수로서) 계산은 쉽지만 주어진 f(x)를 계산하기는 어려운 술어 b(즉, 출력이 단일 비트인 함수)이다.공식적인 면에서는 만약 x한결같이 어떤 PPT 상대만 노골적인 비트 b())고 균일하게 임의로 비트 재치를 구별할 수 있는, 그때 주어진 f())에 그려져 있는 f())에서 x.[1]의 무작위 선택:34 다른 단어에서는 확률 크게 2분의 1보다 통계적으로 b())를 계산하지 확률론적 다차 함수 시간(PPT)알고리즘은.hneglx의 길이에 비해 읽기 쉬운 ^[2]장점

하드코어 함수는 유사하게 정의될 수 있다.즉, x를 무작위로 균일하게 선택한 다음 f(x)를 주어진다면, 어떤 PPT 알고리즘도 x의 길이에 대해 무시할 수 있는 이점을 가진 길이 h(x)의 하드코어 함수 값 h(x)와 균일하게 무작위 비트를 구별할 수 있을 뿐이다.^[3][4]

하드코어 술어는 f를 뒤집는 경도를 "집중된 의미"로 포착한다.

단방향 함수는 반전하기 어렵지만, 이미지 f(x)에서 preimage c에 대한 부분적인 정보를 계산하는 실현 가능성에 대한 보장은 없다.예를 들어, RSA가 단방향 함수로 추측되는 동안, 프리이미지의 자코비 기호는 이미지의 그것으로부터 쉽게 계산될 수 있다.^{[1]: 121}

일대일 함수가 하드코어 술어를 가지고 있다면 그것은 반드시 한 가지 방법임이 분명하다.오드 골드레이치와 레오니드 레빈(1989)은 모든 일방적 기능이 어떻게 사소한 방식으로 수정되어 특정 하드코어 술어를 가진 일방적 기능을 얻을 수 있는지를 보여주었다.^[5]f를 단방향 함수로 하자.g(x,r) = (f(x), r)를 정의한다. 여기서 r의 길이는 x의 길이와^th 같다. x는_j x의 j 비트와 r의_j^th j 비트를 나타낸다.그러면

${\displaystyle b(x,r):=\langle x,r\r\rangele =\bigoplus _{j}x_{j}r_{j}}}}}$

g의 핵심 술어다.b(x, r) = <x, r>, 여기서 <···>는 벡터 공간(Z₂)에 있는 표준 내측 제품을 나타낸다.ⁿ이 술어는 계산상의 문제로 인해 하드코어다. 즉 g(x, r)는 이론적으로 손실되는 정보이기 때문에 계산하기가 어렵지 않다.오히려 이 술어를 효율적으로 계산하는 알고리즘이 존재한다면 f를 효율적으로 반전시킬 수 있는 다른 알고리즘이 존재한다.

유사한 구조는 O(log x ) 출력 비트로 하드코어 기능을 산출한다.f가 강력한 단방향 함수라고 가정하자.g(x, r) = (f(x), r)를 정의하십시오. 여기서 r = 2 x . 길이 함수 l(n) = O(log n) s.t. l(n) ≤ n을 선택하십시오.

${\displaystyle b_{i}(x,r)=\bigoplus _{j}x_{j}r_{i+j}}}$

그러면 h(x, r) := b₁(x, r) b₂(x, r) ...b_{l( x )}(x, r)는 출력 길이 l( x ^[6])를 갖는 하드코어 함수다.

입력 x의 실제 비트가 하드코어인 경우도 있다.예를 들어 RSA 함수에 대한 모든 입력 비트는 RSA의 하드 코어 술어이며, 다항 시간(RSA 함수가 반전되기 어렵다는 가정 하에)의 O(log x ) 비트 블록은 랜덤 비트 문자열과 구별할 수 없다.^[7]

하드코어 술어는 모든 단방향 순열로부터 유사 항문 생성기를 구성할 수 있는 방법을 제공한다.b가 단방향 순열 f의 하드코어 술어이고 s가 임의의 씨앗이라면,

${\displaystyle \{b(f^{n}s)\}_{n}}$

가성 비트 시퀀스인 여기서 f는ⁿ s에 f를 적용하는 n번째 반복을 의미하며 b는 각 라운드 n에 의해 생성된 하드코어 비트다.^{[1]: 132}

트랩도어 단방향 순열(트랩도어 술어)의 하드 코어 술어를 사용하여 의미적으로 안전한 공용 키 암호화 체계를 구축할 수 있다.^{[1]: 129}

참고 항목

• 목록 디코딩(Descripts list-decoding; 단방향 함수의 하드코어 술어를 Goldreich-Levin 구성의 핵심은 Hadamard 코드를 리스트 디코딩하는 알고리즘으로 볼 수 있다).

참조

• Oedded Goldreich, Cryptography의 Foundations of Cryptography vol 1: Basic Tools, 2001.