Improvements on quantum designated verifier signature based on Bell states

비밀 메시지를 보내는 것이 단순히 디지털 금고에 가두는 것이 아니라, 오직 한 명의 특정 사람만이 돌릴 수 있는 특별한 열쇠를 건네주는 일이라고 상상해 보십시오. 이것은 아주 작은 입자(광자와 같은)의 기묘하고 꿈틀거리는 규칙을 사용하여 정보를 보호하는 분야인 양자 암호학의 영역입니다. 디지털 서명의 옛날 방식에서는 적절한 공개 키를 가진 사람이라면 누구나 그 메시지가 진짜인지 확인할 수 있었습니다. 하지만 때로는 당신이 무언가에 서명했다는 사실을 모두가 알기를 원치 않을 수도 있습니다. 당신은 오직 특정한 친구만이 그것을 검증하기를 원하며, 그 친구가 제삼자에게 당신이 그것을 했다는 것을 증명할 수 없기를 원합니다. 이것을 **지정 검증자 서명(Designated Verifier Signature)**이라고 부릅니다. 이것은 마치 당신의 가장 친한 친구만이 읽을 수 있는 노트를 쓰는 것과 같습니다. 설령 그 친구가 제삼자에게 그것을 보여주려 해도, 그들 스스로도 직접 쓸 수 있었던 것이기에 당신이 썼다는 것을 증명할 수 없는 것과 같습니다. 여러분이 지금 탐구하게 될 논문은 양자 물리학의 법칙을 사용하여 이러한 종류의 "초비밀" 서명을 구축하려는 구체적인 시도를 다루며, 그 과정에서 갑옷의 틈새를 발견하고 나서 영리한 새로운 설계로 이를 보완하는 내용을 담고 있습니다.

---

깨진 자물쇠와 새로운 열쇠

최근의 양자 서명 시스템 구축 시도를 **벨 상태(Bell states)**를 이용해 하이테크 금고를 만들려는 엔지니어 팀에 비유해 생각해 보십시오. 양자 세계에서 벨 상태는 서로 완벽하게 연결된(얽힌) 마법의 주사위 쌍과 같습니다. 만약 한쪽 주사위에서 6이 나오면, 아무리 멀리 떨어져 있어도 다른 쪽 주사위도 즉시 6을 보여줍니다. 연구자 신(Xin)과 그의 팀은 이 연결된 주사위들이 서명의 핵심이 되는 체계를 제안했습니다. 그들은 자신들의 금고가 해킹 불가능하다고 주장했습니다.

하지만 이 논문의 저자인 장카이(Cai Zhang), 리커솬(Kechuan Li), 쑨즈웨이(Zhiwei Sun)는 그 자물쇠를 따보기로 했습니다. 그들은 그 "마법의 주사위" 시스템에 치명적인 결함이 있다는 것을 발견했습니다. 침입자 이브(Eve)가 수신자에게 가는 메시지를 가로채는 상황을 상상해 보십시오. 신(Xin)의 체계에서 이브는 메시지를 망가뜨리기 위해 비밀 키를 알 필요가 없습니다. 그녀는 단순히 서명 입자에 특정 양자 "플립(flip)"(Y-연산이라 불리는 것)을 수행하기만 하면 됩니다. 이는 마치 당신이 글자를 'A'에서 'B'로 바꾸려 할 때, 마스터 키를 가질 필요 없이 특정 리듬으로 종자를 톡톡 두드리면 아무도 모르게 'A'가 'B'로 마법처럼 변하는 것을 깨달은 것과 같습니다. 저자들은 이브가 완전히 새로운 유효한 서명을 위조할 수 있으며, 수신자는 그것이 위조라는 사실을 전혀 알 수 없음을 입증했습니다. 원래의 체계는 안전하지 않았습니다.

"비얽힘(No-Entanglement)" 솔루션

이를 해결하기 위해, 저자들은 단순히 깨진 자물쇠를 수리하는 데 그치지 않고, 마법의 주사위를 아예 사용하지 않는 완전히 새로운 문을 만들었습니다. 그들의 새로운 체계는 비얽힘(entanglement-free) 방식이며, 이는 까다로운 연결된 입자에 의존하지 않음을 의미합니다. 대신, 이 방식은 단일 큐비트(개별 양자 입자)와 간단한 가역적 연산(스위치를 켜거나 다이얼을 돌리는 것과 같은)을 사용합니다.

이 새로운 시스템이 어떻게 작동하는지 재미있는 비유를 통해 설명하겠습니다:
앨리스가 밥에게 비밀 메시지를 보내고 싶어 한다고 가정해 봅시다.

1. 설정: 앨리스와 밥은 사전에 서로 잘 알고 있는 노래 재생 목록처럼, 비밀 코드북(비밀 키)을 공유합니다.
2. 서명: 메시지에 서명하기 위해, 앨리스는 각 글자에 대해 자신의 비밀 코드북에 따라 "춤 동작"을 적용합니다. 그녀는 글자를 회전시키거나(Hadamard 연산) 뒤집을(Y 연산) 수 있습니다. 그 결과물인 양자 서명은 코드를 모르는 사람에게는 엉망진창으로 뒤섞인 것처럼 보입니다.
3. 함정: 서명을 보내기 전, 앨리스는 혼합물 속에 몇 개의 "미끼(decoy)" 입자를 숨겨 넣습니다. 마치 병 안에 실제 나비와 함께 가짜 나비를 몇 마리 넣어두는 것과 같습니다. 그녀는 밥에게 가짜 나비가 어디에 있는지, 그리고 그것들이 어떤 모습이어야 하는지 알려줍니다.
4. 검증: 밥이 병을 받았을 때, 그는 먼저 가짜 나비들을 확인합니다. 만약 가짜 나비들이 흐트러져 있다면, 그는 도둑(이브)이 훔쳐보려 했다는 것을 알고 전체를 버립니다. 만약 가짜 나비들이 완벽하다면, 그는 자신의 비밀 코드북 복사본을 사용하여 앨리스의 춤 동작을 "되돌립니다". 만약 글자들이 원래의 메시지와 똑같이 돌아온다면, 그는 그것이 진짜임을 알게 됩니다.

이 새로운 설계가 승리하는 이유

저자들의 새로운 체계는 두 가지 주요한 이유로 상당한 개선을 이루었습니다. 첫째, 훨씬 단순합니다. 모든 키를 보유하고 얽힌 입자를 준비하는 "신뢰할 수 있는 센터(중간 관리자)"와 복잡한 얽힌 입자 자체를 없앰으로써, 이 시스템은 실제로 구축하고 운영하기가 훨씬 쉽습니다. 이는 복잡한 다수 인원의 계주 경기를 단순한 일대일 전달 경기로 바꾸는 것과 같습니다.

둘째, 그리고 가장 중요한 점은, 안전하다는 것입니다. 저자들은 자신들의 새로운 방법이 "정보 이론적으로 안전(information-theoretically secure)"하다는 것을 수학적으로 증명했습니다. 이는 무한한 컴퓨착 능력을 가진 아주 똑똑한 해커가 서명을 추측하려고 노력하더라도, 서명이 순수한 무작위 소음처럼 보일 것이라는 뜻입니다. 그들은 양자 상태의 "밀도"가 매우 균일하여, 서명만 보고는 하나의 메시지와 다른 메시지를 구분할 수 없음을 보여주었습니다.

나아가, 그들은 자신들의 체계가 기존의 것을 무너뜨렸던 특정 위조 공격을 성공적으로 방어함을 입증했습니다. 서명은 단일 입자와 전송 중에 절대 공유되지 않는 비밀 키를 사용하여 생성되기 때문에, 이브는 미끼 입자들에 걸리지 않고는 메시지를 바꾸기 위해 서명을 단순히 "플립"할 수 없습니다.

"비전이성(Non-Transferability)"의 마법

이 새로운 시스템의 가장 멋진 점은 "비전이성" 약속을 지킨다는 것입니다. 이 양자 춤 속에서 검증자인 밥은 서명을 만들기 위해 앨리스가 했던 것과 똑같은 춤 동작을 실제로 수행할 수 있습니다. 이는 만약 밥이 제삼자에게 서명을 보여주려 할 때, 그 제삼자는 누가 이것을 만들었는지 증명할 수 없음을 의미합니다. 밥이 직접 만들었을 수도 있기 때문입니다! 이는 앨리스의 프라이버시를 보호하며, 그녀의 서명이 오직 밥에게만 의미를 갖도록 보장합니다.

요약하자면, 저자들은 인기 있는 양자 서명 아이디어의 결함을 찾아냈고, 도둑이 어떻게 그것을 깰 수 있는지 정확히 보여주었으며, 복잡한 "마법의 주사위"나 중간 관리자가 필요 없는 더 강력하고 단순하며 안전한 버전을 구축했습니다. 이는 양자 보안의 세계에서, 가장 유망해 보이는 자물쇠라도 신뢰하기 전에는 반드시 먼저 따보는 과정이 필요하다는 것을 상기시켜 줍니다.