Fiat-Shamir Transformation

본 글에서는 임의의 public-coin IP 프로토콜 $\mathcal L$ 을 non-interactive, publicly verifiable한 프로토콜 $\mathcal Q$ 로 변환하는, Fiat-Shamir Transformation에 대해 알아보겠습니다.

이 때 Public-coin protocol이란 Verifier의 모든 randomness가 Prover에게 공개되는 IP 시스템을 말합니다. 이러한 프로토콜은 대체로 $\mathcal V$가 $\mathcal P$에게 random challenge 를 보내고 $\mathcal P$는 그것에 답하는 형식으로 이루어 집니다. 이번 장에서 배울 Fiat-Shamir Transform을 적용하면 해당 IP 증명을 공개적으로 검증가능한 하나의 transcript로 간소화할 수 있습니다.

Random Oracle Model

Random Oracle Model (ROM) 이란 진짜 random function과 구별할 수 없는 Cryptographic hash function $R$이 존재한다는 가정입니다. Prover와 Verifier는 모두 $R$에 $x$를 쿼리해 $R(x)$ 값을 얻을 수 있습니다. 이 때 $R$은 한번 쿼리한 $x$에 대해서는 같은 결과값 $R(x)$를 출력한다는 점에서 consistent 하며, 한번도 쿼리되지 않은 $x$에 대해선 uniform random한 $R(x)$ 값을 리턴합니다.

이러한 Random Oracle Model을 가정하는 이유는 일반적인 Cryptographic hash function의 가정으로 안전성이 증명되지 않는 프로토콜을 ROM 하에서 hash function이 완전히 random 하다는 가정으로 안전성을 증명하기 위함입니다.

ROM 가정은 현실 세계와는 거리가 있는데, $R: \{0,1\}^{\ell_{in}} \to \{0,1\}^{\ell_{out}}$ 으로 놓으면 랜덤 함수 $R$을 저장하는 데에만 $2^{\ell_{in}}\cdot\ell_{out}$ 비트가 필요하게 됩니다. 그러나 현실에서는 $2^{\ell_{in}}\ge 2^{256}$ 정도로 큰 값을 사용하기에 이를 구현하기에 무리가 있습니다. 또한, ROM 하에서 안전성이 증명되었다고 real world에서 안전성이 증명되는 것은 아닙니다. 이와 관련된 반례를 다음 논문에서 찾아볼 수 있습니다. [CGH04] 그럼에도 ROM을 사용하는 것은 아직까지 ROM 가정 하에 안전성이 증명되었으나 뚫린 프로토콜 중 현실에서 사용되는 것은 없으며, ROM과 같은 강한 가정 하에서라도 안전성의 증명이 있는것이 낫기 때문입니다.

Motivation

우리는 어떻게 public-coin IP를 non-interactive, publicly verifiable한 증명으로 변환할 수 있을까요? 가장 naive한 접근은, Prover $\mathcal P$에게 모든 random challenges와 transcript 작성을 맡기는 것입니다. 그러면 Verifier $\mathcal V$는 $\mathcal P$와 interact할 필요 없이, 주어진 transcript에 적힌 random challenges에 대해 올바른 답이 적혀있는지만 검사하면 됩니다. 그러나 이 방법의 문제점은 $\mathcal P$가 untrusted 이므로 $\mathcal P$가 제시한 random challenges가 실제 uniform random하게 뽑힌 것인지 확인할 수 없다는 점입니다.

이를 개선하기 위해 random challenge를 random oracle $R$을 이용해 $i$번째 랜덤 값을 $r_i=R(i)$ 와 같은 방법으로 뽑아보겠습니다. 우리는 ROM을 가정했기 때문에 $\mathcal V$는 $r_i\stackrel{?}{=}R(i)$ 인지만 확인하면 $r_i$가 uniform random 값이라는 것을 확인할 수 있습니다. 그러나 이 방법 또한 unsound 합니다! 그 이유는 $\mathcal P$ 가 메세지 $g_1,\cdots,g_i$를 보내기 전에 challenge $r_1,\cdots,r_i$를 알고 있으므로 해당 challenge를 만족하도록 $g_i$ 를 조작한 뒤 보낼 수 있기 때문입니다. 예시로 $\mathcal P$가 다항식 $g_1(X), s(X)$에 대해 $g_1(r_1)=s(r_1)$임을 확인함으로써 $g_1=s$ 임을 증명하는 프로토콜을 생각해보겠습니다. 이 때 $\mathcal P$는 $r_1=R(1)$ 값을 오라클에 쿼리함으로써 미리 알 수 있기 때문에 false $g_1$을 다음과 같이 설정할 수 있습니다:

$$g_1(X)=s(r_1)+(X-r_1)h(X)$$

($h(X)\neq 0$는 임의의 다항식). 이 경우 $g_1\neq s$이지만 $g_1(r_1)=s(r_1)$ 임으로 false proof가 accept 되게 됩니다.

이를 해결하는 방법은 $\mathcal V$의 challenge $r_i$를 $\mathcal P$의 input $g_1,\cdots,g_i$에 의존하는 점에서 random oracle을 이용해 $r_i$를 뽑는 것입니다. 이렇게 하면 $\mathcal P$가 $g_i$를 조작하면 그에 따라 challenge $r_i$도 uniform random한 다른 값으로 바뀌므로 위와 같은 공격이 불가능하게 됩니다.

Fiat-Shamir transformation

Fiat-Shamir transformation의 완전한 construction은 다음과 같습니다:

public-coin IP $\mathcal L$의 round $i$에서 $\mathcal P$가 보낸 메세지 $g_i$에 대해 $\mathcal V$가 random challenge $r_i$를 보낸다고 가정하겠습니다. Fiat-Shamir Transform을 적용한 프로토콜 $\mathcal Q$ 에서, $\mathcal P$ 는 challenge $r_1,\dots,r_{l-1}$ 에 대해 계산된 $g_1,\dots,g_l$ 이 포함된 하나의 transcript를 보냅니다. 이 때, round $i$의 challenge $r_i=R(x,g_1,\dots,g_i)$ ($x$는 프로토콜의 public-input) 로 random oracle에 쿼리한 값을 사용합니다. 이렇게 변환된 $\mathcal Q$는 non-interactive하며, random oracle $R$에 쿼리할 수 있는 누구나 공개적으로 검증할 수 있습니다.

Notes

실제 구현에선 random oracle $R$으로 적당한 cryptographic hash function을 이용합니다. 또한 계산량을 줄이기 위해 hash chaining이라는 테크닉을 사용하는데, $r_i$를 계산할 때 한번에 $g_1,\dots,g_i$를 해시하는 것이 아니라 이전 라운드의 $r_{i-1}$ 값을 써서 $r_i=R(x,i,r_{i-1},g_i)$ 와 같이 계산합니다. 이러한 구현 방법도 random oracle model 하에서 secure함이 증명 가능합니다.

또 하나 중요한 디테일은, 각 라운드의 challenge $r_i$에 프로토콜의 input $x$가 같이 해시되어야 한다는 점입니다. 이렇게 $r_i$에 $x$를 포함해 해시하는 것을 strong Fiat-Shamir, 그렇지 않은 것을 weak Fiat-Shamir라고 부릅니다. 이러한 weak Fiat-Shamir는 false proof를 forge 할 수 있게되는 Frozen Heart 취약점을 일으킵니다. 예시로, input $x\in\mathbb F^n$에 대해 $C(x)=y$ 를 증명하는 GKR 프로토콜에 weak Fiat-Shmair를 적용한 것을 생각해보겠습니다. GKR 프로토콜의 마지막 라운드에서 우리는 input layer의 $x$에 대해 그 MLE $\tilde x$ 가 어떤 random point $r$과 값 $m$에 대해 $\tilde x(r)=m$ 임을 확인했습니다. 그러나 이 경우 $x$가 challenge $r$에 independent 하므로, 우리는 $r$과 $m$ 값을 미리 계산한 뒤 input $x$를 조작해 $\tilde {x}'(r)=m$ 을 만족하는 다른 $x'$을 찾을 수 있습니다. 해당 취약점에 대한 설명은 다음 블로그를 참고하세요. [1] [2]

Security

Sound한 public-coin IP $\mathcal I$에 대해, 그것을 Fiat-Shamir로 변환한 non-interactive proof $\mathcal Q$는 sound 할까요? 답은 그렇지 않을 수 있다입니다. (이것은 Fiat-Shamir가 만능이 아니라는 것을 시사해줍니다.) 우리는 변환된 $\mathcal Q$가 sound하게 되는 증명된 두 개의 ($\mathcal I$에 대한) 조건을 살펴보겠습니다.

Round-by-round soundness

먼저, $\mathcal I$가 round-by-round soundness 성질을 만족시키면 $\mathcal Q$ 또한 (ROM 하에서) sound 합니다. 이 때 round-by-round soundness란 다음 세 성질을 만족할 때 성립합니다:

1. $\mathcal I$의 모든 라운드에서 지금까지의 transcript에 의존하는 잘 정의된 state가 존재합니다. 이 때 "doomed" 상태라는게 존재하는데, 한번 doomed된 프로토콜은 (negligible한 확률을 제외하고) 영원히 doomed 상태를 유지하게 됩니다.

2. false input $x$에 대해서 $\mathcal I$의 초기 상태는 doomed 여야 합니다.

3. 만약 interaction이 끝날때 doomed 상태이면 검증자가 reject 합니다.

Sum-check 프로토콜을 예시로 생각해보면, 각 라운드마다 $g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$ 와 같은 관계식이 성립하는지 확인하고 한번이라도 reject되면 전체 프로토콜을 reject 하므로 round-by-round soundness를 만족한다는 것을 알 수 있습니다. 더 나아가 [CCH+19] 논문은 sum-check를 기반으로 한 모든 IP가 round-by-round soundness 하다는 것을 증명하였습니다. 따라서 이전 블로그에서 다룬 GKR 프로토콜 또한 Fiat-Shamir를 적용해도 (물론 ROM 가정 하에) 안전합니다.

Constant-round 인 경우

두번째로, $\mathcal I$가 sound한 constant-round IP 이면 $\mathcal Q$ 또한 sound 합니다. 여기에 대한 암호학적인 증명을 살펴보겠습니다.

Theorem 5.1. $\mathcal{I}$를 negligible한 soundness error를 갖는 constant-round public-coin IP (또는 argument) 라고 하자. 그러면 ROM 하에서 $\mathcal{I}$에 Fiat-Shamir 변환을 적용하여 얻은 $\mathcal{Q}$ 또한 negligible한 (computational) soundness error를 갖는다.

Proof. 이 증명은 귀류법과 함께 proof by reduction을 사용합니다. 만약 변환된 프로토콜 $\mathcal{Q}$를 깰 수 있는 공격자 $\mathcal{P}_{FS}$가 존재한다면, 이를 이용해 원래 프로토콜 $\mathcal{I}$를 깨는 공격자 $\mathcal{P}^*$를 만들 수 있음을 보입니다. 그러나 가정에 의해 이는 모순이므로 증명이 끝이 납니다.

먼저 증명을 간단히 하기 위해, $\mathcal{I}$를 증명자가 먼저 말하는 3-메시지 프로토콜이라고 가정합니다. 메시지 형태는 $(\alpha, \beta, \gamma)$입니다. ($\alpha$: $\mathcal P$의 첫 메시지, $\beta$: $\mathcal V$의 random challenge, $\gamma$: $\mathcal P$의 응답) 이제 false input $x$에 대해 시간 $T$ 안에 $\mathcal{Q}$의 검증자를 non-negligible한 확률 $\epsilon$으로 통과시키는 악의적인 증명자 $\mathcal{P}_{FS}$가 존재한다고 가정합니다. 일반성을 잃지 않고 $\mathcal{P}_{FS}$는 랜덤 오라클 $R$에 정확히 $T$번의 서로 다른 쿼리를 하며, random challenge $\beta=R(x, \alpha)$는 반드시 이 $T$번의 쿼리 중에 포함되어 있다고 가정합니다.

$\mathcal{P}^*$의 구성: 우리는 $\mathcal{P}_{FS}$를 내부 subroutine으로 실행시켜서, 원본 프로토콜 $\mathcal{I}$의 실제 검증자 $\mathcal{V}$를 속이는 증명자 $\mathcal{P}^*$를 다음과 같이 구성합니다. (이 과정이 proof by reduction의 핵심입니다. 이러한 증명에 익숙해지고 싶으시면 Katz & Lindell 교재를 보시는 것을 추천드립니다.)

1. $\mathcal{P}^*$는 $i \in \{1, \dots, T\}$ 중 하나를 무작위로 선택합니다. (이는 $\mathcal{P}_{FS}$가 보낼 $(x,\alpha)$ 쿼리가 몇 번째일지 맞히는 것입니다.)

2. $\mathcal{P}^*$ 는 $\mathcal{P}_{FS}$ 를 실행시키며 $\mathcal{P}_{FS}$ 가 랜덤 오라클에 쿼리할 때 마다 다음 규칙으로 대신 응답해줍니다.

   • $1 \dots i-1$ 번째 쿼리: $\mathcal{P}_{FS}$가 쿼리한 값을 그대로 랜덤 오라클에 쿼리해서 응답합니다.

   • $i$ 번째 쿼리: $\mathcal{P}_{FS}$가 $(x, \alpha)$를 쿼리 하면, $\mathcal{P}^*$는 이 $\alpha$를 외부의 실제 검증자 $\mathcal{V}$에게 첫 메시지로 전송합니다. $\mathcal{V}$가 $\alpha$에 대한 random challenge $\beta$를 보내오면, $\mathcal{P}^*$는 이 $\beta$를 마치 랜덤 오라클의 응답인 것처럼 $\mathcal{P}_{FS}$에게 전달합니다. (만약 쿼리가 $(x,\alpha)$ 가 아니라면 $i$ 값을 맞추지 못한 것이므로 종료합니다.)

   • $i+1 \dots T$ 번째 쿼리: 다시 랜덤 오라클에 쿼리해 응답합니다.

3. $\mathcal{P}_{FS}$가 최종 transcript $(\alpha, \beta, \gamma)$를 출력하면, $\mathcal{P}^*$는 $\gamma$를 $\mathcal{V}$에게 마지막 응답으로 보냅니다.

이제 $\mathcal P^*$가 성공할 확률 $\epsilon^*$을 구해보겠습니다. $\mathcal P^*$ 가 무작위로 선택한 $i$에 대해 정확히 $i$ 번째 쿼리가 $(x,\alpha)$ 가 되면 $\mathcal P^*$ 는 항상 성공함을 알 수 있습니다. 이 때 $i$ 값을 맞출 확률은 $1/T$ 이므로, $\epsilon^* \ge \epsilon/T$ 가 성립합니다. $\epsilon$은 non-negligible이고 $T$는 다항시간이므로 $\epsilon^*$ 또한 non-negligible 합니다. 즉, 우리는 false input $x$에 대해 기존의 IP $\mathcal I$를 non-negligible한 확률로 통과하는 증명자 $\mathcal P^*$ 를 만들었습니다. 이는 가정에 모순이므로, $\mathcal Q$를 다항시간에 깨는 공격자 $\mathcal P_{FS}$는 존재하지 않습니다. $\ \square$

Conclusion

이번 블로그에서는 Fiat-Shamir를 이용해 public-coin IP를 non-interactive, publicly verifiable한 증명으로 변환하는 방법을 알아보았습니다. 그러나 그 구현과 조건에 따라 취약점이 발생할 수 있다는 것을 이해해야 합니다. 감사합니다.