💻 computer science

NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam

이 논문은 논리 퍼즐 'Hotaru Beam'이 NP-완전 문제임을 증명하고, 그 해법을 실제로 물리적으로 증명하는 영지식 증명 프로토콜을 제시합니다.

원저자: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

게시일 2026-03-03

📖 4 분 읽기☕ 가벼운 읽기

원저자: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

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

1. 반딧불이 빔 (Hotaru Beam) 이란 무엇인가요?

상상해 보세요. 격자무늬가 그려진 종이 위에 **반딧불이 (원형)**들이 여러 개 놓여 있습니다. 각 반딧불이에게는 "내 빛이 꺾이는 횟수"를 알려주는 숫자가 적혀 있거나, 아무 숫자도 없을 수 있습니다.

미션: 모든 반딧불이를 빛의 선 (빔) 으로 연결해서 하나의 거대한 덩어리를 만들어야 합니다.

규칙:

직진과 꺾임: 빛은 직선으로 가다가 숫자만큼 꺾일 수 있습니다.
교차 금지: 빛은 서로 겹치거나 갈라질 수 없습니다.
완전 연결: 모든 반딧불이가 빛으로 이어져 있어야 합니다.

이 퍼즐의 정답을 찾는 것은 매우 어렵습니다. 수학자들은 이 퍼즐이 "NP-완전 (NP-Complete)" 문제라고 증명했습니다. 쉽게 말해, **"정답을 찾는 것은 매우 어렵지만, 정답을 보여주고 확인하는 것은 아주 쉽다"**는 뜻입니다. (예: 100 만 개의 조각을 맞춰 그림을 완성하는 건 어렵지만, 완성된 그림을 보고 "아, 이게 맞네"라고 확인하는 건 쉽죠.)

2. 제로-지식 증명 (Zero-Knowledge Proof): "내가 정답을 알지만, 절대 말해주지 않을게"

이 논문의 핵심은 바로 **'제로-지식 증명 (ZKP)'**입니다.

상황:

프로버 (Peter): 퍼즐의 정답을 알고 있는 사람.
검증자 (Vera): 정답을 모르고, Peter 가 진짜로 정답을 알고 있는지 확인하려는 사람.

목표:
Peter 는 Vera 에게 **"내가 정답을 알고 있어!"**라고 증명하고 싶지만, 정답 자체 (어떤 선을 그었는지) 는 절대 보여주고 싶지 않습니다.

마치 **"내가 금고 비밀번호를 알고 있어"**라고 말하면서, 비밀번호를 말하지 않고도 Vera 가 Peter 가 비밀번호를 알고 있다는 것을 믿게 만드는 것과 같습니다.

3. 어떻게 카드로 증명할까? (물리적 제로-지식 증명)

이 논문은 컴퓨터 프로그램이 아니라, 실제 카드와 손으로 이 증명 과정을 수행하는 방법을 제안합니다.

🃏 카드의 역할

뒷면: 모두 똑같은 카드 (정보를 숨김).
앞면:
- ♡ (하트): 빈 공간 (빔이 지나갈 수 있는 곳).
- ♣ (클로버): 벽 (빔이 지나갈 수 없는 곳).
- 숫자 카드: 반딧불이의 위치.
- ♢ (다이아몬드): 빔의 시작점이나 방향 표시.

🎭 마법 같은 카드 조작 (프로토콜)

Peter 는 Vera 가 보는 앞에서 카드를 뒤집거나 섞거나 이동시키며 다음과 같은 일을 합니다.

보드 준비: 격자판 위에 카드들을 깔아둡니다. 빈 공간은 하트 (♡), 벽은 클로버 (♣) 로 표시합니다.
빔 그리기 (Segment Embedding): Peter 는 자신의 정답대로 빔을 그립니다. 이때 Vera 에게는 **"내가 여기다 선을 그었다"**는 사실만 보여주고, **"어떤 경로로 그렸는지"**는 숨깁니다.
- 비유: Peter 는 검은색 가위로 종이 위에 선을 그립니다. Vera 는 가위가 움직인 흔적 (선) 만 보고, 가위가 정확히 어디를 지나갔는지 (구체적인 경로) 는 모릅니다.
꺾임 수 숨기기: 숫자가 적힌 반딧불이는 빔이 꺾이는 횟수가 정해져 있습니다. Peter 는 이 횟수를 맞추면서 Vera 에게는 "내가 꺾임 수를 지켰다"는 사실만 증명합니다.
연결성 확인 (Connections Table): 모든 반딧불이가 연결되었는지 확인하기 위해 별도의 **'연결 테이블'**이라는 카드를 사용합니다.
- 이 테이블은 "반딧불이 A 와 B 가 연결되었나요?"라는 질문을 참 (T) 또는 **거짓 (F)**으로 표시하는 카드들입니다.
- Peter 가 빔을 그릴 때마다, 연결된 반딧불이들의 관계를 '참'으로 업데이트합니다.
- 마지막에 Vera 는 이 테이블을 확인합니다. 모든 카드가 '참 (T)'이 되어 있다면, Peter 는 모든 반딧불이를 성공적으로 연결했다는 뜻입니다.

🔄 중요한 기술: "섞기 (Shuffle)"

가장 중요한 마법은 카드 섞기입니다. Peter 는 Vera 가 카드를 보지 못하도록 카드를 섞거나, 순서를 바꿉니다.

Vera 는 "어떤 카드를 선택했는지"는 알 수 없지만, "선택된 카드가 규칙에 맞는지"는 확인할 수 있습니다.
이 과정을 통해 Peter 는 정답의 구체적인 내용 (어떤 선을 그었는지) 은 숨기면서, 정답이 유효하다는 사실만 증명합니다.

4. 이 연구의 의의는 무엇일까요?

수학적 증명: 반딧불이 빔 퍼즐이 수학적으로 매우 어렵다는 것 (NP-완전) 을 증명했습니다.
실용적인 암호 기술: 복잡한 수학적 증명 없이, 일반인도 카드와 손으로 암호학적 증명 (제로-지식 증명) 을 할 수 있게 했습니다.
- 이는 향후 블록체인, 개인정보 보호, 혹은 퍼즐 커뮤니티에서 "내가 해답을 알고 있다"는 것을 증명할 때 유용하게 쓰일 수 있습니다.
새로운 아이디어: 특히 '빔의 꺾임 수'를 숨기면서 증명하는 방법과, '연결 상태'를 추적하는 카드를 만드는 방법은 다른 기하학적 퍼즐에도 적용할 수 있는 새로운 아이디어를 제시했습니다.

📝 한 줄 요약

"이 논문은 반딧불이 빔 퍼즐이 매우 어렵다는 것을 증명하고, 정답을 절대 알려주지 않으면서도 '내가 정답을 알고 있다'는 것을 카드 놀이로 증명하는 마법 같은 방법을 고안해냈습니다."

이 논문은 논리 퍼즐 'Hotaru Beam(호타루 빔)'의 계산 복잡도 분석과 이를 위한 물리적 제로지식 증명 (Physical Zero-Knowledge Proof, ZKP) 프로토콜을 제안합니다. 주요 내용은 다음과 같습니다.

1. 문제 정의 (Hotaru Beam)

Hotaru Beam 은 격자 (grid) 위에 배치된 반딧불이 (fireflies, 원) 를 연결하는 논리 퍼즐입니다.

목표: 모든 반딧불이를 단일 연결 요소 (single component) 로 연결하는 선 (빔) 을 그리는 것.
규칙:
1. 시작점: 각 반딧불이의 경계와 격자 선이 만나는 점에 찍힌 점 (dot) 에서 빔이 시작됩니다.
2. 구부림 제약 (Bending Constraint): 반딧불이 내부의 숫자는 해당 빔이 구부러져야 하는 횟수를 지정합니다. 숫자가 없으면 구부림 횟수에 제한이 없습니다.
3. 연결성 제약 (Connectivity Constraint): 모든 빔은 서로 교차하거나 분기하지 않으며, 모든 반딧불이가 하나의 연결된 그래프를 이루어야 합니다.
4. 종료: 빔은 다른 반딧불이의 경계에 도달할 때 멈춥니다.

2. NP-완전성 증명 (NP-Completeness)

저자들은 Hotaru Beam 문제가 **NP-완전 (NP-complete)**임을 증명했습니다.

증명 방법: 'Planar Monotone 3-SAT' 문제에서 Hotaru Beam 문제로 다항식 시간 환원 (polynomial-time reduction) 을 수행했습니다.
구현: 변수 (variable) 와 절 (clause) 을 시뮬레이션하는 기구 (gadgets) 를 격자 위에 설계했습니다.
- 변수 기구: 빔의 방향을 통해 참 (True) 또는 거짓 (False) 값을 표현합니다.
- 절 기구: 변수 기구와 연결되어 논리식을 만족하는지 확인합니다.
- 모든 반딧불이가 연결되어야 한다는 제약 조건이 3-SAT 의 만족 가능성 (satisfiability) 과 동치임을 보였습니다.

3. 물리적 제로지식 증명 (Physical ZKP) 프로토콜

저자들은 카드와 같은 물리적 도구를 사용하여, 풀이를 가진 증명자 (Prover, Peter) 가 검증자 (Verifier, Vera) 에게 풀이를 알고 있음을 증명하되, 풀이 자체는 전혀 노출하지 않는 프로토콜을 개발했습니다.

핵심 구성 요소 및 기법

카드 표현:
- 보드 (Board): 격자 점을 나타내는 카드들로 구성. 빈 공간은 ♡, 빔이 지나간 곳은 ♣, 빔의 시작/중간 지점은 ♢ 등으로 표현.
- 연결 테이블 (Connections Table): $n$ 개의 반딧불이 간의 연결 상태를 논리적 카드 쌍 (Logical Card Pair, 예: ♣♡=True, ♡♣=False) 으로 관리. 두 반딧불이가 같은 연결 요소에 속하면 True 로 설정됩니다.
핵심 프로토콜 기법:
- 세그먼트 임베딩 (Segment Embedding): 빔의 한 구분을 그리며 보드 카드를 ♡에서 ♣로 변경하는 과정.
  - 마스크 시퀀스 (Mask Sequence): 빔의 길이와 방향을 숨기기 위해 사용되는 보조 카드 시퀀스. 'Pile-shifting shuffle' 등을 통해 Vera 는 빔이 그려진 사실은 알지만, 구체적인 경로나 길이를 알 수 없게 합니다.
  - 방향 숨김: 왼쪽/오른쪽 방향을 숨기기 위해 두 가지 버전의 마스크를 준비하고 무작위로 선택합니다.
  - 구부림 수 숨김: 구부림 횟수가 지정되지 않은 경우, 가상의 길이 0 세그먼트를 추가하여 총 세그먼트 수를 고정함으로써 Vera 가 구부림 횟수를 추측하지 못하게 합니다.
- 연결성 유지 (Connectivity Maintenance):
  - 빔이 두 반딧불이를 연결할 때마다 '연결 테이블'의 해당 논리 카드 쌍을 True 로 업데이트합니다.
  - 마지막 단계에서 모든 반딧불이가 연결되었음을 증명하기 위해, 연결된 노드들의 논리값을 'OR' 연산하여 모든 쌍이 True 가 됨을 검증자에게 보여줍니다.
물리적 조작:
- Pile-shifting shuffle: 카드 더미를 무작위 순서로 이동시켜 위치 정보를 지웁니다.
- Pile choosing: Vera 에게 특정 더미를 선택했음을 알리지 않고 연산을 수행하게 합니다.
- Set membership proving: 특정 카드가 주어진 집합에 속함을 증명하되 값을 밝히지 않습니다.

4. 주요 기여 및 의의

새로운 퍼즐의 복잡도 분석: Hotaru Beam 이 NP-완전 문제임을 최초로 증명했습니다.
구체적인 제약 조건을 가진 ZKP 설계:
- 기존에 물리적 ZKP 가 연구된 퍼즐들 (Sudoku, Slitherlink 등) 과 달리, **'구부림 횟수 (bending constraint)'**라는 기하학적 제약을 물리적 카드로 어떻게 숨길지 해결했습니다.
- 마스크 시퀀스와 가상 세그먼트를 도입하여 빔의 길이와 구부림 수를 완벽하게 은닉하는 방법을 제시했습니다.
연결성 검증의 효율성: 단순히 경로만 그리는 것이 아니라, 모든 노드가 하나의 컴포넌트로 연결되었음을 '연결 테이블'을 통해 체계적으로 증명하는 프로토콜을 제안했습니다.
일반화 가능성: 격자 기반 퍼즐이나 특정 그래프의 존재성을 증명하는 다른 기하학적 문제들에 대한 ZKP 설계에 유용한 통찰 (마스크 시퀀스, 연결성 추적 등) 을 제공합니다.

5. 결론

이 논문은 Hotaru Beam 퍼즐이 계산적으로 어렵다는 것을 수학적으로 증명하고, 이를 해결한 사람이 있음을 물리적 카드 놀이를 통해 신뢰할 수 있게 증명하는 방법을 제시했습니다. 특히, 빔의 경로와 구부림 수를 동시에 숨기면서 연결성을 검증하는 독창적인 프로토콜은 물리적 암호학 및 퍼즐 기반 ZKP 연구에 중요한 기여를 합니다.