[서평]「Algorithms on Strings, Trees, and Sequences」

김동규(Dong Kyue Kim) 한국정보과학회 2000 정보과학회지 Vol.18 No.3

정수 문자집합상의 접미사트리 구축을 위한 새로운 합병알고리즘

김동규(Dong Kyue Kim),심정섭(Jeong Seop Sim),박근수(Kunsoo Park) 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.1·2

주어진 스트링S 의 접미사트리T_S 를 구축하기 위하여, 먼저 홀수위치들에 대한 접미사트리 T_o 를 재귀적으로 구축하고, 짝수위치들에 대한 접미사트리T_e 를 T_o 로 부터 구축한 다음, T_o 와 T_e 를 합병하여 T_S 를 구축하는 새로운 방식이 사용되고 있다. 인덱스 자료구조에 관련된 문제들 중 정수 문자집합상의 접미사트리를 선형시간에 구축하는 문제는 오랫동안 미해결문제로 남아있었다. Farach은 이 방식을 적용하여 처음으로 선형시간이 소요되는 알고리즘을 제시하였다. 이 알고리즘 중 가장 어려운 곳은 합병하는 부분이다. 본 논문에서는 BFS(breadth-first search)에 기반한 새로운 합병알고리즘을 제안한다. 제안된 합병알고리즘은 Farach의 DFS(depth-first search) 방식보다 개념적으로 단순하게 동작하므로, 다른 응용으로 쉽게 확장될 수 있다. A new approach of constructing a suffix tree T_S for the given string S is to construct recursively a suffix tree T_o for odd positions, construct a suffix tree T_e for even positions from T_o , and then merge T_o and T_e into T_S . To construct suffix trees for integer alphabets in linear time had been a major open problem on index data structures. Farach used this approach and gave the first linear-time algorithm for integer alphabets. The hardest part of Farach's algorithm is the merging step. In this paper we present a new and simpler merging algorithm based on a coupled BFS (breadth-first search). Our merging algorithm is more intuitive than Farach's coupled DFS (depth-first search) merging, and thus it can be easily extended to other applications.

IPv6용 IPSec 하드웨어 칩을 위한 AES 모듈

김경태(Kyung-Tae Kim),김지욱(Ji-Wook Kim),박상길(Sang Kil Park),양인제(Inje Yang),김동규(Dong Kyue Kim),이정태(Jungtae Lee) 한국멀티미디어학회 2002 한국멀티미디어학회 학술발표논문집 Vol.2002 No.1

DNA 스트링에 대하여 써픽스 배열을 구축하는 빠른 알고리즘

조준하(Junha Jo),김남희(Namhee Kim),권기룡(Ki-Ryong Kwon),김동규(Dong Kyue Kim) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.7·8

DNA 스트링과 같은 대용량의 데이타에 대한 빠른 검색을 수행하기 위해서는 전체 텍스트 인덱스 자료구조를 구축하여 검색하는 방법이 효율적이다. 가장 일반적인 인덱스 자료구조는 써픽스 트리와 써픽스 배열이다. 써픽스 배열은 써픽스 트리보다 적은 공간을 사용하기 때문에 DNA 스트링과 같은 대용량의 데이타에 적합한 자료구조이다. 기존의 써픽스 배열 구축 알고리즘들은 정수 문자집합에 적합한 알고리즘들이어서 DNA 스트링에 적합하지 않았다. 본 논문에서는 DNA 스트링의 문자집합이 4로 고정되어 있는 사실을 이용하여 DNA 스트링에 대한 써픽스 배열을 빠르게 구축하는 방법을 제안한다. 고정길이 문자집합에 효율적인 Kim et. al.[1]의 알고리즘의 인코딩 과정과 합병 과정 개선으로 전체 구축 시간을 향상시켰다. 실험 결과 1.3배에서 1.6배 정도 구축 속도가 향상되었으며, 기존의 다른 써픽스 배열 구축 알고리즘들과 비교한 결과에서도 대부분 가장 빠르게 써픽스 배열을 구축하였다. To perform fast searching in massive data such as DNA strings, the most efficient method is to construct full-text index data structures of given strings. The widely used full-text index structures are suffix trees and suffix arrays. Since the suffix array uses less space than the suffix tree, the suffix array is proper for DNA strings. Previously developed construction algorithms of suffix arrays are not suitable for DNA strings since those are designed for integer alphabets. We propose a fast algorithm to construct suffix arrays on DNA strings whose alphabet sizes are fixed by 4. We reduce the construction time by improving encoding and merging steps on Kim et al.[1]'s algorithm. Experimental results show that our algorithm constructs suffix arrays on DNA strings 1.3-1.6 times faster than Kim et al.'s algorithm, and also for other algorithms in most cases.

블록 암호 알고리즘을 사용하지 않는 인증 암호화 방법

이문규,김동규,박근수,Lee, Mun-Kyu,Kim, Dong-Kyue,Park, Kunsun 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.5

We propose a new authenticated encryption scheme that does not require any block encryption algorithm. Our scheme is based on the Horster-Michels-Petersen authenticated encryption scheme, and it uses a technique in the Bae~Deng signcryption scheme so that the sender's signature can be verified by an arbitrary third party. Since our scheme does not use any block encryption algorithm, we can reduce the code size in its implementation. The computation and communication costs of the proposed scheme are almost the same as those of the Bao-Deng scheme that uses a block encryption algorithm. Our scheme also satisfies all the security properties such as confidentiality, authenticity and nonrepudiation. 본 논문에서는 블록 암호 알고리즘을 사용하지 않는 새로운 인증 암호화 방법을 제안한다. 이 방법은 Horster-Michels-Petersen 인증 암호화 방법에 기반하고 있으며, Bao-Deng 서명암호화에 이용된 기법을 적용함으로써 전송자의 서명을 수신자 이외의 임의의 제삼자가 검증할 수 있는 특성을 지닌다. 제안된 방법은 블록 암호 알고리즘을 이용하지 않으므로 구현시 코드 크기를 줄일 수 있는 장점을 가지며, 블록 암호 알고리즘을 이용하는 Bao-Deng 방법과 거의 같은 정도의 계산량 및 통신량만을 필요로 한다. 또한 제안된 방법은 기밀성, 인증성, 부인방지 등 안전성 요건들을 만족시킨다.

가스절연 개폐장치에서 유전율 구배를 갖는 고체 절연물의 형상 최적화

주흥진,김동규,고광철,Ju, Heugn-Jin,Kim, Dong-Kyue,Ko, Kwang-Cheol 한국전기전자재료학회 2012 전기전자재료학회논문지 Vol.25 No.6

A functionally graded material (FGM) spacer, which the distribution of dielectric permittivity inside an insulator changes spatially, can considerably reduce the electric field concentration around a high-voltage electrode and along the gas-insulator interface when compared to a conventional spacer with a uniform permittivity distribution. In this research, we propose the FGM spacer with an elliptical permittivity distribution instead of that with a distribution of dielectric permittivity varying along a radial direction only in order to improve efficiently the insulation capability. The optimal design of the elliptical FGM spacer configuration is performed by using the response surface methodology (RSM) combined with the steepest descent method (SDM).

A String Reconstruction Algorithm and Its Application to Exponentiation Problems

심정섭,이문규,김동규,Sim, Jeong-Seop,Lee, Mun-Kyu,Kim, Dong-Kyue Korean Institute of Information Scientists and Eng 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.9

Most string problems and their solutions are relevant to diverse applications such as pattern matching, data compression, recently bioinformatics, and so on. However, there have been few works on the relations between string problems and cryptographic problems. In this paper, we consider the following string reconstruction problems and show how these problems can be applied to cryptography. Given a string x of length n over a constant-sized alphabet ${\sum}$ and a set W of strings of lengths at most an integer $k({\leq}n)$, the first problem is to find the sequence of strings in W that reconstruct x by the minimum number of concatenations. We propose an O(kn+L)-time algorithm for this problem, where L is the sum of all lengths of strings in a given set, using suffix trees and a shortest path algorithm for directed acyclic graphs. The other is a dynamic version of the first problem and we propose an $O(k^3n+L)$-time algorithm. Finally, we show that exponentiation problems that arise in cryptography can be successfully reduced to these problems and propose a new solution for exponentiation. 대부분의 문자열 문제들과 이들에 대한 알고리즘들은 패턴 매칭, 데이타 압축, 생물정보학 등의 분야에 응용되어 왔다. 그러나 문자열 문제와 암호화 문제의 관련성에 대한 연구는 거의 진행되지 않았다. 본 논문에서는 다음과 같은 문자열 재구성 문제들에 대해 연구하고 이 결과들이 암호학에 응용될 수 있음을 보인다. 유한 알파벳으로 구성된 길이 n인 문자열 x와, 길이 $k({\leq}n)$ 이내의 문자열의 집합 W가 주어졌을 때, 첫 번째 문제는 내의 문자열들 중 일부 문자열들을 최소의 회수로 연결하여 x를 재구성할 수 있는 연결 순서를 찾는 문제이다. 이 문제에 대해 O(kn+L)-시간 알고리즘을 제시한다. 이때, L은 W 내의 모든 문자열들의 길이의 합을 표시한다. 두 번째 문제는 첫 번째 문제의 동적 버전이며 이에 대해 $O(k^3n+L)$시간 알고리즘을 제시한다. 마지막으로 암호학과 관련된 멱승문제와 위에 제시된 재구성 문제들과의 관련성을 보이고 멱승문제를 해결하는 새로운 알고리즘을 제시한다.

모듈러 멱승을 계산하는 일반화된 모델

김지은(Jieun Kim),김동규(Dong Kyue Kim) 한국멀티미디어학회 2003 한국멀티미디어학회 학술발표논문집 Vol.2003 No.1

전력분석공격 방지 기법을 적용한 ARIA 하드웨어 모듈 구현

김용민(Yongmin Kim),김동규(Dong Kyue Kim),이문규(Mun-Kyu Lee) 대한전자공학회 2010 대한전자공학회 학술대회 Vol.2010 No.6

IoT 기술과 보안

김호원(Howon Kim),김동규(Kim, Dong Kyue) 한국정보보호학회 2012 情報保護學會誌 Vol.22 No.1

최근까지 정보 기술 분야에서는 유비쿼터스(Ubiquitous)라는 용어가 크게 유행한 적이 있다. 현재는 다소 식상하게 들리는 용어일지도 모르지만 사물의 지능화와 통신화라는 유비쿼터스 개념은 이미 우리의 생활에 깊이 파고 들어왔다. 최근 유행하는 IT 기술인 스마트폰이나 지능형 전력망, 와이파이, 소셜 네트워크, 센싱 데이터 처리 기술과 개념은 이러한 유비쿼터스 기술의 대표적인 사례로 볼 수 있다. 국내에서는 이러한 유비쿼터스라는 개념을 유비쿼터스 센서 네트워크 (Ubiquitous Sensor Network: USN)라는 용어로서 2004년부터 정보통신부 혹은 지식경제부의 적극적인 지원에 힘입어 많은 기술적/산업적 성과를 이루기도 했다. 하지만 이러한 USN은 센서네트워크 개념으로 제한적으로 오용되는 경우가 많았다. 이에 본고에서는 이러한 유비쿼터스 환경을 실현하는 사물의 지능화/통신화에 대한 기술 동향과 보안 기술을 논하기 위해서 USN과 거의 비슷한 개념이지만 국내외적으로 더욱 보편적으로 사용되고 있는 IoT(Internet of Things) 용어를 사용할 것이며, 이러한 IoT에 대한 기술 동향과 보안 기술을 논하고자 한다.