암호학적난제연구단 서울대학교 수리과학부 교수 천정희.

Presentation on theme: "암호학적난제연구단 서울대학교 수리과학부 교수 천정희."— Presentation transcript:

1 암호학적난제연구단 서울대학교 수리과학부 교수 천정희

2 개요 연구주제 관련 교과목 구성원 정수론 및 암호론
Computational and Algorithmic Number Theory, Cryptology 관련 교과목 정수론: Computational number theory, Geometry of numbers, Elliptic Curves, Algebraic number theory 암호론, 조합론, 알고리즘 등 구성원 석박통합 11명, 포닥 4 박사학위 17 (교수 6, 삼성 3, 국보연 3, 마이크로소프트, NTT, ENS, KT)

3 연구 분야 [난제제안] Computation Number Theory [난제환원] Theory of Computation
인수분해, 빠른 지수승 [난제환원] Theory of Computation P versus NP, 난제간의 환원(AGCD~LWE~NPC) [암호설계] Cryptology 동형암호/함수암호/양자내성암호 [암호응용] Information Security Block Chain, 생체인증, Ransomware

4 연구 주제 소개

5 연구 주제: Overview 암호학적 난제 안전성 분석 동형/함수 암호 연구 (산업수학콜로퀴움 강연 참조)
인수분해, 이산로그 (w/ AI, FFS) 격자문제, Approximate Number Theory 동형/함수 암호 연구 (산업수학콜로퀴움 강연 참조) 설계: 실수동형/인증동형 설계, 효율적구현  HEAAN 공개 응용: 머신러닝, DNA, Smart Car/Drone (CPS), 암호화된 데이터분석 양자내성/경량 공개키 암호설계 키관리: 생체정보 보안, Noisy Key Encryption 암호의 응용 및 보안기술과의 접목 빅데이터의 안전한 공유를 위한 동형 키블록체인

6 암호란? 암호화: 푸는 열쇠를 가진 사람만 읽을 수 있도록 부호화하는 방법 Cryptography: 안전한 암호체계를 설계
비밀키 암호 공개키 암호: 수학적 난제에 기반 Cryptanalysis: 암호체계를 분석/해독 Computational Number Theory, Grobner Basis

7 동형암호 복호화 없이 암호화된 데이터 간의 연산을 허용하는 암호 시스템
1978년 Rivest, Adleman, Dertouzos에 의해 최초로 개념 제시 2009년 Gentry에 의해 임의의 연산이 가능한 동형 암호 최초 설계됨 암호문 상태에서 키워드 검색, 통계계산 등 임의의 계산 가능 Encrypted CPU도 이론적으로 가능 2011년 MIT Technical Review지에서 10 Emerging technology 선정

8 난제간의 Reduction 난제들 사이의 reduction은 암호론 속의 다양한 주제들을 이어주는 다리 역할을 하고 있다.
Millennium problem: P=NP? Approximate GCD Learning with errors

9 인수분해 및 이산로그 인수분해 문제 이산로그 문제 강한 이산 로그 문제 600-bit (200자리) 인수분해 성공
Number Field Sieve and Elliptic Curve Method 이산로그 문제 Given 𝑔, ℎ , 𝑔 𝑥 ≡ℎ 𝑚𝑜𝑑 𝑛 , find 𝑥 유한체와 타원곡선 위에서 이산로그 문제들이 연구되고 있음 Characteristic 이 작은 체 위의 이산로그: 최근 다항식 시간 알고리즘 강한 이산 로그 문제 Given 𝑔, 𝑔 𝑥 , 𝑔 𝑥 2 , 𝑔 𝑥 3 , …, 𝑔 𝑥 𝑡 , find 𝑥 작은 이미지를 갖는 다항식을 찾는 문제로 reduction

10 AGCD and LWE 근사 최대공약수 문제 Learning with Errors (LWE)
GCD: 소수 p의 배수들을 보고 p를 찾는 문제 AGCD: Given xi=pqi+ei for many i, find prime p Learning with Errors (LWE) Given a matrix A∈ 𝑍 𝑚×𝑛 and a vector b∈ 𝑍 𝑚×1 , find a vector x∈ 𝑍 𝑛×1 s.t. 𝐴𝑥=𝑏. (m>n) What if 𝐴𝑥≈𝑏? What if the entries are polynomials over Zq?

11 Geometry of Numbers: Lattices
(Integral) Lattice, 격자 A lattice is a discrete subset of 𝑅 𝑛 , equivalently L=𝑍 𝑣 1 +⋯+𝑍 𝑣 𝑚 for some lin. Indep. 𝑣 1 ,⋯, 𝑣 𝑚 ∈ 𝑅 𝑛 𝑜𝑟 𝑍𝑛 SVP (shortest vector problem) : Given a basis of a lattice L, find a shortest non-zero vector. Minkowski: Upper bound of SV’s length 𝜆 1 𝐿 ≤ 𝑛 det⁡(𝐿) 1/𝑛 LLL: find a vector of size 2 (𝑛−1)/4 det⁡(𝐿) 1/𝑛 in poly time of inputs. Exact SVP: Approx. factor is poly(n) with expo time algorithm (NP-hard)

12 연구실 생활 및 진로

13 학년별 학습코스 석1: 수학전분야 공부, 석박통합자격고사 석2: 계산정수론/암호론, 연구실인턴(과제참여)
박1: 연구팀합류, 코딩시험, 국내인턴 박2: 집중 연구(논문집중지도), 해외인턴 박34(Ph.D Candidate): 자기주도연구  박사후 과정: 해외포닥

14 공부 교재(기본 블루, 중급 보라, 고급 레드) 기초정수론 및 대수적정수론 계산정수론 암호론
Niven-Zucherman-Montgomery, Theory of Numbers Algebraic Number Theory 계산정수론 Shoup, A Computational Intro. to Number Theory and Algebra Galbraith, Mathematics for Public Key Cryptography Gathen-Gerhard, Modern Computer Algebra 암호론 Washington-Trappe, Intro. to Cryptography w/ Coding Theory Katz-Lindell, Intro. to Modern Cryptography 타원곡선암호(Blake-Seroussi-Smart I, II) 기타: Algorithm, Coding, Combinatorics, Complexity, 고전 논문 읽기, 최신 논문 읽기

15 연구방법 랩미팅 (매주 수요일 1시) 랩세미나 (매주 금요일 9시) 팀별세미나: 신입생, 설계/분석/응용, 과제미팅 논문발표
연구결과 소개 랩세미나 (매주 금요일 9시) 연구내용 발표, 최신논문소개연구 팀별세미나: 신입생, 설계/분석/응용, 과제미팅 논문발표 국가암호공모전 세계암호학회 (Crypto/Eurocrypt/Asiacrypt…) 수학/CS/EE 저널 (MathComp, IEEE T.,InfoSci)

16 진로 및 관련기관 관련연구기관 (*최근 3년내 공동연구기관) 인턴 (1-3개월)
기업: 삼성전자*, 삼성SDS*, SK*, KT, LG, 스마트인증*, … 연구소: 국보연*, NIMS, ETRI, KISA* 정부: 국정원, 검찰, 기무사… (교수 6, 삼성 3, 국보연 3, NTT, UCSD, ENS, KT) 인턴 (1-3개월) 해외: 미국 MS Research, 일본 NTT, 프랑스 ENS, UC Irvine, 싱가폴 A*star 국내: NIMS, 국보연, ETRI, 기업 More info: math.snu.ac.kr/~jhcheon or google Jung Hee Cheon

17 졸업생 현황 홍정대(2010.2): 국방부 기무사령부 서재홍(2011.2): 한양대 수학과 교수
김민규(2012.2): 국가보안기술연구소 선임연구원 김성욱(2012.8): 삼성전자 SW센터 책임연구원 김명선(2012.8): 수원대 정보보호학과 교수 김홍태(2013.2): 공군사관학교 교수부 수학과 교수 이형태(2013.2): 전북대학교 컴퓨터공학부 교수 김태찬(2014.2): 일본 NTT중앙연구소 전임연구원 (tenured) 김진수(2015.2): 삼성전자 SW센터 책임연구원 홍현숙(2015.8): 삼성전자 메모리사업부 선임연구원 류한솔(2016.8): 국가보안기술연구소 선임연구원 김미란( ): 텍사스 주립대학교 교수  정희원( ): KT 연구원   이창민( ): MyLyon Postdoc in ENS de Lyon  송용수( ): Microsoft Research 연구원 (tenured) 김진수( ): 해군사관학교 교수 한규형( ): 서울대 박사후연구원