[논문]동형암호 가속 하드웨어 개발 기술 동향 분석

남기빈; 정헌희; 백윤흥

동형암호 가속 하드웨어 개발 기술 동향 분석 원문보기

情報保護學會誌 = KIISC review, v.33 no.5, 2023년, pp.47 - 55

남기빈 (서울대학교 전기정보공학부, 반도체공동연구소) , 정헌희 (서울대학교 전기정보공학부, 반도체공동연구소) , 백윤흥 (서울대학교 전기정보공학부, 반도체공동연구소)

초록
AI-Helper

동형암호는 암호화 상태에서도 연산이 가능하다는 특징을 지니고 있어 매우 유망한 프라이버시 보호 기술로 알려져 있다. 하지만 이런 장점에도 불구하고 아직 활발히 활용되지 못하고 있는데, 이는 매우 느린 연산 성능이라는 단점 때문이다. 이런 단점을 극복하기 위해서 동형암호 가속을 목표로 하는 많은 연구들이 수행되었으나, 아직 보편화 수준에 도달하지 못했으며, 특히 각 연구들이 독립적으로 산개되어 시너지효과를 누리지 못하고 있다는 특징을 보여주고 있다. 본 논문은 산업/학계의 다양한 동형암호 가속 연구들을 분류, 소개하며, 이들간의 관계를 분석하여 시너지 효과를 누릴 수 있는 가이드라인을 제시한다.

표/그림 (6)

그림 [그림 1] BGV, BFV, CKKS 쳬계의 암호문 형태[10]
표 [표 1] 동형암호 보안수준(λ)과 다항식/벡터의 차수(N)에 따른 권장된 항의 계수의 길이(q)
그림 [그림 2] Radix-2 Cooley Tukey 알고리즘을 이용한 FFT 연산 과정[12]
그림 [그림 3] EVA 컴파일러가 x²+x를 연산하는 다양한 방법. (a) 기본 (b) 항상 rescale 우선 (c)scale 맞춤 우선 방법[15]
표 [표 2] Microsoft SEAL을 활용한 N=8192일 때 CKKS 체계의 여러 하위함수들의 연산 시간
그림 [그림 4] Radix-4 FFT 단위 연산

AI 본문요약
AI-Helper

문제 정의

본 논문은 최근 동형암호 가속 연구들에 대한 동향을 분석, 이들을 연계하여 시너지 효과를 내며 가속기를 설계할 수 있는 방향을 제시했다. 특히 현재 다양한 분야에서 이루어지고 있는 연구들이 독립적으로 산개되어있는 상황에서, 각 연구들이 서로 시너지 효과를 내기 위해서는 HW 특성을 고려하여 메모리 크기, datapath의 사이즈 등 다양한 요소들을 고려하고, 보다 일반적인 보편화된 동형암호 가속기 설계로 이어지는 것의 필요성을 제안한다.
본 논문은 동형암호 가속 연구들의 동향을 분석, 분류 하는 구성으로 이루어져 있다. 특히, 본 논문은 수학적 접근과 HW의 특성을 활용한 접근 등 독립적으로 산개되어있는 연구결과들 중 시너지 효과를 일으켜 더욱 가속을 이룰 수 있는 방향으로 진행할 수 있도록 가이드라인을 제시하는 것을 목표로 한다.

제안 방법

본 논문은 동형암호 가속 연구들의 동향을 분석, 분류 하는 구성으로 이루어져 있다. 특히, 본 논문은 수학적 접근과 HW의 특성을 활용한 접근 등 독립적으로 산개되어있는 연구결과들 중 시너지 효과를 일으켜 더욱 가속을 이룰 수 있는 방향으로 진행할 수 있도록 가이드라인을 제시하는 것을 목표로 한다.
본 장은 기존 동형암호 가속 연구들의 접근법과 결과를 수학/알고리즘 중심 접근법, 컴파일러 중심 접근법, 그리고 HW 가속기 구현 연구로 분류하여 소개한다.

이론/모형

요소 단위 병렬처리의 경우, 한 연산기가 들고 있는 데이터를 재사용하기 어렵다는 단점이 있다. Cooley Tukey 방식의 FFT 연산 수행을 생각해보자. 한 stage에서 하나의 butterfly operation에 사용된 데이터는 다음 stage에서 다른 연산기에 필요하기에 데이터 이동이 필요하다.

성능/효과

첫째로, 기존 modular 연산을 수행하는 정수 연산기들은 FFT에서 활용하지 못하기 때문에, 별도의 연산기를 두어야 하여 resource 측면에서 낭비로 바라볼 수 있다. 둘째로, NTT를 사용할 경우, modular reduction이 필요한데, 이는 CPU나 GPU의 경우 매우 오래 걸리는 연산이며, FPGA나 ASIC으로 별도의 커스텀 연산기를 사용한다 하더라도 해당 연산기가 매우 많은 resource를 필요로 한다. 특히, 주어진 상수에 대한 reduction이 아닌 다수의 수들에 대한 reduction, 즉 나눗셈이 필요한 경우, CPU 혹은 GPU와 동일한 수준의 연산 부하가 발생한다.
이 하위함수들에 대해 중요한 점은 크게 두가지다. 첫째, 각 하위함수들은 매우 많은 수의 다항식 연산들로 이루어져있다. 예를들어, 표준 파라미터를 활용한 TFHE의 bootstrapping은 blind rotation이라는 다른 하위함수를 630번 반복 수행해야 하며, 각 blind rotation은 최소 12번의 암호문 곱셈을 필요로 한다.
다른 예시로는 Cooley Tukey 접근을 활용한 FFT 연산의 다양한 내면을 예시로 들 수 있다. 첫째로, 기존 modular 연산을 수행하는 정수 연산기들은 FFT에서 활용하지 못하기 때문에, 별도의 연산기를 두어야 하여 resource 측면에서 낭비로 바라볼 수 있다. 둘째로, NTT를 사용할 경우, modular reduction이 필요한데, 이는 CPU나 GPU의 경우 매우 오래 걸리는 연산이며, FPGA나 ASIC으로 별도의 커스텀 연산기를 사용한다 하더라도 해당 연산기가 매우 많은 resource를 필요로 한다.

후속연구

본 논문은 최근 동형암호 가속 연구들에 대한 동향을 분석, 이들을 연계하여 시너지 효과를 내며 가속기를 설계할 수 있는 방향을 제시했다. 특히 현재 다양한 분야에서 이루어지고 있는 연구들이 독립적으로 산개되어있는 상황에서, 각 연구들이 서로 시너지 효과를 내기 위해서는 HW 특성을 고려하여 메모리 크기, datapath의 사이즈 등 다양한 요소들을 고려하고, 보다 일반적인 보편화된 동형암호 가속기 설계로 이어지는 것의 필요성을 제안한다. 본 논문에서 제안한 방안을 바탕으로 다양한 연구들의 결과들이 합쳐진 가속기 연구가 이루어질 수 있었으면 하는 바램과 함께 본 논문을 마친다.

참고문헌 (22)

Gentry, Craig. "Fully homomorphic encryption using ideal lattices." Proceedings of？the forty-first annual ACM symposium on？Theory of computing. 2009.
Rivest, Ronald L., Len Adleman, and Michael L.？Dertouzos. "On data banks and privacy homomorphisms." Foundations of secure computation 4.11 (1978): 169-180.
Rivest, Ronald L., Adi Shamir, and Leonard？Adleman. "A method for obtaining digital signatures and public-key cryptosystems."？Communications of the ACM 21.2 (1978):？120-126.

상세보기
ElGamal, Taher. "A public key cryptosystem and a signature scheme based on discrete？logarithms." IEEE transactions on information？theory 31.4 (1985): 469-472.
Paillier, Pascal. "Public-key cryptosystems based on composite degree residuosity classes."？International conference on the theory and applications of cryptographic techniques. Berlin,？Heidelberg: Springer Berlin Heidelberg, 1999.
Brakerski, Zvika, Craig Gentry, and Vinod？Vaikuntanathan. "(Leveled) fully homomorphic？encryption without bootstrapping." ACM？Transactions on Computation Theory (TOCT)？6.3 (2014): 1-36.
Fan, Junfeng, and Frederik Vercauteren.？"Somewhat practical fully homomorphic？encryption." Cryptology ePrint Archive (2012).
Cheon, Jung Hee, et al. "Homomorphic encryption for arithmetic of approximate numbers."？Advances in Cryptology-ASIACRYPT 2017:？23rd International Conference on the Theory and？Applications of Cryptology and Information？Security, Hong Kong, China, December 3-7,？2017, Proceedings, Part I 23. Springer？International Publishing, 2017.
Chillotti, Ilaria, et al. "TFHE: fast fully homomorphic encryption over the torus." Journal of？Cryptology 33.1 (2020): 34-91.

상세보기
Nam, Kevin, et al. "Partially Homomorphic？Encryption HW accelerator." Proceedings of the？Korea Information Processing Society？Conference. Korea Information Processing？Society, 2020.
Albrecht, Martin, et al. "Homomorphic encryption standard." Protecting privacy through？homomorphic encryption (2021): 31-62.
Lopes, Joao & Sousa, Jose. (2017). Fast Fourier？Transform on the Versat CGRA.
Chen, Hao, Kim Laine, and Rachel Player.？"Simple encrypted arithmetic library-SEAL v2.？1." Financial Cryptography and Data Security:？FC 2017 International Workshops, WAHC,？BITCOIN, VOTING, WTSC, and TA, Sliema,？Malta, April 7, 2017, Revised Selected Papers？21. Springer International Publishing, 2017.
Dathathri, Roshan, et al. "CHET: an optimizing？compiler for fully-homomorphic neural-network？inferencing." Proceedings of the 40th ACM？SIGPLAN conference on programming language？design and implementation. 2019.
Dathathri, Roshan, et al. "EVA: An encrypted？vector arithmetic language and compiler for efficient homomorphic computation." Proceedings？of the 41st ACM SIGPLAN conference on programming language design and implementation.？2020.
Jones, Douglas L. "Radix-4 FFT Algorithms."？Connexions module: m12027 (2006).
Nam, Kevin, et al. "Accelerating n-bit operations over tfhe on commodity cpu-fpga." Proceedings？of the 41st IEEE/ACM International Conference on Computer-Aided Design. 2022.
Gupta, Saransh, Rosario Cammarota, and Tajana？Simunic Rosing. "Memfhe: End-to-end computing with fully homomorphic encryption in？memory." ACM Transactions on Embedded？Computing Systems (2022).
Samardzic, Nikola, et al. "F1: A fast and programmable accelerator for fully homomorphic？encryption." MICRO-54: 54th Annual？IEEE/ACM International Symposium on Microarchitecture. 2021.
Samardzic, Nikola, et al. "Craterlake: a hardware？accelerator for efficient unbounded computation on encrypted data." Proceedings of the 49th？Annual International Symposium on Computer？Architecture. 2022.
Jiang, Lei, Qian Lou, and Nrushad Joshi.？"Matcha: A fast and energy-efficient accelerator？for fully homomorphic encryption over the？torus." Proceedings of the 59th ACM/IEEE？Design Automation Conference. 2022.
Geelen, Robin, et al. "BASALISC:？Programmable Hardware Accelerator for BGV？Fully Homomorphic Encryption." IACR？Transactions on Cryptographic Hardware and？Embedded Systems (2023): 32-57.

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

연합인증