[논문]ARM/NEON 프로세서를 활용한 NIST PQC SABER에서 Toom-Cook 알고리즘 최적화 구현 연구

송진교; 김영범; 서석충

doi:10.13089/jkiisc.2021.31.3.463

초록
AI-Helper

NIST(National Institute of Standards and Technology)에서는 2016년부터 양자컴퓨팅 환경을 대비하여 양자내성암호 표준화 사업을 진행하고 있다. 현재 3라운드가 진행 중이며, 대부분 후보자(5/7)는 격자기반 암호이다. 격자기반 암호는 효율적인 연산 처리와 적절한 키 길이를 제공하여 다른 기반의 양자내성 암호보다 리소스가 제한적인 임베디드 환경에서도 적용이 가능하다는 평가를 받고 있다. 그중 SABER KEM은 효율적인 모듈러스와 연산 부하가 큰 다항식 곱셈을 처리하기 위해 Toom-Cook 알고리즘을 제공한다. 본 논문에서는 ARMv8-A 환경에서 ARM/NEON을 활용하여 SABER의 Toom-Cook 알고리즘에서 평가와 보간 과정에 대한 최적화 구현 방법을 소개한다. 평가과정에서는 ARM/NEON의 효율적인 인터리빙 방법을 제안하며, 보간 과정에 서는 다양한 임베디드 환경에서 적용 가능한 최적화된 구현 방법론을 소개한다. 결과적으로 제안하는 구현은 이전 레퍼런스 구현보다 평가과정에서는 약 3.5배 보간과정에서는 약 5배 빠른 성능을 달성하였다.

Abstract ▼ AI-Helper

Since 2016, National Institute of Standards and Technology (NIST) has been conducting a post quantum cryptography standardization project in preparation for a quantum computing environment. Three rounds are currently in progress, and most of the candidates (5/7) are lattice-based. Lattice-based post...

Since 2016, National Institute of Standards and Technology (NIST) has been conducting a post quantum cryptography standardization project in preparation for a quantum computing environment. Three rounds are currently in progress, and most of the candidates (5/7) are lattice-based. Lattice-based post quantum cryptography is evaluated to be applicable even in an embedded environment where resources are limited by providing efficient operation processing and appropriate key length. Among them, SABER KEM provides the efficient modulus and Toom-Cook to process polynomial multiplication with computation-intensive tasks. In this paper, we present the optimized implementation of evaluation and interpolation in Toom-Cook algorithm of SABER utilizing ARM/NEON in ARMv8-A platform. In the evaluation process, we propose an efficient interleaving method of ARM/NEON, and in the interpolation process, we introduce an optimized implementation methodology applicable in various embedded environments. As a result, the proposed implementation achieved 3.5 times faster performance in the evaluation process and 5 times faster in the interpolation process than the previous reference implementation.

주제어

표/그림 (12)

그림 Fig. 1. Evaluation in Toom-Cook Algorithm
그림 Fig. 3. Interpolation in Toom-Cook Algorithm
그림 Fig. 2. Karatsuba Multiplication
표 Table 1. Summary of A64 and ASIMD Instruction Set in ARMv8-A Series [6], [7]
그림 Fig. 4. Evaluation Implementation in ARM Processor
표 Table 2. Summary of Register Scheduling
그림 Fig. 5. Evaluation Implementation in NEON Engine
그림 Fig. 6. Interleaving Approach
그림 Fig. 7. Register Scheduling for Interpolation in Toom-Cook Algorithm
그림 Fig. 8. Proposed Optimization of Interpolation in Toom-Cook Algorithm
그림 Fig. 9. Interpolation Implementation in NEON Engine
표 Table 3. Comparison of performance between reference implementation and our work

AI 본문요약
AI-Helper

문제 정의

본 논문에서는 처음으로 ARMv8-A Series에서 ARM/NEON 프로세서를 활용하여 SABER의 핵심 연산인 다항식 곱셈 Toom-Cook 알고리즘의 평가와 보간 단계의 최적화 구현 방안을 제시한다. 제안하는 방법을 통해 레퍼런스 구현보다 평가과정에서는 약 3.
하지만 최근 ARM Cortex-A Series는 모바일, 태블릿, 자율주행에서 널리 사용되고 더욱 강력한 NEON 엔진까지 지원하여 다양한 암호 최적화 연구가 활발히 수행되고 있다. 본 논문에서는 최초로 ARM Cortex-A Series(ARMv8)에서 ARM/NEON 프로세서를 활용한 Toom-Cook 알고리즘의 평가 및 보간 단계의 최적화 구현 방법을 소개한다.
하지만 임베디드 환경에서 양자내성암호의 최적화 구현연구 대부분은 ARM Cortex-M4 환경에서 수행하였다. 본 논문에서는 최초로 ARMv8 환경에서 NIST PQC SABER의 핵심 연산인 다항식 곱셈 Toom-Cook 알고리즘에 대한 최적화 구현 방법을 제안하였다. 제안하는 방법을 통해 평가 및 보간 과정에서 레퍼런스 구현보다 3.

제안 방법

또한, ARMv8 환경에서 이전 연구결과가 존재하지 않아 레퍼런스 구현과의 성능을 비교하였으며, 레퍼런스 구현은 C로 구현되어있고 사이클 측정 결과는 –O2 최적화 옵션을 적용하였다.
먼저 ARM 프로세서에서의 병렬 최적화 방법을 소개하고 그 다음 NEON 엔진에서의 병렬 최적화 방법을 소개한다. 마지막으로 ARM/NEON의 각 구현을 인터리빙하여 효율적으로 ARM 명령어에 대한 지연시간을 NEON 명령어로 숨기는 방법을 소개한다. Table 2는 ARM/NEON 프로세서의 각 구현에서 레지스터 스케쥴링을 보여준다.
본 절에서는 Toom-Cook 알고리즘의 평가과정에 대한 ARM/NEON 프로세서를 활용한 최적화 방법을 소개한다. 먼저 ARM 프로세서에서의 병렬 최적화 방법을 소개하고 그 다음 NEON 엔진에서의 병렬 최적화 방법을 소개한다. 마지막으로 ARM/NEON의 각 구현을 인터리빙하여 효율적으로 ARM 명령어에 대한 지연시간을 NEON 명령어로 숨기는 방법을 소개한다.

대상 데이터

본 절에서는 제안하는 Toom-Cook 알고리즘의 평가 및 보간과정에 대한 성능 측정 결과를 제안한다. 우리는 라즈베리파이 4B 환경에서 성능을 측정하였으며, 라즈베리파이 4B는 4개의 코어 ARM Cortex-A72(ARMv8)과 4GB 내장 메모리를 탑재하고 있다. 우리의 타겟장비는 우분투 20.
우리는 라즈베리파이 4B 환경에서 성능을 측정하였으며, 라즈베리파이 4B는 4개의 코어 ARM Cortex-A72(ARMv8)과 4GB 내장 메모리를 탑재하고 있다. 우리의 타겟장비는 우분투 20.04 운영체제가 설치되어있으며, VS Codium 개발환경 내 AArch64-gnu-gcc 컴파일러를 통해 성능을 측정하였다. 또한, ARMv8 환경에서 이전 연구결과가 존재하지 않아 레퍼런스 구현과의 성능을 비교하였으며, 레퍼런스 구현은 C로 구현되어있고 사이클 측정 결과는 –O2 최적화 옵션을 적용하였다.

성능/효과

5배 향상되었다. 게다가 보간과정에서는 8개 계수에 대한 병렬처리 기법과 메모리 접근 부하를 최소화하여 레퍼런스 구현보다 약 5배 향상된 결과를 달성하였다. SABER에서 가장 성능 부하가 큰 부분은 행렬 곱셈으로 제안하는 방법을 통해 SABER 전체적으로는 더 큰 성능향상이 기대된다.
본 논문에서는 최초로 ARMv8 환경에서 NIST PQC SABER의 핵심 연산인 다항식 곱셈 Toom-Cook 알고리즘에 대한 최적화 구현 방법을 제안하였다. 제안하는 방법을 통해 평가 및 보간 과정에서 레퍼런스 구현보다 3.5배, 5배의 성능 향상을 달성하였다. 향후 Toom-Cook 알고리즘의 Karatsuba 곱셈 및 NTT 곱셈에 대한 최적화 구현을 연구할 계획이다.
평가과정은 두 개의 다항식 A, B에 관한 결과의 클럭 사이클을 측정하였다. 평가과정에서는 ARM/NEON 인터리빙 구현과 8개 계수에 대한 병렬처리 기법을 통해 레퍼런스 구현보다 약 3.5배 향상되었다. 게다가 보간과정에서는 8개 계수에 대한 병렬처리 기법과 메모리 접근 부하를 최소화하여 레퍼런스 구현보다 약 5배 향상된 결과를 달성하였다.

후속연구

게다가 보간과정에서는 8개 계수에 대한 병렬처리 기법과 메모리 접근 부하를 최소화하여 레퍼런스 구현보다 약 5배 향상된 결과를 달성하였다. SABER에서 가장 성능 부하가 큰 부분은 행렬 곱셈으로 제안하는 방법을 통해 SABER 전체적으로는 더 큰 성능향상이 기대된다.
특히 양자내성암호 중 격자기반 암호는 빠른 속도를 제공하여 실제 임베디드 환경에서도 적용하다. 게다가 ARMv8은 저전력과 고효율의 장점으로 앞으로도 임베디드 SoC로서 널리 활용될 것으로 기대된다. 하지만 임베디드 환경에서 양자내성암호의 최적화 구현연구 대부분은 ARM Cortex-M4 환경에서 수행하였다.
5배, 5배의 성능 향상을 달성하였다. 향후 Toom-Cook 알고리즘의 Karatsuba 곱셈 및 NTT 곱셈에 대한 최적화 구현을 연구할 계획이다.

참고문헌 (10)

Peter W. Shor, "Polynomial-time algorithm for prime factorization and discrete logarithms on a quatum computer", SIAM review, vol. 41, no. 2, pp. 303-332, Oct. 1997

상세보기
NIST PQC Standardization "https://csrc.nist.gov/projects/post-quantum-cryptography", 2021. 4. 15
Hwajeong Seo, Taehwan Park, Shinwook Heo, Gyuwon Seo, Bongjin Bae, Zhi Hu, Lu Zhou, Yasuyuki Nogami, Youwen Zhu, Howon Kim, "Parallel Implementations of LEA, Revisited", WISA, 10144, pp. 318-330, Aug. 2016
Hwajeong Seo, Kyuhwang An, Hyeokdong Kwon, Taehwan Park, Zhi Hu and Howon Kim, "Parallel Implementations of CHAM", WISA, 11402, pp. 93-104, Aug. 2018
Hwajeong Seo, Taehwan Park, Janghyun Ji, Zhi Hu, and Howon Kim, "ARM/NEON Co-design of Multiplication/Squaring", WISA, 10763, pp. 72-84, Aug. 2017
ARMv8 A64 Instruction set, "https://developer.arm.com/documentation/ddi0596/2020-12/Base-Instructions", 2021. 4. 15
ARMv8 ASIMD Instruction set, "https://developer.arm.com/documentation/ddi0596/2020-12/SIMD-FP-Instructions", 2021. 4. 15
Leon Botros, Matthias J. Kannwischer, Peter Schwabe, "Memory-Efficient High-Speed Implementation of Kyber on Cortex-M4", AFRICACRYPTO, vol. 11627, pp 209-228, July. 2019
Jose Maria Bermudo Mera, Angshuman Karmakar, and Ingrid Verbauwhede, ""Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice based cryptography", CHES, vol. 2020, no. 2, pp. 222-244, Sep. 2020,
Denisa O. C. Greconici, Matthias J. Kannwischer and Daan Sprenkels, "Compact Dilithium Implementations on Cortex-M3 and Cortex-M4", CHES, vol. 2021, no. 1, pp. 1-24, Sep. 2021

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

ARM/NEON 프로세서를 활용한 NIST PQC SABER에서 Toom-Cook 알고리즘 최적화 구현 연구
Optimization Study of Toom-Cook Algorithm in NIST PQC SABER Utilizing ARM/NEON Processor 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (12)

표/그림 (12)

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (10)

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

ARM/NEON 프로세서를 활용한 NIST PQC SABER에서 Toom-Cook 알고리즘 최적화 구현 연구 Optimization Study of Toom-Cook Algorithm in NIST PQC SABER Utilizing ARM/NEON Processor 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (12) 모든 표/그림 보기

표/그림 (12) 슬라이드로 보기

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (10)

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

ARM/NEON 프로세서를 활용한 NIST PQC SABER에서 Toom-Cook 알고리즘 최적화 구현 연구
Optimization Study of Toom-Cook Algorithm in NIST PQC SABER Utilizing ARM/NEON Processor 원문보기

초록
AI-Helper

표/그림 (12)

표/그림 (12)

AI 본문요약
AI-Helper