완전동형암호로 암호화된 데이터에 적합한 산술 가산기의 구현 및 성능향상에 관한 연구
Implementation and Performance Enhancement of Arithmetic Adder for Fully Homomorphic Encrypted Data
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본 연구에서는 완전동형암호로 암호화된 데이터에 적용할 수 있는 가산기 및 다수개의 데이터를 가산할 때 적용할수 있는 성능이 향상된 가산 방법을 제안한다. 제안 산술 가산기는 기존의 하드웨어 기반의 산술 가산기 중 최적 회로단계(level)를 가지는 Kogge-Stone Adder 방법을 기반으로 하며, 완전동형암호가 제공하는 암호학적SIMD(Single Instruction for Multiple Data) 기법을 적용하기에 적합하게 설계되었다. 제안한 다수 가산 방법은 완벽한 가산 결과를 보장하는 Kogge-Stone Adder를 반복적으로 사용하여 다수개의 데이터를 가산하지 않고, 3 개 이상의 수를 더해야 할 경우, Full-Adder를 이용하여 3개의 수를 최종 C(Carry-out)과 논리합의 결과인S(Sum) 의 두 개로 줄인다. 이러한 과정을 반복하여 최종적으로 두 개의 수를 더할 경우에만 Kogge-Stone Adder 를 사용하여 가산하는 방법이다. 제안 방법은 더하고자 하는 데이터의 개수가 많아질수록 성능이 비약적으로 향상되었고, 이를 실험을 통해 검증한다.
Abstract
In this paper, we propose an adder that can be applied to data encrypted with a fully homomorphic encryption scheme and an addition method with improved performance that can be applied when adding multiple data. The proposed arithmetic adder is based on the Kogge-Stone Adder method with the optimal circuit level among the existing hardware-based arithmetic adders and suitable to apply the cryptographic SIMD (Single Instruction for Multiple Data) function on encrypted data. The proposed multiple addition method does not add a large number of data by repeatedly using Kogge-Stone Adder which guarantees perfect addition result. Instead, when three or more numbers are to be added, three numbers are added to C (Carry-out) and S (Sum) using the full-adder circuit implementation. Adding with Kogge-Stone Adder is only when two numbers are finally left to be added. The performance of the proposed method improves dramatically as the number of data increases.
참고문헌 (25)
- T. Yu, "Secure data management in decentralized systems", Springer Science and Business Media, 33, pp.355~380 (2007), Springer Press
- C. Gentry, "Fully homomorphic encryption using ideal lattices", Proceedings of the 41st ACM Symposium on Theory of Computing, pp.169~178 (2009)
- A. Chatterjee, "Accelerating sorting of fully homomorphic encrypted data", the 14th International Conference on Cryptology in India, LNCS 8250, pp.262~273 (2013)
- G. S. Cetin, "Low depth circuits for efficient homomorphic sorting", IACR ePrint Arch, ~ (2015)
- J. H. Cheon, "Optimized search-and-compute circuits and their application to query evaluation on encrypted data", IEEE Transactions on Information Forensics and Security, 11(1), pp.188~199 (2016)
- S. Knowles, "A family of adders", Proceedings of the 14th IEEE Symposium on Computer Arithmetic, pp.277~281 (2001)
- N. P. Smart, "Fully homomorphic SIMD operations", Designs, codes and cryptography, 71(1), pp.57~81 (2014)
- N. Sureka, "An efficient high speed wallace tree multiplier", International Conference on Information Communication and Embedded Systems, pp.1023~1026 (2013)
- Z. Brakerski, "(Leveled)fully homomorphic encryption without bootstrapping", ACM Transactions on Computation Theory, 6(3), pp.309~325 (2014)
- "Design and implementation of a homomorphic encryption library" (2013)[URL]
- S. Goldwasser, "Probabilistic encryption and how to play mental poker keeping secret all partial information", Proceedings of the 14th annual ACM symposium on Theory of computing, pp.365~377 (1982)
- 정명인, "완전동형암호 기술의 연구 동향", 한국콘텐츠학회 논문지, 13(8), pp.36~43 (2013), 한국콘텐츠학회[DOI]
- 정성재, "클라우드 보안 위협요소와 기술 동향 분석", 보안공학연구논문지, 10(2), pp.199~212 (2013), 보안공학연구지원센터
- T. E. Gamal, "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE transactions on information theory, 31(4), pp.469~472 (1985)
- P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes", International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 1592, pp.223~238 (1999)
- D. Boneh, "Evaluating 2-DNF formulas on ciphertexts", Proceedings of Theory of Cryptography Conference, LNCS 3378, pp.325~341 (2005)
- R. A. Popa, "CryptDB : protecting confidentiality with encrypted query processing", Proceedings of the 23rd ACM Symposium on Operating Systems Principles, pp.85~100 (2011)
- S. Tu, "Processing analytical queries over encrypted data", Proceedings of the VLDB Endowment, 6(5), pp.289~300 (2013)
- T. Han, "Fast area-efficient VLSI adders", IEEE 8th Symposium on Computer Arithmetic, pp.49~56 (1987)
- J. Kaur, "Analysis of 16 &32 bit kogge stone adder using xilinx tool", Journal of Environmental Science, Computer Science and Engineering &Technology, vol. 3. no. 3, pp. 1639-1644, Jun, 3(3), pp.1639~1644 (2014)
- K. Knauer, "Ripple-carry adder", U.S. Patent No. 4,839,849, ~ (1989)
- E. H. J. Persoon, "Full adder circuit", U.S. Patent No. 5,117,386, ~ (1992)
- P. Kogge, "A parallel algorithm for the efficient solution of a general class of recurrence equations", IEEE Transactions on Computers, C-22(8), pp.786~793 (2009)
- C. Babbage, "Passages from the life of a philosopher", pp.59~63 (1864), Cambridge University Press
- R. Brent, "A regular layout for parallel adders", IEEE Transaction on Computers, C-31(3), pp.260~264 (1982)