Modification to Fully Homomorphic Modified Rivest Scheme

Each language version is independently generated for its own context, not a direct translation.

1. 배경: 투명 유리 상자와 마법 같은 계산

상상해 보세요. 여러분은 **비밀 번호 (평문)**를 넣을 수 있는 **투명 유리 상자 (암호문)**를 가지고 있습니다.

기존 방식 (FHMRS): 이 상자는 마법처럼, 안의 비밀 번호를 꺼내지 않고도 상자 밖에서 더하기나 곱하기 연산을 할 수 있게 해줍니다. 예를 들어, "비밀 번호 5"와 "비밀 번호 3"을 넣은 두 상자가 있다면, 상자 밖에서 두 상자를 합치면 "8"이라는 결과가 나오는 상자가 만들어집니다.
문제점: 이 방식은 계산이 끝난 후, 상자만 열어주면 원래 숫자를 알 수 있습니다. 하지만 이 방식에는 치명적인 구멍이 있었습니다.

2. 발견된 치명적 구멍: "유리 상자"가 너무 커서 안이 다 보이는 상황

논문 2 절에서는 기존 방식의 치명적인 약점을 지적합니다.

상황: 암호화할 때, 비밀 번호에 무작위 숫자 (가상인 '유리 조각') 를 섞어서 넣습니다. 그런데 계산할 수 있는 횟수 (곱셈) 가 많을수록, 이 '유리 조각'이 너무 커져버립니다.
결과: 상자가 너무 커져서, 유리 조각이 상자의 벽 (모듈로 연산) 을 뚫고 나가지 못해 안이 그대로 비치는 상황이 발생합니다.
도둑의 공격 (KPA): 도둑이 "비밀 번호가 5 였고, 암호문은 100 이었다"는 사실을 알면, 100 에서 5 를 빼면 95가 나옵니다. 이 95 는 사실 '비밀 키 (u)'의 배수입니다. 도둑이 여러 개의 이런 데이터를 모으면, **최대공약수 (GCD)**를 구하는 간단한 수학으로 비밀 키 (u) 를 바로 찾아낼 수 있습니다.
비유: 마치 "비밀 번호 5 를 넣었는데, 상자가 너무 커서 '5 + (비밀 키 × 무작위 수)'가 그대로 적혀 있는 것처럼 보이는 상황"입니다. 도둑은 이걸로 열쇠를 쉽게 찾아냅니다.

3. 해결책: 작은 상자로 나누어 담기 (mFHMRS)

저자들은 이 구멍을 막기 위해 **수정된 방식 (mFHMRS)**을 제안합니다. 핵심은 **"상자를 여러 개로 쪼개고, 크기를 조절하는 것"**입니다.

① 상자를 여러 개로 쪼개기 (다중 소수 사용)

기존: 큰 상자 하나 (두 개의 큰 소수 p, q) 만 썼습니다.
수정 후: **N+S 개의 작은 상자 (소수 p1, p2, ...)**를 사용합니다.
비유: 한 번에 큰 상자에 모든 걸 넣지 않고, 비밀 번호를 여러 개의 작은 상자에 나누어 담습니다. 각 상자는 서로 다른 자물쇠 (소수) 로 잠겨 있습니다.

② 유리 조각의 크기 조절 (랜덤 수 크기 조절)

핵심: 도둑이 안을 훔쳐볼 수 없도록, '유리 조각 (랜덤 수)'의 크기를 상자의 벽보다 작게 유지합니다.
원리: 계산이 아무리 복잡해지더라도, 안의 숫자가 상자의 벽을 뚫고 밖으로 튀어나오지 않도록 상자 (소수) 의 크기를 계산 결과보다 충분히 크게 설정합니다.
효과: 도둑이 "100 - 5 = 95"를 구하려 해도, 95 는 더 이상 '비밀 키의 배수'가 아니라 상자 벽에 부딪혀 찌그러진 (나머지 연산된) 숫자가 됩니다. 그래서 최대공약수를 구해도 비밀 키가 나오지 않습니다.

4. 새로운 방식의 작동 원리 (일상적인 비유)

1. 암호화 (Encryption): "비밀 편지 나누기"

비밀 편지 (메시지) 에 무작위 잉크 (랜덤 수) 를 섞습니다.
이 혼합물을 **N+S 개의 작은 유리 병 (소수 p1~pN+S)**에 나누어 담습니다.
각 병은 서로 다른 자물쇠로 잠깁니다. 병 하나만으로는 내용을 알 수 없습니다.

2. 계산 (Homomorphic Operations): "병 밖에서 흔들어 섞기"

도둑은 병을 열지 않고도, 병을 서로 부딪히게 하거나 (곱셈), 같은 병에 다른 물건을 넣는 (덧셈) 연산을 할 수 있습니다.
이때 병 안의 내용물이 섞이기는 하지만, 병의 벽 (모듈로 연산) 이 너무 두꺼워서 내용물이 밖으로 새어 나오지 않습니다.

3. 복호화 (Decryption): "병을 합쳐서 원래 모습 찾기"

정당한 주인은 모든 병 (p1~pN+S) 의 열쇠를 가지고 있습니다.
모든 병을 합치면 (중국인의 나머지 정리, CRT), 원래 섞여 있던 '비밀 편지 + 무작위 잉크'가 완벽하게 재구성됩니다.
마지막에 '무작위 잉크'만 걸러내면 (u 로 나눗셈), 원래의 비밀 편지가 나옵니다.

5. 왜 이 방식이 안전한가? (도둑의 시나리오)

시나리오 1 (직접 뚫기): 도둑이 병 하나만 가지고 있어도, 병이 너무 작고 자물쇠가 복잡해서 내용을 알 수 없습니다.
시나리오 2 (수학으로 풀기): 도둑이 "비밀 번호 5 였고, 병 내용물이 100 이었다"고 알아내도, 100 은 병 벽에 부딪혀 찌그러진 숫자입니다. 그래서 100-5 를 해도 의미 있는 숫자가 나오지 않습니다.
시나리오 3 (격자 공격): 도둑이 병들의 모양을 분석해서 자물쇠를 추측하려 하지만, 저자들은 병의 크기와 무작위 잉크의 크기를 아주 정교하게 설계했습니다. 수학적으로 "너무 짧아서 찾을 수 없는 길"을 만들었기 때문에, 슈퍼컴퓨터를 써도 자물쇠를 뚫을 수 없습니다.

6. 결론: "작은 상자들이 모여 만든 안전한 금고"

이 논문은 **"큰 상자 하나만 믿으면 도둑이 쉽게 뚫는다"**는 사실을 발견하고, **"작은 상자 여러 개를 조합하고 크기를 조절하면 도둑이 아무리 노력해도 뚫을 수 없다"**는 새로운 암호 방식을 제안했습니다.

핵심 메시지: 암호화 기술은 단순히 '잠금장치'를 만드는 것이 아니라, 계산이 일어나는 동안 데이터가 '새어 나오지 않도록' 크기와 구조를 정교하게 설계하는 예술입니다.
실제 효과: 이 방식을 사용하면 클라우드 서버에 비밀 데이터를 올려놓고, 서버가 데이터를 해독하지 않은 채로 분석 (계산) 을 할 수 있게 됩니다. 즉, 내 비밀은 내 것만 알고, 남들은 계산 결과만 볼 수 있는 완벽한 보안이 가능해진 것입니다.

이처럼 mFHMRS는 기존 방식의 구멍을 막고, 수학적으로 더 튼튼한 '다중 소수'와 '크기 조절'이라는 전략으로 암호화의 안전성을 한 단계 업그레이드한 기술입니다.

Each language version is independently generated for its own context, not a direct translation.

논문 요약: 완전 동형 암호화 Rivest 변형 scheme 의 수정 및 보안 강화

1. 문제 제기 (Problem)

이 논문은 기존에 제안된 대칭키 기반의 완전 동형 암호화 Rivest 변형 scheme (FHMRS) 에서 발견된 심각한 보안 취약점을 해결하는 것을 목표로 합니다.

기존 FHMRS 의 구조: FHMRS 는 중국 나머지 정리 (CRT) 를 활용하여 메시지를 $p$ 와 $q$ 라는 두 개의 소수로 나눈 나머지 (shares) 로 암호화합니다. 암호문은 $(m_i + g_i \cdot u) \pmod p$ 와 $(m_i + g_i \cdot u) \pmod q$ 형태로 구성됩니다. 여기서 $u$ 는 비밀 소수이며, $g_i$ 는 난수입니다.
취약점 (Known-Plaintext Attack, KPA): FHMRS 가 곱셈 동형성을 지원할 때, $p$ $p$ 와 $q$ $q$ 의 크기가 암호화 과정에서의 오버플로우를 방지하기 위해 충분히 크지 않으면, 암호화 연산 중 모듈로 연산이 실제로 수행되지 않는 경우가 발생합니다.
- 공격자가 평문 $m$ 과 이에 대응하는 암호문 $c$ 를 알고 있다면, $c - m = g \cdot u$ 를 얻을 수 있습니다.
- 두 개의 평문 - 암호문 쌍 $(m_1, c_1)$ 과 $(m_2, c_2)$ 를 확보하면, $(c_1 - m_1)$ 과 $(c_2 - m_2)$ 의 최대공약수 (GCD) 를 계산하여 비밀 소수 $u$ 를 쉽게 추출할 수 있습니다.
- $u$ 가 노출되면 전체 시스템의 보안이 붕괴됩니다.

2. 방법론 (Methodology)

저자들은 FHMRS 의 보안 취약점을 해결하기 위해 수정된 FHMRS (mFHMRS) 를 제안합니다. 핵심적인 수정 사항은 다음과 같습니다.

다중 소수 (Multi-prime) 방식 도입:
- 기존 FHMRS 는 2 개의 소수 ( $p, q$ ) 를 사용했으나, mFHMRS 는 $N+S$ 개의 소수 ( $p_1, p_2, \dots, p_{N+S}$ ) 를 사용합니다. 여기서 $N$ 은 지원하는 연속 곱셈 횟수, $S$ 는 보안 강화를 위해 추가된 소수의 개수입니다.
- 암호문은 $N+S$ 개의 shares 로 구성되며, 각 share 는 서로 다른 소수 $p_i$ 에 대해 모듈로 연산을 수행합니다.
매개변수 크기 최적화:
- 비밀 소수 $p_i$ 의 크기: $p_i$ 의 비트 길이를 암호문 share 의 값 범위보다 충분히 크게 설정하여, 모듈로 연산이 실제로 수행되도록 보장합니다. 이는 $c_i - m_i = g_i \cdot u - k_i \cdot p_i$ 형태가 되도록 하여 $u$ 를 직접 추출하는 것을 방지합니다.
- 비밀 소수 $u$ 와 $p_i$ 의 관계: $u > p_i$ 가 되도록 설정하여, $g_i$ 의 차이로 인한 $k_i$ (몫) 의 변화를 예측 불가능하게 만듭니다.
- 난수 $g_i$ 의 크기: $g_i$ 의 비트 길이를 충분히 크게 ( $lg \ge \lambda/4$ ) 설정하여 선형 방정식 풀이 공격을 무력화합니다.
복호화 과정:
- 암호문 $c_i = (c_{i1}, \dots, c_{i(N+S)})$ 를 입력받아 CRT 를 사용하여 $m_i + g_i \cdot u$ 를 재구성한 후, 최종적으로 $u$ 로 모듈로 연산을 수행하여 원래 메시지 $m_i$ 를 복원합니다.

3. 주요 기여 (Key Contributions)

KPA 취약점 해결: 기존 FHMRS 의 GCD 기반 평문 - 암호문 공격 (KPA) 을 성공적으로 차단하는 새로운 암호화 구조를 설계했습니다.
보안 분석 및 증명: 제안된 mFHMRS 에 대한 다양한 공격 시나리오에 대한 체계적인 보안 분석을 수행했습니다.
- Brute-force Attack: 키 공간의 크기를 분석하여 무차별 대입 공격이 비현실적임을 보였습니다.
- Lattice-based Attack: LLL 알고리즘을 이용한 격자 기반 공격에 대해, 오차 항 (error term) 의 크기와 격자 기저의 길이를 분석하여 공격이 실패함을 증명했습니다.
- 선형 방정식 풀이 공격: 여러 평문 - 암호문 쌍을 이용한 선형 방정식 시스템을 통해 비밀키를 추출하려는 공격에 대해, 난수 $g_i$ 와 몫 $k_i$ 의 불확실성으로 인해 공격이 불가능함을 보였습니다.
정확성 보장 조건 도출: $N$ 번의 곱셈과 $A$ 번의 덧셈을 지원하기 위해 필요한 소수 $p_i$ 와 $u$ 의 최소 비트 길이에 대한 수학적 조건을 제시했습니다.

4. 결과 (Results)

보안성: mFHMRS 는 알려진 KPA, 격자 기반 공격 (Lattice-based), 선형 방정식 공격 등에 대해 저항성을 가집니다. 특히 $p_i$ 와 $u$ 의 비트 길이를 적절히 설정함으로써 (예: $\lambda=128$ 일 때 $p_i \approx 128$ 비트, $u \approx 130$ 비트), 공격자가 비밀키를 추론하는 것을 방지합니다.
성능 및 크기:
- 단일 곱셈 ( $N=1$ ) 을 지원하는 경우, 3 개의 128 비트 소수를 사용하여 암호문 크기를 최대 384 비트로 유지합니다.
- 14 번의 곱셈 ( $N=14$ ) 을 지원하는 경우, 6 개의 180 비트 소수를 사용하여 암호문 크기는 약 3420 비트가 됩니다. 이는 동형 암호화 연산의 복잡도 증가에 비례하여 확장 가능한 구조임을 보여줍니다.
Correctness: 제안된 매개변수 조건 하에서 CRT 기반 재구성과 $u$ 에 의한 모듈로 연산이 항상 올바른 평문을 복원함을 수학적으로 증명했습니다.

5. 의의 (Significance)

이 연구는 Rivest 의 초기 아이디어를 기반으로 한 완전 동형 암호화 scheme 의 실용성을 높이는 중요한 단계입니다.

실용적 보안 강화: 기존 scheme 의 치명적인 설계 결함을 수정하여, 실제 클라우드 환경이나 보안이 필요한 데이터 처리에서 FHMRS 를 안전하게 사용할 수 있는 기반을 마련했습니다.
효율성과 보안의 균형: 과도하게 큰 키 크기를 요구하지 않으면서도, 다중 소수 구조와 매개변수 최적화를 통해 강력한 보안을 제공합니다.
동형 암호화 연구의 발전: 동형 암호화 시스템에서 평문 - 암호문 쌍 공격 (KPA) 에 대한 취약점 분석과 이를 해결하기 위한 체계적인 방법론을 제시함으로써, 향후 유사한 구조의 암호 시스템 설계에 중요한 참고 자료가 됩니다.

결론적으로, 이 논문은 Rivest 기반 동형 암호화 scheme 의 보안 취약점을 다중 소수 구조와 엄격한 매개변수 제어를 통해 해결함으로써, 안전하고 효율적인 완전 동형 암호화 시스템 구현을 가능하게 했습니다.