[논문]R-LWE 암호화를 위한 근사 모듈식 다항식 곱셈기 최적화

이재우; 김영민

doi:10.7471/ikeee.2022.26.4.736

R-LWE 암호화를 위한 근사 모듈식 다항식 곱셈기 최적화
Optimization of Approximate Modular Multiplier for R-LWE Cryptosystem 원문보기

전기전자학회논문지 = Journal of IKEEE, v.26 no.4, 2022년, pp.736 - 741

이재우 (School of Electronic & Electrical Eng. Hongik University) , 김영민 (School of Electronic & Electrical Eng. Hongik University)

초록
AI-Helper

격자 기반 암호화는 최악의 경우를 기반으로 한 강력한 보안, 비교적 효율적인 구현 및 단순성을 누리기 때문에 포스트 양자 암호화 방식 중 가장 실용적인 방식이다. 오류가 있는 링 학습(R-LWE)은 격자 기반 암호화(LBC)의 공개키암호화(Public Key Encryption: PKE) 방식이며, R-LWE의 가장 중요한 연산은 링의 모듈러 다항식 곱셈이다. 본 논문은 R-LWE 암호 시스템의 중간 보안 수준의 매개 변수 집합을 대상으로 하여 근사 컴퓨팅(Approximate Computing: AC) 기술을 기반으로 한 모듈러 곱셈기를 최적화하는 방법을 제안한다. 먼저 복잡한 로직을 간단하게 구현하는 방법으로 LUT을 사용하여 근사 곱셈 연산 중 일부의 연산 과정을 생략하고, 2의 보수 방법을 활용하여 입력 데이터의 값을 이진수로 변환 시 값이 1인 비트의 개수를 최소화하여 필요한 덧셈기의 개수를 절감하는 총 두 가지 방법을 제안한다. 제안된 LUT 기반의 모듈식 곱셈기는 기존 R-LWE 모듈식 곱셈기 대비 속도와 면적 모두 9%까지 줄어들었고, 2의 보수 방법을 적용한 모듈식 곱셈기는 면적을 40%까지 줄이고 속도는 2% 향상되는 것으로 나타났다. 마지막으로 이 두 방법을 모두 적용한 최적화된 모듈식 곱셈기의 면적은 기존대비 43%까지 감소하고 속도는 10%까지 감소하는 것으로 나타났다.

Abstract ▼ AI-Helper

Lattice-based cryptography is the most practical post-quantum cryptography because it enjoys strong worst-case security, relatively efficient implementation, and simplicity. Ring learning with errors (R-LWE) is a public key encryption (PKE) method of lattice-based encryption (LBC), and the most important operation of R-LWE is the modular polynomial multiplication of rings. This paper proposes a method for optimizing modular multipliers based on approximate computing (AC) technology, targeting the medium-security parameter set of the R-LWE cryptosystem. First, as a simple way to implement complex logic, LUT is used to omit some of the approximate multiplication operations, and the 2's complement method is used to calculate the number of bits whose value is 1 when converting the value of the input data to binary. We propose a total of two methods to reduce the number of required adders by minimizing them. The proposed LUT-based modular multiplier reduced both speed and area by 9% compared to the existing R-LWE modular multiplier, and the modular multiplier using the 2's complement method reduced the area by 40% and improved the speed by 2%. appear. Finally, the area of the optimized modular multiplier with both of these methods applied was reduced by up to 43% compared to the previous one, and the speed was reduced by up to 10%.

주제어

표/그림 (6)

그림 Fig. 1. The hardware design of approximate modular multiplier. 그림 1. 근사화 모듈식 곱셈기의 하드웨어 설계도
그림 Fig. 2. The approximate modular multiplier proposed as LUT-based Method. 그림 2. LUT 기반의 방법으로 제안된 근사화 모듈식 곱셈기
표 Table 1. Bit position of input data with the same result. 표 1. 결과값이 동일한 입력 데이터의 규칙
그림 Fig. 3. Comparison of LUT assignment results for existing modular (a) and modular multiplier with two optimization methods in Artix-7 FPGA device (b-d). 그림 3. FPGA Artix-7 장치에서 두 가지 최적화 방법을 적용한 (b-d)와 기존 모듈식 곱셈기에 대한 LUT 할당 결과 비교
표 Table 2. Result of proposed modular multiplier in FPGA. 표 2. FPGA에서의 제안된 모듈식 곱셈기 결과값
표 Table 3. The result of modules synthesized with TSMC 0.18um standard cells. 표 3. TSMC 0.18um 표준 셀로 모듈을 합성한 결과

참고문헌 (15)

Mavroeidis, Vasileios, et al., "The impact of？quantum computing on present cryptography,"？IJACSA, vol.9, no.3, pp.405-414, 2018.？DOI: 10.48550/arXiv.1804.00200
Nejatollahi, Hamid, et al., "Post-quantum？lattice-based cryptography implementations: A？survey," ACM Computing Surveys (CSUR), vol.1,？no.1, pp.1-41, 2019. DOI: 10.1145/3292548

상세보기
Liu, Dongsheng, et al., "A resource-efficient？and side-channel secure hardware implementation？of ring-LWE cryptographic processor," IEEE？Transactions on Circuits and Systems I: Regular？Papers, vol.66, no.4, pp.1474-1483, 2018.？DOI: 10.1109/TCSI.2018.2883966

상세보기
Lyubashevsky, Vadim, Chris Peikert, and？Oded Regev, "On ideal lattices and learning with？errors over rings," Annual international conference？on the theory and applications of cryptographic？techniques, pp.1-23, 2010.？DOI: 10.1007/978-3-642-13190-5_1

상세보기
Poppelmann, Thomas, and Tim Guneysu,？"Towards efficient arithmetic for lattice-based？cryptography on reconfigurable hardware," International conference on cryptology and information？security in Latin America. Springer, Lecture Notes？in, pp.139-158, 2012.？DOI: 10.1007/978-3-642-33481-8_8

상세보기
Poppelmann, Thomas, and Tim Guneysu,？"Area optimization of lightweight lattice-based？encryption on reconfigurable hardware," IEEE？international symposium on circuits and systems？(ISCAS). IEEE, pp.2796-2799, 2014.？DOI: 10.1109/ISCAS.2014.6865754
Khalid, Ayesha, et al., "Lattice-based cryptography？for IoT in a quantum world: Are we ready?," IEEE 8th international workshop on advances in？sensors and interfaces (IWASI), pp.194-199, 2019.？DOI: 10.1109/IWASI.2019.8791343
Aysu, Aydin, Cameron Patterson, and Patrick？Schaumont, "Low-cost and area-efficient FPGA？implementations of lattice-based cryptography,"？IEEE international symposium on hardware-oriented？security and trust (HOST), pp.81-86, 2013.？DOI: 10.1109/HST.2013.6581570
Zhang, Xinmiao, and Keshab K. Parhi. "Reduced-complexity modular polynomial multiplication？for R-LWE cryptosystems," IEEE International？Conference on Acoustics, Speech and Signal？Processing (ICASSP), pp.7853-7857, 2021.？DOI: 10.1109/ICASSP39728.2021.9414005
Liu, Zhe, et al., "Efficient Ring-LWE encryption？on 8-bit AVR processors," International Workshop？on Cryptographic Hardware and Embedded Systems.？Springer, pp.663-682, 2015.？DOI: 10.1007/978-3-662-48324-4_33
Liu, Weiqiang, et al., "Optimized schoolbook？polynomial multiplication for compact lattice-based？cryptography on FPGA," IEEE Transactions on？Very Large Scale Integration (VLSI) Systems,？vol.27, no.10, pp.2459-2463, 2019.？DOI: 10.1109/TVLSI.2019.2922999

상세보기
Kundi, Dur E. Shahwar, et al., "AxMM: Area？and power efficient approximate modular multiplier？for R-LWE cryptosystem," 2020 IEEE International？Symposium on Circuits and Systems (ISCAS),？pp.1-5, 2020.？DOI: 10.1109/ISCAS45731.2020.9180839
Zhang, Yuqing, et al., "An efficient and？parallel R-LWE cryptoprocessor," IEEE Transactions？on Circuits and Systems II: Express Briefs, vol.67,？no.5, pp.886-890, 2020.？DOI: 10.1109/TCSII.2020.2980387

상세보기
Barrett, Paul, "Implementing the Rivest Shamir？and Adleman public key encryption algorithm on？a standard digital signal processor," Conference？on the Theory and Application of Cryptographic？Techniques. Springer, pp.311-323, 1986.？DOI: 10.1007/3-540-47721-7_24
Roy, Sujoy Sinha, et al., "Compact ring-LWE？cryptoprocessor," International workshop on？cryptographic hardware and embedded systems.？Springer, pp.371-391, 2014.？

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

연합인증