Asiacrypt 2015 학회

▩ CRYPTO, Eurocrypt, Asiacrypt는 IACR(International Association for Cryptologic Research; 국제 암호연구회)에서 1년마다 개최하는 3개의 conference로, 암호학자들은 이들 3개의 학회를 암호 3대학회로 부른다. 이들 3개의 학회에서는 암호학계에서도 가장 영향력 있는 중요한 결과들이 발표되어 왔다. 이 중에 하나인 Asaicrypt에 참석하여 암호학계의 국제적 이슈 및 연구 결과를 파악하고자 한다. 특히, 우리 사업에서 관심을 가지고 집중적으로 연구하고 있는 다변수 2차방정식을 푸는 문제에 기반한 암호시스템에 관한 결과를 포함하여, 대표적인 수학적 난제인 이산대수문제, 이를 확장한 multiple 이산대수 문제 등에 관한 여러 연구결과들이 발표되는바, 이러한 결과들은 현재 및 향후 연구사업에 직간접적으로 도움이 될 만한 결과들이며, 또한 해당 결과의 연구자들과의 폭넓은 토론을 통하여, 해당 과제에서 더 나은 결과를 얻을 수 있을 것으로 기대된다.

▩ 이번 Asiacrypt에서는 18개의 세션에서 73편의 논문이 발표되었다. 올해의 Eurocrypt와 Crypto가 그랬던 것처럼, Asiacrypt 역시 올해에는 처음으로 parallel session을 도입하였다. 학회 장소는 캠퍼스 중앙에 있었던 Owen Glenn Lecture Theatre의 지하에 있는 여러 개의 강의실 중에서 Lecture Theatre 4와 Lecture Theatre 5 두 곳에서 발표가 진행되었다.

▲ 그림 1. 학회가 진행되었던 Owen Glenn Lecture Theatre의 외관

▣ 발표시간은 25분으로 비교적 넉넉히 주어진 편이었다. 최근에 논문을 많이 뽑는 경향 때문에 없어졌던 free afternoon이 올해 다시 시행되어, 화요일 오후에는 발표가 없었다. 이번 Asiacrypt에는 총 251개의 논문이 접수되어 63개의 논문이 선정되었으며 acceptance rate는 25.1% 정도였다. 이번 Asiacrypt의 Best paper award는 "Improved security proofs in lattice-based cryptography: using Renyi divergence rather than the statistical distance"라는 논문이 선정되었으며, 두 개의 논문 “Key-Recovery Attacks on ASASA”와 “The Tower Number Field Sieve”은  Journal of Cryptology에 초대되는 영광을 안았다.

▣ 이번 Asiacrypt 2015 학회에서는 세 번의 초청강연이 있었다.첫 번째 초청 강연은 일본 NTT의 Masayuki Abe 박사가 “Structure Preserving Cryptography”이라는 주제로 강연을 하였다. 두 번째 초청 강연은 Spain의 IMDEA Sofrware Institute의 Gilles Barthe 박사가 “Computer-Aided Cryptography: Status and Prespectives”라는 주제로 강연을 하였다. 컴퓨터 내의 하드웨어와 소프트웨어를 암호화한다는 다소 생소한 개념의 강연이었다.

▲ 그림 2. Gilles Barthe의 Asiacrypt 초청 강연

▣ 화요일의 Track A에서는 Albrecht Petzoldt 등의 “Design Principle for HFEv- based Multivariate Signature Schemes”에 대한 발표가 있었다.  Multivariate Quadratic Cryptosystem에 관련된 발표였다. HFEv-란, 기존에 발표된 HFE(Hidden Field Equation)기반 스킴이 깨지자 안전성 보완을 위해 Vinegar 개념과 식을 몇 개 없애는 “-” 개념을 추가한 스킴으로, 2001년에 QUARTZ라는 이름으로 발표되었다. 하지만, QUARTZ는 중앙다항식의 차수가 너무 커 다른 서명 알고리즘에 비해 매우 느렸으며, 따라서 현실적으로 사용하기에 적합하지 않았다. 하지만 작년 PQCrypto에서 HFEv 스킴의 degree of regularity에 대한 연구 결과가 발표되었으며, 이 결과를 바탕으로 중앙 다항식의 차수$D$ , vinegar 변수의 개수$V$ , 마지막에 제거된 다항식의 수$a$ , 이 3개의 변수와 안전성 등의 관계를 연구하여 최적의 조합을 찾아낸 것이 바로 이번에 발표된 Gui 스킴이다. 이번 스킴은 기존의 서명 알고리즘과 충분히 비교할만한 스킴이다. 스킴을 연구한 A. Petzoldt와 이를 구현한 Ming-Shing Chen이 나누어 발표를 하였다.

▲ 그림 3. Albrecht Petzoldt, Ming-Shing Chen의 Asiacrypt 일반 강연

▣ 월요일의 마지막 세션은 “Discrete Logarithms and Number Theory”로 출장자의 연구 분야와 연관이 깊은 분야여서 관심이 많았다. 첫 번째 발표는 Aurore Guillevic의 “Computing Individual Discrete Logarithms Faster in GF($p^n$) with the NFS-DL Algorithm”이라는 주제의 발표였다. 이산대수 문제를 푸는 알고리즘 중 하나인 Number Field Sieve에 관련된 결과였다. 최근 발표된 Logjam attack을 이용하면 precomputation을 사용하여 아주 빠르게 이산대수 문제를 풀 수 있다. 하지만 이러한 방법은 medium characteristic이 크면서 prime field가 아닌 경우에는 적용하기 어렵기 때문에 booting step이라는 새로운 스텝을 적용하여 전체 알고리즘의 퍼포먼스를 향상시킨 것이었다. 

▣ 두 번째 발표는 서울대학교 출신으로 현재 일본의 NTT에서 박사후 연구원으로 있는 김태찬 박사의 “Multiple Discrete Logarithm Problem with Auxiliary Inputs”라는 주제의 발표였다. [2006년 서울대학교 천정희 교수님께서 Strong Diffie-Hellman Problem의 특수한 경우에 이를 알려진 방법보다 훨씬 쉽게 푸는 알고리즘을 발표하여 개막강연을 하신 적이 있었다.]이번 김태찬 박사의 발표는 [이 문제를 조금 확장한 새로운 문제에 대해] 현존하는 몇 개의 스킴이 이 문제에 기반하고 있어 안전성에 타격을 받을 수 있을 것 같다.

▲ 그림 5. A. Guillevic 박사의 Asiacrypt 일반 강연

▣ 세 번째 발표는 Yao Lu의 “Solving Linear Equations Modulo Unknown Divisors: Revisited”에 관한 발표였다. 어떤 다항식 와 인수분해가 알려지지 않은 정수 에 대해 )인 를 찾는 문제에 대한 결과였다. 이는 특히 1997년에 Coppersmith가 LLL알고리즘을 이용하여 특수한 경우에 이 문제를 푸는 알고리즘이 알려지면서부터 RSA의 하나의 공격루트로 쓰였는데, 이번 발표에서는 1998년 Boneh등이 발표한 메시지의 일부를 알고 있을 때 특정한 수의 nontrivial divisor를 찾는 알고리즘을 조금 더 향상시킨 결과를 발표하였다. 또한 인 경우에 대한 May의 2004년 결과 역시 이 큰 경우에 더 나은 결과를 발표하였다. Craig Costello의 “FourQ : four-dimensional decompositions on a Q-curve over the Mersenne Prime”에 관한 발표였다. 그는 이 발표에서 128 비트 안전성을 갖는 암호 스킴에서 사용될 수 있는 한 타원곡선을 발표하였다. 이 곡선은 연산의 속도가 빠른데도, 안전성이 좋아 알려진 타원곡선들에 비해 많은 장점을 가지고 있는 커브라고 소개하였다.

▲ 그림 6. C. Costello 박사의 Asiacrypt 일반 강연

▣ 화요일의 "Signature" section에서는 Khoa Ngyuen의 “A Provably Secure Group Signature from Code-Based Assumption”이라는 주제로 강연을 하였다. Post-Quantum으로 적용 가능한 Group Signature가 최근 5년간 6개가 제안되었으나, 모두 lattice 구조에 기반하고 있어, 키 길이와 서명 길이가 길고, 구현하기가 어렵다는 단점이 있다. 따라서 이런 단점을 피하기 위해 coding theory에 기반한 group signature를 이번에 새로 제안한 것이다. 또한 구현한 후 기존 결과들과 비교하였는데, 저자들은 post-quantum group signature의 첫 번째 구현결과라고 주장하였다.

융합수학연구부 ㅣ Asiacrypt 2015