최근 양자 컴퓨터 시대에도 안전한 PQC(Post-Quantum Cryptography) 전자서명 기술이 각광받고 있습니다. 그 중에서도 MPC-in-the-Head(MPCitH)* 방식의 서명은 트랩도어** 없이도 강력한 보안을 제공하는 것으로 주목받았는데요. 다만 서명 크기가 크고 속도가 느리다는 단점 때문에 현실 적용에 어려움이 있었죠. 삼성SDS 연구소와 KAIST 연구진은 이 비효율의 원인을 ‘벡터 커밋먼트(Vector commitment)’에서 찾아, 그 요구사항을 살짝 완화하는 기발한 방법으로 문제를 해결했습니다. 새로운 벡터 세미-커밋먼트(Vector semi-commitment) 기술을 적용한 결과, 서명 크기를 약 18% 줄이고 서명/검증 속도를 2배 이상 높이는 성과를 거두었습니다. 이로써 MPCitH 계열 서명 중 가장 빠르고 작은 기록을 세우며, 양자컴퓨팅 시대를 대비한 전자서명 실용화에 한 걸음 다가서게 되었습니다.
* MPC-in-the-Head(MPCitH): Multi-Party Computation을 여러 참가자가 아닌 한 사람의 “머릿속”에서 가상으로 실행하는 zero-knowledge 증명 기법. 원본 MPC 프로토콜을 서명자 혼자 시뮬레이션하여 proof를 생성하는 방식을 가리킨다.
** 트랩도어(trapdoor): 수학적 알고리즘에 존재하는 숨겨진 비밀값으로, 이를 아는 사람만 특정 연산을 쉽게 풀 수 있지만 모르는 사람은 풀 수 없도록 만든 일종의 백도어 키. 전통적 RSA, ECC 서명에는 소수의 곱, 이산로그 같은 트랩도어가 존재하나, MPCitH 서명은 그런 구조가 없다.
MPCitH 서명, 안전한데 왜 이렇게 느릴까?
여러분은 디지털 전자서명을 사용할 때 한 가지 숨은 고민이 있다는 걸 아나요? 바로 현존하는 많은 전자서명 방식들이 양자 컴퓨터의 위협 앞에서 취약해질 수 있다는 점입니다. 미래에도 안전한 전자서명을 위해 연구자들은 다양한 PQC 전자서명 기법을 개발 중인데요. 그 중 하나가 바로 MPCitH방식의 서명입니다. 말 그대로 다자간 연산(Multi-Party Computation, MPC)을 마치 한 사람의 머릿속에서 시뮬레이션하듯 수행하여 증명을 만드는 방법이죠. 이 방식의 가장 큰 장점은 트랩도어 같은 숨은 비밀 구조에 의존하지 않는다는 것입니다. 서명 생성에 오직 일반적인 일방향 함수만 사용되기에, 잠재적인 수학적 약점 없이도 강력한 보안을 확보할 수 있죠. 실제로 블록 암호나 코드 문제처럼 오랫동안 검증된 난제들을 기반으로 안전성을 증명할 수 있어 신뢰성이 높다는 평가를 받습니다.
그런데 이렇게 탄탄한 보안을 자랑하는 MPCitH 서명에는 치명적인 단점이 있었으니, 바로 무거운 연산량과 거대한 서명 크기입니다. 한 사람 머릿속에서 N명의 가상 참가자가 MPC 프로토콜을 수행하다 보니, 그 복잡도가 늘어나 버립니다. 쉽게 말해, 안전성을 높일수록 서명에 담아야 할 데이터 양과 계산량이 기하급수적으로 증가하는 구조인 것이죠. 예를 들어 MPCitH 기반서명의 경우, 서명자가 머릿속에서 여러 ‘가상 참가자’를 만들어 각자 기록을 미리 봉인(커밋먼트, commitment) 해 두고, 서명 과정에서 뽑힌 무작위 지시가 정한 일부 기록만 열어 보여주면, 검증자가 그 기록들이 규칙에 맞는지 확인해서 전체 계산이 제대로 됐다고 믿게 하는 방식입니다.이를 위해 사용하는 기술이 GGM(Goldreich-Goldwasser-Micali) 트리라는 것인데요. GGM 트리는 N개의 시드*를 모두 나열하는 대신 트리 구조로 묶어 필요한 정보만 공개하도록 해 서명 크기를 줄여줍니다. 하지만 이런 최적화를 동원하고도 여전히 기존 타원곡선이나 격자 기반 서명에 비해 서명이 크고 느리다는 평가를 받아왔습니다. 많은 연구자들이 프로토콜 최적화나 효율적인 암호 프리미티브(Primitive)를 도입해 이 문제를 개선하고자 노력해왔지만, MPCitH 서명의 무거운 특성은 여전히 실용화를 가로막는 난제로 남아 있었죠.
* 각각의 가상 참가자가 알고있(다고 가정하)는 비밀 중간값(다자간 연산에 사용되는 값)을 랜덤 “시드”를 통해 생성
‘벡터 커밋먼트’를 풀어주면 생기는 마법
그렇다면 MPCitH 서명의 무엇이 이렇게 비대한 몸집을 만드는 걸까요? 삼성SDS-KAIST 연구팀은 눈을 돌려 벡터 커밋먼트(Vector commitment)라는 구성 요소에 주목했습니다. 간단히 말해 커밋먼트(commitment)란, 특정 값을 나중에 공개할 것을 약속하면서 그 내용을 봉인해 두는 암호학적 장치입니다. 이를테면 “비밀 편지 봉투”에 비유할 수 있는데요. 내용은 상대방에게 감추되(Hiding, 숨김성), 한 번 봉인한 뒤에는 내용을 함부로 바꾸지 못하게 하는 것(Binding, 바인딩성)이 커밋먼트의 역할입니다. 벡터 커밋먼트는 봉투 하나로 여러 개의 값(벡터)을 통째로 봉인(숨김성+바인딩성)할 수 있는 기술을 말합니다. MPCitH 서명에서는 다수 가상 참가자의 난수 시드(seed)들을 한꺼번에 커밋해 두었다가, 검증시 일부만 열어 보여주는 용도로 이 기술이 활용됩니다.
하지만 바인딩(Binding)이라는 속성에 너무 집착한 나머지 효율을 잃고 있는 건 아닐까? 연구진은 이렇게 문제를 제기했습니다. 사실 따지고 보면, 커밋먼트의 바인딩이 조금 깨진다고 바로 서명이 위조되는 건 아닙니다. 바인딩은 “봉인 후 내용 위조 불가”를 뜻하지만, 서명 위조란 “변경한 내용이 로또 1등 번호를 맞추는 문제”이기 때문에 몇 번 변경할 수 있다고 해서 서명 위조를 할 수 있지 않다는 것* 입니다. 그렇다면 아예 이 엄격한 약속을 살짝 풀어주는 대신 성능을 얻자는 발상이 가능합니다. 이번 연구의 핵심 아이디어인 “벡터 세미-커밋먼트(Vector semi-commitment)”가 바로 그것입니다. 이름 그대로 완전히 묶어두지 않은 커밋먼트인데요. 구체적으로는 여러 개의 서로 다른 값이 같은 커밋 결과를 내도록 허용해주는 것입니다. 마치 하나의 자물쇠에 열쇠가 딱 하나만 맞아야 하는 기존 방식에서, 몇 개 다른 열쇠도 운 좋으면 열릴 수 있게 한 셈입니다. 물론 완전히 아무 열쇠로나 열리게 둔 것은 아니며, 여전히 정해진 소수의 열쇠 외에는 통하지 않게 제한합니다. 논문에서는 이를 추출 가능 세미-바인딩 특성으로 정의하는데, 한 커밋먼트에 대해 공격자가 찾아낼 수 있는 다른 해석의 개수가 아주 제한적임을 보장하는 성질입니다. 쉽게 말해, 봉투 하나에 서로 다른 두 세 개의 편지가 우연히 들어맞을 순 있어도, 수십 개의 엉뚱한 편지를 한 번에 그 봉투로 위조해내는 일은 불가능하다는 것이죠.
* 바인딩을 깨고 서명 위조를 한다는 것은 봉인 내용을 바꿈과 동시에 바꿔진 시드가 랜덤한 비밀 중간값이 다자간 연산의 등호가 정확하게 들어맞게끔 생성해야 가능
이렇게 커밋의 자유도를 조금 늘려주면 무엇이 좋을까요? 가장 직접적인 효과는 커밋 데이터의 크기를 줄일 수 있다는 점입니다. 기존 벡터 커밋먼트에서는 안전한 바인딩을 위해 출력물에 충분한 길이(예: 2λ-bit)를 할당했지만, 세미-커밋먼트에서는 출력 크기를 절반(λ-bit)으로 줄여도 문제가 없었습니다. 또한 GGM 트리 등 기존 최적화 기법과도 잘 맞물려 동작합니다. 이번 연구에서는 두 가지 환경(모델)에서 이 아이디어를 구현했는데, 하나는 해시 함수를 이상적으로 보는 랜덤 오라클 모델이고 다른 하나는 블록 암호를 이상화한 아이디얼 사이퍼(Ideal Cipher) 모델입니다. 특히 이상적인 블록 암호 모델에서는, 최근 제안된 상관관계가 있는 GGM 트리 기법과 고정키 AES 기반 난수 생성기 등의 최신 최적화를 모두 결합하여 시스템을 구축했습니다. 쉽게 말해, 한 번의 트리 계산으로 여러 시드들을 효율적으로 만들어내고(AES 활용), 트리의 구조적 반복을 줄이는(상관 GGM) 방법들을 함께 적용한 것이죠. 이렇게 하면 연산 호출 횟수를 절반으로 줄이고도, 바인딩 완화로 생길 수 있는 문제를 솔팅된 GGM 트리(salted tree*)로 막아내어 보안도 잡고 성능도 잡는 효과를 얻었습니다.
* Salted tree: GGM 트리를 만들 때, 트리 전체에 ‘salt’라는 추가 랜덤 값을 섞어 노드들을 생성하는 방식. 이 salt 덕분에 매 서명 마다 트리의 입력 영역이 달라져 서로 다른 시도들 사이에서 공격자가 구조를 재활용하기 어려움
무엇보다 중요한 건, 이렇게 커밋먼트를 느슨하게 바꾸어도 서명 자체의 안전성에는 큰 문제가 없다는 것을 증명해냈다는 점입니다. 연구진은 제안 기법을 기존 MPCitH 서명 알고리즘인 BN++에 적용한 후, 아이디얼 사이퍼 모델 하에서 암호학적 안전성을 이론적으로 증명했습니다. 한마디로, 기존의 빡빡한 커밋먼트 대신 우리 방식의 세미-커밋먼트를 써도 서명이 뚫리지는 않는다는 강한 확신을 준 것입니다. 성능 향상을 얻되 보안에 타협이 없도록 세심하게 설계했다는 뜻이겠지요.
실제로 논문의 내용을 살펴보면, 수식이 너무 많고 복잡하여 이해하기가 어렵기 때문에 이렇게 긴 블로그 소개글을 쓰게 된 것인데요. 그럼에도 불구하고 논문상 여러 수식 중 딱 하나만 핵심을 꼽아보자면 느슨한 바인딩을 수식으로 보여주는 ‘Lemma 3’의 보안 경계식이 가장 핵심을 집어내고 있다고 생각됩니다.
\( \text{Adv}_{\text{RO-VSC}}^{u-\text{esb}} (A) \leq \frac{10Q}{2^{\lambda}} \) where, \( u = 2N \left( \frac{\lambda}{\log \lambda} \right)^2 \)
보안 경계식이라고 표현한 이유는, ‘공격자가 성공할 최대 확률(=유리함, advantage)이 이 값보다 크지 않다’ 라고 윗부분을 잘라(upper bound)주는 부등식이기 때문입니다. \[ \text{Adv}_{\text{RO-VSC}}^{u-\text{esb}} (A) \]는 공격자가 느슨한 바인딩을 깨서 한 커밋에서 너무 많은 충돌을 만들어내는 데 성공할 확률/이점을 뜻하고, 식의 오른쪽 값은 그 최대치를 주는 경계 입니다. 보안 파라미터 λ가 충분히 크고(예: 128) 공격자가 하는 질의 수 Q가 현실적이면, 이 값은 무시 가능 할 정도로 극도로 작아지게 됩니다. 즉, 현실적으로 깨기 어렵다고 이론적으로 보장이 된다는 의미입니다.
더 작고 빠르게 – 성능은 얼마나 향상됐을까?
그렇다면 정량적으로 얼마나 서명이 작아지고 빨라졌을까 궁금해집니다. 연구팀은 이번에 제안한 기법들을 삼성SDS가 개발한 AIMer v2.0 서명 스킴에 적용해 성능을 측정했습니다. 결과는 매우 인상적이었습니다. 서명 크기는 최대 18%까지 줄어들고, 서명 생성 및 검증 속도는 무려 2배 이상 향상되었는데요. 예를 들어 이전에 5KB 정도 되던 서명이 약 4KB대로 감소하고, 서명 계산 시간도 절반 이하로 단축된 셈입니다. 이러한 개선 덕분에 해당 스킴은 현재까지 발표된 MPCitH 계열 서명들 가운데 가장 빠른 처리 속도와 가장 작은 서명 크기를 달성하게 되었습니다. 다른 유사한 후발 연구들인 SDitH(SD-in-the-Head)나 FAEST 등의 성능과 비교해봐도 우리 팀의 개선된 서명이 두각을 나타낸다는 것이 확인되었습니다. 한편 보안성 측면에서도, 반복 횟수 등의 매개변수를 증가시키지 않고도 동일한 수준의 보안을 유지하면서 효율만 높인 것이기에 의미가 큽니다.
이런 성능 개선은 실제 응용 환경에서 상당한 차이를 만들어낼 수 있습니다. 네트워크 대역폭이나 저장 공간을 절약할 수 있어 업데이트 패치 서명이나 인증 토큰 등에 응용하기에 한층 수월해집니다. 서명 생성·검증 속도가 빨라졌다는 것은 곧 대량의 서명 검증이 필요한 서버나 블록체인 노드에서도 효율적으로 운영될 수 있음을 뜻합니다. 특히 블록체인과 같이 지속적으로 다수의 서명을 처리해야 하는 시스템에서는 서명 크기와 속도가 곧 직접적인 비용과 연결되므로, 이러한 최적화가 가져올 이점이 큽니다.
앞으로 어디에 활용될 수 있을까?
이번 연구가 보여준 ‘느슨한 커밋먼트’ 아이디어는 향후 다양한 보안 분야에서 활용 가능성을 기대하게 합니다. 첫째로, 양자 컴퓨터 시대를 대비해야 하는 정부, 군사, 금융 시스템에서 신뢰할 수 있는 전자서명 솔루션으로 적용될 수 있습니다. 트랩도어 없이 대칭키 암호만으로 안전성을 보장하기 때문에, 장기적으로도 안전한 디지털 인증서를 발급하는 데 유리하죠. 둘째로, IoT 기기나 스마트 차량처럼 연산 능력이 약한 환경에도 포스트 양자 서명을 경량화된 형태로 심어 넣는 길을 열어줍니다. 서명 크기가 줄어든 덕분에 배터리 소모나 통신 부하를 최소화하면서도 미래 보안을 선제적으로 확보할 수 있을 것입니다. 그 밖에도 블록체인 스마트 컨트랙트(Smart Contract), 디지털 서명 기반 소프트웨어 업데이트 등 광범위한 IT 인프라에 이번 기술을 접목해볼 수 있습니다. 핵심은 양자 시대에도 안전하면서, 실제로 쓰기에도 부담 없는 서명을 만드는 것인데요. 이번 연구의 성과가 바로 그 중요한 퍼즐 조각을 제공했다고 볼 수 있습니다. 앞으로 이 벡터 세미-커밋먼트 기법이 발전되어, 우리가 일상적으로 사용하는 모든 보안 시스템이 양자 위협에도 끄떡없는 든든한 모습을 갖추게 되기를 기대해 봅니다.
👉 논문 바로가기