격자기반 양자내성암호에서 RST를 이용한 기각 샘플링 병렬 최적화 구현 (Implementation of Parallel Optimization of Rejection Sampling using RST in Lattice-Based Post-Quantum Cryptography)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 28권 / 5호 / 314 ~ 319페이지
· 저자명 : 안상우, 서석충

초록

NIST에서는 양자 알고리즘에도 안전한 양자내성암호를 표준화하기 위하여 공모전을 진행하고 있다. 선정된 최종 후보 알고리즘 중 격자기반 전자서명 알고리즘인 CRYSTALS-Dilithium의 주요 연산중 하나는 무작위의 다항식 벡터 행렬을 생성하는 ExpandA 함수다. ExpandA 함수는 기각 샘플링을 기반으로 생성된 난수를 다항식의 계수로 입력하는 과정을 수행하는데, 기존의 기각 샘플링 과정은 분기문으로 이루어진 수용-기각 판단 후 순차적인 다항식 계수 입력 과정을 거치기 때문에 병렬 연산에 적합하지 않다는 단점이 존재한다. 본 논문에서는 병렬 연산에 적합하지 않은 기각 샘플링을 최적화하여 병렬 연산에 적합한 그래픽 처리 장치에서 효율적으로 ExpandA 함수를 처리할 수 있는 기법을 제시한다. 본 논문에서 제시하는 기법은 신속한 서명 및 검증 속도를 보장해야 하는 자율주행 자동차 통신 프로토콜 환경에서 적극적으로 활용될 수 있다.

영어초록

NIST conducted a contest to standardize post-quantum cryptography, which is safe for quantum algorithms. Among the finalist algorithms, CRYSTALS-Dilithium is a lattice-based digital signature algorithm. One of the main operations of CRYSTALS-Dilithium is the ExpandA function, which generates a random polynomial vector matrix. The ExpandA function performs a process of inputting a random number generated based on rejection sampling as a polynomial coefficient. Since the existing rejection sampling process goes through a sequential polynomial coefficient input process after an acceptance-rejection branch decision, there is a disadvantage that it is not suitable for parallel operation. In this paper, we propose a technique that can efficiently process the ExpandA function in a graphic processing unit suitable for parallel operation by optimizing rejection sampling that is not suitable for parallel operation. The technique presented in this paper can be actively utilized in the autonomous vehicle communication protocol environment, which must ensure fast signature and verification speed.

참고자료

· 없음