🛡️

[컴퓨터보안] 대학원 수업 정리

2025년 2학기 대학원 과목인 “고급컴퓨터보안” 수업 내용을 정리한 글입니다.

[Week 1] Introduction

1. 인터넷 시대의 보안과 프라이버시

우리는 인터넷 덕분에 물리적으로 아무리 멀리 떨어져 있어도 쉽게 소통할 수 있다. 하지만, 이러한 편리함에는 대가가 따른다. 우리가 주고받는 통신 채널은 대부분 ‘공개된’ 상태이기 때문에, 누군가 악의적인 목적으로 데이터를 몰래 훔쳐보거나 위조하기가 너무 쉬워졌다.

그렇다면 이렇게 공개된 채널에서 어떻게 데이터를 안전하게 지킬 수 있을까? 이 질문에 대한 해답은 바로 암호학(Cryptography)에서 알 수 있다.

2. 암호화 (Encryption)

공개된 채널로 소통하는 인터넷 세상에서 데이터 보안을 지키려면, 암호화(Encryption)라는 과정이 필수적이다. 암호화는 허가되지 않은 사람이 데이터를 알아볼 수 없도록 변환하는 기술이다.

좋은 암호 알고리즘을 설계할 때는 두 가지를 고려해야 한다:

•

효율성: 키(Key)를 가진 허가된 사용자는 암호화와 복호화를 빠르고 쉽게 할 수 있어야 됨

•

안정성: 키가 없는 공격자는 어떤 방법을 쓰더라도 데이터에 대한 아주 작은 정보라도 얻을 수 없어야 됨

3. 상대해야 할 공격자들

‘이 정도면 안전하겠지’라고 안일하게 생각하면 안 된다. 암호학에서는 다음과 같이 매우 강력한 공격자를 가정한 뒤, 보안을 설계한다:

•

공격자는 우리보다 월등히 좋은 컴퓨터 환경을 갖고 있음

•

공격은 굉장히 오랜 시간에 걸쳐 이루어질 수 있음

•

공격자는 전체 데이터를 복구하는 게 아니라, 아주 작은 부분적인 정보만 얻으려 할 수 있음

•

공격자는 상상할 수 있는 모든 종류의 알고리즘을 동원해 공격할 수 있음

4. 현대 암호의 뿌리: 수학적 난제

그렇다면 공격자가 어떤 알고리즘을 사용할지 전혀 모르는 상태에서 모든 공격을 막아내는 암호를 만드는 게 가능할까?

여기서 수학자들은 “아무리 좋은 컴퓨터라도 다항 시간(polynomial-time) 안에 풀 수 없는 어려운 문제들이 존재할 것”이라고 추측한다. 이것이 바로 유명한

P

NP

문제와 관련이 있다.

전통적인으로 암호 알고리즘에 많이 사용된 수학적 난제들은 다음과 같다:

•

소인수분해 문제 (Factorization problem)

•

이산 로그 문제 (Discrete logarithm problem)

•

타원곡선 이산 로그 문제 (Discrete logarithm problem on elliptic curves)

이러한 문제들을 기반으로 만들어진 암호 시스템이 바로 RSA(Rivest-Shamir-Adleman), ECC(Elliptic Curve Cryptography), ECDSA(Elliptic Curve Digital Signature Algorithm) 등 이다.

5. 양자컴퓨터와 양자내성암호(PQC)

1994년, 피터 쇼어(Peter Shor)라는 수학자가 양자컴퓨터를 이용하면 위에서 언급된 소인수분해나 이산 로그 문제를 다항 시간 내에 풀 수 있는 알고리즘을 발표했다. 이는 미래에 강력한 양자컴퓨터가 등장하면 현재 우리가 사용하는 대부분의 암호 시스템이 무력화된다는 의미이다.

그래서 등장한 개념이 바로 양자내성암호(Post-Quantum Cryptography)이다. 현재 미국 국립표진기술연구소(NIST) 주도로 표준화 작업이 진행 중이다.

가장 유망한 PQC 후보는 격자 기반 암호(Lattice-based cryptography)이다. NIST가 선정한 4개의 PQC 알고리즘 중 3개가 격자 기반이다. 격자 기반 암호는 격자 위에서 정의된 어려운 문제들(SVP, CVP, SIS, LWE 등)에 기반하여, 속도나 키 크기 면에서 효율적이라는 장점이 있다.

6. 암호화된 상태로 연산하기

기존 암호 기술에는 일단 데이터를 암호화하면, 그 내용에 대한 임의의 연산(덧셈, 곱셈 등)을 할 수가 없는 한계가 있다. 이 한계를 극복하기 위해 최근 활발히 연구되는 기술들이 있다:

•

동형 암호 (Homorphic Encrption): 암호화된 데이터 상태 그대로 원하는 연산을 지원하는 암호 기법이다. 덕분에 클라우드 서버가 사용자의 개인 데이터를 복호화하지 않고도 서비스를 제공할 수 있게 되어, 프라이버시와 편리함 사이의 딜레마를 해결해 준다.

•

다자간 계산 (Multi-Party Computation, MPC): 여러 사용자의 데이터를 다룰 때, 각자의 데이터를 서로에게 공유하지 않으면서도 원하는 연산 결과 값만 공유하고 싶을 때 사용하는 프로토콜이다. 전자 투표나 ‘백만장자의 문제’ 같은 시나리오에 활용될 수 있다.

<백만장자의 문제> 두 명의 백만장자가 누가 더 부유한지 알고 싶어하면서 둘 중 누구도 상대방의 순자산을 배우지 않는다. 이 상황에 대한 해결책은 본질적으로 비교 기능을 안전하게 평가하는 것이다.

7. 응용분야: Private AI

인공지능(AI) 산업이 발전하면서 복잡한 보안 문제가 걸림돌이 되고 있다. 예를 들어, ChatGPT 같은 서비스를 이용할 때 다음과 같은 프라이버시 문제가 발생할 수 있다:

클라우드 서비스를 받으려면 내 데이터를 그대로 제공해야 합니다.

모델을 학습시키려면 수많은 제3자의 데이터가 필요합니다.

서버는 AI 모델의 가중치(weights)를 자신들의 자산으로 여깁니다.

AI가 내놓은 결과가 정말 내가 기대한 그 모델에서 나온 것인지 확신할 수 없습니다.

앞서 배운 동형암호나 다자간 계산 같은 기술들이 바로 이런 Private AI 문제를 해결하는 열쇠가 될 수 있다.

[Week 2] Classical Cryptography and Modern Cryptography

1. 암호학이란?

과거에 암호학(Cryptography)은 단순히 ‘암호를 만들고 푸는 기술 정도로 여겨졌다. 뛰어난 암호를 만들거나 해독하는 것은 소수의 창의력과 개인적인 능력에 달려 있었다. 그래서 암호학을 ‘예술(art)’의 한 형태로 보기도 했다.

하지만, 20세기 후반부터 암호학은 이론을 기반으로 ‘과학’으로 발전했다. 이제 암호학은 다음과 같은 훨씬 더 넓은 영역을 다룬다:

•

메시지 인증: 메시지가 정말 그 사람이 보낸 것이 맞는지 확인

•

디지털 서명: 문서의 위조를 막고 작성자를 증명함

•

키 교환 프로토콜: 안전하게 비밀 키를 주고받는 방법 연구

2. 비밀 키 암호

두 사람이 미리 비밀 정보(key)를 공유하고, 이 키를 이용해 메시지를 암호화하고 복호화하는 것이 기본 아이디어이다. 이를 비밀 키(Private Key) 또는 대칭 키(Symmetric Key) 방식이라고 부른다.

•

평문(Plaintext): 암호화하기 전의 원본 메시지

•

암호문(Ciphertext): 암호화된 후의 메시지

•

키(Key): 평문을 암호문으로, 암호문을 평문으로 바꾸는 데 사용되는 비밀 정보

•

암호화(Encrypt): 키를 이용해 평문을 암호문으로 바꾸는 과정

•

복호화(Decrypt): 키를 이용해 암호문을 평문으로 되돌리는 과정

여기서 중요한 가정은, “두 사람이 키를 다른 사람이 모르게 안전한 방법으로 미리 공유했다:는 것이다.

3. 케르크호프스의 원칙: “알고리즘은 공개되어도 안전해야 한다”

“암호를 더 안전하게 만들려면 암호화 방식(알고리즘) 자체를 비밀로 해야 하지 않을까” 라고 생각할 수 있다. 하지만, 19세기 암호학자 오귀스트 케르크호프스(Auguste Kerckhoffs)는 정반대의 주장을 했다.

”암호 방식은 비밀일 필요가 없으며, 적의 손에 넘어가도 문제가 없어야 한다.”

암호 시스템의 안전성은 오직 ‘키의 비밀성’에만 의존해야 한다는 것이다. 알고리즘은 한 번 개발되면 여러 사람이 계속 사용하지만, 키는 필요할 때마다 바꿀 수 있다. 만약 알고리즘이 유출되었을 때 보안이 뚫린다면, 그 시스템 전체를 바꿔야 하는 큰 혼란이 생기기 때문이다.

•

4가지 주요 공격 시나리오

Ciphertext-only attack (암호문 단독 공격)

•

공격자가 오직 암호문만 훔쳐볼 수 있는 상황

•

이 암호문만을 가지고 원래의 평문을 알아내려고 시도함 (가장 약한 공격자 모델)

Known-plaintext attack (알고있는 평문 공격)

•

공격자가 이전에 유출되었거나 알려진 ‘평문과 그에 해당하는 암호문 쌍’을 여러 개 알고 있는 상황

•

이 정보를 바탕으로, 같은 키로 암호화된 다른 암호문의 평문을 알아내는 것이 목표

Chosen-plaintext attack (CPA; 선택 평문 공격)

•

공격자가 암호화 기계(오라클)에 접근할 수 있어서, 자신이 원하는 어떤 평문이든 선택해서 그에 대한 암호문을 얻어낼 수 있는 상황

•

이를 통해 (자신이 직접 암호화해보지 않은) 목표 암호문의 평문을 알아내려 함

Chosen-ciphertext attack (CCA; 선택 암호문 공격)

•

공격자가 복호화 기계(오라클)에 접근할 수 있어서, 자신이 원하는 어떤 암호문이든 선택해서 그에 대한 평문을 얻어낼 수 있는 상황 (단, 목표 암호문 자체를 물어볼 수는 없음)

•

이를 통해 목표 암호문의 평문을 알아내려 함

4. 고전 암호 해독

시저 암호 (Shift Cipher)

•

원리: 알파벳을 일정한 숫자(Key)만큼 밀어서 다른 글자로 바꾸는 방식이다. 율리어스 시저가 3글자씩 밀어서 사용했다. (예: a → D, b → E, …)

•

문제점: 키로 가능한 숫자가 0부터 25까지, 총 26개 밖에 없다. 그냥 모든 키를 하나씩 다 시도해보는 Brute-force attack(전수 조사) 만으로도 순식간에 뚫린다.

•

교훈: “충분한 키 공간의 원칙”. 안전한 암호는 전수 조사가 현실적으로 불가능할 만큼 키 공간이 충분히 커야 된다.

단일 치환 암호 (Mono-alphabetic Substitution)

•

원리: 알파벳 하나하나를 다른 알파벳으로 일대일 대응시키는 방식 (예: a → X, b → E, …) 키 공간의 크기는 26!으로, 전수 조사는 절대 불가능.

•

문제점: 키 공간은 크지만, 언어의 통계적 특성을 이용하면 쉽게 뚫림. 예를 들어, 영어에서는 ‘E’라는 알파벳이 가장 많이 쓰이기에 암호문에서 가장 빈번하게 나타나는 글자가 바로 ‘E’일 확률이 높다. 이런 식으로 빈도 분석(Frequency Analysis)을 하면, 키를 금방 알아낼 수 있다.

•

교훈: 암호는 평문의 통계적 특성을 암호문에 그대로 드러내서는 안 된다.

비즈네르 암호 (Vigenere Cipher)

•

원리: 짧은 단어를 키(Key)로 사용하여, 키의 각 글자에 해당하는 숫자만큼 시저 암호를 반복 적용한다. (예: 키가 CAFE면, 첫 글자는 C(2)만큼, 두 번째는 A(0)만큼, 세 번째는 F(5)만큼 밀어 암호화) 이렇게 하면 평문에서 같은 글자라도 암호문에서는 다른 글자로 바뀌게 되어 빈도 분석이 어려워짐

•

문제점: 카시스키 테스트(Kasiski’s Method)나 일치 지수법(Index of Coincidence Method) 같은 더 발전된 통계적 분석으로 키의 길이를 알아낼 수 있다. 키의 길이를 알면, 결국 이 암호는 여러 개의 시저 암호를 합쳐놓은 것에 불과하므로 쉽게 해독 가능

•

교훈: “안전한 암호를 설계하는 것은 매우 어려움” 전문가가 아닌 사람이 어설프게 만든 암호는 거의 항상 뚫린다고 봐야 함

5. 현대 암호학의 3가지 기본 원칙

보안에 대한 엄밀하고 정확한 ‘정의’부터 시작하라

•

우리가 무엇을 달성하고 싶은지(예: 어떤 공격을 막고 싶은지) 명확하게 정의하지 않으면, 그것을 달성했는지조차 알 수 없음

증명되지 않은 ‘가정’에 보안을 의존한다면, 그 가정을 명확하고 최소한으로 기술하라

•

현대 암호는 대부분 “소인수분해는 어렵다”와 같은 수학적 난제에 기반한다. 이 가정이 틀리면 암호도 깨진다.

•

따라서 어떤 가정 위에 보안이 성립하는지 명확히 하고, 가능한 한 최소한의 가정만 사용해야 한다.

암호 구조는 ‘엄밀한 증명’을 동반해라

•

암호학에서는 직관이 통하지 않을 때가 많다.

•

원칙 1에서 정의한 보안 목표를, 원칙 2에서 기술한 가정하에 만족한다는 것을 수학적으로 엄밀하게 증명해야 된다.

[Week 3] Definition of Security

1. 좋은 보안 정의란 무엇일까?

•

잘못된 정의 1: “암호문을 봐도 비밀키를 찾을 수 없으면 안전하다.”

◦

문제점: 암호의 목적은 메시지를 보호하는 것이지, 키를 보호하는 게 주가 아니다. 만약 암호화 과정에서 키는 무시하고 그냥 평문을 그대로 내보내는 암호 시스템이 있다고 가정하자. 공격자는 비밀키를 절대 찾을 수 없겠지만, 메시지는 그대로 노출되니 전혀 안전하지 않음

•

잘못된 정의 2: “암호문에 해당하는 평문 전체를 찾을 수 없으면 안전하다.”

◦

문제점: 평문의 90%가 노출되더라도, 나머지 10%를 알아내기 어렵다면 정의상 ‘안전’한 것이 된다. 하지만 연봉계약서에서 다른 내용은 다 표준 문구이고 ‘연봉’ 정보만 비밀인데, 그 연봉이 90% 안에 포함되어 노출된다면 암호화의 의미가 전혀 없다.

•

잘못된 정의 3: “암호문으로부터 평문에 대한 ‘의미 있는’ 정보를 얻을 수 없다면 안전하다.”

◦

문제점: ‘의미 있는’이라는 표현이 너무 애매하다. 어떤 정보가 의미 있는지는 상황과 응용에 따라 달라지기 때문이다. 좋은 보안 정의는 미래에 등장할 그 어떤 응용에서도 통할 수 있어야 된다.

•

올바른 정의: “암호문으로부터 평문에 대한 ‘어떠한 함수 값’도 계산할 수 없으면 안전하다.”
⇒ An encryption scheme is secure if no adversary can compute any function of the plaintext from the ciphertext

◦

이 정의가 현대 암호학에서 받아들여지는 올바른 정의이다.

◦

이 정의는 공격자가 평문의 길이, 특정 단어의 포함 여부, 짝수인지 홀수인지 등 아주 사소한 정보조차도 암호문만 보고는 알아낼 수 없어야 한다는 매우 강력한 보안 수준을 요구한다.

2. 완벽한 비밀성(Perfect Secrecy)

정의: 어떤 메시지

m

이 있고, 어떤 암호문

c

가 있을 때, 암호문

c

를 관찰하기 전과 후의 메시지

m

에 대한 확률 분포가 변하지 않는다. 즉,

Pr[M = m | C=c] = Pr[M=m]

이 성립한다면, 이 암호 시스템은 완벽한 비밀성을 가진다.

쉽게 말해, 암호문을 봐도 평문에 대한 그 어떤 정보도 추가로 얻을 수 없다는 뜻이다. 공격자는 암호문을 보나 마나 평문에 대해 아는 것이 전혀 달라지지 않는다.

이와 동등한 정의로 완벽한 구별 불가능성(Perfect Indistinguishability)이 있다. 공격자가 두 개의 다른 메시지

m_0, m_1

을 고르면

m_0

를 암호화한 결과와

m_1

을 암호화한 결과의 분포가 완전히 동일해서 공격자가 둘을 전혀 구별할 수 없다는 뜻이다.

[원타임 패드 (One-Time Pad, OTP)]

OTP는 완벽한 비밀성을 만족하는 암호 방식이다.

•

원리: 평문과 똑같은 길이의 랜덤한 비밀키를 생성하여, 평문과 키를 비트별로 XOR 연산하여 암호문을 만든다.

•

한계:

키가 메시지만큼 길어야 한다. 즉, 1GB 영화를 암호화하려면 1GB의 비밀키가 필요하다.

키를 딱 한 번만 사용해야 한다. (재사용 금지)

이론적으로 완벽하지만, 현실적으로 키를 안전하게 전달하고 관리하기가 매우 어렵다.

3. 계산적 비밀성 (Computational Security)

현실 세계에서는 완벽한 비밀성을 가진 암호를 쓰기 어렵다. 그래서 두 가지 조건을 완화한 계산적 비밀성이라는 개념을 사용한다.

제한된 능력의 공격자: 공격자는 무한한 시간을 갖는 신이 아니라, ‘다항 시간(Polynomial-time)’ 안에 작동하는 효율적인 알고리즘만 사용할 수 있다고 가정한다.

무시 가능한 성공 확률: 공격자가 암호를 깨뜨릴 확률이 0은 아니지만, 그 확률이 1/ncn^cnc 보다 작아서 ‘무시할 수 있을 정도(negligible)’ 작다고 본다.

이를 바탕으로 한 보안의 정의는 다음과 같습니다:

•

다항 시간 내에 실행되는 모든 공격자 AAA에 대해, 두 메시지 m0,m1m_0, m_1m0​,m1​ 중 어느 것이 암호화되었는지 마출 확률이 1/2+negl(n)1/2+negl(n)1/2+negl(n) 보다 작을 때, 이 암호 시스템은 안전하다고 말한다.

◦

1/21/21/2 : 그냥 찍어서 맞출 확률

◦

negl(n)negl(n)negl(n) : 무시할 만큼 작은 값이니, 결국 공격자는 찍는 것보다 아주 약간 더 잘 맞추는 것조차 불가능하다는 의미

4. 공개키 암호 (Public Key Encryption)

지금까지 논의한 비밀키 암호는 ‘키를 어떻게 사전에 안전하게 공유할 것인가?’라는 근본적인 문제를 안고 있다. 이를 해결하기 위해 등장한 것이 공개키 암호이다.

•

원리: 키를 공개키(Public Key)와 개인키(Private Key) 한 쌍으로 만든다.

◦

공개키: 모두에게 공개된다. 누구나 이 키를 이용해 나에게 보낼 메시지를 암호화할 수 있다.

◦

개인키: 나만 안전하게 보관한다. 공개키로 암호화된 메시지는 오직 나의 개인키로만 복호화할 수 있다.

더 이상 비밀 정보를 사전에 공유하기 위해 따로 만날 필요가 없다. 내 공개키를 웹사이트나 명함에 게시해두면, 누구든 안전하게 통신할 수 있게 된다.

[Partial Solution: Key Distribution Centers]

•

키 분배 센터 (KDC)

◦

비밀키 암호화 방식의 가장 큰 숙제는 통신을 시작하기 전, 어떻게 안전하게 비밀키를 공유하느냐 이다.

◦

이에 대한 한 가지 접근 방법은 조직의 모든 구성원이 신뢰할 수 있는 중앙 관리 주체(예: IT 관리자)를 두는 것이다.

◦

이 중앙 관리자는 키 분배 센터(Key Distribution Center, KDC)라고 불리는 단일 서버를 구축한다.

◦

이후 통신을 원하는 직원들(employees)이 생기면, 이 KDC 서버가 중개자 역할을 하며 안전하게 통신할 수 있는 키를 분배한다.

•

KDC의 한계점

◦

중앙 집중식 보안 위협: 만약 공격자가 KDC 서버를 성공적으로 공격하면, 전체 통신 시스템이 완전히 뚫리게 된다.

◦

단일 장애점(Single Point of Failure): KDC 시스템은 단일 장애점을 가진다. 즉, KDC 서버가 다운되면 모든 보안 통신이 일시적으로 불가능해진다.

◦

내부자 위협: KDC 서버 자체가 악의적인 의도를 갖고 있다면, 모든 당사자 간의 통신 내용을 마음대로 엿들을 수 있다.

[Public Key Encryption (공개키 암호화)]

•

공개키 암호화는 비대칭키 암호 방식의 일종이다. 여기서 핵심은 키가 공개키(Public Key)와 개인키(Private Key), 이렇게 한 쌍으로 이뤄져 있다는 점이다.

◦

키 생성: 메시지를 받을 수신자가 한 쌍의 키(공개키, 개인키)를 생성한다.

◦

암호화: 메시지를 보내는 송신자는 수신자의 공개키를 가져와 메시지를 암호화한다. 공개키는 이름 그대로 누구에게나 공개되어 있어 쉽게 얻을 수 있다.

◦

복호화: 암호화된 메시지는 오직 해당 공개키와 쌍을 이루는 개인키를 가진 수신자만이 원래의 메시지로 복호화할 수 있다. 개인키는 수신자 본인만 안전하게 보관한다.

•

공개키 사용 방식

실시간 생성 및 전송: 엘리스(수신자)가 밥(송신자)과 통신해야 한다는 것을 알았을 때, 그 시점에 키 쌍을 생성하고 밥에게 공개키를 암호화되지 않은 일반 채널로 보낸다. 밥은 공개키를 받아 메시지를 암호화해서 엘리스에게 보낸다.

사전 생성 및 배포: 엘리스가 특정 송신자와 상관없이 미리 키 쌍을 생성한다. 그리고 자신의 공개키를 공개된 곳에 널리 배포한다. 그러면 엘리스와 안전하게 통신하고 싶은 사람 누구든지 공개된 키를 찾아 메시지를 암호화할 수 있다.

•

알고리즘 정의

공개키 암호화 시스템은 수학적으로 다음과 같은 3개의 확률적 다항 시간 알고리즘으로 구성된다.

◦

Gen (키 생성): 보안 매개변수 1n1^n1n을 입력받아 한 쌍의 키(pk, sk). 즉, 공개키와 개인키를 출력하는 알고리즘

◦

Enc (암호화): 공개키(pk)와 메시지(m)를 입력받아 암호문(c)을 출력하는 알고리즘

c←Encpk(m)c ← Enc_{pk}(m)c←Encpk​(m)

◦

Dec (복호화): 개인키(sk)와 암호문(c)을 입력받아 원래의 메시지(m) 또는 실패를 의미하는 특수 기호 ⊥ 를 출력하는 결정론적(deterministic) 알고리즘.

m:=Decsk(c)m := Dec_{sk}(c)m:=Decsk​(c)

[공개키 암호의 보안 정의 (IND-CPA)]

•

공개키는 모두에게 알려져 있기 때문에, 공격자는 언제든지 원하는 평문을 암호화 가능하다.

•

이런 상황을 선택 평문 공격(Chosen-Plaintext Attack, CPA)이라고 한다 ⇒ 따라서, 공개키의 암호 보안은 더 강력해야된다.

•

정의: 공격자가 공개키를 가지고 원하는 평문을 얼마든지 암호화해볼 수 있는(오라클 접근) 상황에서도, 두 메시지 m0m_0m0​, m1m_1m1​ 중 어느 것이 암호화되었는지 구별할 수 없을 때, 이 공개키 암호 시스템은 CPA에 의해 안전하다고 말한다.

[EL Gamal Encryption (엘가말 암호)]

•

엘가말 암호는 이산 로그 문제(Discrete Logarithm Problem)의 어려움에 기반한 대표적인 공개키 암호 시스템이다.

•

이 암호 시스템이 IND-CPA 안전성을 갖는다는 것은 결정적 디피-헬만 가정(Decisional Diffie-Hellman, DDH) 문제가 어렵다는 가정하에 엄밀하게 증명된다.

[Week 4] Homorophic Encryption

1. Homorophic Encryption

•

동형암호란?

비밀키 없이 암호화된 데이터에 대해 덧셈이나 곱셈 같은 산술 연산이 가능할까? 그리고 그 연산 결과(암호문)을 복호화했을 때, 암호화되지 않은 원본 데이터로 동일한 연산을 수행하는 것과 같은 정확한 결과가 나올까?

◦

기존 방식: 데이터를 서버에 보내기 전 ‘암호화’하고, 서버가 ‘복호화’한 뒤 분석하고, 결과를 다시 ‘암호화’해서 받아야 한다. 이 과정에서 서버 내 민감한 원본 데이터를 보게 된다.

◦

동형암호 방식: 데이터를 ‘암호화’해서 서버에 보낸다. 서버는 데이터를 복호화하지 않은 암호화된 상태 그대로 연산을 수행한다. 그 결과 암호문을 나에게 돌려주면, 내 비밀키로 복호화하여 결과를 얻는다.

•

동형암호의 정의

Setup (설정): 보안 매개변수 1λ1^\lambda1λ 를 받아 암호 시스템에 필요한 공개 파라미터를 생성한다.

Keygen (키 생성): 파라미터를 받아 공개키(pk), 비밀키(sk), 그리고 연산키(evaluation key)를 생성한다. 이 evk가 바로 암호문 연산에 사용되는 특별한 키이다.

Enc (암호화): 공개키(pk)와 평문(m)으로 암호문(c)을 만든다.

Eval (연산): 연산키와 수행할 함수 fff, 그리고 암호문 c1c_1c1​, …, clc_lcl​ 을 받아 연산이 완료된 암호문 cfc_fcf​를 출력한다.

Dec (복호화): 비밀키(sk)로 암호문 cfc_fcf​를 복호화하여 최종 결과 mfm_fmf​를 얻는다.

이름이 동형(Homomorphic)인 이유는 수학의 ‘준동형 사상(Homomorphism)’ 개념에서 따왔기 때문이다. 이는 평문 세계에서의 연산(

\circ

)이 암호문 시계에서의 연산(

\bullet

)과 구조적으로 보존되는, 즉

Dec(sk, Enc(pk, m_1)\bullet Enc(pk,m_2)) = m_1 \circ m_2

관계가 성립하는 것을 의미한다.

•

노이즈(Noise) 문제

현재 대부분의 동형암호 방식은 보안을 위해 암호화 시 ‘노이즈(noise)’ 또는 ‘오류(error)’라고 불리는 작은 임의의 값을 추가한다.

◦

간단한 예시: 평문 m∈0,1m \in {0, 1}m∈0,1 을 암호화할 때, c=(a,b=a⋅s+2e+m)c = (a, b = a \cdot s + 2e + m)c=(a,b=a⋅s+2e+m) 형태로 만든다. 여기서 sss 는 비밀키이고, eee 가 작은 노이즈이다.

◦

복호화: b−a⋅s=2e+mb - a \cdot s = 2e + mb−a⋅s=2e+m 을 계산한 뒤 (mod 2) 연산을 하면 mmm 을 복구할 수 있다. (물론 eee 가 충분히 작아야 가능함)

문제는 연산할 때, 발생한다.

◦

덧셈: c1+c2c_1 + c_2c1​+c2​ 를 하면, 노이즈가 e1+e2e_1 + e_2e1​+e2​ 가 된다.

◦

곱셈: 곱셈을 하면, 노이즈가 e1⋅e2e_1 \cdot e_2e1​⋅e2​ 처럼 훨씬 더 급격하게 증가한다.

이 노이즈가 계속 커져서 특정 임계치(Noise Ceiling)를 넘어버리면,

b-a\cdot s

값이 너무 커져서 (mod 2) 연산을 해도

m

이 아닌 엉뚱한 값이 나오게 된다. 즉, 복호화가 실패한 것이다.

이 때문에 초기 동형암호는 연산 횟수에 제한이 있었다.

•

Gentry’s Bootstrapping

2009년 크레이그 젠트리가 이 노이즈 문제를 해결하고 완전 동형암호(Fully Homorophic Encryption, FHE)를 최초로 구현했다. 이 아이디어는 크게 3단계이다:

SHE (Somewhat HE) 구축: 일단 제한된 횟수의 덧셈과 곱셈이 가능한 암호(SHE)를 만든다.

Squashing (압축): 이 SHE의 복호화 회로를 더 단순하게 만든다.

Bootsrapping (부트스트래핑): 노이즈가 가득 찬 암호문 ccc 가 있다고 하자. 이 ccc 를 동형암호의 ‘복호화 회로’ 자체를 동형 연산하여 ‘새로고침’한다.

◦

개념:

▪

[Left] 일반 복호화: [암호문 E[p]E[p]E[p]] + [비밀키 sksksk] → [복호화 회로] → [평문 ppp]

▪

[Right] 동형 복호화: [암호화된 암호문 E[E[p]]E[E[p]]E[E[p]]] + [암호화된 비밀키 E[sk]E[sk]E[sk]] → [동형 연산되는 복호화 회로] → [암호화된 평문 E[p]E[p]E[p]]

◦

결과: 노이즈가 많았던 E[p]E[p]E[p] 가 입력으로 들어가서, 노이즈가 깨끗하게 리셋된 ‘새로운 E[p]E[p]E[p]가 나온다.

이 ‘새로고침’ 과정을 통해 암호문 노이즈를 계속 줄일 수 있으므로, 무한한 연산이 가능한 FHE가 된다.

2. Basics of Lattices

•

현대 동형암호의 기반: 격자 (Lattices)

◦

양자 컴퓨터의 위협: 1994년 피터 쇼어(Peter Shor)는 양자컴퓨터로 소인수분해와 이산 로그 문제를 빠르게 풀 수 있음을 보였다. 이는 현재 사용되는 RSA, ECC 같은 암호들이 양자컴퓨터가 등장하면 모두 깨진다는 의미이다

◦

PQC (양자내성암호): 이에 따라 미국 NIST를 중심으로 양자컴퓨터에도 안전한 PQC 표준화가 진행 중이다.

◦

격자 기반 암호: 가장 유망한 PQC 후보이다. NIST가 선정한 4개의 알고리즘 중 3개가 격자 기반이다.

격자 기반 암호는 격자 위에서의 어려운 문제들(SVP(Shortest Vector Problem), CVP(Closest Vector Problem), SIS(Short Integer Solution), LWE(Learning With Errors))에 기반하며, 효율적이고 다양한 기능을 구현하기에 적합하다.

•

격자(Lattice) 기초

◦

정의: 규칙적인 패턴으로 배열된 이산적인(떨어져 있는) 점들의 집함. 벡터 공간과 비슷하지만, 기저(basis) 벡터들의 정수 선형 결합으로만 이뤄진다.

◦

기저(Basis): 격자는 하나의 격자를 표현하는 여러 종류의 기저를 가질 수 있다. 같은 격자(점들)를 표현하는 두 개의 다른 기저 {b1,b2{{b_1, b_2}}b1​,b2​}, {b1′,b2′b_1^{'}, b_2^{'}b1′​,b2′​} 가 나온다.

◦

기저 변환: 격자에서는 유니모듈러 행렬(행렬식이 ±1\pm 1±1 인 정수 행렬)을 통해서만 기저를 바꿀 수 있다.

◦

어려운 문제:

▪

SVP(Shortest Vector Problem): 격자 내에서 0이 아닌 가장 짧은 벡터를 찾는 문제

▪

SIVP(Shortest Independent Vectors Problem): nnn개의 선형 독립인 짧은 벡터들을 찾는 문제

•

LWE(Learning With Erros) 문제

현대 동형암호의 보안 근간은 바로 LWE 문제이다.

◦

개념: 노이즈(오류)가 포함된 선형 연립방정식에서 비밀키(sss)를 복원하는 문제

◦

난이도: 만약 노이즈가 없다면, 가우스 소거법(Gaussian elimination)으로 쉽게 풀 수 있다. 하지만 노이즈가 끼어있으면, 가우스 소거법은 오히려 노이즈를 증폭시켜서 풀 수 없게 만든다.

◦

LWE 분포 (As,χA_{s,\chi}As,χ​): LWE 문제는 다음과 같은 분포에서 샘플을 뽑는다.

랜덤 벡터 aaa를 뽑는다.

작은 노이즈(오류) ϵ\epsilonϵ 을 뽑는다.

a,b=s⋅a+ϵ(modq)a, b = s \cdot a + \epsilon \pmod qa,b=s⋅a+ϵ(modq) 를 출력한다. sss가 비밀키이다.

◦

안전성: LWE 문제는 (양자컴퓨터로도 풀기 어려운) 격자 문제(SVP/SIVP)만큼 어렵다는 것이 수학적으로 증명되었다.

3. Concept of Approximate HE

•

근사 동형암호 (Approximate HE) - CKKS의 아이디어

이 모든 것을 어떻게 합칠까요? 특히 머신러닝 등에 필요한 실수 연산은 어떻게 할까요?

◦

실수 다루기: BGV, BFV 같은 다른 동형암호는 정수나 비트 연산을 지원한다. 실수 연산을 위해, 스케일링 팩터(Scaling Factor) Δ\DeltaΔ 를 도입한다.

◦

인코딩: 실수 mmm을 ⌊Δ⋅m⌉\lfloor \Delta \cdot m \rceil⌊Δ⋅m⌉ (반올림) 한 정수로 저장한다.

◦

예시 (1.23×4.561.23 \times 4.561.23×4.56):

Δ\DeltaΔ = 100 으로 설정한다.

m1=1.23→123m_1 = 1.23 \rightarrow 123m1​=1.23→123 , m2=4.56→456m_2 = 4.56 \rightarrow 456m2​=4.56→456 로 저장한다.

(Δ⋅m1)⋅(Δ⋅m2)(\Delta \cdot m_1) \cdot (\Delta \cdot m_2)(Δ⋅m1​)⋅(Δ⋅m2​) = 123 ×\times× 456 = 56088

결과 해석: 56088은 스케일링 팩터가 Δ2\Delta^2Δ2 = 10000 이 된 5.6088로 해석한다.

◦

문제점 (정확한 곱셈): 곱셈을 할 때마다 스케일링 팩터가 Δ→Δ2→Δ4…\Delta \rightarrow \Delta^2 \rightarrow \Delta^4 \dotsΔ→Δ2→Δ4… 로 제곱이 된다. 이러면 숫자가 금방 커져서 모듈러 qqq 의 범위를 넘어가 버리고, 중요한 상위 비트(MSB)들을 읽게 된다.

◦

해결책 (근사 곱셈): CKKS 스킴은 이 문제를 해결한다. 곱셈 후, 불필요하게 늘어난 하위 비트(LBS)들을 버린다.

◦

이 과정을 리-스케일링(Rescaling)이라고 부른다.

▪

덧셈: Δm1,Δm2→Δ(m1+m2)\Delta m_1, \Delta m_2 \rightarrow \Delta(m_1 + m_2)Δm1​,Δm2​→Δ(m1​+m2​) (스케일 Δ\DeltaΔ 유지)

▪

곱셈: Δm1,Δm2→Δ2m1m2\Delta m_1, \Delta m_2 \rightarrow \Delta^2 m_1 m_2Δm1​,Δm2​→Δ2m1​m2​ (스케일 Δ2\Delta^2Δ2 증가)

▪

리-스케일링: Δ2m→Δm\Delta^2 m \rightarrow \Delta mΔ2m→Δm (스케일 Δ\DeltaΔ 복원)

•

RLWE (Ring-LWE) 문제

LWE는 효율적이지만, 더 빠른 연산을 위해 LWE의 변형인 Ring-LWE(RLWE)를 사용한다.

◦

개념: 일반 숫자(정수) 대신 다항식 링(Ring) R=Z[X]/(XN+1)\mathcal{R} = \mathbb{Z}[X]/(X^N+1)R=Z[X]/(XN+1) 위에서 LWE 문제를 정의한다.

◦

RLWE 인스턴스:

▪

랜덤 다항식 a∈Rqa \in \mathcal{R}_qa∈Rq​, 비밀 다항식 s∈Rs \in \mathcal{R}s∈R, 작은 노이즈 다항식 e∈Re \in \mathcal{R}e∈R 를 뽑는다.

▪

(b,a)(b,a)(b,a) 쌍을 만드는데, 이때 b=−a⋅s+e(modq)b = -a \cdot s + e (mod q)b=−a⋅s+e(modq) 이다.

◦

RLWE 문제: 이렇게 만들어진 (b, a) 쌍과 그냥 랜덤하게 뽑은 다항식 쌍 (b′,a′)(b^{'}, a^{'})(b′,a′) 을 구별하는 문제

“50대의 추교현이 20대의 추교현에게 감사할 수 있도록 하루하루 최선을 다해 살고 있습니다.”

The End.