These days, with the advancement and propagation of the Internet and Information Technology, many security issues have emerged. One of keys enabling to deal with such issues is to adopt Cryptography. Unfortunately, cryptography will not work well if a piece of critical information ($\emph{e.g. secret key}$) is not kept secret from unauthorized entities. When the secret key is revealed, all cryptographic systems will be compromised. Actually, exposing secret keys seems to be unavoidable. And we call this the key exposure problem.
Recently, the notion of $\emph{key-evolving paradigm (or key-evolving protocol)}$ was proposed as a means of mitigating the harmful effects that key exposure can cause. In this model, the whole lifetime is divided into distinct periods such that at time period j, the signer holds the secret key $SK_j$ and updates it periodically, while the public key PK is fixed during its lifetime.
In this thesis, we investigate the key exposure problem in a key-evolving protocol. We then present the concept of intrusion-resilience, one of alternative concepts such as forward-security, key-insulated security, etc., standing against the key exposure problem. Our intrusion-resilience has the following property: If secret keys of all periods are not compromised, it is impossible to forge signatures relating to non-exposed secret keys. In the next stage, we propose a key-evolving protocol which guarantees intrusion-resilience. Our scheme is constructed from the unforgeably secure Schnorr signature scheme, one of the schemes based on the $\emph{discrete logarithm problem}$ (DLP). Applying for a threshold scheme is also enabling to make our scheme robust. Finally, we can show equivalence between existence of a forger and feasibility of solving the DLP under the random oracle model.
공개키 기반 구조에서 개인키의 분실은 가장 심각한 문제 중 하나이며 피할 수 없는 문제로 여겨진다. 이것을 키 노출 문제(key exposure problem)라고 한다. 현재 사용되고 있는 전자서명 기법에서 서명자의 개인키가 노출이 되면, 이러한 사실을 인지하지 못한다 하더라도, 마치 서명자가 서명한 문서를 위조 할 수 있다. 이를 방지하기 위하여 전방 보안(forward-secure)서명 기법, 문턱 (threshold) 서명 기법, key-insulated 서명 기법, intrusion-resilient 서명 기법 등의 연구들이 이루어져 왔다. 또한 이에 맞춰 키 전개 (key-evolving) 프로토콜이 개발 되었는데, 이 모든 기법들은 프로토콜 전구간을 부분적인 시간 구간으로 나눈 뒤 각 시간 구간들이 진행 되어 갈 때마다 개인키가 갱신된다. 따라서 공격자가 어느 특정한 시간 구간안의 개인키를 획득하더라도 다른 시간 구간의 개인키는 보호되어 질 수 있다. 물론 보호된 개인키로 서명한 문서 또한 위조 할 수 없을 것이다. 이렇게 시간 구간이 전개해 나가면서 개인키 또한 갱신되고 어느 시점에서도 누구나 서명 문서를 검증 할 수 있어야 하므로, 프로토콜 전 구간 동안 검증에 필요한 공개키는 하나의 값으로 고정될 것이다. 이렇듯 위의 방법은 한 사용자의 개인키가 분실 되더라도 그 분실에서 올 수 있는 심각한 문제를 줄일 수 있는 방법이라고 할 수 있다.
본 논문에서는 암호학적으로 어려운 문제인 이산로그의 어려운 문제(discrete logarithm problem) 에 기반 한 키 전개 프로토콜을 설계하고 이것의 안전성에 대한 정량적 근거를 제시한다. 키 전개 프로토콜이 가능한 공격에 대해서 안전하다는 것을 보장하기 위해 키 전개 프로토콜이 얼마나 안전한 가에 대한 정형적이고 엄격한 수학적 증명이 수반되어야 할 것이다. 키 전개 프로토콜에 대한 안전성이 증명되면 이를 서명 기법에 적용한다. 키 전개 프로토콜이 이산로그의 어려운 문제에 기반하고 있기 때문에 같은 문제에 기반한 모든 서명 기법들에 적용될 수 있다. 따라서 본 논문은 안전한 비밀키 갱신이 가능한 키 전개 서명 기법을 제시하고자 한다.
