표제지
목차
국문요약 10
Abstract 12
제1장 서론 14
제2장 본론 16
제1절 차세대 암호 알고리즘 16
1.1. Ring-LWE 암호 18
1.2. 양자내성암호(Post-Quantum Cryptography) 20
1.3. 동형암호(Homomorphic Encryption) 22
제2절 NTT 알고리즘 27
2.1. NTT 다항식 곱셈기 28
2.2. FFT 알고리즘 29
2.3. 회전인자(Twiddle Factor) 31
2.4. Cooley-Tukey 알고리즘 31
2.5. Gentleman-Sande 알고리즘 35
제3절 모듈러 연산기 37
3.1. 모듈러 덧셈기/뺄셈기 38
3.2. 모듈러 곱셈기 41
제4절 NTT 아키텍처 46
4.1. 파이프라인 NTT 아키텍처 47
4.2. 제안하는 SDF NTT 아키텍처 48
4.3. 제안하는 MDF NTT 아키텍처 56
제5절 구현 및 성능 비교 62
5.1. 제안하는 NTT 아키텍처의 성능 분석 62
5.2. 기존 NTT 아키텍처와 비교 분석 70
5.3. 동형암호 아키텍처에 적용 시 성능 비교 분석 72
제3장 결론 74
참고문헌 76
표 1. 양자내성암호 공모전 3차 후보군 22
표 2. 세대별 완전동형암호 24
표 3. 동형암호표준화기구 제안 파라미터 25
표 4. 동형암호 CKKS Scheme의 파라미터 선정의 예 26
표 5. N=8 일 때 회전인자의 배열 34
표 6. 모듈러 덧셈기/뺄셈기의 구현 및 성능비교 39
표 7. Barrett modular reduction 기반 모듈러 곱셈기의 구현 및 성능비교 44
표 8. 기존 연구의 반복 방식과 파이프라인 방식 비교 48
표 9. 제안하는 NTT 아키텍처의 구현 및 성능 분석 63
표 10. 제안하는 INTT 아키텍처의 구현 및 성능분석 65
표 11. CPU 대비 연산속도 성능 비교 (N=2¹⁴ 일 때) 70
표 12. 기존 NTT 아키텍처와 제안하는 NTT 아키텍처의 성능 비교 71
표 13. CKKS 동형암호 암호화 아키텍처에 적용시 성능 비교 분석결과 73
그림 1. 격자의 예 및 격자 표현식 17
그림 2. Ring-LWE 암호 18
그림 3. NTT를 사용하는 양자내성암호 (CRYSTALS-Kyber) 21
그림 4. 기존의 클라우드(上), 동형암호를 적용한 클라우드 시스템(下) 23
그림 5. Cooley-Tukey 알고리즘의 Dataflow 32
그림 6. Cooley-Tukey Butterfly 33
그림 7. N=2m-1 NTT와 N=2m NTT의 관계도[이미지참조] 33
그림 8. Gentleman-Sande 알고리즘의 Dataflow 35
그림 9. Gentleman-Sande Butterfly 36
그림 10. N=2m-1 INTT와 N=2m INTT의 관계도[이미지참조] 36
그림 11. 모듈러 덧셈기의 블록도 38
그림 12. 모듈러 뺄셈기의 블록도 38
그림 13. Barrett modular reduction 기반 모듈러 곱셈기의 블록도 41
그림 14. DSP를 이용한 51비트 정수 곱셈기 43
그림 15. DSP를 이용한 64비트 정수 곱셈기 43
그림 16. 반복 방식 NTT 아키텍처 47
그림 17. 파이프라인 방식 NTT 아키텍처 47
그림 18. 제안하는 SDF NTT 아키텍처 블록도 48
그림 19. 제안한 NTT 아키텍처의 PE1 블록도 49
그림 20. 제안하는 NTT 아키텍처의 회전인자 메모리 구조 50
그림 21. 51비트 SDF NTT 아키텍처의 타이밍 다이어그램 (N=216)[이미지참조] 52
그림 22. 64비트 SDF NTT 아키텍처의 타이밍 다이어그램 (N=216)[이미지참조] 52
그림 23. 제안하는 SDF INTT 아키텍처 블록도 53
그림 24. 제안한 INTT 아키텍처의 PE1 블록도 53
그림 25. 51비트 SDF INTT 아키텍처의 타이밍 다이어그램 (N=216)[이미지참조] 55
그림 26. 64비트 SDF INTT 아키텍처의 타이밍 다이어그램 (N=216)[이미지참조] 55
그림 27. 제안하는 MDF NTT 아키텍처 블록도 56
그림 28. 제안한 NTT 아키텍처의 PE2 블록도 56
그림 29. 51비트 MDF NTT 아키텍처의 타이밍 다이어그램 (N=216)[이미지참조] 58
그림 30. 64비트 MDF NTT 아키텍처의 타이밍 다이어그램 (N=216)[이미지참조] 58
그림 31. 제안하는 MDF INTT 아키텍처 블록도 59
그림 32. 제안한 INTT 아키텍처의 PE2 블록도 59
그림 33. 51비트 MDF INTT 아키텍처의 타이밍 다이어그램 (N=216)[이미지참조] 61
그림 34. 64비트 MDF INTT 아키텍처의 타이밍 다이어그램 (N=216)[이미지참조] 61
그림 35. (a) SDF NTT 아키텍처의 시뮬레이션 결과(N=216일 때) (b) MDF NTT 아키텍처의 시뮬레이션 결과(N=2¹⁴일 때)[이미지참조] 67
그림 36. 51비트 SDF NTT와 Microsoft SEAL의 결과 비교(N=216일 때)[이미지참조] 67
그림 37. 64비트 SDF NTT와 Microsoft SEAL의 결과 비교(N=215일 때)[이미지참조] 68
그림 38. 51비트 MDF NTT와 Microsoft SEAL의 결과 비교(N=2¹⁴일 때) 68
그림 39. 64비트 MDF NTT와 Microsoft SEAL의 결과 비교(N=2¹³일 때) 69
그림 40. CKKS 암호화 아키텍처 72
그림 41. 제안하는 NTT를 이용한 CKKS 암호화 아키텍처 72