2025년 4월, SK텔레콤의 가입자정보관리핵심서버(HSS)가 해킹당해 약 2,480만 회선의 유심 정보가 유출되는 초유의 사태가 벌어졌습니다.
핵심 인증 정보가 외부로 유출된 만큼, SKT 고객이라면 즉시 보안 조치를 해야 합니다.

이 글에서는 가장 효과적인 5단계 대응 방법을 간단명료하게 정리합니다.

1. 유심(USIM) 무상 교체하기

가장 먼저 해야 할 일은 유심을 새 것으로 교체하는 것입니다.
SK텔레콤은 4월 28일부터 전국 T월드 매장과 공항 로밍센터에서 무료 유심 교체를 시작합니다.

왜 유심을 바꿔야 하나요?

이번 해킹으로 유심 관련 정보(IMSI, IMEI 등)가 유출된 것이 확인되었습니다. 또한, 일부 보도에서는 통신망 인증에 사용되는 핵심 비밀키(Ki) 유출 가능성도 제기되고 있습니다.
SK텔레콤은 Ki 유출 여부에 대해 공식적으로 확인하지 않았지만, 만일 Ki가 유출되었다면 복제폰 제작이나 심 스와핑(SIM swapping) 같은 피해로 이어질 위험이 있습니다. 따라서 안전을 위해 유심을 새 것으로 교체하는 것이 권장됩니다.

교체 방법

• 가까운 T월드 매장 방문 (신분증 지참)
• 공항 로밍센터 방문 (해외여행 예정자)

빠를수록 좋습니다.
특히 금융 서비스 이용이나 본인 인증을 자주 사용하는 분들은 가급적 서둘러 유심을 교체하는 것이 좋습니다.

2. 유심보호서비스 가입하기

유심을 교체했다면, 두 번째로 할 일은 유심보호서비스 가입입니다.
현재 SKT는 이 서비스를 무료로 제공하고 있습니다.

유심보호서비스 주요 기능

• 무단 기기변경 차단
• 무단 로밍 설정 변경 차단
• 부정 개통·변경 시 실시간 탐지

가입 방법

• T월드 앱 접속
• SKT 홈페이지 가입
• 고객센터 전화 신청 (114)

다만, 로밍을 자주 사용하는 경우 일부 제한이 있을 수 있으니 참고하세요.

3. 심(SIM) PIN 설정하기

추가적인 보안을 위해 유심에 비밀번호(PIN)를 설정해두는 것도 강력 추천합니다.

SIM PIN이란?

• 스마트폰을 껐다 켤 때마다 심 카드에 비밀번호를 입력해야 작동하는 기능입니다.
• 유심 탈취나 복제폰 공격을 차단하는 효과적인 수단입니다.

설정 방법 예시

• 안드로이드: 설정 → 보안 → SIM 카드 잠금 → PIN 설정
• 아이폰: 설정 → 셀룰러 → SIM PIN → PIN 활성화

※ PIN 코드를 꼭 기억해두세요. 잊으면 유심 재발급이 필요합니다.

4. 금융 및 본인인증 보안 강화하기

이번 사고는 통신사 인증을 기반으로 한 금융 서비스까지 영향을 줄 수 있습니다.
따라서 다음 조치도 병행해야 합니다.

필수 보안 강화 조치

• 금융앱, 포털앱 비밀번호 모두 변경
• 2단계 인증(2FA) 설정 (가능한 모든 서비스)
• 본인명의로 등록된 서비스 목록 점검

특히 은행, 증권사, 간편결제앱은 가장 먼저 확인하는 것이 좋습니다.

5. 이상 징후 감시하기

모든 조치를 완료했더라도, 지속적인 모니터링이 중요합니다.

이런 증상이 보이면 즉시 신고

• 휴대폰 통화 품질 이상(끊김, 먹통)
• 갑작스런 로밍 설정 알림
• 모르는 나라에서 로그인 시도 감지
• 본인 모르게 개통·기기변경

신고 방법

• SKT 고객센터: ☎️ 080-800-0577 (무료)

조금이라도 이상하다 싶으면 망설이지 말고 바로 문의하세요.

결론

이번 SKT HSS 해킹 사건은 유심 정보가 직접 유출된 만큼, 단순한 개인정보 유출 사고보다 훨씬 심각합니다.
빠른 대응만이 피해를 막을 수 있습니다.

정리

• 유심 교체
• 유심보호서비스 가입
• 심 PIN 설정
• 금융 보안 강화
• 이상 징후 감시

꼼꼼하고 빠른 대응으로 많은 분들이 피해 없으시길 바랍니다~!!

⸻

2025년 4월 19일, SK텔레콤(SKT)의 가입자정보관리핵심서버(HSS) 일부에서 악성코드 감염 정황이 발견되어, 최대 2,480만 회선의 유심(USIM) 정보가 유출됐을 가능성이 제기되었습니다.
이는 국내 최대 통신사의 핵심 시스템이 위협받은 사건으로, 소비자 불안과 산업 전반의 보안 경각심을 높이고 있습니다.
이 글에서는 현재까지 알려진 사실, 가능한 침투 경로, SKT의 대응, 그리고 우리가 얻을 교훈을 정리합니다.

⸻

1. 사건 개요: 무슨 일이 일어났나?

사건 발생

• 일시: 2025년 4월 19일 오후 11시 40분경, SKT HSS 서버에서 정교한 악성코드 감염이 탐지됨.
• 대상: HSS는 통신망에서 가입자 인증과 식별을 담당하는 핵심 시스템. 유심 관련 데이터(IMSI, IMEI, 인증키 등)를 저장.
• 유출 가능 정보 (SKT 발표 기준):
  • IMSI: 국제모바일가입자식별번호
  • IMEI: 단말기 고유식별번호
  • 인증키(Ki): 유심과 네트워크 간 암호화 통신용 비밀키
• SKT 주장: 이름, 주민등록번호, 주소 등 개인정보는 유출되지 않은 것으로 파악.
• 영향 규모 (잠정):
  •  SKT 가입자 약 2,310만 명
  • SKT 망 알뜰폰 가입자 약 187만 명
  • 총 약 2,480만 회선 (최종 조사 결과에 따라 변동 가능성 있음)

초기 대응

• 4월 19일: 악성코드 발견 후 즉시 삭제 및 의심 장비 격리 조치
• 4월 20일: 한국인터넷진흥원(KISA)에 신고
• 4월 22일: 개인정보보호위원회(PIPC)에 신고 및 홈페이지 공지
  
  

피해 현황

• 현재(4월 26일)까지 심 스와핑, 보이스피싱 등의 직접 악용 사례는 공식적으로 보고되지 않음.
• 다만, 유출 가능 정보 특성상 복제폰 제작, 금융사기 등에 악용될 위험이 존재.
• 소비자 불편: 초기 유심 교체 비용(7,700원) 발생 → 이후 무상 교체 발표.
• 유심보호서비스 가입자 급증 (4월 24일 기준 161만 명 가입).

⸻

2. 침투 경로: 어떻게 뚫렸나? (현재 조사 중)

HSS는 외부 인터넷과 직접 연결되지 않은 내부망 시스템입니다. 하지만 복잡한 통신사 IT 환경(클라우드, API, 제3자 연동 등)으로 인해 다양한 침투 가능성이 존재합니다. 정확한 침투 경로는 현재 관계기관(과기정통부, 경찰 등) 조사 중입니다.
가능성이 제기된 주요 가설은 다음과 같습니다:

2.1 공급망 공격 가능성 (Supply Chain Attack)

• 설명: 장비 또는 소프트웨어 공급업체(예: 노키아, 에릭슨) 관련 취약점을 악용했을 가능성.
• 가설 과정:
  1. 해커가 벤더의 업데이트 서버를 해킹해 악성코드를 심음
  2. SKT가 정상 업데이트로 착각하고 설치
  3. 악성코드가 내부 시스템 침투 후 데이터 유출 시도
• 참고: 과거 중국 APT 그룹 ‘위버 앤트(Weaver Ant)’가 유사 공격 이력 있음(시그니아 보고서 기준).
  
  

2.2 제로데이 취약점 가능성 (Zero-Day Exploit)

• 설명: HSS 시스템(리눅스, 전용 소프트웨어 등) 내 알려지지 않은 취약점이 악용됐을 가능성.
• 가설 과정:
  1. 제로데이 취약점 발견 및 원격코드실행(RCE)
  2. 악성코드 삽입 및 데이터 탈취 시도
• SKT 발표에서는 “정교한 악성코드”가 사용됐다고 설명, 제로데이 가능성을 뒷받침.
• [주의]
  • 공급망 공격/제로데이 등은 공식 확인이 아니라 가능성입니다.
  • 수사 결과에 따라 경로가 달라질 수 있습니다.

⸻

3. SKT 보안 취약점 분석 (현재까지 드러난 문제)

기술적 취약점

• 패치 지연 가능성
• 일부 데이터 암호화(AES-256 등) 적용 미흡 가능성
• 침입 탐지 시스템(IDS) 고도화 부족
  
  

운영적 문제

• 보안 예산 감소 (2023년 대비 2024년 감소 추정)
• 벤더 및 협력사 관리 강화 필요성
• 직원 대상 보안 교육(특히 피싱 대응) 강화 필요성
  
  

산업적 배경

• 2024년 통신사 대상 사이버 공격 급증 (체크포인트 보고서 기준 47% 증가)
• 클라우드, API 노출 증가로 외부 공격면이 넓어짐

⸻

4. SKT 대응: 평가

초기 대응 (4월 19일~22일)

• 장비 격리, 악성코드 삭제 등 기술적 조치는 신속.
• 그러나 초기 대고객 소통은 미흡(문자 알림 없이 홈페이지 공지 위주).
  
  

후속 조치 (4월 23일~26일)

• 유심보호서비스 무료 제공 (기기변경·로밍 제한 기능)
• 4월 25일: 유심 무상 교체 정책 발표 (4월 28일부터 시행 예정)
• 4월 25일: 유영상 대표 공식 사과 발표
• FDS(비정상 인증 차단 시스템) 강화 계획 발표

평가

• 무상 교체 및 사과는 신뢰 회복 노력으로 긍정적.
• 다만, 유심보호서비스 사용상 일부 불편, 초기 소통 부족에 대한 비판 존재.

⸻

5. 사회적·산업적 파장

소비자 영향

• 심 스와핑, 금융사기 우려 확산
• 유심 교체 및 통신사 보안서비스 가입 문의 폭주
• 일부 시민단체(예: 참여연대) 집단소송 추진 논의 중
  
  

산업 영향

• KT, LGU+ 등 다른 통신사도 HSS 점검 강화 착수
• 클라우드 보안 및 MSSP(보안관제) 투자 확대 전망
  
  

정부 대응

• 과기정통부, 개인정보보호위원회, 경찰 수사 진행 중 (수개월 소요 예상)
• 개인정보보호법상 과징금 가능성

⸻

6. 교훈과 향후 과제

SKT

• AI 기반 침입탐지 고도화
• 공급망 및 협력사 보안 감사 강화
• 고객 소통 투명성 제고

정부

• 민관 공동 APT 대응 훈련 필요성
• 개인정보보호법 등 규제 강화 검토
  
  

소비자

• 유심보호서비스 가입 및 PIN 설정 권장
• 통신 비정상 사용 모니터링 및 고객센터 신고(080-800-0577)
• 비밀번호 재설정 등 추가 보안 강화

⸻

7. 결론

SKT HSS 해킹 사태는 공급망 공격, 제로데이 취약점 등 복합적 원인이 결합된 고도화된 사이버 공격 가능성이 있습니다.
SKT는 초기 대응과 소통에서 아쉬움을 남겼지만, 유심 무상 교체와 사과를 통해 신뢰 회복을 시도하고 있습니다.
이번 사건은 통신 인프라 보안의 중요성을 다시금 일깨우는 계기가 되었습니다.
조만간 발표될 수사 결과를 통해 정확한 원인과 책임 소재가 규명되기를 기대합니다.

⸻

서론

양자역학 시리즈의 두 번째 논의에서는 양자 얽힘(Quantum Entanglement)에 초점을 맞춥니다. 첫 번째 글에서는 큐비트의 중첩과 얽힘 특성을 통해 양자컴퓨팅의 기초를 탐구하였습니다. 이번에는 얽힘의 이론적 본질, 실험적 구현, 그리고 양자컴퓨팅 및 기타 응용에서의 중추적 역할을 심층적으로 분석합니다. 양자 얽힘은 전자와 광자를 포함한 입자 간의 비고전적 상관관계를 가능하게 하며, 이는 양자정보 과학의 핵심 동력입니다. 본 글에서는 얽힘의 수학적 표현, 생성 메커니즘, 그리고 그 잠재력을 구체적으로 다루며, 독자들에게 이 현상의 심오한 의미를 전달하고자 합니다.

1. 양자 얽힘의 이론적 기초

1.1 얽힘의 수학적 정의

양자 얽힘은 두 개 이상의 입자가 단일 양자 상태로 기술되어, 한 입자의 측정이 다른 입자의 상태를 즉시 결정짓는 현상입니다. 두 큐비트 시스템을 예로 들면, 얽힌 상태는 다음과 같은 벨 상태(Bell State)로 표현됩니다:

\[ |\Phi^+\rangle = \frac{1}{\sqrt{2}} (|00\rangle + |11\rangle) \]

이 상태에서는 첫 번째 큐비트를 측정하여 \( |0\rangle \)을 얻으면 두 번째 큐비트가 즉시 \( |0\rangle \)이 되며, \( |1\rangle \)을 얻으면 \( |1\rangle \)이 됩니다. 이 상태는 개별 큐비트로 분리하여 기술할 수 없으며, 전체 시스템의 힐베르트 공간에서 단일 벡터로 표현됩니다.

또 다른 벨 상태는 다음과 같습니다:

\[ |\Psi^-\rangle = \frac{1}{\sqrt{2}} (|01\rangle - |10\rangle) \]

여기서는 첫 번째 큐비트가 \( |0\rangle \)이면 두 번째가 \( |1\rangle \), 반대도 마찬가지입니다. 이러한 상관관계는 고전적 확률로는 설명할 수 없는 비국소성(non-locality)을 드러냅니다.

1.2 비국소성과 벨 부등식

얽힘의 비고전적 특성은 1935년 아인슈타인, 포돌스키, 로젠(EPR)의 논문에서 처음 논의되었습니다. EPR은 얽힘이 양자역학의 불완전성을 드러낸다고 주장하였으나, 1964년 존 벨(John Bell)은 벨 부등식을 제안하여 고전적 상관관계와 양자적 상관관계를 구분하였습니다. 벨 부등식은 고전적 이론(국소적 실재론)이 예측하는 상관관계의 한계를 정의하며, 양자 얽힘은 이를 위반합니다.

예를 들어, 얽힌 두 입자의 스핀을 서로 다른 축에서 측정할 때는 양자역학이 고전적 이론보다 강한 상관관계를 예측합니다. 1982년 알랭 아스페(Alain Aspect)의 실험은 얽힌 광자 쌍의 편광 측정을 통해 벨 부등식 위반을 확인하였으며, 양자 얽힘의 비국소성을 입증하였습니다. 이 실험은 얽힘이 단순한 확률적 상관관계가 아님을 보여줍니다.

1.3 얽힘의 정량화

얽힘의 정도는 엔트로피 기반 척도나 얽힘 증인(entanglement witness)을 통해 정량화됩니다. 두 큐비트 시스템의 얽힘 엔트로피는 부분 시스템의 폰 노이만 엔트로피로 정의됩니다:

\[ S(\rho_A) = -\text{Tr}(\rho_A \log_2 \rho_A) \]

여기서 \( \rho_A \)는 전체 상태 \( \rho \)에서 두 번째 큐비트를 추적(trace out)한 축소 밀도 행렬입니다. 최대 얽힘 상태(예: 벨 상태)에서는 \( S(\rho_A) = 1 \) 비트로, 완전한 얽힘을 나타냅니다.

2. 전자와 광자를 통한 얽힘 구현

양자 얽힘은 다양한 물리적 시스템에서 구현되며, 전자와 광자는 그 대표적 매개체입니다. 이들은 양자컴퓨팅과 실험에서 중요한 역할을 합니다.

2.1 전자와 얽힘

전자는 스핀을 통해 얽힘을 구현합니다. 두 전자의 스핀 singlet 상태는 다음과 같습니다:

\[ |\psi\rangle = \frac{1}{\sqrt{2}} (|\uparrow\downarrow\rangle - |\downarrow\uparrow\rangle) \]

이 상태는 총 스핀이 0인 반대 방향 스핀 쌍을 나타냅니다. 초전도 큐비트에서는 전류의 양자 상태(시계/반시계 방향)가 큐비트로 사용되며, 마이크로파 펄스를 통해 두 큐비트 간 상호작용을 유도하여 얽힘을 생성합니다. 대화에서 언급된 초저온(10mK) 환경은 데코히런스를 최소화하여 얽힘을 유지합니다.

또한, 전자는 양전자와 쌍 소멸(annihilation)하여 얽힌 광자 쌍을 생성합니다. 이 과정은 의료 영상(PET 스캔)에서 감마선 쌍으로 관찰되며, 얽힘의 실험적 응용을 보여줍니다.

2.2 광자와 얽힘

광자는 편광이나 위상을 통해 얽힘을 구현합니다. 자발적 파라메트릭 하향 변환(SPDC)은 비선형 결정에 레이저를 쏘아 하나의 광자를 두 개의 얽힌 광자로 분할하는 과정입니다:

\[ |\psi\rangle = \frac{1}{\sqrt{2}} (|HH\rangle + |VV\rangle) \]

여기서 \( |H\rangle \)와 \( |V\rangle \)는 수평 및 수직 편광입니다. SPDC는 벨 부등식 실험과 양자 암호학에서 널리 사용됩니다. 대화에서 언급된 바와 같이, 광자는 원자의 에너지 준위 전이(예: 들뜬 상태에서 기저 상태로의 전이)나 쌍 소멸로 생성되며, 이 과정에서 얽힌 상태로 나옵니다.

3. 양자컴퓨팅에서 얽힘의 역할

양자컴퓨팅에서 얽힘은 큐비트 간 강한 상관관계를 형성하여 연산 효율성을 극대화합니다. 대화에서 다룬 쇼어 알고리즘과 그로버 알고리즘을 통해 이를 구체적으로 살펴봅니다.

3.1 쇼어 알고리즘에서의 얽힘

쇼어 알고리즘은 큰 수의 소인수분해를 다항식 시간 내에 해결합니다. 대화에서 다룬 예시(N=15, a=2)에서, 오라클은 함수 \( f(x) = 2^x \mod 15 \)를 계산하며 입력 큐비트(x)와 출력 큐비트(f(x))를 얽히게 합니다:

\[ |\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle |f(x)\rangle \]

이 상태는 주기 \( r=4 \)를 반영하며, 입력과 출력이 얽혀 주기적 패턴을 형성합니다. 양자 푸리에 변환(QFT)은 이 얽힘 상태에서 주기를 추출하여 소인수(3, 5)를 도출합니다. 얽힘은 모든 입력을 병렬로 계산하고 주기성을 상태에 담는 데 필수적입니다.

3.2 그로버 알고리즘에서의 얽힘

그로버 알고리즘은 비정렬 데이터 검색에서 \( \sqrt{N} \)의 속도로 정답을 찾습니다. 오라클은 정답 상태를 표시하고, 확산 연산은 얽힌 큐비트 간 상호작용을 통해 정답의 확률을 증폭합니다. 대화에서 언급된 바와 같이, 얽힘은 큐비트들이 "팀워크"로 작동하게 하여 효율적 탐색을 가능케 합니다.

3.3 얽힘의 연산적 이점

얽힘은 다음과 같은 방식으로 양자컴퓨팅을 강화합니다:

• 병렬성 강화: 얽힌 큐비트는 중첩 상태에서 상호 연결되어, 불필요한 계산 경로를 효율적으로 배제합니다.
• 상관관계 활용: 얽힘은 큐비트 간 복잡한 관계를 단일 상태로 표현하며, 알고리즘의 정보 처리 능력을 높입니다.
• 오류 정정: 얽힌 상태는 양자 오류 정정 코드(예: 표면 코드)에서 다중 큐비트 상관관계를 활용해 오류를 탐지합니다.

4. 얽힘의 실험적 구현과 도전 과제

얽힘을 실험적으로 구현하는 것은 양자 기술의 핵심 과제입니다. 대표적 방법은 다음과 같습니다:

• 광자 기반: SPDC를 통해 얽힌 광자 쌍을 생성합니다. 편광 측정 장치로 얽힘을 확인합니다.
• 초전도 큐비트: 조셉슨 접합에서 마이크로파 펄스로 얽힘을 생성합니다. IBM의 127-큐비트 Eagle 프로세서가 대표적입니다.
• 트랩된 이온: 레이저로 이온의 스핀을 조작하여 얽힘을 구현합니다. IonQ의 시스템은 높은 충실도(fidelity)를 자랑합니다.

그러나 얽힘은 데코히런스로 인해 쉽게 붕괴됩니다. 환경 노이즈(열, 전자기파 등)는 얽힌 상태를 분리된 상태로 전환하며, 이를 방지하려면 초저온 환경(10mK)이나 진공 챔버가 필요합니다. 현재 NISQ(Noisy Intermediate-Scale Quantum) 장치는 얽힘의 유지 시간을 늘리기 위해 노력하고 있습니다.

5. 얽힘의 응용과 미래 전망

양자 얽힘은 양자컴퓨팅 외에도 혁신적 응용을 제공합니다:

• 양자 암호학: 얽힌 광자를 사용한 양자 키 분배(QKD)는 도청 불가능한 보안 통신을 구현합니다(예: 중국의 Micius 위성).
• 양자 텔레포테이션: 얽힘을 활용하여 양자 상태를 원거리로 전송하며, 양자 인터넷의 기반 기술로 기능합니다.
• 양자 메트롤로지: 얽힌 상태는 초정밀 측정(예: LIGO의 중력파 탐지)을 가능하게 합니다.

미래에는 얽힘 기반 양자 네트워크가 데이터 센터와 양자컴퓨터를 연결하여 분산 양자컴퓨팅을 실현할 가능성이 있습니다. 그러나 스케일링과 오류율 문제는 여전히 해결 과제로 남아 있습니다.

6. 결론

양자 얽힘은 전자와 광자를 통해 구현되는 비고전적 상관관계로, 양자컴퓨팅의 병렬성과 효율성을 가능하게 합니다. 벨 상태의 수학적 표현, 벨 부등식 실험, 그리고 쇼어와 그로버 알고리즘에서의 역할은 얽힘이 단순한 이론적 호기심을 넘어 실질적 기술로 발전했음을 보여줍니다. 전자와 광자는 얽힘의 매개체로서 양자정보 과학의 발전을 이끌고 있으며, 암호학, 통신, 센싱 등 다양한 분야에서 혁신을 예고합니다.

다음 글에서는 그로버 알고리즘을 통해 얽힘이 비정렬 데이터 검색에서 어떻게 활용되는지 탐구할 예정입니다. 얽힘이 정답을 빠르게 찾아내는 과정에 대해 더 알고 싶다면, 질문과 의견을 공유해 주시기 바랍니다.

양자역학 기초: 큐비트 이해하기

소개

양자역학은 떠오르는 분야인 양자 컴퓨팅의 기반이 되며, 특정 작업에서 기존 컴퓨팅 시스템을 능가할 수 있는 계산 방식을 제시합니다. 양자 컴퓨팅의 핵심에는 큐비트(qubit)가 있습니다. 큐비트는 고전적 비트의 양자적 대응물로, 중첩(superposition)과 얽힘(entanglement) 같은 양자역학적 현상을 활용할 수 있다는 점에서 차별화됩니다.

이 글은 양자역학 시리즈의 첫 번째 글로, 큐비트의 이론적 기초, 주요 특성, 그리고 물리적 구현 방법을 자세히 살펴봅니다. 수학적, 물리적 기반을 심층적으로 다루어 독자들이 이 양자 정보의 기본 단위를 탄탄하게 이해할 수 있도록 하는 것이 목표입니다.

1. 큐비트: 고전적 비트의 양자적 확장

1.1 고전적 비트

고전 컴퓨팅에서는 정보가 비트에 저장되며, 각 비트는 서로 배타적인 두 상태(0 또는 1) 중 하나를 가집니다. 예를 들어, \(1010\) 같은 비트열은 데이터를 나타내거나 결정론적 논리 게이트를 통해 처리됩니다. 이 단순한 이진 시스템은 기본 산술 연산부터 복잡한 머신러닝 알고리즘에 이르기까지 모든 고전적 계산의 토대가 됩니다.

1.2 큐비트: 정의와 수학적 표현

큐비트(qubit, quantum bit)는 양자역학을 이용해 고전적 비트를 확장한 것입니다. 고전적 비트와 달리, 큐비트는 중첩 상태로 존재할 수 있으며, 이는 다음과 같은 기저 상태들의 선형 결합으로 표현됩니다:

\[ |\psi\rangle = \alpha |0\rangle + \beta |1\rangle \]

여기서 \(\alpha\)와 \(\beta\)는 복소수(진폭)이며, 정규화 조건을 만족합니다:

\[ |\alpha|^2 + |\beta|^2 = 1 \]

여기서 \(|\alpha|^2\)와 \(|\beta|^2\)는 각각 큐비트를 \(|0\rangle\) 또는 \(|1\rangle\) 상태로 측정할 확률을 의미합니다. 예를 들어, 큐비트가 다음 상태에 있을 경우:

\[ |\psi\rangle = \frac{1}{\sqrt{2}} |0\rangle + \frac{1}{\sqrt{2}} |1\rangle \]

0으로 측정될 확률과 1로 측정될 확률이 각각 50%가 됩니다.

1.3 중첩: 다중 상태의 힘

중첩(superposition)은 큐비트가 0과 1을 동시에 표현할 수 있게 해주며, 여러 큐비트가 있을 때 이 능력은 지수적으로 확장됩니다. \(n\)개의 큐비트가 있을 때 전체 상태는 \(2^n\)개의 기저 상태들의 중첩으로 표현됩니다:

\[ |\psi\rangle = \sum_{x=0}^{2^n-1} c_x |x\rangle, \quad \sum |c_x|^2 = 1 \]

예를 들어, 두 큐비트는 다음과 같은 상태에 있을 수 있습니다:

\[ |\psi\rangle = \frac{1}{2} |00\rangle + \frac{1}{2} |01\rangle + \frac{1}{2} |10\rangle + \frac{1}{2} |11\rangle \]

이로 인해 양자 컴퓨터는 여러 입력값을 동시에 처리할 수 있으며, 이는 양자 컴퓨터의 계산적 잠재력의 핵심 요소입니다.

2. 얽힘: 고유한 양자 현상

얽힘(entanglement)은 두 개 이상의 큐비트 상태가 서로 강하게 연결되어, 한 큐비트의 상태를 단독으로 설명할 수 없는 양자역학적 현상입니다. 대표적인 두 큐비트 얽힘 상태(벨 상태)는 다음과 같습니다:

\[ |\Phi^+\rangle = \frac{1}{\sqrt{2}} (|00\rangle + |11\rangle) \]

만약 첫 번째 큐비트를 \(|0\rangle\)로 측정하면, 두 번째 큐비트도 반드시 \(|0\rangle\)로 측정됩니다. 이 현상은 두 큐비트가 공간적으로 멀리 떨어져 있어도 마찬가지로 적용되며, 아인슈타인이 "거리 너머의 유령 같은 작용"이라고 묘사했던 것입니다.

얽힘은 고전적 시스템으로는 구현할 수 없는 의존성을 만들어내어 계산 효율성을 향상시킵니다. 예를 들어, 쇼어(Shor)의 알고리즘에서는 입력과 출력 큐비트 간의 얽힘을 통해 대수적 패턴을 인코딩하여 큰 수를 빠르게 인수분해합니다.

3. 큐비트의 물리적 구현

중첩과 얽힘을 활용하기 위해서는 양자적 특성을 지닌 물리적 시스템 안에서 큐비트를 구현해야 합니다. 대표적인 세 가지 구현 방식을 소개합니다.

3.1 초전도 큐비트

초전도 큐비트는 IBM, Google 같은 기업에서 가장 많이 사용하는 플랫폼 중 하나입니다.

원리
초전도 큐비트는 조셉슨 접합(Josephson junction)을 이용해 제작된 초전도 회로를 사용하며, 전기 저항을 제거하기 위해 극저온(10–20 mK)에서 동작합니다. 큐비트는 회로의 양자화된 에너지 준위로 인코딩되며, 이는 종종 초전류 방향(시계 방향, 반시계 방향) 또는 전하 상태로 나타납니다.

작동 방식
- 상태 조작: 마이크로파 펄스를 이용해 \(|0\rangle\)과 \(|1\rangle\) 상태 간 전이를 유도하거나 중첩을 만듭니다.
- 판독: 큐비트는 공진자에 결합되어 있으며, 공진 주파수의 변화를 측정하여 상태를 판별합니다.

예시
IBM의 127큐비트 "Eagle" 프로세서는 트랜스몬 큐비트(transmon qubit)를 사용합니다. 이는 개선된 코히런스 시간을 특징으로 합니다.

도전 과제
- 디코히런스: 환경과 상호작용하여 중첩과 얽힘이 사라질 수 있어, 극저온 및 차폐 기술이 필요합니다.
- 확장성: 오류율을 낮춘 채 큐비트 수를 늘리려면 고급 오류 수정 기술이 필수입니다.

수학적 설명
트랜스몬 큐비트의 해밀토니안은 다음과 같이 근사할 수 있습니다:

\[ H = 4E_C (n - n_g)^2 + \frac{E_J}{2} (1 - \cos\phi) \]

여기서 \(E_C\)는 충전 에너지, \(E_J\)는 조셉슨 에너지, \(n\)은 전하 수 연산자, \(\phi\)는 위상 차이를 나타냅니다. 이 모델은 \(|0\rangle\)과 \(|1\rangle\) 상태를 정의하는 에너지 준위를 설명합니다.

3.2 트랩된 이온 큐비트

트랩된 이온 큐비트는 개별 이온을 전자기장으로 가두어 양자 상태를 조작합니다. IonQ와 Quantinuum 같은 기업이 이 방식을 채택하고 있습니다.

원리
전하를 띤 원자(이온)를 전자기장에 가두고, 레이저 펄스를 이용해 이온의 전자 준위를 조작하여 큐비트로 사용합니다.

작동 방식
- 상태 조작: 특정 파장의 레이저를 사용해 \(|0\rangle\)과 \(|1\rangle\) 상태 사이를 전환하거나 중첩 상태를 만듭니다.
- 얽힘: 공진된 모드(집단 진동 모드)를 통해 다수의 이온 간 얽힘을 생성합니다.

예시
IonQ는 고유한 이온 트랩 기술을 활용하여 20큐비트 이상의 고품질 얽힘을 구현했습니다.

도전 과제
- 스케일링: 많은 이온을 개별적으로 제어하고 판독하는 것은 기술적으로 매우 어렵습니다.
- 속도: 큐비트 게이트 속도가 초전도 큐비트에 비해 느린 편입니다.

수학적 설명
트랩된 이온 시스템에서 이온 간 상호작용은 다음과 같은 형태로 모델링할 수 있습니다:

\[ H = \sum_i \frac{\omega_0}{2} \sigma_z^{(i)} + \sum_{i<j} J_{ij} \sigma_x^{(i)} \sigma_x^{(j)} \]

여기서 \(\omega_0\)는 큐비트 간격, \(J_{ij}\)는 이온 간 상호작용 세기, \(\sigma\)는 파울리 행렬을 나타냅니다.

3.3 광자 큐비트

광자 큐비트는 빛의 입자인 광자를 기반으로 양자 정보를 인코딩합니다. Xanadu, PsiQuantum 같은 기업이 주도적으로 연구 중입니다.

원리
광자의 편광(polarization) 상태, 위상(phase), 경로(path) 등을 사용하여 \(|0\rangle\)과 \(|1\rangle\)을 인코딩합니다.

작동 방식
- 상태 조작: 빔 스플리터(beam splitter), 위상 시프터(phase shifter) 같은 광학 소자를 이용해 광자 상태를 조작합니다.
- 얽힘: SPDC(Spontaneous Parametric Down-Conversion) 같은 과정을 통해 얽힌 광자 쌍을 생성합니다.

예시
Xanadu는 광자 기반의 양자 컴퓨터를 개발하여 "Gaussian boson sampling" 작업에서 고전적 컴퓨터를 능가하는 결과를 발표했습니다.

도전 과제
- 광자 손실: 장거리 전송 중 광자가 소멸할 수 있어 오류 수정이 까다롭습니다.
- 얽힘 생성률: 고품질 얽힌 광자쌍을 대규모로 생성하는 데 기술적 도전이 있습니다.

수학적 설명
광자 상태는 포크 상태(Fock state)로 기술할 수 있으며, 하나의 광자 상태는 다음과 같이 표현됩니다:

\[ |1\rangle = \hat{a}^\dagger |0\rangle \]

여기서 \(\hat{a}^\dagger\)는 생성 연산자(creation operator)입니다.

4. 결론

큐비트는 고전적 비트와 달리 양자 중첩과 얽힘이라는 독특한 특성을 지니며, 이는 양자 컴퓨터가 특정 문제를 고전적 컴퓨터보다 훨씬 빠르게 해결할 수 있게 합니다. 다양한 물리적 플랫폼—초전도 큐비트, 트랩된 이온 큐비트, 광자 큐비트—는 각각 장단점을 지니고 있으며, 기술적 진보에 따라 향후 표준 플랫폼이 결정될 것입니다.

양자 컴퓨팅의 궁극적인 성공 여부는 코히런스 시간, 오류율, 확장성, 제어의 정밀도 같은 요소들에 달려 있습니다. 미래의 양자 기술을 깊이 이해하고 기여하기 위해서는 큐비트의 물리적 구현과 이론적 토대를 모두 탄탄히 이해하는 것이 필수적입니다.

참고문헌

• M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2000).
• J. Preskill, "Quantum Computing in the NISQ era and beyond," Quantum 2, 79 (2018).
• IBM Quantum, "What is a qubit?" quantum-computing.ibm.com
• IonQ, "How trapped ions work," ionq.com
• Xanadu Quantum Technologies, "Photonic quantum computing," xanadu.ai

참고

Efficient and robust approximate nearest neighbor search using HNSW 논문

C++ HNSW implementation with python bindings

Lucene95HnswVectorsFormat code

배경

 ANN(Approximate Nearest Neighbor)이란 공간에서 query 벡터와 유사한 벡터(문서, 이미지 등이 학습된 데이터)들을 빠르게 검색하는 알고리즘 이다. Approximate라 표현하는 이유는 ANN이 반환한 벡터들이 실제 정답셋이 아니다. 벡터 크기가 보통 1000차원 이상 크고 학습하는 데이터도 규모있는 서비스 경우 수 억건이 넘어가기에 실제 정답을 구하는 비용이 크다. 효율적으로 계산하기 위해 recall(재현율) 및 precision(정밀도)를 기준치 이상 유지하며 빠르게 검색하는 알고리즘들이 개발되고 있다.
(http://ann-benchmarks.com/ 참고)
 

이번 글은 ANN 알고리즘 중 HNSW에 대해 알아보자. HNSW는 본래 c++ 기반으로 위 참고 github에서 먼저 공개되었고 Lucene9x, ES8x 부터 적용되었다. Lucene에서는 native java로 변환하여 적용되었으며 SIMD 등 칩에 최적화하는 과정이 빠져있어 c++보다 성능이 떨어질 수 있다. 참고로 현재 recall 대비 가장 빠른 검색 성능을 내는 알고리즘은 2020년 구글이 공개한 ScaNN 이다.

분석

1. NSW

NSW는 공간상의 벡터들을 배치하고 이들을 적절하게 연결하여 벡터 간 탐색 가능하도록 만드는 알고리즘이다. 크게 벡터를 저장하는 방식(Dense, Sparse ...), 거리 함수, 그리고 벡터를 연결하는 알고리즘(방향성 그래프 기반)으로 구성한다.

그림1 은 편의상 2차원 공간에 4개의 벡터들로 NSW를 구성한 예시이다. M은 이웃 수를 나타내며 보통 10 ~ 20개로 구성한다. 제한된 이웃 수로 효율적인 NSW를 구성하기 위해 아래 두 가지 목표를 설정한다.

1. 최소 방문으로 원하는 목적지 탐색
2. 탐색 불가능한 노드가 없도록

1번은 NSW 내 임의의 두 벡터를 선택했을 때 최단경로 길이의 평균을 최소화 하는 것이다. 2번은 edge(이웃)가 방향성을 가지기 때문에 발생하는 탐색불가능 노드를 최소화 하는 것이다. 예를들어 아래와 같은 상황을 만들면 ANN 성능이 크게 떨어진다.

그림2 는 가장 가까운 벡터들로만 이웃을 구성했을 때 NSW 예시이다. 왼쪽 3개의 벡터들은 서로 연결되어 탐색 가능하지만 오른쪽위 벡터로 가는 길은 없다. HNSW 논문의 Algorithm 3(SELECT-NEIGHBORS-SIMPLE)은 단순 거리계산만 적용된 이웃탐색 알고리즘이며 사용하지 말라고 알려주는 것이다. 이를 대신하여 Algorithm 4(SELECT-NEIGHBORS-HEURISTIC)를 제안한다. 

Algorithm 4는 처음 이웃을 구할 땐 가장 가까운 벡터를 선택하지만 다음 벡터부터 이전에 선택한 방향과 다른 벡터들을 탐색하는 것이 특징이다. 아래 예시를 통해 자세히 알아보자.

그림3 처럼 벡터(노란색, q)가 새로 추가될 때 첫 번째 이웃은 가장 가까운 벡터를 선택한다.

이후 첫 번째 이웃과 직선의 중심에서 수직선을 그어 아래 파란영역에 포함된 벡터들을 모두 후보군에서 제외한다. 만약에 벡터가 3차원 공간이라면 2차원 평면이 기준이 되어 q와 먼 거리의 벡터들을 제외한다. N차원 공간에 대해 N-1차원으로 경계를 만드는 것이다.
(실제 알고리즘과 절차는 약간 다르지만 이 프로세스가 결과를 직관적으로 이해하기 편하다.)

이어서 두 번째 이웃으로 오른쪽위 벡터를 선택하고 마찬가지로 초록색 영역의 벡터들은 후보군에서 제외된다. 이처럼 SELECT-NEIGHBORS-HEURISTIC은 이웃들을 다방면으로 연결하여 그래프 내 강한연결요소(Strongly Connected Component)를 줄인다. (탐색 속도 증가) 또한 군집에서 멀리 떨어진 벡터를 연결하여 탐색 불가능 영역을 최소화 한다. (recall 증가, 논문 Fig. 2. 참고)

2. HNSW

HNSW는 Hierarchical Navigable Small World의 약자로 NSW를 수직 계층적으로 구성하는 것을 뜻한다. 앞서 설명한 NSW를 여러 계층으로 구성하여 탐색 시간을 줄이기 위함이다.

HNSW의 가장 하단 $Lv_0$ 에 실제 찾고자 하는 벡터들을 배치한다. 그리고 $Len(Lv_{n}) = log(Len(Lv_{n-1}))$ 이 되도록 레벨이 높을수록 벡터 수를 log-scale로 줄인다. 이 때 벡터를 선택하는 기준은 랜덤이며 각 $Lv$의 NSW는 독립적으로 동작한다. 최상위 레벨에는 하나의 벡터만 있으며 이 벡터가 시작 $ep$(entry point) 이다.

이 계층을 두는 이유는 검색 시 NSW에서 이웃들을 탐색할 때 최적의 시작위치($ep$)를 구하기 위함이다. HNSW 논문에 Algorithm 1(색인)과 Algorithm 2(검색) 모두 이 계층을 통해 최적화되어 있으며 두 알고리즘은 유사해 검색 예시 하나로 설명한다.

Algorithm 1 (색인)

 

HNSW가 그림5 처럼 색인되어 있고 query 벡터가 들어오면 $Lv_2$의 $ep$ q부터 탐색을 시작한다. $Lv_2$의 $ep$는 탐색할 이웃이 없기 때문에 동일한 $Lv_1$의 $ep$에서 탐색을 진행한다. $Lv_1 ep$의 이웃들을 탐색하면서 query와 떨어진 거리를 기준으로 priorityQueue에 후보 벡터들을 저장한다. 이는 $ef$ 또는 $efConstruction$ 이라 명명한 후보군 제한 수 설정 때문이다. 그림5 예시와 달리 벡터가 많을 경우 검색 시 모든 벡터들을 탐색할 수 있다. 때문에 $ef$ 수를 넘은 만큼 priorityQueue에서 query와 가장 멀리 벡터들을 제거하여 검색 성능을 높인다.

 

$Lv_1 ep$는 그림5-2 처럼 query와 가까운 쪽으로 이동하고 이를 최종 $Lv_0 ep$로 한다. 마지막 $Lv_0$ 검색은 $ep$를 결과 priorityQueue에 저장하여 원하는 결과 벡터 수가 나올 때까지 탐색한다.

다음

Lucene9.x에 적용된 HNSW와 개선점

선행

Lucene 역색인(Inverted Index) 심층분석 1 - 전체 색인 구조

Lucene 역색인(Inverted Index) 심층분석 2 - FST

참고

Lucene90 FST code

Lucene90 BlockTreeTerms code

Burst Tries - A Fast, Efficient Data Structure for String Keys 논문

분석

Burst Tries 논문은 너무 추상적이고 정답이 없는 문제를 다뤄 증명 대신 실험에 의한 효과 증명으로 결과를 입증한다. 따라서 이번 글에선 최적화 요소가 더 많이 적용되고 더 직관적으로 이해할 수 있는 Lucene 역색인 모듈들을 직접 분석한다.

1. BlockTreeTerms Writer

심층분석 1에서 대략적으로 다뤘듯이 Lucene은 색인할 Term 전체를 FST에 저장하지 않는다. Lucene의 역색인은 BYTE 단위로 Term을 잘라 common prefix는 FST에 저장하고 나머지 suffix들은 Block으로 묶어서 저장한다. 색인 전 과정은 BlockTreeTermsWriter가 담당하며 아래 정의 및 절차에 따라 진행한다.

1. Terms는 사전순 정렬을 전제로 하며 순차적으로 iteration 하며 common prefix를 찾는다.
2. 가장 긴 prefix를 기준으로 Block 가능성을 탐색한다.
   (예를들어 "abc", "abd"의 common prefix는 "a" 일수도 있지만 "ab"가 더 길어서 기준이 됨)
3. Block 구성에 필요한 최소 Term 수(MIN_BLOCK_SIZE)는 25, 최대 Term 수(MAX_BLOCK_SIZE)는 48개 이다.
4. MAX_BLOCK_SIZE 넘어서는 common prefix는 여러 Block들로 나눠 저장하며 이는 FloorBlock이라 한다.
5. Term에서 common prefix 이후 첫 BYTE를 label이라 한다. floorLeadLabel은 FloorBlock 첫 Term의 label 이다.
6. Block으로 묶으면 Pendings의 Term들이 하나의 SubBlock으로 대체된다.
   (그림1에서 "ab" ~ "abcz" Term들이 "ab" SubBlock이 됨)
7. Block은 Terms 뿐만 아니라 SubBlock도 저장할 수 있다. 때문에 .tim의 구조를 BlockTreeTerms 라 불린다.
8. Block 내 SubBlock 없이 Terms 만 있다면 LeafBlock이라 한다.

그림1의 "ab" leafBlock 생성과정을 통해 자세히 알아보자. BlockTreeTermsWriter는 common prefix를 가진 Term 수가 MIN_BLOCK_SIZE 이상이 될 때까지 Pendings를 탐색한다. "aa"로 시작하는 Terms는 하나이므로 "ab"를 기준으로 Terms 범위를 찾는다. ("aa"는 추후 "a" Block에 저장한다.) "ab" ~ "abcz" Terms는 40개로 MIN_BLOCK_SIZE 이상 MAX_BLOCK_SIZE 미만이라서 하나의 Block만 생성한다. Block 생성 시 FST에는 .tim FP, floor info를 저장하며 BlockTreeTerms에는 suffixes 및 postings FP를 저장한다.

"ab~" Terms는 Pendings에서 SubBlock으로 변환하여 하나의 요소가 된다. 이후 "ac~", "ad~", "ae~" 기준들로 Block 생성 시도하지만 MIN_BLOCK_SIZE를 넘지 못해 넘어간다. 이후 "b" Term을 처리하는 시점(leadLabel의 index가 바뀌는 시점)에 "a~" Pendings로 Block 생성 시도한다.

"a~" Pendings는 총 74개로 MAX_BLOCK_SIZE를 넘어 여러 Block들로 저장해야 한다. 이때도 label을 기준으로 Block들을 나누는 기준이 된다. 그림2 예시로 "a" ~ "acw" 까지 26개 Pendings가 묶인다. 이때까지 label은 'c'이며 "ada"를 탐색하는 순간 label이 'd'로 바뀐다. Block에 Pendings를 넣을 때 "ada" ~ "adx" 중 top 몇 개의 Pendings 만 넣을 수 없다. 현재 26개 Pendings로 구성하고 있는 Block에 MAX_BLOCK_SIZE를 채우기 위해 모자란 22개 "ad~" Terms만 Block에 넣을 수 없다는 뜻이다. "a" ~ "adx"로 Block을 구성하면 50개로 MAX_BLOCK_SIZE를 넘기에 "a" ~ "acw" 까지 최초의 "a~" Block을 생성한다. 첫 번째 Term이 suffix가 없으면 lead label이 -1 이다.

leadLabal이 'd' 인 상태로 나머지 Block 생성을 진행한다. "ad~" Pendings는 MIN_BLOCK_SIZE를 넘지않아 leadLabel 'e' 까지 탐색하고 "ada" ~ "aex" 까지 총 48개 Pendings로 Block을 생성한다. "ad~" Pendings는 MIN_BLOCK_SIZE를 넘지 않지만 "ae~" Pendings는 MIN_BLOCK_SIZE를 넘으면 어떻게 Block을 구성할 지 의문이 들 수 있다. 예를들어 "ad~" Pendings가 24개이고 "ae~" Pendings가 30개라면 총 54개로 MAX_BLOCK_SIZE를 넘기 때문이다. 하지만 이 경우는 존재하지 않는다. "a~" Pendings로 Blocks를 구성하는 시점에 "ae~" Pendings는 이미 MIN_BLOCK_SIZE를 넘어 하나의 SubBlock Pending으로 변해 있기 때문이다. 때문에 두 개의 서로 다른 labels로 Block 내 MAX_BLOCK_SIZE 이상 Pendings를 저장 할 수 없다. 그리고 MAX_BLOCK_SIZE는 이론상 (MIN_BLOCK_SIZE - 1)의 배수여야 한다.

SubBlock을 저장은 .tim의 경우 현재 FP 위치와 prefix Block FP의 차이만큼 저장한다. 그림2 예시로 "a"(-1) Block 내 "ab" SubBlock의 FP가 500이고 "ab~" Block의 FP가 20 이라면 next FP에 480을 저장하는 방식이다. BlockTreeTerms는 이렇게 간단하게 구현하지만 FST는 약간 복잡하다. 왜냐하면 "ab~" Block을 먼저 생성하고 "a~" Block이 나중에 생성 되었으므로 사전순으로 FST에 색인할 수 없기 때문이다. 이를 해결하기 위해 색인 중에만 BlockTree level에 따라 subIndices라는 child FST를 생성한다. Block 생성시 subIndice 병합하는 과정을 아래와 같이 거쳐 FST 생성 시 사전 순 입력을 보장한다. (BlockTreeTermsWriter::compileIndex 참고)

  public void compileIndex(
      List<PendingBlock> blocks,
      ByteBuffersDataOutput scratchBytes,
      IntsRefBuilder scratchIntsRef)
      throws IOException {

      ...

      // Copy over index for all sub-blocks
      for (PendingBlock block : blocks) {
        if (block.subIndices != null) {
          for (FST<BytesRef> subIndex : block.subIndices) {
            append(fstCompiler, subIndex, scratchIntsRef);
          }
          block.subIndices = null;
        }
      }
      
      ...
  }

  private void append(
        FSTCompiler<BytesRef> fstCompiler, FST<BytesRef> subIndex, IntsRefBuilder scratchIntsRef)
        throws IOException {
      final BytesRefFSTEnum<BytesRef> subIndexEnum = new BytesRefFSTEnum<>(subIndex);
      BytesRefFSTEnum.InputOutput<BytesRef> indexEnt;
      while ((indexEnt = subIndexEnum.next()) != null) {
        fstCompiler.add(Util.toIntsRef(indexEnt.input, scratchIntsRef), indexEnt.output);
      }
    }
  }

전반적인 프로세스 설명은 마치며 FST -> BlockTreeTerms -> Doc, Pos, Pay 절차 및 Codec을 간략히 정리하면 아래와 같다. Lucene은 끊임없이 최적화 요소를 적용하고 있어서 자세한 사항은 내부 구현 및 테스트로 확인해야 한다.

2. BlockTreeTerms Reader

색인에서 term을 찾고 데이터를 읽는 과정이다. 앞서 BlockTreeTermsWriter 과정 이해를 전제로 한다.

SegmentTermsEnum이 각각의 Segment에 대응하여 생성되고, 특정 term을 찾거나 전체 term들을 찾는 동작을 수행한다. SegmentTermsEnum은 Block의 depth 마다 SegmentTermsEnumFrame을 생성하고 읽기 상태에 따라 FST.Arcs, term 데이터를 관리한다. SegmentTermsEnumFrame이 Block을 읽는 역할을 수행하며 FloorBlock들도 한 Frame 내에서 읽는다.

Block을 읽는 동작과 Postings를 읽는 동작은 분리되어 있다. 즉 term을 찾을 땐 .tip/.tim 파일만 decoding 하고 해당 term의 Postings를 읽을 때 .doc/.pos/.pay 파일을 decoding 한다.

전체 Terms 탐색 (NextTerm)

1. 전체 탐색은 .tip에서 .tim 시작 FP만 참조할 뿐 .tip에서 검색하지 않는다.
2. .tim의 root Block에서 SegmentTermsEnumFrame을 생성하고, root Block의 term 들을 순차적으로 탐색한다.
3. 탐색할 때 NonLeafBlock(term이 아닌 Block)이 나오면 SegmentTermsEnumFrame를 하나 더 생성하고 depth가 증가한다.
4. 마치 tree 탐색처럼 모든 Leaf를 탐색하면 depth가 감소하여 다시 탐색하는 동작을 반복한다.

특정 Term 탐색 (SeekExact)

1. 특정 term 탐색은 .tip에서 term의 첫 번째 char부터 순차적으로 FST를 탐색한다.
2. FST에 char의 arc를 찾을 수 있다면 SegmentTermsEnumFrame을 생성하고 다음 char를 탐색한다.
   (이때 SegmentTermsEnumFrame에는 arc 정보와 FST의 output을 읽어서 저장한다.)
3. FST에서 찾을 수 있는 최대 길이의 prefix를 다 찾았다면 FloorBlock을 탐색한다.
4. FloorBlock들의 정보는 FST의 output에 VInt로 저장되어 순차적으로 탐색해야 한다.
5. 최종 확인해야 할 Block이 정해지면 해당 Block을 load 한다. (suffixs, stats, postings FP 정보)
6. suffixs를 탐색하여 해당 term이 매칭되는지 확인한다.
   
   

심화

Lucene 역색인 시공간 복잡도

MIN_BLOCK_SIZE, FST::BYTE가 색인의 크기, 검색 속도를 결정하는 중요한 값.

Block의 시공간 복잡도

• "a~" blocks 에는 "ab~" pendings가 MIN_BLOCK_SIZE개 이상 존재할 수 없다.
• "a~" blocks 의 가능한 모든 label의 경우의 수는 기본값 FST::BYTE의 크기이며 최대 256 이다.
• "a~" blocks 내 같은 label의 최대 pendings 수는 MIN_BLOCK_SIZE - 1 이다.
• "a~" blocks 내 최대 pendings 수는 BYTE x (같은 label 최대 pendings 수) 이므로 256 * (MIN_BLOCK_SIZE - 1) 이다.
• 그렇다면 최대 FloorBlock 수도 구할 수 있다. label이 최대 BYTE 가지 존재하고 label이 바뀌는 시점마다 FloorBlock을 생성 할 수 있다. label이 최소 2번은 바뀌어야 FloorBlock을 생성 할 수 있기 때문에 최대 FloorBlock 수는 BYTE1 / 2 이다.
  
  

MIN_BLOCK_SIZE 특성

• MAX_BLOCK_SIZE는 (MIN_BLOCK_SIZE - 1) 의 배수
• MIN_BLOCK_SIZE가 높을수록 FST와 BlockTreeTerms의 크기 및 깊이가 감소한다.
• MIN_BLOCK_SIZE가 높을수록 전체 Block 수는 감소하지만 FloorBlock 수는 지수배로 늘어난다.
  물론 MIN_BLOCK_SIZE가 1 ~ 5로 극단적으로 작다면 Block 및 FloorBlock 수 모두 늘어나고 검색효율도 떨어진다.
• MIN_BLOCK_SIZE가 높을수록 SeekExact 시 FST 탐색속도 빨라지고 BlockTreeTerms 탐색속도는 상당히 느려진다.
  애초에 FST가 빠른 탐색이 목적이기에 전체 검색속도는 FST 탐색이 감소한만큼 급격하게 늘어난다.
  FloorBlocks는 현재 순차적으로 탐색하기에 여기에서 병목 또한 늘어날 것으로 예상한다.
  FloorBlocks 탐색 개선요소 주석
  
  

FST::BYTE 가 커질 수록

• Block을 묶는 기준이 강화되서 총 Block 수 및 depth가 감소한다.
• 최대 FloorBlock 수가 늘어난다. (BYTE_SIZE / 2)
• FST 크기가 소폭 감소한다. 특정 Block에서 FloorBlock 수가 늘어 output이 커질 수 있지만 총 Block 수가 줄어드므로 전체 크기는 감소한다. FST 탐색속도는 언어에 따라 다를 수 있다. 예를들어 한글의 경우 BYTE2 이상으로 설정하면 불필요한 구간에서 node, arc가 발생하지 않아 검색속도 개선에 유리하다.
• BlockTreeTerms 크기가 증가한다. 더 세밀하게 term들을 쪼개지 못해 평균 FloorBlock 수가 증가 했으므로 탐색시간이 증가한다. depth가 줄어들어 크기는 감소할 수 있지만 묶지 못한 케이스가 많을 경우 suffix 데이터가 증가하여 전체 크기는 증가한다.

선행

이번 글은 Lucene 역색인 전체구조에서 FST 구조만 설명합니다.

Lucene의 FST는 Direct Construction of Minimal Acyclic Subsequential Transducers 논문을 기반으로 하며 TestFSTs 로 테스트할 수 있다.

목표

전체 역색인 과정에서 FST의 역할은 Terms의 prefix와 이와 매칭되는 tim의 FP(파일포인터)를 함께 저장할 수 있어야 한다. 또한 term 검색 시 log(BYTE x len(term)) 이내로 빠르게 찾을 수 있어야 하며, Segment 간 병합을 위해 사전순으로 Terms를 iteration 할 수 있어야 한다. 

Lucene에서 FST의 input은 Terms의 공통 prefix를 BYTE 단위로 쪼개 node로 생성하며, output은 .tim의 FP로 long 타입이다. 논문에서 output은 string으로 전제하였다. FST는 output 또한 공통부분을 추출하여 저장하기에 타입에 따라 효율이 크게 달라진다. 예를들어 "100"과 "101"는 공통부분이 "10" 이지만 100과 101은 공통부분이 100이다. 

논문분석

Definition 1.

Subsequential Transducer는 inputs, outputs와 상태 및 함수들로 구성된 tuple로 이 글에선 $\mathbb{T}$ 로 표현한다. Subsequential Transducer는 모든 상태가 결정되었음을 전제로 하며 이 뜻은 inputs 집단과 outputs 집단이 변하지 않음을 뜻한다. Lucene도 주기에 맞춰 Segment 내에서 색인할 때 추출된 Terms로만 FST를 구성할 뿐 기존 FST에 추가할 수 없다. FST에 input을 추가하거나 output을 변경할 때는 처음부터 새로 생성해야 하며 이는 Segment 병합 시 FST를 새로 생성하는 이유기도 하다.

$\mathbb{T}  =  <\Sigma, \Delta, S, s, F, \mu, \lambda, \Psi>$

$\Sigma \ \ is \ a \ finite \ input \ alphabet;$
$\Delta \ \ is \ a \ finite \ output \ alphabet;$
$S \ \ is \ a \ finite \ set \ of \ states;$
$s \in S \ \ is \ the \ starting \ state;$
$F \subseteq S \ \ is \ the \ set \ of \ final \ states;$
$\mu \ : \ S \ \times \ \Sigma \rightarrow S \ \ is \ a \ partial \ function \ called \ the \ transition \ function;$
$\lambda \ : \ S \ \times \ \Sigma \rightarrow \Delta^{*} \ \ is \ a \ partial \ function \ called \ the \ output \ function;$
$\Psi \ : \ F \rightarrow 2^{\Delta^{*}} \ \ is \ the \ final \ function;$

Subsequential Transducer의 구성은 위와 같다. $\Sigma, \Delta, S, F$ 는 집합이며 나머지 함수들은 파라미터와 결과 타입을 의미한다. $\mu, \lambda$ 의 첫 번째 파라미터는 node이며 두 번째 파라미터는 온전한 Term이 아닌 부분으로 쪼갠 Term의 일부다. $\lambda$의 결과 또한 공통 부분만 추출한 output의 일부를 표현한 것이다.

이해를 돕기위해 월별 데이터로 FST를 구성하면 위 과정을 거친다. 입력은 월별 영어 약자($\Sigma$) 이며 출력은 월별 말일($\Delta$) 이다. ○(compiled, 확정된), □(compiling, 계산중) 들은 node를 의미하며 $S$에 속한다. 각 함수의 결과 값은 node 및 arc에 저장되며 아래 예시처럼 동작한다. (Lucene FST 코드에서 정점을 node, 간선을 arc로 명명하여 이 글에서도 똑같이 표현한다.)

$\Sigma$ = {['a','p','r'], ['a','u','g'], ['d','e','c'], ['f','e','b'], ... }
$\Delta$ = {"30", "31", "31", ["28", "29"], ...}
$\mu$(s5, 'p') $\rightarrow$ s2
$\lambda$(s5, 'p') $\rightarrow$ "0"
$\Psi$(s1) $\rightarrow$ ""
$\Psi$(s8) $\rightarrow$ ["8", "9"]

$\mu, \lambda$ 의 확장함수($^*$) 들은 두 번째 파라미터로 하나의 문자가 아닌 prefix 문자열($\sigma$)을 받으며 아래 규칙을 따른다.

${\forall}r \in S, \forall\sigma \in \Sigma^*, {\forall}a \in \Sigma$ ($\Sigma^*$ 은 모든 prefix inputs 집합)
$\mu^*(r, {\sigma}a) = \mu(\mu^*(r, \sigma), a)$
$\lambda^*(r, {\sigma}a) = \lambda^*(r, \sigma)\lambda(\mu^*(r, \sigma), a)$

e.g.
$\mu^*$(t0, "apr") = $\mu$($\mu^*$(t0, "ap"), 'r') = $\mu$(s2, 'r') = s1
$\lambda^*$(t0, "apr") = $\lambda^*$(t0, "ap")$\lambda$($\mu^*$(t0, "ap"), 'r') = "30"$\lambda$(s2, 'r') = "30"

최종으로 input language 함수 $L$과 output 함수 $O_{\mathbb{T}}$ 정의는 아래와 같다.

$L(\mathbb{T}) \ = \{ \sigma \in \Sigma^* \ | \ \mu^*(s, \sigma) \in F \}$
$O_\mathbb{T}(\sigma) \ = \lambda^*(s, \sigma) \cdot \Psi(\mu^*(s, \sigma))$

e.g.
$L(\mathbb{T})$ = {"apr", "aug", "dec", "feb", ...}
$O_\mathbb{T}$("apr") = "30"

임의의 두 Transducers가 $L(\mathbb{T}), O_{\mathbb{T}}$ 의 입출력 값들이 모두 같다면 두 Transducers는 같다고(equivalent) 한다. 

Definition 2, 3.

정의 2, 3은 outputs 측면에서 Minimal Subsequential Transducer를 구성하기 위한 정리들을 설명한다. Minimal Subsequential Transducer란 Equivalent Transducers 중에 가장 node, arc 수가 작으면서 outputs 저장공간이 가장 작은 Transducer를 뜻한다.

정의2 는 $L(\mathbb{T})$ 집합의 prefix 집합 $D(\mathbb{T})$에 대하여 공통의 output을 가장 앞선 node에 배치하기 위한 $g_{\mathbb{T}}(u)$ 함수를 선언한다.

$D(\mathbb{T}) \ = \{ u \in \Sigma^* \ | \ {\exists}w \in \Sigma^* \ (uw \in L(\mathbb{T}) \ \}$
$g_{\mathbb{T}}(u) \ = \ \wedge_{w \in \Sigma^* \ \& \ uw \in L(\mathbb{T})} {\wedge}O_{\mathbb{T}}(uw) $ 
($\exists$는 존재함을 $\wedge$는 and 연산을 의미)

$D(\mathbb{T})$ 는 $L(\mathbb{T})$ 로 만들 수 있는 모든 prefix 집합.
$g_{\mathbb{T}}(u)$ 는 u로 시작하는 모든 input들의 output들을 모아 공통 부분을 추출한 것. 

e.g.
$u$ = "j" 일 때 $uw$ 집합은 {"jan", "jul", "jun"} 이며 각 output은 아래와 같음.

$O_{\mathbb{T}}$("jan") = "31"
$O_{\mathbb{T}}$("jul") = "31"
$O_{\mathbb{T}}$("jun") = "30"

i.g.
$g_{\mathbb{T}}$("j") = $O_{\mathbb{T}}$("jan") $\wedge$ $O_{\mathbb{T}}$("jul") $\wedge$ $O_{\mathbb{T}}$("jun") = "31" $\wedge$ "31" $\wedge$ "30" = "3"

정의3 은 $g_{\mathbb{T}}$ 함수를 활용하여 transducer의 총 $\lambda$ 합을 최소화 하기 위한 함수를 선언한다. 그리고 아래 조건을 만족하는 transducer를 Canonical Subsequential Transducer 라고 명명한다.

${\forall}r \in S, \forall\sigma \in \Sigma^*, {\forall}a \in \Sigma$
$(\mu^*(s, \sigma) = r \ \& \ !\mu(r, a)) \ \rightarrow \ \lambda(r, a) = [g_{\mathbb{T}}(\sigma)]^{-1}g_{\mathbb{T}}({\sigma}a)$
($!\mu$ 는 node가 존재하지 않을 때)

e.g.
$g_{\mathbb{T}}$("a") = "3"
$g_{\mathbb{T}}$("ap") = "30"
$\lambda$(s5, 'p') =  $g_{\mathbb{T}}$("a")$^{-1}g_{\mathbb{T}}$("au") = "0"

Canonical Subsequential Transducer는 논문에 언급한 것처럼 가장 앞선 node에 output을 최대한 많이 저장한다. 그림1 에서 ("jan", "31"), ("jul", "31") 을 저장하는 과정을 다시보자. $\lambda$(t0, 'j')가 빈 값이라면 $\lambda$(t1, 'a'), $\lambda$(t1, 'u') 두 arcs에 "31"을 저장하므로 중복이 발생한다. 그러므로 가장 앞선 node인 $\lambda$(t0, 'j')에 "31"을 저장하는 것이 공간을 최소화하는 방법이다. 

이후 ("jun", "30")을 저장할 때는 $g_{\mathbb{T}}$ 에 따라 $\lambda$(t0, 'j') = "3", $\lambda$(t1, 'a') = "1", $\lambda$(t2, 'l') = "1", $\lambda$(t2, 'n') = "0" 으로 바뀐다. 즉, 사전순으로 Term을 입력하면서 가장 앞선 node에 공통 output을 저장하여 공간을 최소화 한다. 자세한 증명은 인용 논문인 Minimization algotithms for sequential transducers에서 다루며 node, arc 빌드 과정은 다음 정리 이후 설명한다.

여기까지 Canonical Subsequential Transducer를 구성하기 위한 정의이다. 그리고 논문에서는 Canonical Subsequential Transducer 내에 equivalent node가 없다면 minimal Transducer라고 한다. 쉽게 설명하면 outputs까지 최적화 하였으니 중복된 node, arc를 제거하여 최소화하라는 것이다. 그림1 s1 node가 하나의 예시이며 특정시점 이후 node, arc가 모두 같을 때 해당 node를 재사용하는 과정을 다음 정리에서 설명한다.

Definition 4.

정의 4는 $\mathbb{T}  =  <\Sigma, \Delta, S, s, F, \mu, \lambda, \Psi>$ 가 아래 조건들을 만족할 시 마지막 Term의 prefix인 $w$ 를 제외하고 minimal이라고 한다. 다시 그림1 예시로 조건들을 설명하면 다음과 같다.

  1.  모든 node가 시작 node로 부터 접근 가능해야 한다.

  2. 사전순으로 마지막 단어인 "jul"의 prefix인 $w$의 node들은 아직 $\mathbb{T}$에 포함되지 않은 빌드 중인 상태(□) 이다.

      그리고 아래 정의와 조건을 만족한다.

$w = w_{1}^{\mathbb{T}}w_{2}^{\mathbb{T}}...w_{k}^{\mathbb{T}}, \ w_{i}^{\mathbb{T}} \in \Sigma, \ i \in 1...k$
$t_{0}^{\mathbb{T}} = s; \ t_{1}^{\mathbb{T}} = \mu(t_{0}^{\mathbb{T}}, w_{1}^{\mathbb{T}}); \ ... \ ; \  t_{k}^{\mathbb{T}} = \mu(t_{k-1}^{\mathbb{T}}, w_{k}^{\mathbb{T}})$ 
$T = \{ t_{0}^{\mathbb{T}}, t_{1}^{\mathbb{T}}, ..., t_{k}^{\mathbb{T}}\}$

$\forall{r} \ \in \ S, \forall{i} \ \in \ \{ 1 ... k\}, \forall{a} \ \in \ \Sigma$
$\mu(r,a) = t_i \leftrightarrow (i > 0 \ \& \ r = t_{i-1} \ \& \  a = w_i^{\mathbb{T}})$

   3. $S \setminus T$에 equivalent states 들이 없다. (즉, 모든 node, arc가 unique 함)

   4. $\mathbb{T}$는 Canonical Subsequential Transducer다.

정의4는 부분으로 구성된 Minimal Subsequential Transducer(이하 MST)에 새로운 node, arc를 추가하면서 minimal 상태를 유지하기 위함이다. 이를 위해 MST에 포함된 node(해당 node에서 출발하는 arcs 포함)를 ○로 표시하고 아직 계산 중인 $T$의 node들을 □로 표시한다. $T$ 에서 MST에 node를 추가하는 과정은 가장 끝의 node부터 시작한다. 그림1 예시로 "jul"에서 'l'에 해당하는 node 부터 minimal 상태를 유지한채 transducer에 입력하는 것이다. 이는 아래 보조정리들로 자세히 설명한다.

Lemma1은 $t_{k}$와 동일한 기존 node가 없을 때 이를 $\mathbb{T}$에 추가해도 minimal 이다.

Lemma2는 $t_{k}$와 동일한 기존 node인 p가 있을 때 $t_{k-1}$에서 $w_{k}$ arc의 target을 p로 가리켜도 minimal 이다.

Lemma3는 $t_{k}$와 동일한 기존 node의 조건을 말한다. 요약하면 동일한 노드는 final일 때 출력이 같아야하며 final이 아니면 가리키는 모든 arc 정보가 같아야한다.

다시 그림1의 마지막 사전순 단어 "jul" 에서 마지막 단어부터 $\mathbb{T}$에 추가한다. 이때 다음 단어인 "jun"과 common prefix인 "ju" 만 $T$로 남기고 'l' arc가 추가된다. $g_{\mathbb{T}}$("ju") = "3" 이므로 'l' arc의 output은 "1"이며 $w$ = "jun" 으로 바뀐다. 결과는 아래 그림2와 같다.

Lemma2에 의해 <$\mu$(t2,'l') = s1, $\lambda$(t2,'l') = "1">로 추가해도 $\mathbb{T}$는 minimal이다. 이후 ("MAR", "31)을 색인할 때 common prefix가 하나도 없으므로 t1, t2, t3를 $\mathbb{T}$에 추가해야 한다. Lemma3에 의해 $\mu$(t2,'n')는 s1을 가리키고 t1과 t2는 새로운 node로 추가된다. t1과 t2는 동일한 node가 없어서 추가된 것이므로 Lemma1에 의해 $\mathbb{T}$는 minimal이다.

종합하여 Minimal Subsequential Transducer를 생성하는 과정은 뜨개질과 유사하다. 구성할 모든 단어들을 사전 순으로 탐색하며 마지막 단어의 끝부터 공통의 input, output만 남기고 나머지 부분을 확정짓는 방식이다. 확정된 node들은 이후 수정할 수 없기에 뜨개질 중간에 튀어나온 올을 없애기 힘든 것과 같다. 한 번의 뜨개질로 minimal 상태를 만들어야 하므로 정렬되고 결정된(finite) inputs를 전제로 한다.

다음

이번 글에서 Lucene FST를 이해하기 위한 정의들을 다뤘지만 Theorem3, 4 및 Algorithm이 빠졌습니다. Theorem3, 4는 $T$에서 common prefix만 남기고 나머지 node, arc를 추가하는 상세한 과정과 증명인데 너무 길어서 위에 간략하게만 설명했습니다. 사실 여기까지도 다 읽으실 분들이 많지 않을 것 같아서 요청하시면 추가할게요!

Algorithm은 Lucene의 FST 기반으로 설명드리려 합니다. Lucene의 FST는 파일로 en/decoding 하기에 arc가 많을 시 binary search 할 수 있도록 codec을 구성합니다.

배경

Lucene의 문서 색인의 가장 작은 단위인 Segment 내에 다른 Segment 들과 독립된 색인을 필드별로 생성한다. 그 중 text 타입 역색인은 아래 그림 처럼 크게 3단계로 나뉜다. 예제 데이터는 "ace", "ant", "beautiful", "begin" 단어들로 색인했을 때 루씬 색인 파일 인코딩 구조를 간략화 한 것이다.

색인구조

1. tip

• terms(문서에 포함된 단어들)의 공통 prefix들을 저장하는 FST 자료구조.
• input은 term의 prefix, output은 tim의 FP(파일 포인터).
• term을 일정간격(BYTE1, 2, 4 지원)으로 잘라서 노드를 구성하며 트리 형태로 map 구현.
• FST는 input들의 공통 노드에 겹치는 output을 분리하여 저장하여 크기를 최소화 함.
• Direct Construction of Minimal Acyclic Subsequential Transducers 논문 기반.
• Lucene core util FST에 구현됨.

2. tim

• terms의 suffix들을 저장하는 Burst Tries 자료구조.
• 25 ~ 48개의 elements를 묶어 하나의 block을 생성. (위 예시는 실제와 달리 단순화를 위해 2개로 생성함)
• element는 suffix 또는 하위 block을 가리킴.
• suffix는 해당 term의 doc / pos / pay 의 시작 FP를 저장.
• block 내 하위 block은 특정 term이 아닌 모든 terms를 알파벳 순으로 찾기 위함이며 이는 Segment 병합 시 필요.
• Burst Tries: A Fast, Efficient Data Structure for String Keys 논문 기반
• Lucene core codecs lucene90 blocktree에 구현됨.

3. doc / pos / pay

• doc은 DocId(Segment내 부여된 문서 Id) 들을 저장한 skip list 자료구조.
  (DocId 들은 오름차순으로 저장하여 delta encoding 적용.)
• pos는 term의 위치 정보를 저장.
• pay는 term의 payload 정보로 score 계산 시 유저가 추가한 metadata.
  
  

심화

• Lucene의 역색인은 위처럼 크게 3단계로 구성된다. 이를 깊이있게 살펴보면 왜 term을 저장할 때 prefix, suffix를 나눠서 저장하는 지 의문이 생길 수 있다. Lucene은 전반적으로 검색성능이 떨어지지 않는 선에서 색인의 크기를 최소화하려 한다. 때문에 term에서 공통부분이 많은 prefix는 FST로 저장하고 공통부분이 적은 suffix는 단어를 쪼개지 않고 그대로 저장한다.

  FST                 Burst Tries
b -> e         |         autiful

• 예를들어 "beautiful" 단어를 저장할 때 "be"로 시작하는 단어는 무수히 많다. 때문에 이 단어를 검색할 때 공통 prefix는 Byte 단위로 하나씩 쪼개 node, arc 형태의 트리를 탐색하는 것이 유리하다. 하지만 "beaut"를 공통 prefix로 가진 단어들은 매우 적다. 때문에 suffix를 FST 구조로 "a -> u -> t -> i -> f -> u -> l" 형태로 만들면 공통부분이 없는데 단어 길이만큼 불필요한 node, arc가 생성된다.
  
  
• 효율적인 역색인을 위해 Lucene은 terms를 사전순으로 정렬하여 순차적으로 25 ~ 48개의 공통 prefix를 찾는다. 공통 prefix를 찾을 때 마다 prefix는 FST에 추가하고 나머지 suffix들은 Burst Tries에 추가한다. suffix 마다 해당 term의 doc / pos / pay FP 도 같이 저장하며 FST는 tip에 Burst Tries는 tim에 serialize 되어 저장한다.
  
  

다음

정의

중국인의 나머지 정리(Chinese remainder theorem; CRT)는 중국의 5세기 손자산경에 나오는 문제로 다음과 같다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

이를 수식으로 자세히 정리하면 아래와 같다.

서로 서로소인 음이 아닌 정수 k개가 있다고 가정하자. gcd($n_{i}, n_{j}$) = 1 (i $\neq$ j)
$n_{1}, n_{2}, ..., n_{k}$ 
$n \ = \prod_{i=1}^k n_{i}$

그렇다면 다음 연립 합동 방정식의 해 $a \in \mathbb{Z}/n$ 는 항상 유일하게 존재한다.

$a \equiv a_{1} \ (mod \ n_{1})$
$a \equiv a_{2} \ (mod \ n_{2})$
...
$a \equiv a_{k} \ (mod \ n_{k})$

증명

이 고대 수학 정리는 언뜻 간단해 보이지면 증명을 위해 여러 보조정리가 필요하다.

많은 글에서 보조정리를 나열하여 다루지만 이 글에서는 문제 본연의 풀이에 집중하기 위해 해의 존재성과 유일성 각각에 맞춰 풀이한다.

존재성

존재성은 위 연립 합동 방정식을 만족하는 해 $x \in \mathbb{Z}/n$ (쉽게 $0\leq x <n$ 인 정수) 가 존재함을 증명하면 된다. 확장된 유클리드 호제법 등 많은 정수론에서 해를 구하기 위해 혹은 존재성을 입증하기 위해 베주 항등식을 인용한다.

베주 항등식

$ a,b \in \mathbb{Z} \ (a \neq 0 \ or \ b \neq 0)$,  $gcd(a, b)=d$ 이면

$ d = au + bv $ 를 만족하는 $ u, v \in \mathbb{Z} $ 가 존재한다.

자세한 증명은 링크를 참조바라며 직관적인 이해는 아래와 같다.
최대공약수 d는 a, b의 특정 배수의 합으로 만들 수 있다는 것이다.
이를 확장한 증명으로 d는 a, b 배수 집합의 가장 작은 양의 정수다. 그리고 d의 배수들로 이 집합을 구성할 수 있다.
즉, a와 b로 나타낼 수 있는 정수 집합은 가장 기본 단위가 d라는 뜻 이다.

나머지 정리의 각 $n_{i}$ 에 대해 $ n_{i}, \frac{n}{n_{i}} $ 를 베주항등식 $ a, b $ 에 대입해보자.

 $n_{i}, \frac{n}{n_{i}}$ 는 서로 서로소 이므로  $gcd(n_{i}, \frac{n}{n_{i}}) = 1$

그렇다면 $n_{i}u_{i} + \frac{n}{n_{i}}v_{i} = 1$ 을 만족하는 $u_{i}, v_{i} \in  \mathbb{Z} $가 존재한다.

여기서 $e_{i} = \frac{n}{n_{i}}v_{i}$ 라고 하면 아래 두 식이 성립한다.

$e_{i} \equiv 1\ (mod\ n_{i})$
$e_{i} \equiv 0\ (mod\ n_{j},\ i \neq j)$

결국 각 $e_{i}$ 를 구하는 과정은 $mod\ n_{i}$ 시  $n_{j}\ (i \neq j)$ 에 영향을 받지 않는 값을 구하기 위함이며 이를 모두 합한 a는 위 문제 해답 중 하나이다.

$a = \sum_{i=1}^ka_{i}e_{i} $

유일성

증명을 위해 반례로 $ x, y \in \mathbb{Z}/n $ 두 해가 존재한다고 가정하자. 

그렇다면 모든 $n_{i}$ 에 대해 $ x \equiv y \equiv a_{i}\ (mod\ n_{i}) $ 를 만족하므로 $x-y$ 는 모든  $n_{i}$의 배수이다.

각 $ n_{i},\ n_{j}\ (i \neq j) $는 서로소라고 가정 했으므로 모든 $n_{i}$의 배수는 $n$의 배수이기도 하다.

즉, $x-y$ 는 $n$의 배수라서 $ \mathbb{Z}/n $ 에서 두 해가 존재할 수 없다.

응용

작업 중...

$e_{i}$ 를 구하는 방법: 유클리드 호재법 확장 vs 오일러 정리

개요

 타원곡선 암호는 줄여서 ECC는 공개키 암호화 방식 중 하나로 데이터 암호화 디지털 인증 등 현재 가장 많이 쓰이는 암호방식이다. ECC는 큰 수의 소인수 분해가 어렵다는 것에 착안해 만든 RSA 암호와 달리 이산로그문제에 착안해 만들어졌다. 때문에 256비트의 ECC키는 3072비트의 RSA키와 비슷한 암호화 레벨이며 키값이 커질수록 RSA보다 암호화 레벨이 급격하게 높아진다.

타원곡선

 먼저 타원곡선이란 아래 식을 만족하는 그래프를 뜻하며, 판별식(영어로 discriminant)이 0이 아니어야 한다.

$y^2 = x^3 + ax + b, (4a^3 + 27b^2 \neq 0)$

그래프를 그리면 위와 같이 나타나는데 이 그래프 위의 점들의 집합 G는 아래 조건들을 만족한다.

① G에 속한 임의의 점 P, Q에 대해서 P + Q 또한 G에 속한다
② (P + Q) + R = P + (Q+ R)
③ ideal point 0이 있으며 P + 0 = 0 + P = P
④ Q가 P의 역원이면 P + Q = 0
⑤ P + Q = Q + P

위 조건들 중 만약 두 점 p, q의 합을 단순히 x좌표와 y좌표의 합이라면 ① 식을 만족하지 않는다. ① 식이 만족하는 이유는 타원곡선에서 덧셈연산을 특별하게 정의하고 있기 때문인데, 아래 그림을 먼저 본다.

  위 그림처럼 타원곡선에서 두 점 P, Q의 덧셈은 두 점을 지나는 직선과 타원곡선이 만나는 또 다른 점 -R에서 수직선을 그어 타원곡선과 만나는 점 R이다. 때문에 타원곡선에서 두 점의 합은 타원곡선에서 속한 점이다. 여기서 P, Q를 지나는 직선과 만나는 또다른 점을 -R이라고 한 이유는 -R이 R의 역원이 되기 때문이다. -R과 R은 수직선으로 이 직선과 타원곡선이 만나는 또 다른 점은 없다. 즉 R + (-R) 연산은 기하학적으로 타원곡선과 만나는 점이 없으므로 0(ideal point)으로 표현한다.

 만약 같은 P를 더하면 어떻게 될까? 같은 점을 더하면 위 그림처럼 해당 점의 접선과 타원곡선이 만나는 또다른 점 -R에서 수직선을 그어 만나는 점 R이다. 이와 같이 타원곡선의 덧셈에 대한 정의로 타원곡선의 점은 스칼라 곱셈 연산도 표현 가능하다. 예를 들어 7P는 4P + 3P로 이며 4P는 2P + 2P, 3P는 2P + P 이므로 P의 덧셈연산을 거듭해서 구하다보면 P의 모든 스칼라 곱도 구할 수 있다.

 지금까지 기하학적으로 타원곡선의 덧셈연산을 살펴보았는데 대수적으로 살펴보면 어떨까?

① 타원 위의 서로 다른 두 점 P, Q의 덧셈을 구하려고 할 때

$m = \frac{y_Q  -   y_P}{x_Q   -   x_P}$

m은 두 점을 지나는 직선의 기울기이며 직선의 식은 아래와 같다.

$y = m(x - x_P) + y_P$

이를 타원곡선 식의 y값에 대입하면 아래와 같다.

$(m(x - x_P) + y_P)^2 = x^3 + ax + b$
$x^3 - m^2x^2 + ... = 0$

결국 R의 x값을 구하는 것은 위 3차 방정식의 해를 구하는 것과 같다.

여기서 우리가 이미 알고 있는 P, Q의 x값이 있고 x^3의 계수가 1이므로, 즉 x^2의 계수는 세 근의 합에 -값이 된다.

$(x - x_P)(x - x_Q)(x - x_R) = x^3 - (x_P + x_Q + x_R)x^2 + ...$

이를 먼저 기울기 m에 대해 정리한 식에 대입하면 아래와 같이 R의 x값을 구할 수 있다.

$x_P + x_Q + x_R = m^2$
$x_R = m^2 - x_P - x_Q$

R의 x값을 직선의 방정식에 대입하여 R의 y값도 계산한다.

$y_R = m(x_R - x_P) + y_P$

② 같은 점 P 2개의 덧셈을 구할 때

점 P에서 타원곡선의 접선의 기울기 m은 타원곡선의 미분방정식에 점 P를 대입한 값이므로 아래와 같다.

$m = \frac{3x_P^2  +  a}{2y_P}$

 그리고 결과 R은 같은 점을 더했으므로 Q값 대신 P값을 넣어 아래와 같이 정리할 수 있다.

$x_R = m^2 - 2x_P$
$y_R = m(x_R - x_P) + y_P$

유한체에서 타원곡선

 위에서 그래프로 나타낸 타원곡선은 무한대 실수 범위이다. 하지만 타원곡선을 이용해서 암호화에 적용하려면 유한한 자연수 범위에서 덧셈연산도 역으로 추적하기 어려워야 한다. 타원곡선암호는 모든 점들을 큰 소수 p에 대한 나머지들, 즉 𝔽p 내에 존재한다. 만약 𝔽p에서 점 P(x, y)가 타원곡선 E에 있다면 x, y는 모두 소수 p의 나머지 들이고 타원곡선 식도 mod p에서 만족하면 된다.

${x, y \in \mathbb{F}_p,\ y^2 = x^3 + ax + b\ (mod\ p)}$

 mod p에서 덧셈 연산은 접선의 기울기에서 분모의 역원을 계산할 수 있어야 한다.

${a^{-1} \equiv \ b \ (mod\ p)}$

나머지연산에서 나눗셈은 위와 같이 해당 값의 역원을 찾아서 곱셈으로 표현할 수 있다. 이는 앞서 포스팅한 RSA 암호에서 확장된 유클리드 알고리즘이나 페르마의 소정리를 참고하면 구할 수 있다. (아래 참고로 링크한 andrea corbellin blog에서는 확장된 유클리드 알고리즘을 사용하였으나 소수에 대한 나머지 연산이므로 페르마의 소정리를 사용하는 편이 더 쉬운듯 하다. 역원을 구할 때 시간 복잡도는 O(log p)로 비슷하다.)

 𝔽p에서 덧셈연산과 스칼라 곱 계산을 통해 얻은 타원곡선 위의 점들은 이산로그문제가 된다. 이를 좀 더 간단히 설명하자면

$ 2^n = 64$
${2^n \equiv 9\ (mod\ 17)}$

위에 n값는 6으로 쉽게 구할 수 있지만 mod 17에서 2의 배수 중 9가 되는 값은 일일이 계산해 보지 않는 이상 어렵다. 타원곡선 점들도 이와 같이 몇 번의 덧셈연산으로 결과 값을 구하긴 쉽지만 기준 점으로 부터 몇 번의 연산을 했는지는 구하기 매우 어렵다. 타원곡선암호란 구하기 어려운 몇 번의 덧셈을 해야하는지 위에 이산로그문제에서 지수가 되는 부분을 비밀키로 하고 그 결과가 되는 점을 개인키로 한다.

위처럼 유한체에서 타원곡선은 모든 연산을 유한한 범위의 자연수로 표현가능하고 역방향으로 추적을 어렵게 한다. 하지만 이를 바로 암호화에 사용하기에는 몇가지 검증 작업을 더 거쳐야 한다.  andrea corbellin blog에서는 아래 식을 예로 들었다.

${y^2 \equiv x^3 + 2x + 3\ (mod\ 93),\  G = (3, 6)}$

 위 타원곡선식에서 기준점 G를 이용하여 몇 번의 연산을 통해 키를 생성한다고 가정하자.

0G=0
1G=(3,6)
2G=(80,10)
3G=(80,87)
4G=(3,91)
5G=0
6G=(3,6)
7G=(80,10)
8G=(80,87)
9G=(3,91)

그리고 기준점에 대해 스칼라 곱을 순차적으로 구해보면 위와 같이 점 5개가 반복해서 나타난다. 위 타원곡선을 암호화에 사용한다면 5번의 연산만으로 사용자의 비밀키를 추적할 수 있다. 물론 암호화에서는 큰 소수를 나머지연산에 사용하겠지만 위에서 봤듯이 mod 93인데 기준점과 타원곡선에 따라 표현할 수 있는 점이 5개 밖에 나오지 않는 경우도 있다. 

이처럼 유한체에서 어떤 타원곡선이 표현할 수 있는 총 점의 수는 암호화 레벨을 결정하는 중요한 요소이다. 그리고 현재 이를 구할 수 있는 알고리즘으로 Schoof's algorithm이 있다. (이 알고리즘은 Hasse's theorem on elliptic curves과 중국인의 나머지정리를 기반으로 만들어졌는데, 아직 이해하지 못해 추후 따로 포스팅할 까 합니다. 그리고 타원곡선 표준에서는 이 알고리즘을 통해 미리 정해진 타원곡선과 기준점, 유한체의 범위를 사용하므로 새로운 타원곡선을 만들지 않는 이상 직접적으로 Schoof's algorithm을 사용할 일은 없습니다.)

키 생성

타원곡선 암호에서 키 생성을 위해 domain parameters를 정해야 한다. domain parameters는 a, b, N, n, h, G로 총 6개이다. 먼저 a, b는 타원곡선 식의 요소이고 p는 유한체 범위를 결정하는 소수이다.

그리고 a, b, p값으로 타원곡선의 총 점의 수 N값은 Schoof's algorithm을 통해 구한다. 그 뒤 기준점이 되는 G와 n, h는 아래 순서를 반복해서 구한다.

① 전체 집합 원소의 수 N에서 부분집합의 수인 n을 결정한다. (n은 소수이면서 N의 약수)
② 보조 인자(cofactor)인 h = N/n 를 구한다.
③ 타원곡선 위 임의의 점 P를 골라서 기준점 G = hP를 구한다.
④ G가 0이면 다른 P를 골라서 반복한다.

(domain parameters를 구할 때 andrea corbellin blog에서는 Lagrange's theorem을 언급하며 부분집합에 관한 부가설명이 있습니다. 이 부분도 완벽하게 이해하지 못하여 추후 설명 추가하겠습니다.)

 domain parameters를 모두 정하면 이제 공개키와 비밀키를 만들 수 있다. RSA 암호와 달리 타원곡선 암호에서는 비밀키를 먼저 정한다.

비밀키 d는 [1 ... n-1] 에서 자연수 값으로 키 생성자가 지정할 수 있다. 그리고 공개키는 타원곡선 위의 좌표 H = dG이다.

 위에서 domain parameters를 결정하는 과정은 d(비밀키)와 domain parameters로 부터 공개키를 구하는 것은 쉽지만 H(공개키)와 domain parameters로부터 비밀키를 구하는 것은 어렵게 설계되있다. 이렇게 역추적하려면 어려운 이산로그문제를 풀게 하는 것이 타원곡선암호의 핵심이다.

ECDH

 ECDH는 Diffie–Hellman key exchange을 Elliptic Curve에 적용한 방법이다. Diffie–Hellman key exchange의 핵심은 서로 통신할 두 사람이 같은 키를 공유하는 것인데 중간에 전송하는 정보를 가로채도 사용자의 비밀키를 알 수 없게 하는 데 있다.

ECDSA

작업중

참고

andrea corbellin blog (가장 ECC에 대해 자세하게 설명한 블로그)

Standards for Efficient Cryptography Group