기술 요약: 빠른 유계 독립 함수 및 그 쌍대 함수 (Fast Bounded-Independence Functions and Their Duals)

문제 정의

본 논문은 상수 시간의 계산 오버헤드를 유지하면서 무작위 함수(random functions) 및 무작위 선형 코드(random linear codes)의 통계적 특성을 모방하는 암호학적 프리미티브를 구축하는 과제를 다룹다. 구체적으로 저자들은 다음을 만족하는 "빠른(fast)" 구현(선형 크기 산술 회로 $O(n)$로 계산 가능한 것으로 정의됨)을 추구한다:

1. 유계 독립성 (Bounded Independence): 임의의 상수 $t$에 대해 $t$-wise 독립인 해시 함수.
2. 빠른 쌍대 코드 (Fast Dual Codes): 코드와 그 쌍대(dual) 모두가 빠른 체계적 인코딩(systematic encoding)을 허용하며, 길버트-바르샤모프(Gilbert-Varshamov, GV) 경계에 근접한 거리를 갖는 선형 코드 제품군.
3. 더 강력한 무작위 유사 특성: 단순한 거리를 넘어 리스트 디코딩 가능성(list-decodability)과 같은 특성까지 확장하여, 코드가 국소적 제약(local constraints) 하에서도 무작위 선형 코드처럼 동작하도록 보장함(국소적 유사성).

[IKOS08] 및 [DI14]와 같은 이전 연구들은 빠른 쌍선형 독립(pairwise independent) 해시 함수와 GV 경계에 접근하는 빠른 코드들을 확립했으나, 독립성 파라미터 $t$, 연산 필드, 또는 코드와 그 쌍대를 동시에 최적화할 수 있는 능력 측면에서 종종 한계를 보였다. [BR26]의 최근 연구는 빠른 쌍대 코드를 개선했으나, 이진 필드로 제한되었고, 고정된 비율 1/2을 요구했으며, 무시할 수 없는 실패 확률을 가졌고, 체계적 인코딩이 결여되어 있었다.

방법론

저자들은 "IKOS 구성(Ishai, Kushilevich, Ostrovsky, Sahai)"과 "DI 구성(Druk, Ishai)"을 기반으로 하여, 이를 더 높은 독립성 파라미터로 일반화한다.

1. 해시 함수의 일반화

해시 함수를 위한 핵심 구성은 3단계 파이프라인을 따른다:

1. 외부 인코딩 (Outer Encoding): 큰 (그러나 상수의 크기를 갖는) 알파벳 위에서 큰 거리를 가진 빠른 선형 코드를 입력에 적용한다.
2. 내부 해싱 (Inner Hashing): 인코딩된 벡터의 각 좌표에 상수 크기의 $t$-wise 독립 해시 함수를 적용한다.
3. 추출 (Extraction): 좋은 코드의 생성 행렬의 전치 행렬(transpose of a generator matrix)을 추출기(extractor)로 사용하여 결과를 적용한다.

$t$-wise 독립성을 달성하기 위해, 저자들은 내부 단계에서 상수 크기의 쌍선형 독립 해시 함수를 상수 크기의 $t$-wise 독립 해시 함수로 대체한다. 저자들은 만약 외부 코드가 충분히 큰 거리(구체적으로 $> 1 - 1/t^2$)를 가진다면, $t$개의 입력의 구별성이 충분한 좌표 분율에 걸쳐 보존되어, 내부 해시 함수가 독립적이고 균등한 출력을 생성할 수 있게 하며, 최종 추출 단계가 이를 보존함을 증명한다.

2. 선형 균등 출력 패밀리 (Linear Uniform Output Families, LUOF)

코드를 구축하기 위해 저자들은 선형 균등 출력 패밀리(LUOF) 개념을 활용한다. 무작위 행렬 $A$가 LUOF라는 것은, 임의의 0이 아닌 입력 $x$에 대해 출력 $xA$가 균등하게 분포됨을 의미한다.

• 빠른 LUOF: 저자들은 [DI14]의 구성을 일반화하여 빠른 $t$-LUOF를 만든다. 행렬 $A$가 $t$-LUF라는 것은, 임의의 $t$개의 선형 독립 입력 $x_1, \dots, x_t$에 대해 출력 $x_1A, \dots, x_tA$가 균등하고 확률적으로 독립적임을 의미한다.
• 구성: 이 과정은 해시 함수 구성과 유사하게, 외부 코드, 무작위 상수 크기 행렬 층(내부 함수 역할), 그리고 추출 단계를 포함한다. 저자들은 외부 코드가 충분한 거리를 가진다면, 내부 무작위 행렬들이 선형 독립인 입력들을 독립적인 균등 출력으로 매핑함을 증명한다.

3. 빠른 쌍대 코드의 구축

$t$-LUOF 행렬 $A \in \mathbb{F}_q^{k \times r}$를 사용하여, 저자들은 체계적 인코딩 맵 $x \mapsto (x, xA)$를 갖는 코드 $C$를 정의한다.

• 쌍대성 (Duality): 쌍대 코드 $C^\perp$는 맵 $y \mapsto (-yA^\top, y)$에 의해 생성된다.
• 전치 원리 (Transposition Principle): 전치 원리(Lemma 3.4)를 인용하여, $xA$를 계산하는 것이 빠르면(선형 크기),$yA^\top$를 계산하는 것 또한 빠름을 주장한다.
• 쌍대의 독립성: 핵심적인 기술적 기여는 $A$가 $t$-LUF라면 $A^\top$ 역시 $t$-LUF임을 증명하는 것이다(Lemma 3.9). 이는 Vazirani의 XOR Lemma에 의존하며, 쌍대 코드가 기본 코드의 강력한 무작위성을 상속받도록 보장한다.

주요 기여 및 결과

1. 빠른 $t$-wise 독립 해시 함수

• 결과: 임의의 상수 $t$에 대해, 저자들은 선형 크기 회로로 계산 가능한 $t$-wise 독립 해시 함수 패밀리를 구축한다.
• 최적화: 이진 필드($q=2$)의 경우, 대수적 차수(algebraic degree)는 $\log_2 t$로 최적화된다. 이는 더 낮은 차수로는 $t$-wise 독립성을 지원할 수 없으므로 거의 최적에 가깝다.
• 효율성: 회로 크기는 $O(k+r)$이며, 여기서 $k$는 입력 길이, $r$은 출력 길이이다. 숨겨진 상수는 $t$에 따라 달라지지만(대략 $\Theta(t^7)$), $t$가 고정된 경우 상수로 유지된다.

2. 빠른 쌍대를 갖는 빠른 코드 (GV-Bound)

• 결과: 저자들은 임의의 유한 필드 $\mathbb{F}_q$ 위에서 임의의 비율 $R \in (0, 1)$을 갖는 코드 $C$와 그 쌍대 $C^\perp$의 패밀리를 구축한다.
• 특성:
  • $C$와 $C^\perp$ 모두 빠른 체계적 인코딩(선형 크기)을 지원한다.
  • 두 코드 모두 확률 $1 - 2q^{-\varepsilon n}$로 길버트-바르샤모프(GV) 경계에 $\varepsilon$-근접한 거리를 달성한다.
  • 이 구성은 무시할 수 있는 실패 확률을 가진다([BR26]과 대조적임).
  • 인코딩을 위한 선형 크기의 유니버설 회로를 지원한다.

3. 빠른 쌍대를 갖는 빠른 리스트 디코더블 코드

• 결과: $t$-LUF 특성을 활용하여, 저자들은 구축된 코드를 $t$-국소적으로 유사한(t-locally similar) 무작위 선형 코드로 확장한다.
• 리스트 디코딩: 저자들은 구축된 코드(및 그 쌍대)가 리스트 크기 $L = O(1/\varepsilon)$에 대해 리스트 디코딩 용량까지 $(\rho, L)$-리스트 디코더블함을 증명한다.
• 독창성: 이는 저자들이 아는 바에 따르면, 빠른 인코딩, 빠른 쌍대 인코딩, 그리고 코드와 그 쌍대 모두에 대한 최적의 리스트 디코더블성을 동시에 달성하는 최초의 구성이다.

의의 및 암호학적 응용

본 논문은 이러한 구성들이 높은 효율성과 강력한 보안 보장을 요구하는 시나리오, 특히 암호학에서 강력한 빌딩 블록 역할을 한다는 것을 보여준다.

1. 완벽하게 안전한 다자간 계산 (Perfectly Secure MPC)

저자들은 계산 복잡도가 참여자 수($n$)에 대해 선형적으로 스케일링되는($O(n)$) 완벽하게 안전한 MPC를 위한 최초의 비자명한 프로토콜을 제시한다.

• 맥락: 대수적 코드(예: 리드-솔로몬)를 사용하는 기존 프로토콜은 종종 준선형(quasi-linear) 오버헤드를 발생시켰다.
• 응용: 빠른 쌍대 코드를 사용하여, 저자들은 Oblivious Linear Evaluation (OLE) 프로토콜을 구축하고 이를 일반적인 상수 크기 함수로 확장한다. 이 프로토콜은 수동적 공격자(passive adversary)에 대해 보안 임계값 $t = (1/2 - \varepsilon)n$을 달성한다.

2. 암호화된 행렬-벡터 곱 (Encrypted Matrix-Vector Products, EMVP)

복잡도 기반 암호학의 맥락에서, 저자들은 빠른 쌍대 코드를 암호화된 행렬-벡터 곱에 적용한다.

• 개선: 이 구성은 [BR26] 방식의 한계(이진 필드 $\mathbb{F}_2$로 제한되고 무시할 수 없는 실패 확률을 가짐)를 극복한다.
• 이점: 이를 통해 행렬 인코딩과 쿼리 인코딩 모두가 점근적으로 최적의 회로 복잡도를 갖는 EMVP 프로토콜이 가능해진다.

3. 무작위 선형 코드의 보수적 대체물

$t$-LUF 구성은 무작위 선형 코드(예: LPN - Learning Parity with Noise)의 어려움에 의존하는 응용 분야를 위한 "보수적인" 대체물을 제공한다.

• 장점: 기존 구성들이 최소 거리(1-local similarity)에만 의존했던 반면, $t$-LUF는 $t$-국소적 유사성을 보장하여 리스트 디코더블성과 같은 더 강력한 조합론적 특성을 보장한다. 이는 국소적 구조를 악용할 수 있는 공격에 대해 더 견고한 보안 가정을 제공한다.

4. MPC 친화적 해싱

낮은 대수적 차수를 가진 빠른 $t$-wise 독립 해시 함수는 회로 크기와 대수적 차수가 모두 통신 및 라운드 복잡도에 영향을 미치는 MPC 프로토콜에 직접적으로 적용 가능하다. 이 구성은 두 가지를 동시에 최적화한다.

결 결론

본 논문은 이전의 선형 크기 구성을 더 높은 독립성 파라미터와 더 강력한 무작위 유사 특성을 지원하도록 성공적으로 일반화하였다. 빠른 $t$-LUF를 도입하고 그 쌍대성을 증명함으로써, 저자들은 동시에 빠르고, 체계적이며, 통계적으로 견고한 코드와 해시 함수를 구축하기 위한 통합된 프레임워크를 제공한다. 이러한 결과는 정보 이론적 MPC 및 암호화된 계산, 특히 최적의 점근적 복잡도를 갖는 새로운 암호학적 프로토콜을 가능하게 한다.