본문 바로가기 사이드메뉴 바로가기 주메뉴 바로가기

주메뉴영역

주메뉴영역

혁신으로 세상을 바꾸는 융복합 대학, DIGIST
Innovative University Changing the World through Convergence
이 페이지를 SNS로 퍼가기

Research

암호 시스템의 보안수준을 더 빠르고 정확하게 추정하는 새로운 알고리즘 개발

  • 조회. 177
  • 등록일. 2021.05.03
  • 작성자. 대외협력팀

DGIST 김용준 교수팀, 암호·보안 시스템의 핵심 척도인 '최소 엔트로피'를 더 효율적이고 정확하게 측정하는 새로운 알고리즘 개발
기존 표준방식보다도 약 500배 더 빨라...향후 다양한 응용 가능해

 

관련사진1.DGIST 정보통신융합전공 김용준 교수

 


 DGIST 정보통신융합전공 김용준 교수팀은 암호 및 보안 시스템에 핵심적으로 사용되는 ‘최소 엔트로피(Minimum Entropy)1)’를 효율적이고 정확하게 추정하는 두 가지 알고리즘을 개발했다. 김 교수팀이 개발한 알고리즘은 기존 암호학적 알고리즘에 정보이론과 기계학습 방법론을 접목한 새로운 알고리즘으로, 미국표준기술연구소(NIST)의 표준 알고리즘보다 500배 더 빠른 최소 엔트로피 추정이 가능해, 향후 정보 보호 및 보안의 중요성이 더욱 증대되는 4차 산업혁명 분야에 다양하게 응용될 수 있을 것으로 기대된다.

 난수(亂數)는 암호 시스템의 핵심 구성 요소로, 난수의 무작위성이 암호 시스템의 보안 수준을 결정한다. 이러한 난수의 무작위성을 정량화하기 위해서 NIST는 ‘최소 엔트로피’ 추정을 통해 정량화할 것을 제안한다. 이 때, 최소 엔트로피는 특정 알고리즘을 적용해 결정하는데, NIST는 이러한 알고리즘의 표준으로 ‘압축 추정기(Compression Estimator)’를 채택하고 있다. 하지만 압축 추정기는 연산 복잡도가 높고, 추정 결과에 편향성이 존재하는 등 문제점이 있다.

 이에 김용준 교수팀은 기존의 압축 추정기 보다도 계산 효율과 추정 정확도를 향상시킨 알고리즘을 개발했다. 먼저, 기존의 암호학적 알고리즘에 정보이론과 기계학습의 방법론을 적용한 새로운 최소 엔트로피 추정 알고리즘은 추정 정확도를 유지하면서도 NIST 표준 알고리즘 대비 500배 이상 빠른 속도로 최소 엔트로피 추정이 가능하다. 또한 데이터 샘플을 모두 저장하지 않고도 효율적으로 최소 엔트로피를 추정함으로써 편향성 문제를 개선할 수 있는 새로운 경량 추정 알고리즘도 함께 제안했다.

 DGIST 정보통신융합전공 김용준 교수는 “최소 엔트로피 추정 방법관련해서 NIST 표준 문서를 검토하던 중 정보이론과 기계학습의 방법론을 적용해 기존의 NIST 표준 알고리즘보다 연산 속도와 추정 정확도를 획기적으로 개선할 수 있는 방법을 생각하게됐다”며 “개발한 알고리즘이 기존 NIST 표준 알고리즘과 동일하게 정확할 뿐만 아니라 500배 빠른 추정이 가능한 만큼, 새롭게 개발한 알고리즘이 NIST의 표준 알고리즘으로 채택될 수 있도록 노력중이다”고 말했다.

 한편, 이번 연구는 DGIST 정보통신융합전공 김용준 교수가 제 1저자로 참여했다. 연구 결과는 컴퓨터과학 및 이론 분야의 최우수 학술지인 ‘IEEE Transactions on Information Forensics and Security’에 4월 1일(목) 온라인 게재됐다.

---
1) 엔트로피(Entropy): 정보이론적 관점에서 평균 정보량을 의미. 엔트로피가 낮으면 정보의 예측성이 높고, 확정적인 정보가 많아, 굳이 정보를 전송하지 않아도 되므로 평균 정보량이 적다. 엔트로피가 높을 경우, 정보의 예측성이 낮고 그에 따라 정보량이 많아짐으로써 평균 정보량도 상승한다.


· · ·

연구결과개요


On the Efficient Estimation of Min-Entropy
(Yongjune Kim, Cyril Guyot, and Young-Sik Kim)
(IEEE Transactions on Information Forensics and Security, on-line published on April 1st, 2021) 


최소 엔트로피는 암호 시스템에서 사용하는 난수의 무작위성을 정량화하기 위해 널리 사용되는 측도이다. 최소 엔트로피를 추정하는 다양한 알고리즘 중, Mauer의 범용 테스트에 의존하는 압축 추정기는 현재 NIST 표준(SP 800-90B)에 채택되어 있다. 본 논문에서는 Maurer의 테스트의 두 가지 변형을 활용하여 압축 추정기 대비, 계산 복잡성과 추정 정확도를 향상시킨 최소 엔트로피 추정 알고리즘을 제안한다. 
먼저, Maurer의 테스트를 변형한 Coron의 테스트와 정보이론의 Fano의 부등식을 활용하여, 새로운 최소 엔트로피 추정 알고리즘을 제안한다. 제안된 알고리즘은 압축 추정기의 정확도를 유지하면서 압축 추정기보다 계산적으로 더 효율적이다. 두 번째로 제안된 알고리즘은 Renyi 엔트로피를 계산하는 Kim의 테스트를 사용한다. 이 추정 알고리즘은 추정 정확도와 계산 복잡성을 동시에 개선한다. 
또한, Renyi 엔트로피의 차수에 따라 달라지는 편향-분산 트레이드 오프(bias-variance trade-off)의 특성을 분석하였다. 이러한 이론적 분석을 통하여, Renyi 엔트로피의 차수가 2인 것이 최적임을 관찰하였다. 이론적 분석과 관찰을 통해, 데이터 샘플을 모두 저장하지 않고도 효율적으로 최소 엔트로피를 추정하는 새로운 경량 추정 알고리즘을 제안하였다.  DOI : 10.1109/TIFS.2021.3070424

 

· · ·

연구결과문답


Q. 이번 성과 무엇이 다른가?
기존의 NIST 표준 알고리즘인 압축 추정 알고리즘 대비, 연산량과 정확성을 획기적으로 새로운 알고리즘을 제안하였다. 제안한 알고리즘은 최소 엔트로피 추정을 위한 기존의 암호학적 연구에, 정보이론과 기계학습의 방법론을 적용한 것으로, 표준 알고리즘 대비 500배 이상 빠른 속도로 최소 엔트로피를 추정할 수 있다. 

Q. 어디에 쓸 수 있나?
본 논문에서 제안한 알고리즘은 보안 및 암호 응용처에 폭 넓게 활용될 수 있을 것으로 기대된다. 최근 정보 보호가 더욱 중요해지고 있기 때문에, 알고리즘의 활용도가 더욱 커질 것으로 기대된다. 

Q. 실용화까지 필요한 시간과 과제는?
제안한 알고리즘 자체는 바로 상용화할 수 있다. 우선, NIST 표준 알고리즘으로 채택되는 것을 목표로 하고 있다. NIST 표준 알고리즘으로 채택된다면, 제안한 알고리즘이 광범위하게 활용될 수 있을 것이다. 

Q. 연구를 시작한 계기는?
평소 정보이론과 암호이론의 접목에 대해 관심있게 연구하던 중, 최소 엔트로피 추정에 대한 NIST 표준 알고리즘 문서를 읽게 되었다. NIST 표준 알고리즘들을 검토하고 문제점들을 분석하면서, 정보이론과 기계학습 방법론을 적용하여, 새로운 알고리즘을 개발할 수 있었다. 

Q. 어떤 의미가 있는가?
실용적인 측면에서, 표준 알고리즘 대비 정확도를 유지하면서 500배 이상 빠른 속도로 최소 엔트로피를 추정하는 알고리즘이기 때문에 추후 NIST 표준으로 채택될 가능성이 높다고 생각한다. 
이론적인 측면에서, 기존의 암호학적 알고리즘에 정보이론과 기계학습 방법론을 적용한 알고리즘이기 때문에 더욱 의미가 있다고 생각한다. 

Q. 꼭 이루고 싶은 목표는?
후속 연구를 통해 NIST 표준 알고리즘 중 다른 알고리즘의 연산 효율성과 정확성을 개선하는 알고리즘을 제안하려고 한다. 또한, 보안과 프라이버시를 보장하는 기계학습 방법론에 관한 연구를 수행하려고 한다. 


· · ·

그림 설명

[그림 1] 정규분포를 따르는 데이터의 최소 엔트로피 추정

관련사진2.정규분포를 따르는 데이터의 최소 엔트로피 추정

(그림설명)
정규분포를 따르는 데이터의 최소 엔트로피 추정 결과를 보면, 기존의 압축 추정 알고리즘(Algo. 1) 대비 새롭게 제안된 알고리즘(Algo. 2, 3)가 정확한 것을 확인할 수 있다. 제안된 알고리즘(Algo. 2, 3)는 압축 추정 알고리즘 대비 500배 이상 빠른 속도로 최소 엔트로피를 추정한다. 


[그림 2] Markov 체인에 의해 생성된 데이터의 최소 엔트로피 추정

 

관련사진3.Markov 체인에 의해 생성된 데이터의 최소 엔트로피 추정

(그림설명)
Markov 체인에 의해 생성된 데이터의 최소 엔트로피 추정 결과를 보면, 기존의 압축 추정 알고리즘(Algo. 1) 대비 새롭게 제안된 알고리즘(Algo. 2, 3)이 정확한 것을 확인할 수 있다. 제안된 알고리즘(Algo. 2, 3)는 압축 추정 알고리즘 대비 500배 이상 빠른 속도로 최소 엔트로피를 추정한다. 

 

DGIST Scholar Researcher Page Banner(Kor)_2

 

콘텐츠 담당 담당부서  :   홍보팀 ㅣ 053-785-1135