준동형사상 (Homomorphism)

준동형사상(homomorphism)은 같은 종류의 두 대수 구조, 예를 들어 두 군·두 환·두 벡터 공간 사이에서 연산 구조를 보존하는 함수입니다. 군 G에서 H로의 준동형사상 f는 모든 a, b에 대해 f(a·b) = f(a)·f(b)를 만족합니다. 즉 '먼저 연산하고 옮기든, 먼저 옮기고 연산하든' 결과가 같습니다.

자세히 알아보기

준동형사상이 일대일 대응이면 동형사상(isomorphism)이라 하고, 두 구조는 본질적으로 같습니다. 자기 자신으로의 동형사상은 자기동형사상입니다. 준동형사상은 항등원을 항등원으로, 역원을 역원으로 보냅니다.

항등원으로 가는 원소들의 집합을 핵(kernel)이라 합니다. 핵이 항등원 하나뿐이면 f는 단사입니다. 제1 동형 정리에 따르면 G/ker f는 f의 상(image)과 동형입니다. 준동형사상은 여러 원소를 하나로 합칠 수 있으므로 정보를 잃을 수 있는데, 이 '정보를 잃되 구조는 유지하는' 성질이 암호학에서 유용하게 쓰입니다.

예: 정수의 덧셈군에서 Z/nZ로 가는 x ↦ x mod n, 실수 덧셈군에서 양의 실수 곱셈군으로 가는 x ↦ e^x(동형사상), 행렬의 행렬식 det(AB) = det(A)det(B).

블록체인·암호화폐에서는

• 공개 키 생성: 타원곡선 암호에서 k ↦ kG는 정수 덧셈군 Z/nZ에서 곡선 점 그룹으로 가는 준동형사상입니다. (a + b)G = aG + bG이므로, 비트코인의 HD 지갑(BIP-32)이 공개 키만으로 자식 공개 키를 만들 수 있고, 슈노르 다중 서명(MuSig2)이 공개 키들에 계수를 곱해 더함으로써 하나로 합칠 수 있습니다.
• 페더슨 커밋먼트(Pedersen commitment): C = vG + rH는 금액 v에 대해 덧셈 준동형이어서, 금액을 숨긴 채 '입력 합 = 출력 합'을 확인할 수 있습니다. 모네로의 RingCT와 기밀 거래(Confidential Transactions)가 이 원리를 씁니다.
• 페어링: BLS 서명과 KZG 커밋먼트(이더리움 EIP-4844 블롭)은 e(aP, bQ) = e(P, Q)^ab인 쌍선형 사상을 씁니다.
• 동형 암호: 암호문끼리 연산하면 평문끼리 연산한 결과의 암호문이 되는 암호로, 이름 그대로 준동형사상 성질을 이용합니다.

쉽게 말하면

준동형사상은 '번역해도 계산 규칙이 깨지지 않는 번역기'입니다. 번역 전에 더하든 번역 후에 더하든 같은 답이 나옵니다.

예시

f(x) = x mod 3이면 f(5 + 7) = f(12) = 0이고, f(5) + f(7) = 2 + 1 = 3 ≡ 0으로 같습니다.