🔬 physics

Security evaluation of quantum distance-bounding protocols via semidefinite programming

이 논문은 양자 거리 측정 프로토콜의 빠른 위상을 분리하고 반정부정치 계획법(semidefinite programming)을 활용하여 이산 변수 시스템에 대한 최적의 1라운드 거리 사기 및 마피아 사기 공격 확률을 계산하는 한편, 연속 변수 시나리오에 대한 추정치를 제공함으로써 양자 거리 측정 프로토콜의 보안성을 평가한다.

원저자: Kevin Bogner, Aysajan Abidin, Dave Singelée, Bart Preneel

게시일 2026-09-15

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Kevin Bogner, Aysajan Abidin, Dave Singelée, Bart Preneel

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

당신의 자동차 키가 당신 바로 옆에 있을 때만 잠금이 해제되고, 도둑이 실제로는 수 마일 떨어진 곳에 있는 키를 신호 중계(relay)하여 시스템을 속일 수 없는 세상을 상상해 보십시오. 이것이 바로 거리 바운딩 프로토콜(distance-bounding protocols)의 약속입니다. 이는 단순히 당신이 올바른 비밀 코드를 가지고 있는지를 확인하는 것을 넘어, 당신이 주장하는 바로 그 자리에 서 있는지를 검증하는 디지털 시스템입니다. 고전적인 세계에서 이는 라디오 신호가 되돌아오는 데 걸리는 시간을 측정하는 것에 의존합니다. 하지만 기술이 발전함에 따라, 과학자들은 이 검증 과정을 양자 영역으로 옮겨 빛의 입자를 사용하여 깨지지 않는 타이밍 보증을 만들어내고 있습니다. 그러나 문제는 새로운 양자 설계마다 동작 방식이 달라, 그 보안성을 공정하게 비교하는 것이 거의 불가능하다는 점이었습니다. 어떤 설계는 특정 유형의 속임수에는 강하지만, 다른 설계는 또 다른 속임수에는 취약할 수 있어, 연구자들이 어떤 시스템이 진정으로 안전한지 판단할 공통된 척도를 갖지 못하게 만들었습니다.

벨기에 KU 루벤(KU Leuven)의 연구팀은 이러한 양로 검증을 위한 보편적인 테스트 환경을 구축함으로써 이 비교 문제를 해결했습니다. 그들은 프로토olo의 가장 결정적인 순간, 즉 증명자가 먼 곳에서 빛이 이동할 수 있는 시간보다 더 빨리 질문에 답해야 하는 찰나의 교환 단계인 '빠른 단계(fast phase)'에 집중했습니다. 이 단일 통신 라운드를 분리함으로써, 연구팀은 원격지에서 기만하려는 공격자가 가질 수 있는 절대적인 최대 성공률을 계산하는 수학적 방법을 개발했습니다. 특정 속임수를 추측하거나 시뮬레이션하는 대신, 그들은 준정부호 계획법(semidefinite programming)이라는 강력한 최적화 도구를 사용하여 공격자가 사용할 수 있는 모든 전략을 지도화함으로써 어떠한 잠재적 허점도 놓치지 않도록 했습니다. 이 접근 방식을 통해 연구진은 여러 주요 양자 프로토콜의 정확한 보안 한계를 결정할 수 있었으며, 어떤 프로토콜이 견고하게 버티고 있고 어떤 것이 이전에 생각했던 것보다 더 취약한지를 밝혀냈습니다.

연구진은 이 방법을 네 가지 서로 다른 양자 프로토콜에 적용했는데, 그중 세 가지는 빛의 개별 입자를 사용하고 하나는 빛의 연속파(continuous waves)를 사용합니다. 입자 기반 시스템의 경우, 수학적 계산은 명확하고 흔들림 없는 답을 제공했습니다. 그들은 가장 흔한 유형의 기만, 즉 부정직한 사용자가 실제보다 더 가까이 있는 것처럼 속이려 할 때, 연구된 모든 입자 기반 프로토콜에서 성공률이 정확히 50%라는 것을 발견했습니다. 이는 단일 라운드에서 원격지의 사기꾼이 동전 던지기보다 더 나은 확률을 가질 수 없음을 의미합니다. 그러나 연속파를 사용하는 프로토콜의 경우 이야기가 달라지는데, 동일한 유형의 기만에 대한 성공률이 약 36%로 크게 떨어졌습니다. 또한, 범죄 팀이 협력하여(한 명은 검증자 근처에, 다른 한 명은 정직한 사용자 근처에 위치함) 정보를 중계하는 더 복잡한 공격을 살펴볼 때도 이야기는 달라집니다. 이 시나리오에서 프로토콜들은 매우 다르게 작동했습니다. 연구팀은 가장 널리 알려진 QDB 2019 프로토콜이 이전에 믿었던 것보다 실제로 덜 안전하며, 새로운 분석 결과 공격자가 약 90%의 확률로 성공할 수 있다는 것을 발견했습니다. 또한 Mutual QDB라고 불리는 또 다른 프로토콜 역시 이전의 추정치보다 더 약한 것으로 드러났으며, 공격자의 성공률이 75%로 상승했습니다.

아마도 가장 중요한 발견은 이와 같은 방식으로 엄격하게 테스트된 적이 없던 두 가지 프로토콜에 대한 것이었을 것입니다. 유명한 E91 얽힘 설계를 기반으로 한 프로로콜의 경우, 연구진은 최초의 보안 수치를 계산하여, '마피아식 사기(mafia-style fraud)' 시나리오에서 공격자가 약 93%의 확률로 성공할 수 있음을 찾아냈습니다. 마찬가지로 연속파를 사용하는 프로토콜에 대해서도 최초의 추정치를 제공하였는데, 동일한 유형의 공격에 대해 약 91%의 성공률을 보였습니다. 이 수치들은 단순한 이론적 추측이 아닙니다. 입자 기반 프로토콜의 경우, 연구팀은 다른 어떤 전략도 이보다 더 잘할 수 없음을 증명하는 수학적 인증서를 생성했습니다. 이는 마치 산맥에서 가장 높은 봉우리를 찾는 것과 같습니다. 일단 지도와 증명을 갖추면, 그 누구도 더 높이 올라갈 수 없다는 것을 확실히 알 수 있습니다.

또한 이 연구는 왜 일부 오래된 설계들이 이 비교에서 제외되었는지도 명확히 했습니다. 초기 프로토콜 중 하나는 인증을 증명하기 위해 최종 디지털 서명에 의존했는데, 연구진이 타이밍 메커니즘만을 테스트하기 위해 그 서명을 제거하자 시스템이 완전히 붕괴되어 공격자가 100%의 확률로 성공할 수 있었습니다. 이는 타이밍 메커니즘 자체가 단순히 나중의 확인에 의존하는 것이 아니라, 사용자 인증을 수행할 수 있을 만큼 강력해야 한다는 중요한 원칙을 확인시켜 주었습니다. 연구진은 이 결과들이 단일 통신 라운드에 적용된다는 점을 강조했습니다. 실제 시스템에서 여러 라운드가 진행된다면 보안성은 훨씬 더 높아지겠지만, 단일 라운드의 정확한 한계를 아는 것이 안전한 전체 시스템을 구축하는 필수적인 첫 단계입니다. 이처럼 정밀하고 비교 가능한 수치를 제공함으로써, 연구팀은 엔지니어들이 미래의 안전한 위치 인식 기술을 위한 가장 견고한 프로토콜을 선택할 수 있는 명확한 길을 제시했습니다.

제목: 준정부호 계획법(Semidefinite Programming)을 통한 양자 거리 바운딩 프로토콜의 보안성 평가

문제 정의
양자 거리 바운딩(Quantum Distance-Bounding, QDB) 프로토콜은 증명자가 유효한 비밀 키를 보유하고 있는지와 물리적으로 검증자와 특정 거리 내에 위치하는지를 검증하는 것을 목표로 한다. 이러한 프로토콜은 거리 제약을 강제하기 위해 타이밍이 정밀하게 조절된 양자 통신 "빠른 단계(fast phase)"를 활용한다. 그러나 서로 다른 QDB 프로토ка(예: 준비-측정 방식과 얽힘 기반 방식) 간의 보안성을 비교하는 것은 해당 프로토콜의 빠른 단계가 가진 구체적인 구조에 따라 최적의 공격 방식이 크게 달라지기 때문에 매우 어렵다. 기존 문헌은 프로토콜별 특화된 공격에 초점을 맞추는 경우가 많으며, 이는 다양한 QDB 변형들을 비교할 수 있는 통일된 기준이 결여되어 있다. 또한, 양자 위치 검증(Quantum Position Verification, QPV)은 광범위하게 연구되었으나, 공격자의 분리된 특성으로 인해 비볼록 최적화 문제(nonconvex optimization problems)를 수반하므로 정확한 해를 구하기 어렵다. 본 논문은 단일 라운드 설정에서 거리 사기(Distance Fraud, DF) 및 마피아 사기(Mafia Fraud, MF)에 대한 QDB 프로토콜을 평가하기 위한 통합된 프레임워크의 필요성을 다룬다.

방법론
저자들은 [BASP26]에서 확립된 QDB 보안 프레임워크를 활용하여 DF 및 MF 시나리오에서 공격자의 능력을 정형화한다. 이들은 프로토콜의 빠른 단계를 일-라운드 게임으로 분리하고, 준정부호 계획법(SDP)을 사용하여 최적의 공격 전략을 모델링한다.

이산 변수(Discrete-Variable, DV) QDB: 저자들은 DV-QDB 프로토콜에 대해 DF와 MF 모두의 전략 집합이 정확한 SDP 표현을 가짐을 입증한다.
- 거리 사기(Distance Fraud): 멀리 떨어진 증명자는 검증자의 챌린지에 대한 지식 없이 양자 상태를 준비해야 한다. 이는 공격자가 수락 확률을 최대화하기 위해 밀도 행렬을 최적화하는 "상태 SDP(state SDP)"로 귀결된다.
- 마피아 사기(Mafia Fraud): 공격자는 협력하는 한 쌍(검증자 근처와 증명자 근처)으로 행동하지만, 일-라운드 게임에서는 단일 순차적 전략으로 모델링된다. 공격자는 타이밍이 정해진 챌린지가 도착하기 전 "사전 질의(pre-ask)"(정직한 증명자에게 질의)를 수행하여 양자 시스템을 저장한 후, 검증자의 챌린지에 따라 이를 처리한다. 이 2단계 전략은 "2-슬롯 콤(two-slot comb)"으로 표현되며, "콤 SDP(comb SDP)"로 이어진다.
- 정확한 해결 가능성: 공격자의 분리된 특성으로 인해 비볼록 최적화를 수반하는 QPV와 달리, 일-라운드 게임에서의 QDB MF 공격자는 하나의 순차적 전략으로 붕괴된다. 이를 통해 SDP 최적값이 완화된 경계값이 아닌 정확한 게임 값과 일치하게 된다. 저자들은 정확한 산술(exact arithmetic)을 통해 일치하는 프라이멀(공격) 및 듀얼(인증) 증인을 사용하여 이 값들을 검증한다.
연속 변수(Continuous-Variable, CV) QDB: CV-QDB의 경우, 무한 차원 상태 공간으로 인해 정확한 SDP 정식화가 불가능하다. 대신, 저자들은 보정된 가우시안 공격 모델을 채택한다. 저자들은 공격자의 잠재력을 극대화하기 위해 제로-추가-응답-노이즈(zero-added-response-noise) 가정하에 가우시안 파라미터(프로브 진폭, 측정 각도)에 대한 유한 그리드 탐색을 통해 도출된 성공 확률 추정치를 보고한다.

주요 기여

통합 프레임워크: 본 논문은 빠른 단계를 SDP로 해결 가능한 일-라운드 DF 및 MF 게임으로 환원함으로써 QDB 프로토콜을 비교할 수 있는 통일된 방법을 확립한다.
정확한 SDP 정식화: 저자들은 일반적인 QPV의 완화 기반 접근 방식과 구별되는, 일-라운드 DV-QDB 공격의 전체 전략 공간에 대한 최초의 정확한 SDP 표현을 제공한다.
새로운 보안 경계:
- QDB 2019: 본 연구는 사전 질의 중에 양자 상태를 고전적 추정치로 붕축시키지 않고 온전하게 유지함으로써, 기존에 보고된 것($0.875 $)보다 더 강력한 MF 공격($ p^*_{MF} \approx 0.9045$)을 찾아냈다.
- Mutual QDB: 본 연구는 기존에 보고된 $0.625 $를 개선하여 새로운 MF 값$ 0.75$를 보고한다.
- E91 QDB: 본 논문은 이 프로토콜에 대한 최초의 일-라운드 DF($0.5 $) 및 MF($ \approx 0.9332$) 값을 제공한다.
- CV-QDB: 가우시안 CV-QDB 프로토콜에 대한 첫 번째 라운드당 DF( $\approx 0.3592$ ) 및 MF( $\approx 0.9138$ ) 추정치를 제공한다.
인증(Certification): 모든 DV 결과에 대해, 저자들은 정확한 산술로 검증된 명시적인 프라이멀 및 듀얼 증인을 제공하여 보고된 값이 엄격한 상한 및 하한임을 보장한다.

결과

거리 사기(Distance Fraud, DF): 분석된 모든 이산 변수 프로토콜에 대해, 최적의 일-라운드 DF 성공 확률은 정확히 $0.5$이다. 이는 DF가 이러한 특정 DV-QDB 설계들 사이의 보안성을 구별하지 못함을 나타낸다.
마피아 사기(Mafia Fraud, MF): MF 값은 Mutual QDB($0.75 $)에서 E91 QDB($ \approx 0.9332$)에 이르기까지 프로토콜에 따라 크게 달라진다. 이러한 변동은 공격자가 사전 질의로부터 얻은 정보를 새로운 챌린지에 대한 유효한 응답으로 얼마나 효과적으로 전환할 수 있는지에 달려 있다.
CV-QDB 추정치: CV-QDB 프로토콜은 연속적인 수락 임계값으로 인해 DV 프로토콜보다 낮은 DF 확률( $\approx 0.36$ )을 보이지만, 높은 MF 확률( $\approx 0.91$ )을 보인다. 이 값들은 특정 보정 파라미터(스퀴징, 임계값, 에너지 경계)에 의존하는 추정치이다.
QDB 2017: 본 논문은 빠른 단계 자체가 아닌 최종 MAC에 의존하는 QDB 2017의 경우, (MAC가 제거됨에 따라) 일-라운드 게임에서 MF 값이 $1$이 된다는 점을 언급한다. 이는 거리 측정(ranging)과 인증이 분리될 수 없음을 강조하며, 빠른 단계 자체가 MF 저항성을 제공해야 함을 보여준다.

의의 및 주장
본 논문의 주요 기여는 이산 변수 시스템에 대한 정확한 볼록 정식화(SDP)를 사용하여 공통된 토대 위에서 QDB 프로토콜을 비교할 수 있는 능력을 제공하는 것이라고 주장한다. 이는 공격 최적화가 일반적으로 비볼록인 QPV와 대조된다. 저자들은 이 결과들이 축소된 일-라운드 빠른 단계 게임에 대한 것이며, 다중 라운드 상관관계 및 적응적 전략을 포함하는 전체 프로토콜의 사기 확률과 직접적으로 동일하지 않음을 강조한다. 그러나 보고된 일-라운드 값은 다중 라운드 보안 분석(예: 집중 부등식을 통한 분석)을 위한 필수적인 상수 역할을 한다. 본 연구는 기존 프로토콜(QDB 2019, Mutual QDB)의 보안 이해를 더 강력한 공격을 식별함으로써 업데이트하며, E91 QDB 및 CV-QDB에 대한 최초의 정량적 보안 지표를 제공한다. 저자들은 테러리스트 사기(Terrorist Fraud, TF)는 본 일-라운드 분석의 범위를 벗어난다고 명시적으로 밝힌다.

유사한 논문