가성함수군

암호학에서, 약칭 PRF라고 하는 유사함수 계열은, PRF 계열에서 무작위로 선택한 함수와 랜덤 오라클(출력이 고정된 c인 함수)을 구별할 수 없는 (중대한 우위성을 갖는) 효율적인 연산함수의 집합이다.완전히 임의로).유사성 함수는 암호화 원시성, 특히 안전한 암호화 체계 구축에 필수적인 도구다.

가성 함수는 가성 생성기(PRG)와 혼동해서는 안 된다.PRG의 보장은 입력을 무작위로 선택한 경우 단일 출력이 무작위로 나타나는 것이다.한편, PRF의 보증은 해당 기능이 PRF 계열에서 무작위로 추출된 한, 해당 입력을 어떻게 선택했는지에 관계없이 모든 출력이 무작위로 나타나는 것이다.

가성 함수 패밀리는 예를 들어 골드리치, 골드와세르, 미칼리가 제공한 "GGM" 구조를 사용하여 모든 가성 생성기로 구성될 수 있다.^[1]실제로 블록 암호는 유사 함수가 필요한 대부분의 경우에 사용되지만, AES와 같은 블록 암호는 제한된 입력 수와 키 크기에 대해서만 정의되기 때문에 일반적으로 유사 함수의 패밀리를 구성하지는 않는다.^[2]

무작위 함수의 동기 부여

PRF는 효율적이며(즉, 다항식 시간에 계산 가능), 두 개의 구별되는 집합(도메인 및 범위)을 매핑하는 결정론적 함수로서 진정한 무작위 함수처럼 보인다.

본질적으로, 진정한 무작위 함수는 균일하게 분포된 무작위 항목으로 채워진 룩업 테이블로 구성될 것이다.그러나 실제로는 PRF에 도메인 내의 입력 문자열과 숨겨진 임의 시드가 주어지고 동일한 입력 문자열과 시드로 여러 번 실행되어 항상 동일한 값을 반환한다.그럼에도 불구하고 임의의 입력 문자열이 주어지면, 균일한 분포에서 시드를 추출하면 출력이 무작위로 보인다.

PRF는 그 행동이 진정한 무작위 함수와 구별할 수 없는 경우에 좋은 것으로 간주된다.따라서, 실제 무작위 함수 또는 PRF의 출력이 주어진다면, 출력이 실제 무작위 함수 또는 PRF에 의해 생성되었는지 정확하게 판단할 수 있는 효율적인 방법이 없어야 한다.

형식 정의

기능들의 가족,

${\displaystyle f_{s}:\left\{0,1\right\}^{\lambda (\left s\right )}\rightarrow \left\{0,1\right\}^{\lambda (\left s\right )}}$, where ${\displaystyle s\in \left\{0,1\right\}^{*}}$, and ${\displaystyle \lambda :\mathbb {$$N} \rightarrow \mathb {N} }$

다음 조건이 충족되는 경우 유사함수:

• ${\displaystyle x_{}}$${\displaystyle }$= ${\displaystyle \lambda }$( s${\displaystyle }$) ${\displaystyle \좌측\vert x\우측\vert=\lambda$${\displaystyle {}_{}\mathrm{좌측}}$$\vert s$${\displaystyle \backslash }$$우측\vert$ $)\}$과 같은 s ${\displaystyle$ $s}$ $및$ x ${\displaystystyle$ $f_{s}(x)$를 계산하는 다항식 알고리즘이 항상 존재한다$.$
• $F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$을$($를$)$${\displaystyle }${${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^n}$ ${\$$n$$\}\}$에 걸쳐 균일한 분포로$$ 하고, ${\displaystyle {RF}_{}}$$$ ${\$${$n$}}}}$은(를)의 모든 기능 집합에 걸쳐 균일한 분포를 나타낸다$$$$.${\displaystyle \{}$ ${\displaystyle 0,}$ 1 ${\displaystyle n^{}}$ ${\$$\}\}\{{\displaystyle 0,}$1$$$\}^{n}}{$ 그러면 F n ${\$$displaystyle$$$$F_{n}$와 ${\displaystyle {}_{}}$F {\displaystystyle $RF_{n}$는 계산상 구별이 불가능하며, 여기서 ${\displaystyle n_{}}$은 보안 매개 변수다.즉, F ${\displaystyle n_{}}$ ${\$ 또는$$ $R{\displaystyle }$ ${\displaystyle F_{}}$ n ${\$에서 샘플링된 함수의 오라클을 쿼리할 수 있는 모든 적수에게 주어진 오라클의 종류를 구분할 수 있는 이점은 무시해도 좋다$.$^[3]

망각 유사함수

약칭 OPRF인 망각 유사함수에서 정보는 PRF와 관련된 두 당사자로부터 은폐된다.^[4]즉 앨리스가 비밀의 가치를 암호로 해시하고, 암호로 해시를 블라인딩하여 밥에게 보내는 메시지를 생산하고, 밥이 비밀의 가치를 섞어서 최종 산출물을 얻기 위해 블라인드를 해제하는 앨리스에게 그 결과를 돌려준다면, 밥은 앨리스의 비밀가치도, 최종 산출물도 볼 수 없고, 앨리스도 B를 볼 수 없다는 것이다.ob의 비밀 입력, 그러나 앨리스는 두 입력의 PRF인 최종 출력물을 본다 - 앨리스의 비밀과 밥의 비밀.^[5]이를 통해 신뢰할 수 없는 당사자 간에도 민감한 암호정보의 거래를 안전하게 할 수 있다.

OPRF는 암호 인증 키 계약의 일부 구현에 사용된다.^[5]

OPRF는 Microsoft Edge의 Password Monitor 기능에 사용된다.^[6]

적용

PRF는 다음을 위해 사용할 수 있다.^[7]

1. 동적 완벽한 해싱; 상대가 해싱 함수가 이전 키에 할당한 값에 따라 키 트립을 변경할 수 있더라도 상대는 충돌을 강요할 수 없다.
2. 선택한 메시지 공격에 대해 확실히 안전한 결정론적 메모리 없는 인증 체계(메시지 인증 코드 기반) 구축.
3. 보관량이 적은 스테이션에서 로컬로 확인할 수 있는 용서할 수 없는 ID 번호 배포.
4. 식별 친구 또는 적 시스템 구축.

참고 항목

• 가성순열

메모들

참조

• Goldreich, Oded (2001). Foundations of Cryptography: Basic Tools. Cambridge: Cambridge University Press. ISBN 978-0-511-54689-1.
• Pass, Rafael, A Course in Cryptography (PDF), retrieved 22 December 2015