[논문]사물인터넷 장비 상에서의 양자내성암호 구현 동향

권혁동; 엄시우; 심민주; 서화정

사물인터넷 장비 상에서의 양자내성암호 구현 동향 원문보기

情報保護學會誌 = KIISC review, v.32 no.2, 2022년, pp.37 - 49

권혁동 (한성대학교 IT융합공학부) , 엄시우 (한성대학교 IT융합공학부) , 심민주 (한성대학교 IT융합공학부) , 서화정 (한성대학교 IT융합공학부)

초록
AI-Helper

양자컴퓨터의 발전에 따라 양자알고리즘에 대한 보안성을 보장하는 양자내성암호의 중요성이 대두되고 있다. 미국 국립표준기술연구소 (NIST, National Institute of Standards and Technology)는 양자내성암호 표준화 공모전을 개최하여 차세대 공개키 암호에 대한 검증을 현재 Round 3까지 진행한 상태이다. 본 고에서는 최근에 활발히 연구되고 있는 NIST 양자내성암호 공모전에 제안된 양자내성암호에 대해서 확인해 보도록 한다. 또한 해당 양자내성암호의 연산 효율성을 높이기 위해 사물인터넷 장비 상에서 최적 구현 기법에 대해 확인해 보도록 한다.

표/그림 (25)

표 [표 1] IBM 양자컴퓨터 로드맵.
표 [표 2] Saber의 파라미터, Type: 알고리즘 이름, l: 모듈 디멘션, T: 라운딩 파라미터, μ: 비밀 분산 값 파라미터.
표 [표 3] Saber 키 생성 과정.
표 [표 4] Saber CPA 암호화 과정.
표 [표 5] Saber CPA 복호화 과정.
표 [표 6] Dilithium의 파라미터, Type: 알고리즘 이름, NIST level: NIST 권장 보안 강도, (k, l): 행렬 크기, η: 샘플링 경계 값, β, ω: 거부 임계 값, |pk|: 공개키 크기(byte), |sig|: 서명 크기(byte), exp. 반복 횟수.
표 [표 7] Kyber의 파라미터, Type: 알고리즘 이름, l: 모듈디멘션, T: 라운딩 파라미터, μ: 비밀 분산 값 파라미터.
표 [표 8] SIKE 키 생성 과정.
표 [표 9] SIKE 암호화 과정.
표 [표 10] SIKE 복호화 과정.
표 [표 11] Rainbow의 파라미터. Lv: NIST 권장 보안 강도, |pk|: 공개키 크기(KB), |sk|: 비밀키 크기(KB), |sig|: 서명 크기(KB).
표 [표 12] Rainbow 키 생성 과정.
표 [표 13] Rainbow 서명 생성 과정.
표 [표 14] Rainbow 서명 검증 과정.
표 [표 15] UoV 키 생성 과정.
표 [표 16] UoV 서명 생성 과정.
표 [표 17] UoV 서명 검증 과정.
표 [표 18] ROLLO의 파라미터.
표 [표 19] Intel Core i3-1005G1 프로세서 상의 SIKEp503 구현 결과. op: 연산 종류, K: 키 생성, E: 암호화, D: 복호화.
표 [표 20] Intel Core i3-1005G1 프로세서 상의 SIKEp434, SIKEp610 구현 결과, op: 연산 종류, K: 키 생성, E: 암호화, D: 복호화.
표 [표 21] 마스크가 없는 Saber의 구현 결과 비교, LS: LightSaber, FS: FireSaber, cc: 클록 사이클(단위: k), st: 스택 크기, K: 키 생성, E: 암호화, D: 복호화.
표 [표 22] 마스크가 있는 Saber의 복호화 성능 비교.
표 [표 23] Cortex-A72와 Apple M1 프로세서 상에서의 Kyber, Saber, Dilithium 구현 결과 비교, K: 키 생성, E: 암호화, D: 복호화, (ref): 레퍼런스 Dilithium 코드, (단위: 클록 사이클, k)
표 [표 24] Intel Core i7-8850H(Coffee Lake) 상에서의 ROLLO-I[36], Intel Xeon E3-1220v5(Skylake) 상에서의 ROLLO⁺, BIKE[35]의 키 생성, 암호화, 복호화 과정에 대한 사이클 수 비교(ROLLO-II은 구현하지 않음, 단위: 클록 사이클).
표 [표 25] UoV와 Rainbow의 성능 비교, Lv: 보안 강도,성능평가 단위: 클록 사이클, k, 메모리 단위: bytes.

AI 본문요약
AI-Helper

문제 정의

본고에서는 양자컴퓨터의 발전과 양자내성암호의 최신 동향에 대해서 확인해 보도록 한다. 또한 한정된 자원 환경을 가지는 사물인터넷 기기 상에서의 양자내성암호 최적화 구현 기법에 대해서 확인해 보도록 한다.
본고에서는 NIST에서 진행하고 있는 양자내성 암호 표준화 공모전의 다양한 양자내성 암호에 대해서 확인해 보았다. 이와 더불어 해당 양자내성 암호의 복잡한 연산을, 자원이 한정된 사물인터넷 환경상에서 구현한 방법 및 구현 결과물의 성능을 확인해 보았다.
이를 해결하기 위해 양자내성암호에 대한 필요성이 증가하고 있으며 이에 대응하여 미국 국립표준기술연구소(NIST, National Institute of Standards and Technology)는 양자내성암호 표준화를 위한 공모전을 개최하여 진행 중에 있다. 본고에서는 양자컴퓨터의 발전과 양자내성암호의 최신 동향에 대해서 확인해 보도록 한다. 또한 한정된 자원 환경을 가지는 사물인터넷 기기 상에서의 양자내성암호 최적화 구현 기법에 대해서 확인해 보도록 한다.

제안 방법

Saber는 Fujisaki-Okamoto 변환을 응용하여 안전성을 확보하였고, 2n의 modulus를 사용하는 것으로 modular reduction 연산을 최적화하였다. 이는 Number Theoretic Transform (NTT)를 사용하지 않고서도 빠른 속도로 곱셈 연산을 할 수 있다.
기본적으로 UoV와 Rainbow는 가우에 안소거법을 사용하는데, 이때 사용되는 행렬의 크기가 매우 크기 때문에 연산에 소요되는 시간 또한 증가하게 된다. 본 연구에서는 Block Matrix Inversion 은 역행렬의 크기를 줄이는 것으로 연산에 소요되는 시간을 줄인다. 추가로 서명할 메시지가 주어지기 전에 일부 연산을 미리 계산해두는 사전 연산이 가능하다.
가우스 제거는 키 생성 및 캡슐화에서 샘플링된 요소의 가중치를 확인하는 데 유용하다. 일정한 시간에 가우스 제거를 수행하기 위해 [33]에 제시된 알고리즘을 일반화하여 최초로 도입하였다.
제안하는 기법은 Barret multiplication과 Montgomery multiplication을 NEON SIMD 명령어로 구현하는 데 중점을 두었다. 특히 사용하는 명령어의 숫자를 최소화하여 연산에 소요되는 시간을 줄였다.
Operand에 radix-251 표현을 사용하고 모듈식 축소를 위해 몽고메리의 곱셈 알고리즘을 채택한 Fp, Fp2 산술 연산을 위해 최적화된 라이브러리를 제시하고 있다. 해당 논문에서는 산술 연산의 두 인스턴스 지연 시간을 최소화하는 것과 limb-slicing 기법을 사용하여 8개 인스턴스의 처리량을 최대화하는 것을 포함하여 산술 라이브러리의 다양한 변형을 개발하였다. 몽고메리 곡선에서 병렬점 산술연산을 위한 기술을 설명하고 있으며, 벡터화된 아이 소지니 연산 및 키 캡슐화를 위한 구현 기법을 제시하고 있다.

이론/모형

Cortex-M3 상에서는 16비트, 32비트 두 가지 방식을 제안한다. 16비트 방식은 [28]의 방식을 하였다. 32 비트는NTT 연산 중 비밀 값이 포함될 때마다 연산속도와constant time을맞추기위해public matrix에 non-constant time 연산을 적용하였다.
Dilithium은 NIST 양자내성암호 공모전의 Round 3에 진출한 전자서명 알고리즘으로 격자기반 문제를 사용한다[8]. Dilithium은 Module Small Integer Solutions (M-SIS)와 M-LWE 문제에 기반한다. Dilithium에서 사용하는 모듈은 수식 3과 같으며, 수식 4는 Dilithium의 ring의 매개변수이다.
UoV의 원형인 Oil and Vinegar는 Jacques Patarin 이 디자인한 알고리즘으로, 다변수 기반의 전자서명 알고리즘이다. Oil and Vinegar는 단순한 구조를 지니고 빠른 연산속도를 제공하며 RAM 소모량이 적기 때문에 스마트카드와 같은 자원이 제한된 환경에서 원활하게 구현되었다 [15].
디코딩 알고리즘은 여러 벡터 공간의 교차점을 계산한다. 교집합을 계산하는 한 가지 방법은 Zassennhaus 알고리즘을 사용하는 것이다. 두 벡터 공간의 집합을 생성하는 입력에서 Zassenhaus 알고리즘은 생성집합에서 행렬을 만들고 가우스를 제거한다.
또한 Saber, Dilithium, 그리고Kyber 알고리즘별로 효율적인 NTT 연산을 위해 Butterfly 알고리즘을 NEON SIMD 명령어를 활용하여 구현하였다. 표23 은구현물의성능측정결과이다.
양자컴퓨터는 양자역학을 이용한 컴퓨터로 Feynman의 아이디어에서 비롯되었다[1]. 일반적인 컴퓨터가 전기신호를 사용하여 0과 1을 표현한다면, 양자컴퓨터는 0과 1의 중첩 상태를 사용한다.
Saber는 Matrix Vector Multiplication에 대해 NTT를 계산하는 과정에서 많은 시간이 소요된다. 제안하는 기법은 Multi-moduli NTT를 사용하여 연산 시간과 메모리 소요의 트레이드 오프를 가능하게 하였다.

성능/효과

본고에서는 NIST에서 진행하고 있는 양자내성 암호 표준화 공모전의 다양한 양자내성 암호에 대해서 확인해 보았다. 이와 더불어 해당 양자내성 암호의 복잡한 연산을, 자원이 한정된 사물인터넷 환경상에서 구현한 방법 및 구현 결과물의 성능을 확인해 보았다. 해당 구현 기법에 대한 최신 동향은 현재 국내에서 진행되고 있는 양자내성 암호 표준화 공모전에 적용하여 성능을 개선하는 데 활용 가능할 것으로 사료된다.

후속연구

해당 구현 기법에 대한 최신 동향은 현재 국내에서 진행되고 있는 양자내성 암호 표준화 공모전에 적용하여 성능을 개선하는 데 활용 가능할 것으로 사료된다. 본고에서 살펴본 바와 같이 빠르게 발전해가고 있는 양자컴퓨터와 양자내성 암호에 보다 관심을 가지고 지속적인 연구가 되어야 할 것으로 사료된다.
이와 더불어 해당 양자내성 암호의 복잡한 연산을, 자원이 한정된 사물인터넷 환경상에서 구현한 방법 및 구현 결과물의 성능을 확인해 보았다. 해당 구현 기법에 대한 최신 동향은 현재 국내에서 진행되고 있는 양자내성 암호 표준화 공모전에 적용하여 성능을 개선하는 데 활용 가능할 것으로 사료된다. 본고에서 살펴본 바와 같이 빠르게 발전해가고 있는 양자컴퓨터와 양자내성 암호에 보다 관심을 가지고 지속적인 연구가 되어야 할 것으로 사료된다.

참고문헌 (36)

R.P.Feynman, "Simulating physics with computers," International Journal of Theoretical Physics, 21, pp.467-488 Jun 1982.

상세보기
F.Arute, K.Arya, R.Babbush, D.Bacon, J.C.Bardin, R.Barends, and J.M.Martinis, "Quantum supremacy using a programmable superconducting processor," Nature, 574(7779), pp.505-510, Oct 2019.

상세보기
J.Chow, O.Dial and J.Gambetta, "IBM Quantum breaks the 100 qubit processor barrier," IBM Research Blog, Nov 2021.
S.Jaques, M.Naehrig, M.Roetteler, and F.Virdia, "Implementing Grover oracles for quantum key search on AES and LowMC," In Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Cham, pp.280-310, May 2020.
P.W.Shor, "Algorithms for quantum computation: discrete logarithms and factoring," In Proceedings 35th annual symposium on foundations of computer science, Ieee, pp.124-134, Nov 1994.
A.Abdulrahman, J.P.Chen, Y.J.Chen, V.Hwang, M.J. Kannwischer, and B.Y.Yang, "Multi-moduli NTTs for saber on Cortex-M3 and Cortex-M4," Cryptology ePrint Archive, Jul 2021.
J.P.D'Anvers, A.Karmakar, S.S.Roy, and F.Vercauteren. "Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM." International Conference on Cryptology in Africa, pp.282-305, 2018.
H.Becker, V.Hwang, M.J.Kannwischer, B.Y.Yang, and S.Y.Yang, "Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1," Cryptology ePrint Archive, Nov 2021.
D.Jao, and L.D.Feo, "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies," In International Workshop on Post-Quantum Cryptography, Springer, Berlin, Heidelberg, pp. 19-34, Nov 2011.
D. Jao, et al, "Supersingular Isogeny Key Encapsulation," NIST PQC Round 3 submission, Oct. 1, 2020.
H.Cheng, G.Fotiadis, J.Grossschadl, and P.Y.Ryan, "Highly vectorized SIKE for AVX-512," IACR Transactions on Cryptographic Hardware and Embedded Systems, pp.41-68, Feb 2022.
J.Ding, B.Y.Yang, C.H.O.Chen, M.S.Chen, and C.M.Cheng, "New differential-algebraic attacks and reparametrization of rainbow," International Conference on Applied Cryptography and Network Security. Springer, Berlin, Heidelberg, pp.242-257, 2008.
H.Kwon, H.Kim, M.Sim, W.K.Lee, and H.Seo, "Look-up the Rainbow: Efficient Table-based Parallel Implementation of Rainbow Signature on 64-bit ARMv8 Processors," Cryptology ePrint Archive, Jul 2021
K.A.Shim, S.Lee, and N.Koo, "Efficient Implementations of Rainbow and UOV using AVX2," IACR Transactions on Cryptographic Hardware and Embedded Systems, pp.245-269. Nov 2022.
J.Patarin, "The oil and vinegar signature scheme," In Dagstuhl Workshop on Cryptography September, Sep 1997.
A.Kipnis, and A.Shamir, "Cryptanalysis of the oil and vinegar signature scheme," In Annual international cryptology conference, Springer, Berlin, Heidelberg, pp.257-266, Aug 1998.
A.Kipnis, J.Patarin, and L.Goubin, "Unbalanced oil and vinegar signature schemes," In International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin, Heidelberg, pp.206-222, May 1999.
N.Courtois, L.Goubin, W.Meier, and J.D.Tacier, "Solving underdefined systems of multivariate quadratic equations," In International Workshop on Public Key Cryptography, Springer, Berlin, Heidelberg. pp.211-227, Feb 2002.
C.A.Melchor, N.Aragon, M.Bardet, S.Bettaieb, L.Bidoux, O.Blazy, J.C.Deneuville, P.Gaborit, A.Hauteville, A.Otmani, O.Ruatta, J.P.Tillich, and G.Zemor, "ROLLO-Rank-Ouroboros, LAKE& LOCKER," Submission to the NIST Post Quantum Standardization Process, Round 2, Apr 2019.
E.Gorla, "Rank-metric codes", Journal of Algebraic Combinatorics, 52(1), pp.1-19, 2020.

상세보기
T.Chou, and J.H. Liou, "A Constant-time AVX2 Implementation of a Variant of ROLLO," IACR Transactions on Cryptographic Hardware and Embedded Systems, vol 2022, no. 1, pp. 152-174. Nov 2021.
S.Y.Lee, G.S.Yoo, "Implementation of IoT Sensor Communication Platformusing ARM Cortex-M4," The Journal of Korean Association of Computer Education, 25(1), pp.283-285, 2021.
H.J.Seo, "High Speed Implementation of LEA on ARM Cortex-M3 processor," Journal of the Korea Institute of Information and Communication Engineering, 22(8), pp.1133-1138, 2018.

원문보기 상세보기
I.Lin, B.Jeff, and I.Rickard, "ARM platform for performance and power efficiency-Hardware and software perspectives," 2016 International Symposium on VLSI Design, Automation and Test (VLSI-DAT), pp.1-5, 2016.
H.J.Seo, P.Sanal, and W.K.Lee, "No Silver Bullet: Optimized Montgomery Multiplication on Various 64-Bit ARM Platforms," International Conference on Information Security Applications. Springer, Cham, pp.194-205, 2021.
C.Roberto, and J.Lopez. "Software implementation of SHA-3 family using AVX2," Simposio Brasileiro em Seguranca da Informacao e de Sistemas Computacionais 14 (2014), pp.330-333, 2014.
D.Kostic and S.Gueron. "Using the new VPMADD instructions for the new post quantum key encapsulation mechanism SIKE," 2019 IEEE 26th Symposium on Computer Arithmetic (ARITH), pp.215-218, 2019.
C.M.M.Chung, V.Hwang, M.J.Kannwischer, G.Seiler, C.J.Shih, and B.Y.Yang. "NTT multiplication for NTT- unfriendly rings new speed records for saber and NTRU on Cortex-M4 and AVX2," IACR Transactions on Cryptographic Hardware and Embedded Systems, pp.159-188, Feb 2021.
J.M.Bermudo Mera, A.Karmakar, and I.Verbauwhede. "Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice based cryptography," IACR Transactions on Cryptographic Hardware and Embedded Systems, pp.222-244, Feb 2020.
M.V.Beirendonck, J.P.D'Anvers, A.Karmakar, J.Balasch, and I.Verbauwhede. "A side-channel resistant implementation of SABER," ACM Journal on Emerging Technologies in Computing Systems (JETC), 17(2) pp.1-26, 2021.
D.T.Nguyen and K.Gaj. "Optimized software implementations of CRYSTALS-Kyber, NTRU, and Saber using NEON-based special instructions of ARMv8," Proceedings of the NIST 3rd PQC Standardization Conference (NIST PQC 2021). 2021.
P.Sanal, E.Karagoz, H.Seo, R.Azarderakhsh, and M.M.Kermani. "Kyber on ARM64: compact implementations of Kyber on 64-bit ARM Cortex-A processors," Cryptology ePrint Archive, Report 2021/561, 2021.
D.J.Bernstein, T.Chou, and Peter Schwabe. "Mcbits: fast constant- time code-based cryptography," Cryptographic Hardware and Embedded Systems - CHES 2013, pp.250-272, Springer, 2013.
C.Aguilar-Melchor, N.Aragon, S.Bettaieb, L.Bidoux, O.Blazy, J.C.Deneuville, P.Gaborit, G.Zemor, A.Couvreur, and A.Hauteville. "RQC," 2020. Available: https://pqc-rqc.org/.
M.S.Chen, T.Chou, and M.Krausz. "Optimizing BIKE for the Intel Haswell and ARM Cortex-M4", IACR Transactions on Cryptographic Hardware and Embedded Systems, pp.97-124, 2021.
C.Aguilar-Melchor, N.Aragon, E.Bellini, F.Caullery, R.H.Makarim, and C.Marcolla. "Constant time algorithms for ROLLO-I-128", SN Computer Science, 2(5), pp.1-19, 2021.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증