동형사상 (Isomorphism)

동형사상(Isomorphism)은 같은 유형의 두 구조 사이의 매핑으로, 역매핑을 통해 되돌릴 수 있으면서 구조(연산이나 관계)를 그대로 보존하는 것입니다. 두 수학적 구조는 서로 동형사상이 존재할 경우 동형입니다. 군을 예로 들면, 군 (G, ∘)에서 (H, ∗)로 가는 사상 f가 일대일 대응(전단사)이고 모든 a, b에 대해 f(a ∘ b) = f(a) ∗ f(b)를 만족하면 f는 동형사상입니다. 동형인 두 구조는 원소의 이름과 표기만 다를 뿐, 대수적으로는 같은 구조로 취급합니다.

두 가지 조건

• 가역성: 매핑이 일대일 대응이어서 역매핑으로 원래 원소로 돌아갈 수 있어야 합니다.
• 구조 보존: 한 구조에서 두 원소를 연산한 결과는 다른 구조에서 대응하는 두 원소를 연산한 결과에 대응해야 합니다.

둘 중 하나만으로는 부족합니다. 모스 부호와 알파벳처럼 단순히 되돌릴 수 있는 대응(전단사)은 보존할 연산이 없으므로 동형사상의 예가 아닙니다.

대표적인 예

1. 덧셈과 곱셈: 실수의 덧셈군 (ℝ, +)와 양의 실수의 곱셈군 (ℝ_>0, ×)는 f(x) = e^x로 동형입니다. e^a+b = e^a · e^b이므로 덧셈이 곱셈으로 옮겨지고, 역매핑은 자연로그입니다.
2. 순환군: 위수가 n인 모든 순환군은 n으로 나눈 나머지의 덧셈군 (ℤ_n, +)와 동형입니다. 생성원 g를 가진 순환군에서 k ↦ g^k가 동형사상이 됩니다.
3. 그래프 동형: 두 그래프의 꼭짓점을 일대일로 대응시켰을 때 연결 관계가 그대로 유지되면 두 그래프는 동형입니다. 화학에서는 분자 구조를 그래프로 나타내, 두 분자의 구조가 같은지 판정하는 문제를 그래프 동형 문제로 다룹니다.

준동형사상과의 차이

구조는 보존하지만 일대일 대응이 아닐 수도 있는 사상을 준동형사상(homomorphism)이라고 합니다. 동형사상은 역매핑도 준동형사상인 특별한 준동형사상입니다. 이름이 비슷한 동형 암호(homomorphic encryption)는 ‘준동형’ 성질, 즉 암호문끼리 연산한 결과가 평문끼리 연산한 결과의 암호문이 되는 성질을 이용하는 것으로, 동형사상과는 다른 개념입니다.

암호학에서의 의미

• 이산 로그 문제: 위수가 소수 q인 순환군 G = ⟨g⟩는 (ℤ_q, +)와 동형이며, k ↦ g^k는 쉽게 계산됩니다. 그러나 역방향, 즉 g^k에서 k를 구하는 이산 로그는 G를 어떻게 표현하느냐에 따라 계산 난이도가 크게 다릅니다. 추상적으로 동형인 군이라도 ℤ_q에서는 이산 로그가 쉬운 반면, 잘 고른 타원곡선 군에서는 매우 어렵습니다. 암호의 안전성은 구조 자체가 아니라 동형사상을 효율적으로 계산할 수 있는지에 달려 있습니다.
• 공격으로의 활용: 어떤 암호 구조를 계산하기 쉬운 다른 구조로 옮기는 동형사상을 효율적으로 찾을 수 있다면, 한쪽에서 알려진 공격을 다른 쪽에 적용할 수 있습니다. 일부 약한 타원곡선이 더 쉬운 군으로의 사상 때문에 안전하지 않은 것으로 밝혀진 것이 그 예입니다.
• 영지식 증명: 두 그래프가 동형이라는 사실을, 대응 자체를 공개하지 않고 증명하는 프로토콜은 영지식 증명을 설명하는 고전적인 예입니다.