로컬 믹싱을 통한 코드 난독화

Nicholas Ho, Ran Canetti, Janmajaya Mall에게 피드백과 검토에 특별히 감사드립니다.

이 시리즈의 지난 두 부분에서 우리는 암호학적 난독화(iO) 프로토콜의 주요 계열 두 가지를 살펴보았습니다. 하나는 다소 표준적인 암호학적 가정을 기반으로 구축하려 하지만, 엄청난 오버헤드라는 대가를 치르는 주류적이고 보수적인 라인이며, 다른 하나는 더 많은 새로운 격자 기반 가정(lattice-based assumptions)을 추가하고 오버헤드를 대폭 줄였지만, 여전히 실행 가능할 만큼 충분하지 않은 다이아몬드 iO입니다. 본 포스트에서는 오늘 작업 중인 세 번째 주요 계열인 "로컬 믹싱(local mixing)"에 대해 알아보겠습니다.

로컬 믹싱에 대해 알아야 할 첫 번째 사실은 이것이 암호학을 수행하는 완전히 다른 방식이라는 것입니다. 여기에는 타원 곡선도, 소수 분해(prime factorization)도, 격자 구조도 없습니다. 실제로 "정규적인" 암호학이 여기서 다루는 것과 가장 유사한 것은 대칭키 암호학—암호화 및 해시 함수 설계입니다.

대칭 암호화와 해시 함수 설계에는 "만약 이것을 해독할 수 있다면, 그것은 매우 큰 숫자를 빠르게 인수분해할 수 있음을 의미한다"와 같이 잘 구조화된 수학적 문제로 깔끔하게 환원되는 과정이 없습니다. 대신, 이 분야는 사람들이 의사 난수(pseudorandom) 함수를 만들려고 시도하고, 수학자들이 이를 공격하며, 사람들은 그러한 공격으로부터 보호하는 설계 트릭을 찾아내는 50년에 걸친 전통이 존재해 왔으며, 마침내 모든 것이 안정화되어 오늘날 SHA나 BLAKE와 같은 안전한 해시가 탄생했습니다. 로컬 믹싱의 목표는 바로 그 전통을 가져와 그것의 아이디어를 *회로(circuits)*에 적용하는 것입니다—동시에 기능성을 보존하면서(functionality-preserving), 대칭 암호학자들이 자신들의 핵심 빌딩 블록이 달성해야 한다고 배운 속성을 달성하는 것입니다.

이것은 매우 무모하고 위험한 도박입니다. 백박스 암호학(white-box cryptography)의 실패 사례들이 쌓여 있는 무덤 위에 놓인 것과 같습니다. 로컬 믹싱을 주장하는 연구자들의 희망은, 만약 우리가 이 방향으로 더 많은 노력을 기울이고, 이를 진행하는 데 있어 더 영리해진다면—예를 들어 AI를 활용하여 해시 함수가 안정화되고 동등한 성숙도에 도달하는 데 걸렸던 30년의 시간을 몇 년 안에 단축할 수 있게 한다면—그리고 동시에 높은 오버헤드(overhead)를 감수한다면, 작동하는 무언가를 만들 수 있을 것이라는 것입니다.

로컬 믹싱의 목표는 회로 $C$ (논리 게이트, 예: XOR, AND, NOT으로 구성됨)를 가져와서, 그 기능성을 유지하면서도 내부 논리를 볼 수 있는 능력을 점진적으로 제거하는 일련의 변환을 적용하는 것입니다.

높은 수준에서 가장 중요한 아이디어는 이름인 '로컬 믹싱(local mixing)'에서 유추할 수 있는 바로 그것입니다: 엄청나게 많은 쓰레기 게이트(junk gates)를 추가하고, 모든 것을 뒤섞고, 회로의 작은 부분을 동일한 기능성을 가진 다른 세트의 게이트로 반복적으로 대체하는 것입니다.

하지만 보시다시피, 이것은 파이프라인의 단지 한 단계—믹싱 단계—에 불과합니다. 핵심적인 기발함은 파이프라인의 다른 단계들, 즉 회로를 믹싱하기 친화적이게 설정하고, 근본적인 회로에서 정보 누출을 제거하도록 최적화된 단계들에 있습니다.

이러한 단계들을 하나씩 살펴보겠습니다. 먼저 가역성(reversibility) 추가부터 시작할 것입니다. 왜냐하면 이 단계가 믹싱의 무대를 마련하는 데 필수적이기 때문입니다. 그다음에는 샌드위칭(sandwiching)에 대해 다룰 것입니다. 그 후에, 믹싱이 어떻게 작동하는지에 대해 이야기하고, 이후 현재 로컬 믹싱의 한계에 대해 논하며 보상하기 위해 추가된 주요 도우미 장치인 가젯화(gadgetization)를 설명할 것입니다.

예시로, 이 시리즈에서 이미 보셨을 수도 있는 회로, 즉 두 비트 가산기(two-bit adder)를 사용하겠습니다.

첫 번째 단계는 회로 $C$를 가역적인 회로—앞으로뿐만 아니라 뒤로도 실행될 수 있는 회로—로 변환하는 것입니다.

이러한 방식이 사용되는 주된 이유는 가역 회로(reversible circuits)가 믹싱에 훨씬 더 적합하기 때문입니다. 단일 가역 게이트는 원래 게이트와 동일한 기능을 수행하는 임의로 많은 수의 다른 가역 게이트들로 대체될 수 있습니다. 예를 들어 AND나 OR를 사용하여 이를 구현하는 것은 훨씬 더 어렵습니다.

핵심적인 이유는 비가역 계산(irreversible computation)이 엔트로피를 붕괴시키기 때문입니다: AND는 00, 01, 10을 동일한 출력으로 붕괴시키고, OR 역시 마찬가지로 01, 10, 11을 붕괴시킵니다. 따라서 비가역 게이트의 긴 체인은 기본적으로 회로 길이와 비례하는 엄청난 양의 정보를 파괴합니다. 충분히 큰 무작위 가역 회로는 그럴듯하게 보안 암호학적 순열(cryptographic permutation)이 될 수 있지만, 충분히 큰 무작위 비가역 회로는 몇 가지 가능한 출력만 갖는 상태로 퇴화됩니다.

이러한 속성을 갖지 않는 큰 비가역 회로를 생성하는 방법도 있습니다. 예를 들어, 위에서 설명된 2비트 가산기가 $a+b$와 $b$ 자체를 모두 반환하고, $a+b$의 x100 자릿수를 반환하지 않도록(즉, 덧셈이 순환되도록) 설계된다면, 이는 비가역 게이트로 만들어진 가역 회로가 될 것입니다. 이때 모든 출력은 단일한 유효 입력에 대응하게 됩니다. 하지만 이러한 기법들은 기본적으로 가역 회로를 재발명하는 것에 불과하므로, 가역 회로 자체를 기반 매체로 사용하는 것이 더 쉽습니다.

가역 회로를 선택하는 것은 대칭 키 암호학(symmetric cryptography)에서 오랫동안 전해 내려온 지혜를 반영합니다. 해시 함수와 같은 비가역적인 응용 분야에서도 핵심 근본 빌딩 블록은 가역 순열이며, 비가역성은 그 위에 얇게 추가된 레이어에서 비롯됩니다. 이는 가능한 한 오랫동안 회로의 전체 '상태 공간(state space)'이 실제로 도달 가능하도록 보장하기 위함입니다.

우리의 2비트 가산기의 경우, 이를 가역으로 만드는 과정은 다음과 같습니다:

[IMG:N]

여기서 몇 가지 주목할 점이 있습니다:

이제는 순방향 또는 역방향으로 실행할 수 있는 2비트 가산기가 생겼습니다. 만약 출력 위치에 단순히 101을 넣고 다른 위치에는 0을 채운 다음, 오른쪽에서 왼쪽으로 게이트를 따라가도 입력 위치에 010 + 011이나 100 + 001이 나오지 않고, 완전히 엉뚱한 결과만 나옵니다. 원래의 계산을 실제로 역방향으로 실행할 수 있다는 것은 최종 출력뿐만 아니라 회로의 각 중간 와이어에 있는 최종 값도 가지고 있어야 가능하다는 것을 의미합니다.

이번 단계에서 우리가 얻은 가장 큰 것은, $C$와 동일한 기능을 수행하지만 믹싱(mixing)에 훨씬 더 자연스럽게 친화적인 형식으로 된 객체입니다.

다음 단계는 경화(hardening) 단계입니다. 우리는 가역 회로 $C$를 시작점으로 사용합니다. 이는 이전의 가역화(reversibilization) 단계의 출력일 수도 있고, 또는 '본질적으로 가역적인(natively reversible)' 회로일 수도 있습니다. 목표는 게이트를 조작하지 않고도, 이 회로가 어떤 입력에 대해 $C$를 실행하고 출력을 얻는 것 외에는 아무것도 할 수 없도록 변환하는 것입니다.

이 조건은 두 가지 방식으로 위반될 수 있습니다:

이를 처리하기 위한 주요 기술은 경화된 Toffoli(hardened Toffoli) 기법이라고 불리며, 다음과 같이 작동합니다.

우리는 두 개의 새로운 와이어 세트를 추가합니다:

게이트는 다음과 같습니다:

또는 다이어그램 형태로:

정상적인 경우와 각 '비정상적인' 경우 모두 그 동작을 따라가 볼 수 있습니다:

정상적인 경우:

어떤 헬퍼가 잘못된 값을 가질 때:

역방향으로 실행:

전체 회로를 역방향으로 실행해도 순방향으로 실행하는 것과 정확히 같은 일을 합니다!

저자들의 2026년 연구에는 **샌드위칭(sandwiching)**이라는 다른 접근 방식이 포함되어 있습니다. 샌드위칭은 가역화 단계가 없는 경우에 최적화된 경화된 Toffoli의 한 형태로 생각할 수 있으며, 무작위 순열을 직접 난독화하는 데 사용됩니다 (가장 즉각적인 사용 사례는 공개 키 암호화를 구축하는 것입니다.)

샌드위칭(Sandwiching) 방식은 기존의 약 4배에 비해 오버헤드가 약 2배이며, 추가적인 $u_{\delta}$ 와이어를 요구하지 않고 단지 $S'$-와 유사한 단계를 한 번만 수행합니다. 이 방식은 입력에서 0이 아니어야 하는(nonzero) 보조 와이어(ancillas)에 대해 방어할 필요가 없는데, 이는 무작위 순열(random permutations)에 적용되도록 설계되었기 때문이며 이러한 순열에는 반드시 0이어야 하는 보조 와이어가 없습니다. 다만 출력 와이어에서 0이 아닌 입력에 대해서는 방어하는데, 이를 위해 더 간단한 트릭을 사용합니다: 일련의 무작위 '슬라이스(slice)' 게이트를 사용하여 해당 와이어들이 0이 아니게 들어올 경우 입력 전체가 완전히 망가지도록 만듭니다. 또한 '계산 $C$ 역방향' 단계는 임의의 무작위 회로 $D$로 대체됩니다.

믹싱(Mixing)은 개념적으로 이해하기 매우 쉽습니다: 이는 회로의 작은 부분에 대해 반복적으로 변환을 가하는 것입니다. 각 변환은 기능성을 유지하면서 구조에 대한 보이는 정보 일부를 파괴하거나 (라기보다는 혼란스럽게 하고 확산시키는) 역할을 합니다. 수백만 번의 변환 라운드가 지나면, 원래 회로의 모든 게이트는 믹싱 단계를 수백 번 거치게 됩니다.

현재 코드에서는 여러 기술을 조합하여 믹싱을 수행하며, 이를 순차적으로 설명하겠습니다.

생성 믹싱(Generation mixing)은 다음과 같이 작동합니다:

로컬 믹싱 레포지토리(local mixing repo)의 상당 부분 작업량은 이 절차를 최적화하는 데 있습니다: 여기에는 테이블이 생성되기 전에도 동일한 작은 회로들을 자동으로 식별하는 몇 가지 트릭을 사용하는 정규화(canonicalization) 단계, 다항식 형태(polynomial form)로 변환하는 과정, 그리고 모든 것을 공간 효율적으로 저장하고 쿼리를 빠르게 만들기 위한 '레인보우 테이블(rainbow table)' 메커니즘이 포함됩니다.

생성 믹싱이 어떻게 작동하는지에 대한 단순화된 다이어그램은 다음과 같습니다 (실제 버전은 약 7~10개의 게이트 그룹을 사용하며, 레인보우 테이블은 수백 기가바이트에 달하지만 훨씬 작은 '큐레이션 테이블(curated table)'도 이용 가능합니다:

생성 혼합(Generation mixing)은 파이프라인에서 가장 강력한 단계입니다. 이는 창(window) 내부의 값들이 표현되는 방식을 전반적으로 변화시킬 수 있습니다. 이 때문에 비선형성을 도입하는 데 가장 효과적인 단계가 되며, 원래 회로에 있는 임의의 값 (x)가 난독화된 회로의 값들의 비선형 함수로만 표현되게 만듭니다. 생성 혼합은 또한 원래 계산 그래프에서 멀리 떨어진 두 개의 회로 조각을 잠재적으로 "붙여서" 결합할 수도 있습니다. 이 과정은 해당 두 조각의 조합인 서브-회로를 그 둘이 얽혀 있는(interleaves) 하나의 회로로 대체하며, 이후 추가적인 혼합 생성을 통해 이러한 얽힘 구조는 감지하고 역추적하기 어렵게 만듭니다.

이 파이프라인은 각 게이트를 여러 번 커버하는 것을 목표로 엄청난 수의 라운드 동안 생성 혼합을 수행합니다. 또한 여러 단계에 걸쳐 이를 진행하는데, 하나는 회로 확장에 편향되고 다른 하나는 크기를 유지하는 데 편향되며, 마지막에는 결국 약간 줄어들게 만듭니다.

스플리팅(Splitting)은 r57 게이트를 더 광범위한 1개 및 2개 제어 게이트 세트로 대체합니다. 여기에는 여러 가지 기법들이 포함되어 있습니다.

((\oplus) 는 xor,
(\lor)
는 or, (\land) 는 and, (\neg)
는 not)

첫째, (a\ {\oplus}{=}\ b \lor \neg c)를 각각 (a\ {\oplus}{=}\ b;\ a\ {\oplus}{=}\ \neg b \land \neg c) 또는 (a\ {\oplus}{=}\ \neg c;\ a\ {\oplus}{=}\ b \land c)로 대체할 수 있습니다.

둘째, 임의의 와이어에 대해 다음을 수행할 수 있습니다:

스플리팅은 개별 와이어와 게이트의 의미에 대한 특정 유형의 가시적 정보를 파괴하는 데 도움을 줍니다. 충분한 라운드가 지나면, 어떤 와이어가 "x"를 나타내는지 그리고 어느 것이 "not-x"를 나타내는지 구분하는 것은 실용적이지 않게 됩니다.

사용되는 게이트 세트를 확장함으로써, 스플리팅은 또한 다음 단계를 구현하는 데 필요한 조건을 생성하여, 훨씬 적은 제약으로 게이트의 순서를 조정할 수 있게 해줍니다.

서로 '충돌(collide)'하지 않는 두 게이트는, 즉 한 게이트가 값을 쓰면 다른 게이트가 읽는 식의 관계가 아닌 경우, 자유롭게 순서를 바꿀 수 있습니다. 하지만 서로 충돌하는 두 게이트 역시 재배열할 수 있는데, 이때 읽기와 쓰기가 위치를 바꾸는 것에 대한 보상으로 새로운 게이트를 추가하기만 하면 됩니다.

작동 방식은 세 가지 사례로 나누어 설명하겠습니다:

원칙적으로, 원하는 만큼 멀리 떨어진 곳에 있는 게이트를 이동시킬 수 있으며, 지나가는 각 게이트마다 '잔여물(residues)'을 남기게 됩니다.

이 단계는 $k$개의 제어 신호를 가진 게이트를 가져와서 최대 $2k-1$개의 제어 신호를 가진 게이트로 출력한다는 점에 주목하십시오. (위 다이어그램은 $k=2$인 경우를 보여주지만, $k ext{ }
less 3$도 지원됩니다.)

이는 교차 이동 경로(crossing walk) 자체에는 심각한 문제가 아닙니다. 단지 이 과정을 여러 번 반복하면 많은 제어 신호를 가진 게이트가 생길 수 있다는 의미일 뿐입니다. 게다가, 제어 신호 수가 높아질수록 교차 지점마다 여러 개의 '잔여물' 게이트를 생성해야 할 수도 있습니다.

하지만 만약 현재처럼 생성 믹싱(generation mixing) 이후에만 교차 이동 경로를 수행하는 것이 아니라, 그 도중에 수행하기로 결정한다면 문제가 됩니다. 왜냐하면 현재의 레인보우 테이블은 $r57$ 게이트만을 포함하고 있기 때문입니다. 높은 제어 신호 수를 가진 게이트를 포함하는 레인보우 테이블을 만들 수는 있지만, 이는 동일한 커버리지 수준에서 레인보우 테이블의 크기를 기하급수적으로 증가시킬 위험이 있습니다. 가장 쉬운 해결책은 3개 이상의 제어 신호를 가진 각 게이트를 다시 일련의 두 개 제어 신호 게이트로 줄이는 것입니다.