SMPC-01. 보안 다자간 계산(SMPC) 소개 및 주요 기법 비교

1. 보안 다자간 계산(Secure Multi-Party Computation, SMPC)이란?

현대 사회에서 데이터는 막대한 가치를 지니지만, 동시에 개인정보, 기업비밀 등 민감한 정보를 포함하고 있어 그 공유와 활용에 큰 제약이 따릅니다. 보안 다자간 계산(SMPC)은 이러한 딜레마를 해결하는 혁신적인 암호 기술로, 서로 신뢰하지 않는 여러 참여자가 각자의 데이터를 공개하지 않고도 공동으로 분석하고 활용할 수 있게 해줍니다. '데이터를 사용하되, 노출하지 않는다(Compute on data without seeing it)'는 원칙을 실현하여, 프라이버시를 지키면서 데이터의 가치를 극대화하는 것을 목표로 합니다.

 

신뢰할 수 있는 제3자(TTP, Trusted Third Party)가 존재한다면 이 문제는 쉽게 해결됩니다. 모두가 TTP에게 자신의 비밀 값을 알려주고, TTP가 계산을 수행한 뒤 결과만 알려주면 되기 때문입니다. 하지만 현실에서는 모든 참여자가 신뢰할 수 있는 제3자를 찾기 어렵거나, 제3자 자체가 보안 위협이 될 수 있습니다. SMPC는 이러한 신뢰 주체 없이도 동일한 목표를 달성하게 해줍니다.

대표적인 예시: 백만장자의 문제 (Yao's Millionaires' Problem)

두 명의 백만장자 앨리스와 밥이 서로에게 자신의 재산이 얼마인지 밝히지 않으면서 누가 더 부자인지 알고 싶어 하는 문제입니다. SMPC를 이용하면, 두 사람은 각자의 재산 액수를 공개하지 않고도 "앨리스가 더 부유하다" 또는 "밥이 더 부유하다"라는 계산 결과만을 안전하게 얻을 수 있습니다.

2. SMPC의 동작 원리 및 목표

SMPC 프로토콜은 모든 참여자가 정해진 규칙에 따라 암호화된 메시지를 주고받는 과정으로 이루어집니다. 이 과정을 통해 각 참여자는 자신의 입력값 일부와 다른 참여자로부터 받은 정보를 결합하여 계산의 일부를 수행합니다. 모든 과정이 끝나면 최종적으로 계산 결과를 얻게 됩니다.

 

SMPC 프로토콜이 만족해야 할 핵심적인 보안 목표는 다음과 같습니다.

• 프라이버시 (Privacy): 프로토콜에 참여하는 동안 정직한 참여자는 자신의 입력값 외에 다른 참여자의 입력값에 대한 어떤 정보도 얻을 수 없어야 합니다. 오직 최종 계산 결과만이 공개됩니다.
• 정확성 (Correctness): 일부 참여자가 프로토콜을 속이려고 시도하더라도, 정직한 참여자들이 얻는 계산 결과는 올바르게 계산된 값이어야 합니다. 악의적인 참여자가 계산 결과를 조작할 수 없어야 합니다.
• 보안 모델 (Security Models): SMPC는 참여자들이 프로토콜을 얼마나 충실히 따르는지에 따라 다른 보안 모델을 가정합니다. 이를 카드 게임에 비유해볼 수 있습니다. 반-정직한(Semi-Honest) 모델은 규칙대로 게임은 하지만, 우연히 본 정보를 통해 다른 사람의 패를 추측하려는 '호기심 많은 플레이어'를 가정합니다. 반면, 악의적인(Malicious) 모델은 일부러 카드를 속이거나 게임의 규칙을 어겨 판을 망치려는 '사기꾼 플레이어'까지 대비하는 더 강력한 보안 환경을 가정합니다. 악의적인 모델을 만족하는 프로토콜은 더 안전하지만 일반적으로 더 복잡하고 비용이 높습니다.

3. 주요 SMPC 기법 비교

SMPC를 구현하는 대표적인 기술로는 혼합 회로(Garbled Circuits), 비밀 공유(Secret Sharing), 동형 암호(Homomorphic Encryption)가 있습니다. 각 기술은 장단점이 뚜렷하여 사용 사례와 환경에 따라 선택적으로 사용됩니다.

가. 혼합 회로 (Garbled Circuits, GC)

주로 두 참여자 간의 계산(2PC, Two-Party Computation)에 효율적인 기법입니다. 한쪽 참여자(Garbler)가 계산할 함수를 암호화된 회로(Garbled Circuit)로 만들고, 다른 참여자(Evaluator)는 이 회로 위에서 자신의 암호화된 입력값으로 계산을 수행합니다. Evaluator는 회로의 중간값이나 구조를 전혀 알 수 없으며 오직 최종 결과만을 얻게 됩니다.

 

동작 방식:

1. Garbler: 계산할 함수를 논리 게이트(AND, OR, XOR 등)로 구성된 Boolean 회로로 표현하고, 각 게이트와 연결선을 무작위 값으로 암호화(Garbling)합니다. 자신의 입력값에 해당하는 암호화된 키도 함께 준비합니다.
2. 전송: Garbler는 암호화된 회로와 자신의 입력값 키를 Evaluator에게 전송합니다.
3. Oblivious Transfer (OT): Evaluator는 자신의 입력값에 해당하는 키를 Garbler에게서 받아와야 하는데, 이때 Garbler가 Evaluator의 입력값을 알 수 없도록 '잊혀진 전송(OT)' 프로토콜을 사용합니다. 이는 마치 Garbler가 0번 상자와 1번 상자에 각각 다른 키를 넣어두면, Evaluator가 자신의 선택(0 또는 1)에 맞는 상자 하나만을 가져갈 수 있고, Garbler는 Evaluator가 몇 번 상자를 가져갔는지 알 수 없으며, Evaluator는 자신이 선택하지 않은 상자 안의 내용물은 알 수 없는 것과 같습니다. 이 과정을 통해 Evaluator는 자신의 입력값을 노출하지 않고 필요한 암호화 키를 얻을 수 있습니다.
4. Evaluator: 암호화된 회로와 양쪽의 입력 키를 이용해 회로를 한 단계씩 복호화하며 계산을 수행하고 최종 결과값을 얻습니다.

나. 비밀 공유 (Secret Sharing, SS)

하나의 비밀 정보를 여러 개의 조각(Share)으로 나누어 다수의 참여자에게 분배하는 방식입니다. 정해진 수(임계값, Threshold) 이상의 조각이 모여야만 원래의 비밀 정보를 복원할 수 있습니다. 이를 연산에 응용하여, 각 참여자는 비밀 값의 '조각'을 가지고 연산을 수행하고, 결과 '조각'들을 모아 최종 결과값을 얻습니다.

 

동작 방식 (Shamir의 비밀 공유 예시):

1. 분배: 비밀 값 S를 나누려는 참여자는 (t-1)차 다항식을 만듭니다. 이때 상수항이 S가 되도록 설정하고 나머지 계수는 무작위로 선택합니다.
2. $f(x) = S + a_1x + a_2x^2 + ... + a_{t-1}x^{t-1}$
3. 이 다항식 위의 서로 다른 n개의 점 (1, f(1)), (2, f(2)), ..., (n, f(n))을 계산하여 각 참여자에게 조각으로 나누어 줍니다.
4. 복원: t개 이상의 조각(점)이 모이면, 다항식 보간법(Lagrange Interpolation)을 통해 원래의 다항식 f(x)를 복원할 수 있고, f(0)을 계산하여 원래 비밀 값 S를 얻을 수 있습니다. t-1개 이하의 조각으로는 S에 대한 어떤 정보도 얻을 수 없습니다.

다. 동형 암호 (Homomorphic Encryption, HE)

암호화된 상태에서 데이터 연산(덧셈, 곱셈 등)을 가능하게 하는 암호 기법입니다. 데이터를 복호화하지 않고도 서버가 암호문 위에서 직접 분석이나 계산을 수행할 수 있어 데이터 처리 과정 전체에서 프라이버시를 보장할 수 있습니다.

 

동작 방식:

1. 사용자는 자신의 개인키(SK)와 공개키(PK)를 생성합니다.
2. 데이터를 공개키(PK)로 암호화하여 Enc(data) 형태로 서버에 전송합니다.
3. 서버는 암호문 Enc(data1), Enc(data2)를 받아서, 복호화 없이 Enc(data1 + data2)나 Enc(data1 * data2)와 같은 연산을 수행합니다.
4. 사용자는 서버로부터 연산 결과의 암호문을 받아 자신의 개인키(SK)로 복호화하여 data1 + data2와 같은 최종 결과를 얻습니다.

종류:

• 덧셈이나 곱셈 중 하나만 지원하면 부분 동형암호, 제한된 횟수의 덧셈/곱셈을 모두 지원하면 준동형암호, 횟수 제한 없이 모든 연산을 지원하면 완전 동형암호(FHE)라고 부릅니다.

주요 기법 비교표

구분 항목	혼합 회로 (Garbled Circuits)	비밀 공유 (Secret Sharing)	동형 암호 (Homomorphic Encryption)
적합한 참여자 수	2명 (2PC)에 매우 효율적, 다자간 확장은 복잡	다수 (Multi-Party)에 효율적	참여자 수에 크게 구애받지 않음 (주로 Client-Server 모델)
통신 오버헤드	계산 복잡도에 비례하여 회로 크기가 커짐 (비교적 높음)	참여자 수와 연산의 곱셈 횟수에 비례 (라운드 수 많음)	초기 데이터 전송 후 통신량 적음 (비대화형 가능)
계산 비용	비교적 가벼움 (주로 대칭키 암호 연산)	매우 가벼움 (주로 정수 연산)	매우 무거움 (특히 곱셈 및 재암호화(Bootstrapping) 연산에 높은 비용 소요)
핵심 장점	2PC 환경에서 가장 높은 효율성	참여자 수가 많아져도 성능 저하가 비교적 적음	통신 라운드가 거의 필요 없고, 강력한 프라이버시 제공
핵심 단점	참여자 수가 늘어나면 통신량 급증	곱셈 연산을 위해 참여자 간 통신이 필수적	연산 속도가 매우 느리고 암호문 크기가 큼
주요 사용 사례	프라이빗 교집합 연산(PSI), 비밀 경매, 유전 정보 분석	디지털 키 관리, 암호화폐 개인키 보관, 통계 분석	클라우드 환경의 프라이버시 보존 머신러닝, 의료 데이터 분석

4. 결론

세 가지 기법은 각각의 장단점을 가지고 상호 보완적으로 발전하고 있습니다. 혼합 회로는 빠른 속도가 중요한 두 참여자 간의 계산에, 비밀 공유는 다수의 참여자가 협력하는 환경에, 그리고 동형 암호는 연산 속도보다 통신 최소화와 강력한 데이터 보호가 중요한 클라우드 컴퓨팅 환경에 적합합니다. 최근에는 이러한 기법들을 결합하여 특정 시나리오에 최적화된 하이브리드 SMPC 프로토콜을 설계하는 연구가 활발히 진행되고 있습니다. 나아가, 성능 향상을 위한 하드웨어 가속, 연합 학습(Federated Learning)과의 결합을 통한 프라이버시 보존 AI, 블록체인 상의 기밀 스마트 계약 등 새로운 응용 분야로 빠르게 확장되고 있어 그 중요성이 더욱 커질 전망입니다.