연구실 소개 서울대학교 수리과학부 교수 천정희

연구주제 관련 교과목 구성원 정수론 Computational and Algorithmic Number Theory 암호론 Cryptology, 동형암호 Homomorphic Encryption 관련 교과목 정수론: Computational number theory, Geometry of numbers, Elliptic Curves, Algebraic number theory 암호론, 조합론, 알고리즘 등 구성원 포닥 1명: 이문성 박사 8명: 김진수, 류한솔, 홍현숙, 김미란, 정희원, 이창민, 송용수, 한규형, 정진혁, 이주희 석사 4명: 이유현, 김재윤, 김지승, 손용하

연구 주제 소개

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

Lattice Lattice in ℝ 𝑛 is A discrete subgroup of ℝ 𝑛 Integer linear combinations of a linearly independent set of vectors, ℒ={∑ 𝑎 𝑖 𝑏 : 𝑎 𝑖 ∈ℤ, 𝑏 ∈ ℝ 𝑛 }

Lattice and Erroneous Number Theory 근사 공약수 문제(AGCD) Given { 𝑥 𝑖 =𝑝 𝑞 𝑖 + 𝑟 𝑖 }, find 𝑝. Lattice의 짧은 벡터를 이용하여 풀 수 있다 합성수 modulus 상의 다항식의 해를 찾는 문제 Modulus의 인수분해를 알면 쉬움 인수분해를 모를 경우 Coppersmith 방법을 이용하면 크기가 작은 해를 찾을 수 있음 Shortest Vector Problem, Closest Vector Problem

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

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

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

15년 논문 리스트 연도 논문제목 저자 * Eurocrypt 2015 The Best Paper Award 2015 WHAC15 Search and Compute on Encrypted Data 천정희, 김미란, 김명선 Homomorphic Computation of Edit Distance 천정희, 김미란, Lauter Eurocrypt15* Cryptanalysis of Multilinear Map over the Integers 천정희, 이창민, 류한솔, 한규형, Stehle Eurocrypt15 Fully Homomorphic Encryption over the Integers, revisited. 천정희, Stehle Submission White-Box AES Implementation Revisited 백충훈, 천정희, 홍현숙 CSI Batch Verification of Multiple Signatures 천정희, 이문규 MathComp Computing prime divisors in an interval 김민규, 천정희 * Eurocrypt 2015 The Best Paper Award

13-14년 논문 리스트 연도 논문제목 저자 2013 Eurocrypt Batch Fully Homomorphic Encryption over the Integers 천정희, 김진수, 이문성 등 IEEE IT On the Final Exponentiation in Tate Pairing Computations 김태찬, 김성욱, 천정희 SAC A Group Action on Z_p and the Generalized DLP with Auxiliary Inputs 천정희, 김태찬, 송용수 ICISC Invertible Polynomial Representation for Private Set Operations 천정희, 홍현숙, 이형태 2014 MathComp Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs 김민규, 이인석, 천정희 ACM CCS A New Additive Homomorphic Encryption based on the co-ACD Problem 천정희, 이형태, 서재홍 In Revision The Polynomial ACDP and its Application to the FHE 천정희, 류한솔, 이문성. 홍현숙

연구실 생활 및 진로

연구실 생활 1년 차 2년 차 3년~ 코딩 시험 산학과제 경험 신입생 세미나 및 기초 과목 수강 집중 연구 해외인턴쉽 (MSR, ENS, NTT, 공대)

산학과제 산학 협력을 통한 다양한 과제 경험 부여 삼성전자: 무선 사업부, SW 센터 경량화 기기에 알맞은 키 보호 알고리즘 설계 생체정보를 이용한 인증 알고리즘 설계 SKT: 동형암호를 이용한 모바일 사용자 타겟팅 서비스 국가암호기술공모전: 매년 8월-10월 국가정보원장상 등 시상

졸업생 진로 현황 졸업연도 이름 직장 2011 홍정대 육군 기무사령부 암호과장 서재홍 명지대학교 교수 주치홍(석) UNIST 박사과정 김민규 ETRI 부설연구소 선임연구원 2012 홍병도(석) KAIST 박사과정 김명선 수원대학교 교수 김성욱 삼성전자 2013 이형태 난양공대 연구원 (싱가포르) 김홍태 공군사관학교 교수 김태찬 NTT 중앙연구소 포닥 (일본) 2014 김진수

졸업 후 진로 산 삼성전자 SKT KT 학 수학과 정보보호학과 연 국가보안연구소 NTT ETRI KISA

연구실 홈페이지 https://sites.google.com/site/snu00chri/