2016 암호여름학교 - 동형암호 (서울대학교 천정희 교수님)

동형암호

암호의 분류

• 1세대 암호 : 패스워드 (인증기술)
• 2세대 암호 : 대칭키 암호 (데이터 암호화)
• 3세대 암호 : 공개키 암호
• 4세대 암호 : 동형 암호

미래 컴퓨팅 환경

우리가 원하는 완벽한 하인

• 내가 하려는 일을 빠르게 대신 수행
• 비밀을 알지 못한다.

사례1 : 개인 클라우드

• 스토리지 클라우드 (드랍박스, 구글 드라이브, NAS 등)
• 계산 클라우드 : DNA 계산, 헬스케어, 개인성향분석을 통한 추천

사례2 : 다수 사용자 통계분석

• 개인정보기반 마케팅 (구글, 페이스북, 네이버 등)
• 정부 데이터

4세대 암호

4세대 암호 : 암호화된 데이터를 복호화 없이 연산하는 암호

• 탐색가능암호, DB암호 등
• computing on encrypted data, secure multiparty computation

동형암호(Fully Homomorphic encryption) : 2009 Gentry

• MIT가 선정한 2011년 10대 미래 유망 기술

개인정보기반 광고 시장

• facebook, twitter 등의 성장
• 구글 : gmail 등 구글의 개인정보를 통합관리
• 합법적인가? 안전한가?

Privacy Homomorphic

10 Emerging Technologies(MIT Technical Review 2011)

• Gentry's system

동형암호 설계 방법

Find an isomorphism between 주인 and 하인

• 주인쪽 연산을 하인도 동일하게 수행
• Enc : P -> C

• f    f'
  

• Enc : P -> C

문제 : 기지평문공격 (known text attack)

• y = E(x)인 (x, y)를 알면 y2$y^2$ 의 평문은?
• DE(x2)=x2$DE{x}^2{x}^2$, but E(x2)!=E(x)2$E{x}^2{Ex}^2$
• Noisy Isomorphism (C가 P보다 월등히 크다)

Pros and Cons

장점

• 컴퓨터에서 데이터의 모든 연산은 and, or, not의 논리 게이트로 연산
• 암호화된 상태로 and, or, not 연산이 가능하면 컴퓨터로 하는 모든 연산이 가능
• 해커의 데이터 유출 원천 봉쇄

단점

• 암호문 확장 : 10-100 K배 -> 0.1-1배 (대칭키 방식)
• 암복호화 속도 : 수십ms (AES : 1us, RAS : 1ms) -> 이제는 해결됨. 빨라짐
• 암호문 연산 : 곱셈 수백ms
• 응용연산 종류에 따른 속도의 차이가 큼 -> 개별적 최적화

법과 항등식

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) 을 32로 나눈 나머지는?

• (1233+1)((54+2)-(78) ....

완전동형암호

RAD PH

• 비밀키 : 큰 두 개의 소수 p, q
• 공개키 : n = pq
• 암호화 : E(m) = (m mod p, m mod q)
• 복호화 : 중국인의 나머지 정리
• E(m1) + E(m2) = (m1 mod p, m1 mod q) + (m2 mod p, m2 mod q)

•         = (m1 + m2 mod p, m1+m2 mod q) = E(m1 + m2)
  

• 안전한가? Enc : P->C

재부팅 Bootstrapping

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

동형암호

DGVH

• 비밀키 : a large prime p
• 연산키 :

Hard Problem and Security

AGCD Problem

• given several noisy multiples of p, find p.
• e.g, find p given x0 = pq0 + r0, x1 = pq1 + r1 with ri << p

how to solve?

• brute force for noise r or secret p
• Use continue fraction
• use lattice : orthogonal lattice attack and LLL

AGCD is provably hard?

SVP is NP-complete, but only in the worst case

(Ajtai96) SIS is as secure as the uSVP(worst c.)

• find a small integer solution of a system of integer equations

(Regev04) LWE is as secure as GapSVP

• m eqns with n variables over Zp is easy to solve
• what if the answers have noise? -> NP complete
• self-reducible (worst case = average case)

(C.-Stehle 15) AGCD is as secure as LWE

동형암호의 응용

예제1 : 생체인증

생체인증 시장 및 문제점

• 신한은행, 손바닥 정맥 인증 도입, 은행권 생체 본인 인증 본격화
• 생체인증 시장 규모 성장중
• 끊이지 않는 개인정보 유출 사고
• 생체정보는 유출 시 대체 불가능

생체인증 기술 개발

• 생체 정보를 보호하는 동형암호기반 생체인증 기술
• 인증시간 < 0.1초?
• 결과가 맞다 틀리다의 암호문이 나옴. 그래서 풀어주는 절차 필요
• 사용자의 위변조 방지를 위해 MAC 기술 적용

예제 2 : DNA 분석

DNA 분석/정밀의료와 암호화

• 개인의 유전정보를 이용한 정밀의료 새로운 보건의료 패러다임
• 미국 : 정밀의료 이니셔티브(PMI : Precise Medical Initiative) 2016 예산 2억 1500만 달러
• 문제는 유전정보의 보호 기술

DNA 맞춤의학

공공 유전자 변이 DB들로부터 DNA 바이오마커 수집

TCGA 유방암 데이터를 이용하여 유방암 특이적 질병패널 최종선정

• 유방암 질병패널에 기반한 질병감수성 예측모델 추측

DNA Privacy

스트레인저 비전 (조각가, 2012 뉴욕)

• DNA 분석 (공공장소에서 주운 머리카락)
• 얼굴 만드는 소프트웨어 이용
• 3d 프린터

DNA : 궁극의 프라이버시

• 개인의 DNA 정보 수집/악용

예제3 : 암호화된 헬스케어

• 건강진단 <--> 생체정보 (심박/활동량)

개인정보 헬스케어

• 예시 : 서인남성이 심장마비 걸릴 확률에서 변수로 쓰이는 헬스 정보는 나이(a), 키(ht), 몸무게(wt), 수축기 혈압 (sys), 이완기 혈압 (dia), 콜레스테롤 수치(chol) 이다. P(x) = e^x / (e^x-1)
• 실수동형암호의 필요성. 동치 계산을 해야 한다. -> 복소수 동형암호화

Smart Car

Cyber Physical System(CPS)

• 스마트홈에서 센서들이 인터넷에 연결되고 이 정보들과 사용자 명령이 합쳐서 일종의 컨트롤러에 전달되면 이것들이 계산되어 집행됨
• 계산 속도의 문제로 암호화 하지 않은 상태로 사용 중
• 정보조작, 원격조종, 위치정보 공개 등 많은 보안위협 산재
• Floating point HE(실수동형암호)를 통해 새로운 스마트카 제어 모델 설계

What is the next?

동형암호 vs 함수암호

• 현재 추세는 동형암호보다는 함수암호에 더 비중
• 그러나 조금 시각을 달리보면 동형 암호도
• 동형암호 : Enc(M1), ... , Enc(Mn) -> Enc(f(M1, M2, ..., Mn)) 모든 f
• 함수암호 : Enc(M1), ... , Enc(Mn) -> f(M1, M2, ... , Mn) 특정한 f

함수 암호의 응용

• 생체인식 : ENC_k(M1), ENC_k(M2) -> M1 = M2 인지 판별
• 프로그램 난독화 (Obfuscation) : 안전성 증명 -> 존재하는지 아닌지 불확실
• 암호화된 데이터에서 필요 정보 추출 (데이터마다 암호화시 지정)

양자컴퓨터 시대에도 안전!

(PQ) 양자 컴퓨터

양자컴퓨터

pros

• 인수분해와 이산로그를 다항식 시간에 계산
• 검색도 O(sqrt n) 시간에 해결 (groover algorithm)

cons

• NP-hard 문제는 다항식 시간에 계산 안됨
• 다룰 수 있는 q bit를 늘리는 것이 매우 어려움 (현재 수십)

일반적인 예상

• 수십년 이후에나 개발 가능할 듯

Post-Quantum Crypto

NSA Suite B Cryptography (2015 8 19)

• Qunatum Resistant Algorithm 으로 이동 계획 발표
• Suite B에 있는 타원곡선 암호 사용 자제 권고

Post-Quantum Crypto (based on NP-Hard Problem)

• 격자 : SVP and CVP in Integral Lattices of high dim
• 다변수 다항식 : solve multivariate Quandratic eqns
• 코드 : Decode of General Linear Codes
• 해쉬기반

NIST 공모

• 양자 암호에 안전한 공개키 암호 알고리즘
• 전자 서명
• 키 교환 프로토콜
• 다수의 알고리즘을 채택할 것으로 기대
• 공개적으로 투명한 평가를 중시할 예정

cs 쪽에서는 lattice 가 익숙하지만 대수적은 불편 저 두 개를 결합한 이론은 이제 막 연구 시작