양자 암호 - 격자 기반 양자 내성 암호

[개념] 공개키 기반 구조(PKI, Public Key Infrastructure)가 뒷받침되 는 정보처리시스템 또는 정보통신망 환경에서 양자 컴퓨터의 공격에도 안전한 키 교환, 메시지 암·복호화 서비스를 제공할 수 있는 암호 기술

 

[설계] LWE(Learning with Errors), LWR(Learning with Rounding) 등의 격자 문제를 푸는 어려움을 기반으로 설계됨

 

LWE                             Learning with Errors 

LWR                             Learning with Rounding

 

균등분포(uniform distribution)

정의된 영역에서 분포가 균등하게 나타나는 경우

 

공격량(시간 복잡도, time complexity)

주어진 문제를 해결하는 데 소요되는 시간

 

LWE

 

LWE 문제는 2005년 Regev가 처음으로 제안한 격자 기반 문제로, 다양한 암호 프리미티 브를 만드는 데에 사용되고 있다. LWE 문제는 크게 search 문제와 decision 문제로 나 뉘며, 사용되는 수학적 구조에 따라 (plain) LWE 문제, ring-LWE 문제 등으로 나뉜다.

 

LWR

 

LWR 문제는 Banerjee 등이 2012년 처음으로 제안한 격자 기반 문제로, 에러가 랜덤 분 포로부터 추출되는 것이 아니라 라운딩 연산을 통해 결정적으로 정해지는 변형된 LWE 문제이다. LWR 문제는 최근 들어 공개키 암호, pseudorandom generator(PRG), 동형암 호 설계 등을 위한 기반 문제로서 사용되고 있다.

 

출처: TTA,  http://www.tta.or.kr/data/ttas_view.jsp?rn=1&pk_num=TTAK.KO-12.0349-Part1