💻 computer science

Redactable blockchains and polynomial equations

이 논문은 다변수 다항식 방정식 풀이를 통한 일방향 함수의 역산의 계산적 난해함을 활용하여, 편집 가능한 인증 데이터 구조를 위한 양자 내성 보안 구성을 제시한다.

원저자: Alexander Demin, Alexey Ovchinnikov, Vladimir Shpilrain

게시일 2026-08-21

📖 4 분 읽기☕ 가벼운 읽기

원저자: Alexander Demin, Alexey Ovchinnikov, Vladimir Shpilrain

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

디지털 시대에 우리의 세계는 우리가 운전하는 자동차부터 집 안의 온도 조절 장치에 이르기까지, 스마트 기기의 네트워크에 의해 점점 더 밀접하게 엮여 있습니다. 흔히 사물인터넷(IoT)이라 불리는 이러한 시스템들은 안전하게 기능하기 위해 공유된 사건 기록에 의존합니다. 수년 동안 이러한 기록을 안전하게 보관하는 표준은 블록체인이라 불리는 기술이었습니다. 블록체인을 수천 대의 컴퓨터에 복사된 디지털 장부라고 생각하십시오. 여기서 모든 새로운 항목은 이전 항목에 의해 고정됩니다. 일단 기록이 작성되면, 이 시스템의 설계상 이를 수정하거나 삭제하는 것이 거의 불가능하여 누구도 역사를 조작할 수 없도록 보장합니다. 이러한 영구성은 강점이지만, 개인정보 보호법이 사람들에게 '잊힐 권리'를 요구하거나 단순한 인간의 실수를 전체 체인을 파괴하지 않고 수정해야 하는 세상에서는 약점이 되었습니다.

과학자들의 과제는 기록의 불변성을 유지하면서도 필요할 때 신뢰할 수 있는 권위자가 특정 항목을 편집하거나 삭제할 수 있도록 하는 시스템을 만드는 것이었습니다. 이를 해결하려는 이전의 시도들은 오늘날의 컴퓨터로는 풀기 쉽지만, 향가 10년 내에 도착할 것으로 예상되는 미래의 양자 컴퓨터에 의해서는 즉각적으로 깨질 수 있는 수학적 퍼즐에 의존해 왔습니다. 한 연구팀은 이제 이러한 취약한 퍼즐을 완전히 피하는 새로운 솔루션을 제안했습니다. 대신, 그들은 다른 종류의 수학적 난이도, 즉 많은 변수를 가진 복잡한 방정식을 푸는 작업에 기반하여 시스템을 구축했습니다. 이 작업은 현재의 양자 컴퓨터가 효율적으로 해결할 수 없는 것으로 알려진 작업입니다.

연구원들인 알렉산더 데민(Alexander Demin), 알렉세이 오브치니코프(Alexey Ovchinnikov), 블라디미르 슈필라인(Vladimir Shpilrain)은 데이터가 미지수가 포함된 변수를 가진 수학적 표현식, 즉 모르는 수가 포함된 공식과 유사하게 처리되는 방식의 방법을 개발했습니다. 체인의 무결성은 한 블록을 다음 블록으로 연결하는 공개 규칙에 의해 유지됩니다. 그러나 중앙 권위자는 비밀 키를 보유하고 있는데, 이는 본질적으로 이러한 공식들을 배열하는 특정한 방식입니다. 이 비밀 키를 통해 권위자는 블록의 내용을 변경하고, 여전히 공개 규칙을 충족하는 새로운 끝부분을 계산하여, 체인을 깨뜨리지 않고 효과적으로 기록을 편집할 수 있습니다. 비밀 키가 없는 사람에게 이러한 변경을 위조하는 것은 수십 개의 미지수가 포함된 거대한 방정식 시스템을 푸는 것과 같으며, 이는 계산적으로 압도적인 작업입니다.

이 새로운 시스템이 진정으로 안전한지 확인하기 위해, 팀은 먼저 기본적인 버전을 구축한 다음, 어디에서 실패할 수 있는지 보기 위해 일련의 시뮬레이션 공격을 수행했습니다. 그들은 공격자가 코드를 깨뜨리기 위해 시도할 수 있는 네 가지 서로 다른 방법을 테스트했습니다. 한 가지 접근 방식은 새로운 끝부분을 찾기 위해 방정식을 직접 푸는 것이었습니다. 또 다른 방식은 공개된 데이터로부터 비밀 공식을 역설계하는 것이었습니다. 세 번째는 공식이 구축된 패턴을 찾는 것이었습니다. 마지막 네 번째는 시스템이 변화하는 과정을 관찰하여 비밀을 추론하는 것이었습니다. 초기 버전에서 연구진은 시스템이 이 네 가지 공격 모두에 취약하다는 것을 발견했습니다. 충분한 컴퓨팅 능력을 갖춘 공격자는 방정식을 풀거나 비밀 공식을 추론할 수 있으며, 특히 시스템이 여러 번 편집되는 것을 관찰할 수 있다면 더욱 그러했습니다.

이러한 약점을 인식한 팀은 이러한 허점을 메우는 고급 버전으로 설계를 개선했습니다. 이 개선된 구조에서는 블록을 연결하는 공개 규칙이 더 이상 단일한 알려진 공식이 아닙니다. 대신, 규칙은 부분적으로만 공개된 숨겨진 방정식 시스템입니다. 비밀 키는 이제 방정식이 평가되는 특정 지점들을 포함하며, 이 지점들은 비공개로 유지됩니다. 이 변화는 공격자가 단순히 공개 데이터를 보고 비밀을 찾기 위해 방정식을 풀 수 없음을 의미하는데, 왜냐하면 풀어야 할 전체 방정식이 결코 보여지지 않기 때문입니다. 연구진이 동일한 네 가지 공격에 대해 이 고급 버전을 테스트했을 때 결과는 극적으로 달랐습니다. 방정식을 풀려는 시도는 시스템이 너무 복잡하고 필요한 정보가 누락되었기 때문에 실패했습니다. 비밀 공식을 추론하려는 시도는 데이터가 어떻게 변환되는지에 대한 전체 그림을 공격자가 볼 수 없었기 때문에 실패했습니다.

팀은 복잡한 수학 문제를 풀기 위해 설계된 전문 소프트웨어를 사용하여 강력한 컴퓨터에서 이 테스트를 실행했습니다. 그들은 방정식의 크기를 늘려 시스템을 깨뜨리는 데 얼마나 많은 컴퓨팅 능력이 필요한지 확인하기 위해 다양한 난이도의 공격을 시뮬레이션했습니다. 실험 결과, 방정식의 복잡성을 높임에 따라 이를 해결하는 데 필요한 메모리 양이 기하급수적으로 증가함을 보여주었습니다. 약 20비트의 소수를 기반으로 하는 차수가 20인 방정식을 포함하는 그들이 권장하는 매개변수의 경우, 시스템을 깨뜨리는 데 필요한 메모리는 기존의 어떤 컴퓨터의 용량도 초과하여 페타바이트 영역에 달하게 됩니다. 이는 기초적인 버전의 아이디어는 결함이 있었지만, 고급 버전은 현재와 미래의 양자 위협에 대해 강력한 방어력을 제공한다는 것을 시사합니다.

이 연구의 의의는 유연성과 보안 사이의 균те를 맞추는 데 있습니다. 이는 디지털 기록의 신뢰성을 유지하면서도 개인정보 보호와 수정의 필요성을 존중하는 방법을 제공합니다. 양자 컴퓨터가 착취할 것으로 예상되는 수학적 구조에서 벗어나 다변수 다항 방정식의 복잡성으로 이동함으로써, 연구진은 진화할 수 있는 블록체인의 청사진을 제공했습니다. 그들의 연구 결과는 적절한 매개변수를 선택한다면, 이러한 시스템이 컴퓨팅 기술이 발전하더라도 안전하게 유지될 수 있음을 보여주며, 점점 더 연결되고 규제되는 세상에서 데이터를 안전하게 관리하기 위한 잠재적인 경로를 제시합니다.

기술 요약: 편집 가능한 블록체인과 다항식 방정식

문제 정의
본 논문은 사물인터넷(IoT) 네트워크와 프라이빗 블록체인 시스템에서 발생하는 보안 및 개인정보 보호 문제를 다룬다. 블록체인은 변조 탐지 기능을 제공하지만, 고유한 불변성은 '잊힐 권리'와 같은 현대적 개인정보 보호 요구사항이나 인간의 오류를 수정하거나 오래된 기록을 삭제해야 하는 필요성과 충돌한다. 기존의 "편집 가능한(redactable)" 블록체인 솔루션들(권한이 있는 엔티티가 무결성을 유지하면서 데이터를 수정하거나 삭제할 수 있는 구조)은 두 가지 주요 한계점을 가진다. 즉, 비실용적이거나 양자 내성을 갖추지 못했다는 점이다. 구체적으로, 기존의 구성 방식들은 대개 RSA 문제나 숨겨진 부분군 문제(hidden subgroup problems)의 어려움에 의존하며, 이는 양자 알고리즘에 취약하다. 저자들은 양자 공격에 대해서도 안전하면서 경량화된 보안 아키텍처를 갖춘 편집 가능한 블록체인을 개발하고자 한다.

방법론
제안된 방법론은 전통적인 수론적 일방향 함수(RSA 등)를 다변수 다항식 방정식 해를 구하는 계산적 어려움으로 대체한다. 이 구성은 다음 요소들에 기반한다:

블록 구조: 각 블크 $B_i$ 는 영구적인 접두사 $P_i$ , 가변적인 콘텐츠 $C_i$ , 그리고 편집 가능한 접미사 $S_i$ 로 구성된다.
무결성 조건: 체인의 무결성은 공개 다항식 방정식 $F(P_i, C_i, S_i) = P_{i+1}$ 을 통해 유지된다.
트랩도어 메커니즘: 중앙 권한 기관은 공개 다항식 $F$ 의 특정 함수적 분해(functional decomposition)로 이루어진 개인키를 보유한다. 기본 버전에서 $F(x, y, z) = G(x, H(x, y) - z)$ 이며, 여기서 $G$ 와 $H$ 는 개인 다항식이다. 이를 통해 권한 기관은 수정된 콘텐츠 $C'_i$ 에 대해 새로운 접미사 $S'_i$ 를 계산하기 위해 트랩도어 구조로부터 유도된 선형 시스템을 풀 수 있다.
고급 구성: 기본 버전에 대해 식별된 특정 공격들을 방어하기 위해, 저자들은 다음과 같은 고급 구성을 제안한다:
- 다항식 $F(x, y, z)$ 는 비공개로 유지된다.
- 무결성 조건은 비공개이며 서로 다른 지점 $t_0, \dots, t_d$ 에서 평가되는 다항식 시스템으로 정식화된다.
- 선형화 공격(linearization attacks)을 방지하기 위해 트랩도어 구조에 비선형 함수 $R$ 이 도입된다 ( $F(x, y, z) = G(x, R(H(x, y), z))$ ).

주요 기여

양자 내성 보안: 본 논문은 다변수 다항식 방정식에 기반한 편집 가능한 블록체인 아키텍처를 소개한다. 제안된 일방향 함수를 역산하는 것은 여러 변수를 가진 다항식 시스템을 푸는 문제를 요구하며, 이 문제는 현재 효율적인 양자 알고리즘이 존재하지 않아 양자 내성이 있는 것으로 간주된다.
편집 능력: 본 스킴은 권한을 가진 기관이 개인 트랩도어를 보유하고 있다면, 체인의 무결성을 깨뜨리지 않고도 블록 콘텐츠를 변경하거나 데이터를 삭제("망각")할 수 있게 한다.
공격 분석 및 완화: 저자들은 기본 구성에 대한 네 가지 잠재적 공격 벡터를 엄격하게 분석한다:
1. 새로운 접미사를 구하기 위해 다항식 시스템을 푸는 공격 (공격 1).
2. 비밀 다항식 $H$ 를 복구하는 공격 (공격 2).
3. $F$ 의 함수적 분해를 찾는 공격 (공격 3).
4. 여러 번의 편집을 관찰하여 시스템을 선형화하는 공격 (공격 4).
  논문은 기본 구성이 이러한 공격들(특히 선형화를 통한 공격 4와 분해를 통한 공격 2/3)에 취약함을 입증하는 동시에, 고급 구성이 $F$ 를 비공개로 유지하고 비선형성을 도입함으로써 이를 효과적으로 무력화함을 보여준다.

실험 결과
저자들은 Intel i9-13900 프로세서와 50GB 메모리 환경에서 Maple 2024 및 Julia 패키지(Groebner.jl, AlgebraicSolving.jl)를 사용하여 실험을 수행하였다.

기본 구성: 실험을 통해 기본 구성이 공격에 취약함을 확인하였다. 구체적으로, 공격자가 과결정 시스템(overdetermined system)을 생성할 수 있다면 공격 1(시스템 풀기)이 가능해진다. 공격 2와 공격 3은 각각 Gröbner 기저 기법과 분해 알고리즘을 사용하여 해결 가능함이 입증되었다.
고급 구성: 고급 구성은 회복 탄력성을 증명하였다.
- 공격 1: 공개 다항식 $F$ 가 없기 때문에, 공격자는 과결정 시스템을 형성하는 데 필요한 방정식을 생성할 수 없으며, 반드시 정방형 시스템(square system)을 풀어야만 한다. 저자들은 제안된 파라미터( $d > 30$ )를 사용할 경우, 해당 시스템을 푸는 데 약 40 페타바이트의 메모리가 필요할 것이라고 추정하며, 이는 실행 불가능함을 시사한다.
- 공격 2 & 3: $F$ 가 비공개이므로, 분해 알고리즘을 직접 적용하거나 $H$ 를 복구하는 것이 불가능하다.
- 공격 4: 비공개 평가 지점과 비선형 항의 도입은 공격자가 $H$ 의 계수에 대한 선형 시스템을 형성하는 것을 방지한다.

의의 및 주장
본 논문은 양자 취약한 가정에 의존하지 않으면서 탈중앙화 시스템에서 "잊힐 권리"와 오류 수정을 해결할 수 있는, 새롭고 안전하며 프라이빗하고 경량화된 편집 가능한 블록체인 아키텍처를 제공한다고 주장한다. 저자들은 자신들의 구성이 투명하고 쉽게 구현 가능하다는 점을 강조한다.

그 의의는 블록체인 무결성을 위해 군론 기반 암호(RSA, 이산 로그)에서 다변수 다항식 암호로 전환했다는 점에 있다. 저자들은 기본 버전은 취약할 수 있으나, 비공개 다항식과 특정 비선형 트랩도어를 활용한 제안된 고급 구성이 식별된 공격들을 성공적으로 차단한다고 겸허히 기술한다. 저자들은 적절한 파라미터(예: 소수 $n \approx 20$ bits, 차수 $d=20$ )를 선택하면, 본 스킴이 함수 역산이 고전적 및 양자 공격자 모두에게 계산적으로 불가능한 수준의 양자 내성 보안을 제공한다고 결론짓는다.

유사한 논문