동형암호에 대한 리서치 (3) - BGV(Brakerski-Gentry-Vaikuntanathan) 가속기를 위하여

BGV 가속기 - 동형암호 BGV 방법론을 이용한 암호화 연산에 대한 FPGA를 통한 하드웨어 가속

 

동향에 대해 설명되어있는 문서중 이 문서가 가장 자세하다.

[0] https://ettrends.etri.re.kr/ettrends/193/0905193001/001-012_%EB%B0%95%EC%84%B1%EC%B2%9C_193%ED%98%B8.pdf

 

이 문서는 다음 네개의 문서를 참고문헌으로 레퍼런스 하고있다.

[1] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9194003 

[2] https://arxiv.org/pdf/2007.01648.pdf

[3] https://eprint.iacr.org/2016/421.pdf

[4] https://arxiv.org/ftp/arxiv/papers/1909/1909.09731.pdf

 

각 5개 보고서 또는 논문의 목표를 아주 간략히 살펴보자면

[0] FHE 시스템에 적합한 ALU(FPGA 포함)가 아닌 연산 하드웨어를 클라우드 서버상에서 가능하게 개발중.

[1] FHE 연산의 가속을 위해 병렬처리된 FPGA 가속기를 사용했으며 CPU 대비 향상시켰다.

[2] 연산력증대를 위해 하드웨어뿐 아닌 네트워크 클라우드를 이용하기도 하는데 여기서 보안처리를 해준다.

[3] 연산과정에서 소수의 소수점문제를 단순하게 만든 스킴을 통해 연산량 자체를 줄여버리겠다.

[4] FHE 연산을 위한 HEAX 라는 아키텍처를 제시하는데, 격자기반 암호화시스템에서 많이 쓰이는 NTT 개념을 활용.

 

내가 무의식적으로 찾고 있던건 FHE에서 NTT의 포지션에 해당하는 개념인듯하다.

그쪽에 초점을 두고 5개의 문서를 더 깊게 읽어봐야겠다.

 

[4] CKKS를 위한 하드웨어가 없어서 만들었는데 non-CKKS FHE를 위한것도 필요하다. 

 

 

지금 포지션을 잘 잡아야 하는게, 마이크로소프트의 박사 연구원 4명이 시간투자를 엄청해서 만든 결과물을

FPGA 공부를 얼마 하지 않은 주니어 of 주니어가 감히 모방할 생각조차 하면 안된다.

그렇기 때문에, 여기서 내가 배웠던 '하드웨어 가속기 구조' 와 'HEAX 아키텍처'를 비교하며 최소 모듈을 뽑아야 한다.

그 모듈은 분명 연산단위가 될것이다. (그리고 이것뿐 아니라 AXI 써야하기 때문에 ... ㅠ_ㅠ 이것부터 벽인데)

 

자. 

암호데이터 덧셈연산. 

이거 하나만 하는것도 꽤 묵직할 것 같다. 

이것이 가장 시작하기 좋을 주제일 것 같아 보인다.

 

 

저 덧셈에 대해 파보기전에

마음을 조금 가볍게 먹기 위해

(자판기나 만들까, 걍 인공지능할까)

인공지능 관련 캡스톤을 조금 더 구경해보고온다.

 

줄여서 생각할 수 있게 되었다. 이것만 하면 된다.

- FHE 시스템 내부에서 FCL에 해당하는 유사한 걸 찾는다.

- 구현된 가속기를 그에 맞게 일부 변형한다.

{BGV 동형암호 스킴의 덧셈 연산에 대한 FPGA HW 가속}

{BGV 동형암호 스킴의 곱셈 연산에 대한 FPGA HW 가속}

{BGV 동형암호 스킴의 암호화/복호화에 대한 FPGA HW 가속}

- 한동대 포폴과 같이 구성하기 위해 시스템적 요소를 추가한다.

 

 

다시 덧셈에 대해 살펴본다.

 

이 깃을 살펴보자.

https://github.com/google/fully-homomorphic-encryption

GitHub - google/fully-homomorphic-encryption: Libraries and tools to perform fully homomorphic encryption operations on an encry

The FHE C++ Transpiler is a general purpose library that converts C++ into FHE-C++ that works on encrypted input.

whitepaper

 

Encrypt(x, key);

x.Decrypt(key);

만 쓰면 되게끔 라이브러리화 시키는 구글이 미친 것 같다.

 

 

지금 여기서 fthe/fthe.h는 visibility를 통해 opensource로 공개되지는 않아있는듯하다. 아닌가 내가 못찾는 것인가.

 

라이브러리에 대한 코드레벨 말고 개발자문서를 참고할 수 있도록 해보자.

개발자문서는 없다.

 

다시 문서 [0]을 보다가

HomAdd 모듈을 보게 되었다.

(이제 생긴 리터러시로 문서 0을 조금 더 볼수 있을듯하다.)

 

다시 문서를 읽어보니

[0] 동향 정리

[1] BGV 최적화 FHE 가속

[2] BFV 스킴용 FHE 가속 + 클라우드

[3] CKKS

[4] CKKS를 최적화 FHE 가속

다음과 같이 요약될수도 있을듯하다. 

(위에선 개념이 조금 덜잡힌 상태였다.)

 

[1] 에서 이 표를 보고 있었는데

BGV Operation은 이 문서에 나오지 않을듯하다.

 

BGV의 논문은 다음과 같다.

 

Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014). (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3), 13.

https://eprint.iacr.org/2011/277.pdf

 

내가 지금 해야할 일

Encryption, Decryption 연산에 대하여 C로 구현할 수 있을 정도로 연산을 이해한다.

 

연산의 목록

Key Generation(Secret Key, Public Key, Evaluation Key),

Encryption,

Decryption,

Homomorphic Evaluation(Homomorphic Mult./Add./Sub.),

Key Switching,

Modulus Switching

 

함수의 목록

• ParamGen(λ, P, K, B) 

• SecKeygen(params) 

• PubKeygen(params) 

• SecEncrypt(SK, M) 

• PubEncrypt(PK, M) 

• Decrypt(SK, C) 

 

SK 그리고 PK는 동적으로 Generation 되어야하지만

그것을 무시하고 상수취급할 수 있는지 가정하도록 해보자.

Encrypt와 Decrypt로 뭉탱이로 볼 수 있도록 하자.

 

 

우선 이중에 더 간단해보이는 복호화 작업을 먼저 보자.

 

 

ring element, mapping 과정에서 막힌다. 이 두개념을 찾자.

 

찾다보니, RSA 알고리즘의 프레임워크처럼 단순화시킬 필요성이 느껴진다.

분명 이런꼴로 나오게 될 것이다. 

 

메시지 M (=input/output)

공개키 s

비밀키 ...

 

다시 [1] 논문에서 이 부분과 관련된 리소스를 찾는다.

몇개가 보이기는 하는데, 이 논문의 구조가 너무 복잡하고 추가개념이 너무 많아서 

저 부분과 관련해서 간결하게 곱하고 나누고 modular 연산하는 수준으로 보이지는 않는다. 

 

위키피디아로 돌아온다.

 

논문이 두개다.

1.  Z. Brakerski, C. Gentry, and V. Vaikuntanathan. Fully Homomorphic Encryption without Bootstrapping, In ITCS 2012
2. ↑ Z. Brakerski and V. Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In FOCS 2011 (IEEE)

 

내가 찾았던 내용이 위키에서 나온게 아닌가보다 다른곳에서 다시 찾자.

그리고 이 내용에 대해서 공부를 할 필요도 있다라는 것만 인지하고 

 

아래표에서 어떻게 스쿼싱과 부트스트랩핑이 일어나는지에 대해 이해해야한다.

 

(해시위키다 ㅇㅇ)

 

http://wiki.hash.kr/index.php/%EB%8F%99%ED%98%95%EC%95%94%ED%98%B8

동형암호 - 해시넷

 

 

잠시 다시 이 '재부팅 연산'을 살펴보도록 하자.

재부팅연산은 bootstraping이며 개념증명(poc) 과정이다.

 

 

개념증명이 무엇인지 이해하고

사람들이 이걸 '벤치마크'로 어떻게 활용하는지도 보는것도 좋을듯하다.

왜냐하면 결국 이걸 지금 30분에서 4분으로 줄이는데 성공한 것이니깐 말이다.

 

(그나저나 이글 꽤 좋다. http://sti.kostat.go.kr/window/2021a/main/2021_sum_07.html)

 

 

개념증명이란 무엇인가?

Proof of Concept

(Business Develop 관점에서 PoC 말고!)

 

AES-128

https://www.techtarget.com/searchsecurity/definition/Advanced-Encryption-Standard

What is the Advanced Encryption Standard (AES)? Definition from SearchSecurity

 

AES128 연산을 기준으로하여 1bit 연산을 하는 것. 128말고.

그 연산이 어떻게 구현되는지를 이해할 수 있는 레벨까지 가야한다는 것

 

암호학 관점에서 PoC와 크립토씬에서의 ZKP는 학문적으로 어느 지점에서 만나는가?