연구실 소개

연구실 소개

서울대학교

수리과학부 교수

천정희

 연구주제

 정수론 Computational and Algorithmic Number Theory

 암호론 Cryptology, 동형암호 Homomorphic Encryption

 관련 교과목

 정수론 :

Computational number theory, Geometry of numbers, Ellipt ic Curves, Algebraic number theory

 암호론 , 조합론 , 알고리즘 등

 구성원

 포닥 1 명 : 이문성

 박사 8 명 : 김진수 , 류한솔 , 홍현숙 , 김미란 , 정희원 , 이창민 , 송용수 , 한규형 , 정진혁 , 이주희

 석사 4 명 : 이유현 , 김재윤 , 김지승 , 손용하

연구 주제 소개

인수분해 및 이산로그



인수분해 문제

 600-bit (200 자리 ) 인수분해 성공

 Number Field Sieve and Elliptic Curve Method



이산로그 문제

 Given find

 유한체와 타원곡선 위에서 이산로그 문제들이 연구되고 있음



Characteristic 이 작은 체 위의 이산로그 : 최근 다항식 시간 알고리즘



강한 이산 로그 문제

 Given find

 작은 이미지를 갖는 다항식을 찾는 문제로 reduction



Lattice

 Lattice in is

 A discrete subgroup of

 Integer linear combinations of a linearly independe nt set of vectors



Lattice and Erroneous Number The ory

 근사 공약수 문제 (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 은 암호론 속의 다양한 주제들을 이어주는 다리 역할을 하고 있다 .

 새로운 reduction 은 학문에 크나큰 영향

 Millennium problem: P=NP?

Approxi- mate GCD

Learning with

errors

15 년 논문 리스트

연도 논문제목 저자

2015 WHAC15 Search and Compute on Encrypted Data 천정희 , 김미란 , 김명 선

2015 WHAC15 Homomorphic Computation of Edit Distance 천정희 , 김미란 , Lauter

2015 Euro-

crypt15* Cryptanalysis of Multilinear Map over the In- tegers

천정희 , 이창민 , 류한 솔 , 한규형 , Stehle 2015 Euro-

crypt15 Fully Homomorphic Encryption over the In-

tegers, revisited. 천정희 , Stehle

2015 Submission White-Box AES Implementation Revisited 백충훈 , 천정희 , 홍현 숙

2015 CSI Batch Verification of Multiple Signatures 천정희 , 이문규 2015 MathComp Computing prime divisors in an interval 김민규 , 천정희

* Eurocrypt 2015 The Best Paper Award

13-14 년 논문 리스트

연도 논문제목 저자

2013 Eurocrypt Batch Fully Homomorphic Encryption over the

Integers 천정희 , 김진수 , 이문성 등

2013 IEEE IT On the Final Exponentiation in Tate Pairing Com-

putations 김태찬 , 김성욱 , 천정

희 2013 SAC A Group Action on Z_p and the Generalized DLP

with Auxiliary Inputs

천정희 , 김태찬 , 송용 수

2013 ICISC Invertible Polynomial Representation for Private Set Operations

천정희 , 홍현숙 , 이형 태

2014 Math- Comp

Analysis on a generalized algorithm for the

strong discrete logarithm problem with auxiliary inputs

김민규 , 이인석 , 천정 희

2014 ACM CCS A New Additive Homomorphic Encryption based on the co-ACD Problem

천정희 , 이형태 , 서재 홍

2014 In Revi-

sion The Polynomial ACDP and its Application to the FHE

천정희 , 류한솔 , 이문 성 . 홍현숙

연구실 생활 및 진로

연구실 생활

1 년 차

• 신입생 세미나 및 기초 과목 수강

2 년 차

• 코딩 시 험

• 산학과제 경험

3 년 ~

• 집중 연구

• 해외인턴쉽 (MSR,

ENS, NTT, 공대 )

산학과제



산학 협력을 통한 다양한 과제 경험 부여



삼성전자 : 무선 사업부 , SW 센터

 경량화 기기에 알맞은 키 보호 알고리즘 설계

 생체정보를 이용한 인증 알고리즘 설계



SKT:



국가암호기술공모전 : 매년 8 월 -10 월

 국가정보원장상 등 시상

졸업생 진로 현황

졸업연도 이름 직장

2011 홍정대 육군 기무사령부 암호과장

2011 서재홍 명지대학교 교수

2011 주치홍 ( 석 ) UNIST 박사과정

2011 김민규 ETRI 부설연구소 선임연구원

2012 홍병도 ( 석 ) KAIST 박사과정

2012 김명선 수원대학교 교수

2012 김성욱 삼성전자

2013 이형태 난양공대 연구원 ( 싱가포르 )

2013 김홍태 공군사관학교 교수

2013 김태찬 NTT 중앙연구소 포닥 ( 일본 )

2014 김진수 삼성전자

졸업 후 진로 졸업 후 진로 산 산

삼성전자 SKT

KT

삼성전자 SKT

KT

학 학

수학과

정보보호학과 수학과

정보보호학과

연 연

국가보안연구소

NTT ETRI KISA

국가보안연구소

NTT ETRI KISA

 연구실 홈페이지



https://sites.google.com/site/snu00chri/