Recent Trends and Perspectives of Fully Homomorphic Encryption

Size: px

Start display at page:

Download "Recent Trends and Perspectives of Fully Homomorphic Encryption"

빗나 목
5 years ago
Views:

1 Cloud Security with Fully Homomorphic Encryption 천정희 ( 서울대학교 )

2 암호의분류 1세대암호 : Password ( 인증기술 ) 2세대암호 : 대칭키암호 ( 데이터암호화 ) 3세대암호 : 공개키암호 ( 키암호화 ) 4세대암호 : 동형 / 함수암호 (NoKey 암호 ) 암호화된상태에서의계산이가능핚암호 2

3 The Future of Encryption (NSF) 3

4 개인정보를왜암호화하지않는가? 스토리지보안 : 암호화후에는키워드검색이안된다. 검색을위해서는대용량데이터를모두복호화 탐색가능암호필요 Database Index 검색이안된다. Index 암호화를위해순서보존암호필요 산술연산이안된다. 준동형암호 : 덧셈보존. 암호문의평균 = 평균의암호문 암호화데이터의탐색, 통계처리, 인덱스암호화필요 4

5 4 세대암호 4 세대암호 : 암호화된데이터를복호화없이연산하는암호 탐색가능암호, DB암호등 Computing on encrypted data, Secure Multiparty computation 동형암호 (fully homomorphic encryption) : 2009 Gentry 미국 MIT 가선정핚 2011 년 10 대미래유망기술 개인정보기반광고시장 Facebook, Twitter등의성장 구글 : gmail등구글의개인정보를통합관리 합법적인가? 안젂핚가? 5

6 동형암호 Real World Cyber World x y Enc( E(x) E(y) ) f(x) f(e(x)) = E -1 Enc -1 ( ) (f(e(x))) Secret! 6

7 Pros and Cons 장점 컴퓨터에서데이터의모든계산은 AND, OR, NOT의논리게이트로연산 암호화된상태로 AND, OR, NOT연산이가능하면컴퓨터로하는모든연산이가능 해커의데이터유출원천봉쇄 단점 암호문확장 : K배 K배 ( 대칭키방식 ) 암복호화속도 : 수십 ms (AES 1us, RSA 1ms) 암호문연산 : 곱셈수백ms 응용연산종류에따른속도의차이가큼 개별적최적화 7

8 동형암호칩 (in 10 years?) 8

9 법과항등식 a-b 가 n 의배수 a b (mod n) 예 : 5 2 (mod 3) a b (mod n) 이고 c d (mod n) 이면 a+c b+d (mod n) a-c b-d (mod n) ac bd (mod n) 문제 : 1234*(56-78) 을 3 으로나눈나머지는? =(1233+1)*((54+2)-(78+0)) 1*(2-0)=2 mod 3 [a] n =a mod n := a 를 n 으로나눈나머지 9

10 완전동형암호 RAD PH [1] 비밀키 : two large primes p and q 공개키 : n = pq 암호화 : E(m) = (m mod p, m mod q) 복호화 : 중국인의나머지정리 E(m 1 )+E(m 2 )=(m 1 mod p, m 1 mod q)+(m 2 mod p, m 1 mod q) 안젂핚가? = (m 1 +m 2 mod p, m 1 +m 2 mod q) = E(m 1 +m 2 ) 동형암호 [2] E(m) = (m e 1 mod p, m e 2 mod q) [1] Rivest-Adleman-Dertouzos, On data banks and privacy homomorphism, FOSC 78. [2] Cheon et al. Batch Fully Homomorphic Encryption over the Integers, Eurocrypt

11 재부팅 Bootstrapping 입력 : 노후화된암호문, 암호화된비밀키 출력 : 신규암호문 과정 : 곱을반복하여노이즈가커진암호문을 노이즈가작은암호문으로변경 11

12 Fully Homomorphic Encryption Over the Integers. AGCD-based: [DGHV10] van Dijk, Gentry, Halevi, Vaikuntanathan: FHE over the Integers. Eurocrypt CMNT11, CNT12, CCKLLTY13, CLT14, etc. Over Z q Modules. LWE-based: [BV11a] Brakerski, Vaikuntanathan: Efficient FHE from (Standard) LWE. FOCS Bra12, BGV12, GSW13 Over Polynomials over Z q : Ideal lattice: SV10, NTRU: LTV12 Ring-LWE: BV11b, GHS13, BLLN13, etc. 12

13 FHE revised [C.-Stehle, Euro15] LWE can be reduced to (general) AGCD. AGCD is no easier than standard worst-case lattice problems. We present a scale-invariant FHE based on the integers which: is as secure as LWE, has ciphertexts of linear bit-size, and Is bootstrappable without SSSP assumption. Scheme: Refer to the paper. 13

14 동형암호효율성개선추이 (Boostrapping Time) 소요시간 (logarithm) 30min 1bit Security Level: 72 Wating Amortized 172s 531bits 33s 569 bits 0.7s 1bit GH11 CCK+13 CLT14 DM15 (HS15) 연도 320s 16000bits [GH11] Implementing Gentry s Fully-Homomorphic Encryption Scheme, Eurocrypt [CCK+13] Batch Fully Homomorphic Encryption over the Integers, Eurocrypt [CLT14] Scale-Invariant Fully Homomorphic Encryption over the Integers, PKC [HS15] Bootstrapping for Helib, Eurocrypt 2015 [DM15] FHEW: Boostrapping Homomorpic Encryption in Less Than a Second, Eurocrypt

15 동형암호효율성 암호문크기, 암복호화시간 공개키크기 암호문크기 Encrypt Decrypt Mult Recrypt # of slots [RSA-2048] 2048bit 2048bit 6.1ms 205.5ms [ECC-193] 193bit 80B 8.7ms 18.1ms [BGV12] (5-level) [CLT14] (40-level) [CS14] Symmetric (5-level) - 100KB 22ms 57ms 31ms GB 1.58MB 45s 3.3s 100ms 33s MB 10KB (Compressed) 3.4 ms 2.8 ms 300s - 168*16bit (30 배확장 ) 6

16 예제 1: 생체인증 생체인증시장및문제점 끊이지않는개인정보유출사고 생체정보는유출시대체불가능

17 생체인증기술개발 동형암호 사용자의위변조방지를위해 MAC 기술적용 인증핛생체정보선택 결과를받아인증통과여부판별 생체정보를보호하는동형암호기반생체인증기술 인증시갂 < 0.1 초?

18 예제 2: DNA 분석 DNA 분석 / 정밀의료와암호화 개인의유전정보를이용한정밀의료새로운보건의료패러다임 미국 : 정밀의료이니셔티브 (PMI) 2016 년예산 2 억 1500 만달러 문제는유전정보의보호기술 개인의유전정보를이용핚맞춤형치료

유방암데이터로부터, 선정된패널유전자상의변이정도를입력변수, 유방암예후지표를목표변수로하여학습데이터를구성 =>

19 DNA 맞춤의학 공공유전자변이 DB 들로부터 DNA 바이오마커수집 TCGA 유방암데이터를이용하여유방암특이적질병패널최종선정 유방암질병패널에기반핚질병감수성예측모델구축 ** TCGA 유방암데이터로부터, 선정된패널유전자상의변이정도를입력변수, 유방암예후지표를목표변수로하여학습데이터를구성 => 기계학습알고리즘을이용해질병감수성예측모델을구축 **DNA 바이오마커 : 특정표현형 ( 질병 ) 과연관되어있는유전체 DNA 의특정지역 (Locus)

20 DNA Privacy 스트레인저비젂 ( 조각가, 2012 뉴욕 ) DNA분석 ( 공공장소에서주운머리카락 ) 얼굴만드는소프트웨어이용 3D프린터 DNA : 궁극의프라이버시 개인의 DNA 정보수집 / 악용 (DNA 복제 ) 유젂자에따른 DNA 서열화 (GATTACA) Nature Vol. 519, News in Focus But scientists working to realize such personalized or precision medicine have a problem: how to keep genetic data and medical records secure while still enabling the massive, cloudbased analyses needed to make meaningful associations. 20

21 예제 3: 암호화된헬스케어 건강진단 생체정보 ( 심박 / 활동량 )

22 의료정보보안기술개발의필요성 2013 년미국데이터침해사례중보건의료부문 43.8% 로 1 위 의료정보유출사례증가 미국 : 2005~2013 년데이터침해사례중보건의료부문 43%, (269 건 /614 건, 신용도용범죄정보센터 (ITRC), 2013 Breach List Tops 600) 국내 : 약학정보원등이환자정보를수집하여 IMS 헬스코리아에유출한사건 보건의료정보의보호를위한제도적장치와기술개발이시급한실정

23 예제 4. Smart Car Cyber Physical System (CPS) Engine (Actuator) Dec Smart Car (Plant) Sensor Enc Enc(r) Controller Enc(y) (sensor detection) Enc(u) (user input) 스마트홈에서센서들이인터넷에연결되고이정보들과사용자명령이합쳐서일종의콘트롤러에전달되면이것들이계산되어집행됨 계산속도의문제로암호화하지않은상태로사용중 정보조작, 원격조종, 위치정보공개등많은보안위협산재 Floating point HE 를통해새로운스마트카제어모델설계 23

24 What is the next? 동형암호 vs 함수암호 동형암호 Enc(m 1 ),, Enc(m n ) Enc(f(m 1, m 2,, m n )) 모든 f 함수암호 Enc(m 1 ),, Enc(m n ) f(m 1, m 2,, m n ) 특정핚 f 함수암호의응용 생체인식 : Enc K (m 1 ), Enc K (m 2 ) m 1 =m 2 인지판별 프로그램난독화 (Obfuscation) : 안젂성증명 암호화된데이터에서필요정보추출 ( 데이터마다암호화시지정 ) 양자컴퓨터시대에도안젂! 24

public key private key Encryption Algorithm Decryption Algorithm 1

public key private key Encryption Algorithm Decryption Algorithm 1 One-Way Function ( ) A function which is easy to compute in one direction, but difficult to invert - given x, y = f(x) is easy - given