KDDI연구소와 규슈대학은 전 세계 암호화연구자 참여가 예상되는 암호해독 콘테스트(독일 다름슈타드 공과대학 주최)에서 지금까지 아무도 해독할 수 없었던 60차원의 Learning with Errors(LWE ) 문제를 세계 최초로 해독했다고 발표했다.
금융 분야 등에서는 거래의 안전성을 위해 네트워크상에서 암호를 이용하고 있다.공개키 암호라고 부르는 방식에서는, 수학적으로 관련지을 수 있었던 2종의 키(공개키와 비밀키)를 이용하여 정보의 교환을 행한다.그러나 양자 컴퓨터의 실현으로 해독된다는 우려로 어려움이 높은 '격자 암호'라는 공개 키 암호가 검토되고 있다.
LWE 문제는 고의에 오차를 부가한 다원 연립 XNUMX차 방정식을 푸는 문제.이것은 격자 암호의 해독에 해당한다고 한다.안전한 암호화를 실현하기 위해서는 LWE 문제의 차원(미지 변수의 개수)을 높이거나 오차를 크게 하여 해독을 곤란하게 할 필요가 있다.그러나, 차원이 너무 높으면 계산 시간이 증가하고, 오차가 너무 크면 정확한 암호화 처리를 행할 수없는 확률이 증가한다.이 때문에, 안전성이 확보되는 최적의 차원과 오차의 크기를 구하기 위해서, 많은 연구기관에서 고속의 해법의 연구가 진행되고 있다.
이번 연구 그룹은, 해독 알고리즘의 고속화와 병렬화에 성공해, 상용 클라우드의 20대의 가상 PC를 이용하는 것으로, 슈퍼 컴퓨터를 이용한 총당 방식에 의한 계산에서는 60만년 이상 걸리는 16차원의 LWE 문제를 약 55일 동안 해독하였다.또 XNUMX차원 이하의 문제도 해독했다고 한다.
이번 성과는 차세대 공개키 암호로서 격자 암호를 이용할 때에 안전한 차원이나 오차의 크기를 결정하기 위한 중요한 정보가 된다.향후, 해독 알고리즘의 고속화 검토를 한층 더 진행해, 고속으로 안전한 차세대 공개키 암호를 실현하고 싶다고 한다.