A digital signature is one of the most widely used algorithms in software applications, due to its efficiency. It has a lot of types to generate signatures with its usage. Each algorithm offers their own security properties as well as standard security requirements. In practice, the greatest threat against the security of a digital signature scheme is exposure of the secret key, due to compromise of the security of the underlying system storing the key. The danger of successful cryptanalysis of the signature scheme itself is hardly as great as the danger of key exposure, as long as we stick to well known schemes and use large security parameters. But in real world, people are easy to lose their secret key and in most cases they are not aware of the fact. The most widely considered solution to the problem of key exposure is distribution of the key across multiple servers via secret sharing[10, 41]. However distribution of the key is quite expensive. Thus while we expect digital signatures to be very widely used, we do not expect most people to have the luxury of splitting their keys across several machines. Other ways of protecting against key exposure include use of protected hardware such as Smartcards, but these can be costly or impractical.
To protect some aspects of signature security against the exposure of the secret signing key, the notion of forward security is suggested, in particular without requiring distribution or protected storage devices, and without increasing key management costs. Anderson [1] used firstly the notion of forward secrecy in digital signature scheme. After that Bellare and Miner[11] suggested the first practical signature scheme that guarantees the forward security. And it is extended to intrusion resilient scheme by Itkis and Reyzin[25]. But these schemes are not compatible with previous conventional signature scheme.
With a different notion, Hwang, Lee and Lim [22] proposed $\emph{c}$-times digital signature scheme which restricts the number of messages that can be signed. This scheme employs signature scheme that if a signer generates signatures more than threshold values $\emph{c}$, then anyone can reveal the signer's secret key. By restricting the signing capability, we can reduce the risk of exposure of the secret signing key. This scheme is compatible with conventional scheme, but it has limitation in its usage.
In this thesis, we focus on the way to reduce the risk of exposure of secret signing key. We also consider the compatibility with the well-know digital signature scheme such as Schnorr signature scheme, ElGamal signature scheme and DSS (Digital Signature Standard). We propose key evolving forward secure signature with bilinear pairing based on G-DH problem. We prove the security of our scheme based on the fact that the C-DH problem is hard in the additive group of points of elliptic curve over a finite field. The security is analyzed in mathematical way such as cryptographic reduction. We also propose a practical \emph{c-times} signature. This scheme enables us to restrict the signing capability of proxy signer in terms of limiting the number of signatures. Our scheme is practical in the fact that it is compatible with conventional digital signature scheme.
전자서명 기법은 그 효율성 때문에 응용소프트웨어에서 가장 많이 쓰이는 어플리케이션 중의 하나이다. 전자서명은 사용 용도에 따라 다양한 서명 생성 기법이 존재한다. 각 서명기법은 표준 보안요구 사항뿐만 아니라 사용 용도에 따른 고유한 보안요구 사항을 제공하고 있다. 전자서명 알고리즘 자체의 안전성은 검증된 전자서명 기법을 사용하게 되면 현재의 계산능력에서는 안전하다는 사실이 대부분 증명되어 있다. 그러나 실생활에 있어서 전자서명의 가장 큰 위험요소는 알고리즘 자체의 안전성 보다는 비밀키 노출에 의해 안전성이 파괴되는 것이다. 비밀키의 노출은 사용자의 부주의나 의도적인 접근으로 쉽게 이루어 질 수 있고, 실제 생활에서 흔히 일어나고 있는 일이다. 또 이렇게 비밀키를 노출하게 되면, 안전성이 증명되어 있는 전자서명 알고리즘도 해당 비밀키에 대해서는 안전성이 모두 파괴된다. 이러한 문제를 해결하기 위한 가장 일반적인 방법이 비밀분산 기법이다[10,41]. 그러나 비밀분산기법은 다수의 사용자에게 비밀을 분산함으로써 고비용을 유발시킨다. 따라서 일반적인 전자서명 기법에는 적합하지 않다. 또한 스마트카드와 같이 하드웨어를 이용하는 방법은 특별한 목적으로 사용하게 되면 매우 유용하지만 비밀분산 기법과 같이 고비용을 유발하므로 일반적인 전자서명기법에서는 적합하지 않다.
비밀키 노출 시에 비밀분산기법이나 하드웨어 장치를 사용하지 않고 피해를 최소화 하는 방법으로 전방보안의 개념이 제안되었다. 전자서명기법에서는 Anderson[1]이 처음 전방보안(Forward Secure)의 개념을 사용하였다. 이후 Bellare 와 Miner[1]가 처음으로 전방보안을 보장할 수 있는 실용 가능한 전자서명기법을 제안하였다. Itkis와 Reyzin[25]은 전방보안의 개념을 확장하여 침입감내 서명기법(Intrusion Resilient Signature Scheme)을 제안하였다. 또 다른 접근 방법 중의 하나로 황정연등[22]은 $\emph{c-times}$ 전자서명기법을 제안하였다. 이 기법은 서명자의 서명 능력을 $\emph{c}$번으로 제한하는 방법을 사용한다. 이 서명기법은 $\emph{c}$ 차수의 다항식을 사용하여 비밀값에 대한 정보를 각 서명과 함께 공개함으로써 서명자가 $\emph{c}$번 이상의 서명을 생성하게 되면 자신의 비밀값이 드러나게 되는 방법을 사용하고 있다. 이 기법은 기존 서명기법과 호환된다는 점에서 실용적이라고 할 수 있지만 사용목적이 제한되어 있다.
본 학위논문에서는 비밀키 노출에 의해 발생하는 문제점들에 주목하였다. 또한 전자서명 기법을 제안하는데 있어서 Schnorr,ElGamal 그리고 DSS와 같은 기존 서명기법과의 호환성을 고려하였다. 본 학위논문에서는 전방보안을 보장하는 키 전개방식 서명기법을 설계하고 이 서명 기법의 안전성에 대한 정량적 근거를 제시 한다. 특히 복잡도이론(Complexity Theory)에 근거한 암호학적 축소(Cryptographic Reduction) 기법을 사용하여 주어진 시스템의 안전성이 얼마나 되는지 공격자의 자원에 관한 함수로 제시한다. 또 Schnorr 서명기법을 응용한 $\emph{c-times}$ 서명기법을 설계하고 효율성을 평가 하였다. 우리가 제안하는 서명기법은 Schnorr 서명기법 뿐만 아니라 Diffie-Hellman 가정을 기반으로 하는 전자서명 기법들과 호환가능하다. 또한 제안하는 서명기법의 안전성을 증명함으로써 제안하는 서명기법의 안전성이 기존의 서명기법의 안전성과 동일하거나 더 안전하다는 것을 증명한다.
