Thesis
PhD Thesis, ICU, 2002
Title: Zero-knowledge Proofs, Digital Signature Variants, and Their Applications
Advisor: Prof. Kwangjo Kim
Abstract:
A protocol is a series of steps, involving two or more entities, designed to accomplish a task. If mistrusting entities interact in non-face-to-face way over an open network environment, such as the Internet, various security requirements can occur, and they can be satisfied by using cryptographic technologies. A cryptographic protocol is a protocol that uses cryptography to achieve the task and to satisfy security requirements together.
Recently, with the advance of the Internet, many traditional off-line services, such as voting, cash, and auction, are moving to online services over the Internet. Because these real world applications are familiar with us, various and complicated security requirements are already existent. To satisfy them, proper cryptographic primitive technologies should be used in well-designed way. Efficiency or performance issue is also very important in the real world. To improve efficiency, some application protocols are designed assuming the existence of trusted third party (TTP) who provides special service. Note that TTP is very familiar experience in our real world. But, in non-face-to-face interaction over an open network environment, trusting somebody over the network is difficult, therefore reducing the trustedness on TTP is an important research issue.
In this thesis, we try to review recent active researches on real world cryptographic protocols, such as electronic voting, electronic auction, mobile agent, and fair exchange, with focus on their security requirements and performances. We also try to point out their possible security problems and give better designs which can solve these problems. As applications of zero-knowledge proofs, we consider secrecy and verifiability in matchmaking protocol, receipt-freeness in electronic voting protocol, and anonymity and verifiability in public auction protocol. As applications of digital signature variants, we consider strong undeniability and fairness in mobile agent and fairness in the exchange protocol of digital signatures.
Zero-knowledge proofs (ZKP) are fundamental cryptographic primitives for multi-party computation and cryptographic protocols. Using these primitives, a prover can convince a verifier that he knows some secret information without exposing it. We review various ZKP techniques and consider divertible ZKP protocols. First, we design a secure matchmaking protocol in which matched couples are found among two groups of participants without exposing the choices of participants. Second, we apply ZKP techniques to construct a receipt-free electronic voting protocol in which divertible ZKPs and designated-verifier ZKPs provide receipt-freeness. Third, we construct an efficient public auction protocol using signature of knowledge and revocable anonymous signature scheme.
Proxy signatures are useful variants of digital signature in which an original signer delegates her signing capability to a proxy signer, and then the proxy signer signs messages on behalf of the original signer. In this study we show several weaknesses of previously proposed proxy signature schemes and propose a general method to construct strong proxy signatures (SPS). We present construction examples of Schnorr-based SPS and RSA-based SPS, and prove that the proposed SPS schemes are as secure as the original signature schemes. We apply SPS to various applications such as secure mobile agent, multi-proxy signature, and partially blind signature.
To implement fair exchange of digital signatures, we need an efficient scheme to commit a digital signature safely to a specific receiver. To satisfy this security requirement in an efficient manner, we introduce a new variant of digital signature called conditional signature which is a specially interpreted signature on a message and a condition together. By imposing a signer-chosen condition which describes expected action of a specified receiver, conditional signature can be used as a private negotiation statement in two-party communication. We model negotiation problem using conditional signature and then construct a fair exchange protocol. We show that matching negotiation and real exchange give a fair exchange of digital signatures.
요 약
프로토콜이란 둘 이상의 개체간에 특정 작업목표를 수행하기 위해 설계된 일련의 작업단계를 말한다. 인터넷과 같은 개방형 비대면 네트웍 환경에서 상호 신뢰하지 못하는 개체간에 통신이 이루어진다면 여러가지 보안 요구사항들이 제기되며 이들은 암호기술을 이용하여 해결될 수 있다. 암호프로토콜이란 작업목표와 보안요구사항들을 함께 만족시키기 위하여 암호기술을 이용하는 프로토콜을 말한다.
최근 인터넷의 발전에 따라 투표, 현금, 경매 등 기존의 많은 오프라인 서비스들이 인터넷상의 온라인 서비스로 전환되고 있다. 이러한 실생활 응용분야는 우리가 이미 익숙하게 이용하고 있기 때문에 많은 복잡한 보안요구사항들이 존재한다. 이들을 만족시키려면 응용서비스는 여러가지 암호기반기술들을 이용하여 세심하게 설계되어야 한다. 효율성은 실생활 응용분야에서 매우 중요한 요소중 하나이다. 효율성을 높이기 위해서 어떤 응용 서비스들은 신뢰기관을 가정하여 이를 기반으로 설계되기도 한다. 신뢰기관은 실세계에서 매우 익숙한 개념이다. 그러나 비대면의 개방형 네트웍 환경에서 네트웍상에 존재하는 특정 개체를 신뢰한다는 것은 어려운 문제라고 볼 수 있기 때문에 신뢰기관에의 의존을 줄이는 것도 중요한 연구 이슈중의 하나이다.
이 논문에서는 전자투표, 전자경매, 이동에이전트 등 현재 활발히 연구되고 있는 실생활 암호프로토콜들에 대한 기존 연구들을 분석하였으며 특히 보안요구사항과 효율성에 초점을 두고 분석하였다. 기존 연구들의 보안상 문제점을 지적하고 이들을 해결할 수 있는 개선된 암호프로토콜을 제안하고자 하였다. 영지식 증명의 응용분야로서 전자중매 프로토콜에서의 기밀성과 검증성, 전자투표 프로토콜에서의 매표방지 기능, 전자경매 프로토콜에서의 익명성과 전체검증성에 대해 연구하였다. 또한 변형 전자서명기법의 응용분야로서 이동에이전트에서의 부인방지 및 공정성, 공정한 서명교환 프로토콜에 대해 연구하였다.
영지식 증명은 다자간 계산과 암호프로토콜을 설계하기 위한 핵심 암호기반기술중의 하나이다. 영지식 증명 기법을 이용하면 증명자는 검증자에게 비밀정보를 노출시키지 않고도 그 정보를 알고 있다는 사실을 증명할 수 있다. 여기에서는 다양한 영지식 증명 기법들에 대해 살펴보고 변환형 영지식 증명 기법(divertible ZKP)을 고려한다. 첫번째 응용으로 두개의 참여자 그룹 사이에 참여자들의 선택을 노출시키지 않고 커플을 찾아내는 안전한 전자중매 프로토콜을 설계하였다. 둘째, 변환형 영지식 증명기법과 검증자지정 영지식 증명(designated-verifier ZKP)을 이용한 매표방지 가능한 전자투표 프로토콜을 설계하였다. 세째, 영지식서명(signature of knowledge)과 익명성취소 가능한 익명전자서명을 이용하여 효율적인 공개경매 프로토콜을 설계하였다.
대리서명은 원서명자가 대리서명자에게 서명능력을 위탁하고 대리서명자는 원서명자를 대신하여 서명을 생성할 수 있는 변형 전자서명 기법이다. 여기에서는 기존의 대리서명 기법들의 취약점을 제시하고 이들을 해결할 수 있는 강한대리서명을 구성하는 일반적인 기법을 제시한다. 그 사례로서 Schnorr 서명과 RSA 서명에 기반한 강한대리서명 기법을 제시한다. 아울러 이들을 안전한 이동에이전트, 복수대리서명, 부분은닉서명 등에 적용하였다.
공정한 전자서명 교환 프로토콜을 구성하기 위해서는 전자서명을 특정 수신자에게 안전하게 위탁(commit)하는 기법이 필요하다. 이를 구현하기 위해 조건부 서명이라는 새로운 개념을 제시하였다. 이것은 서명자가 특정 수신자에게 메시지에 대한 서명을 조건부로 위탁하는 방법이다. 서명자가 특정 수신자에 대해 서명을 위탁하면서 조건을 지정할 수 있기 때문에 조건부 서명은 개인간의 교섭(negotiation) 또는 흥정의 목적을 위해 사용될 수 있다. 본 연구에서는 교섭 프로토콜을 조건부 서명을 이용하여 모델링하였고 이를 기반으로 공정한 전자서명 교환 프로토콜을 구성하였다. 교섭을 완료한 후 이에 기반하여 서명을 교환함으로써 공정한 전자서명 교환이 가능함을 보였다.
Download : PhD Thesis
Master Thesis, 서울대학교 물리학과, 1988
Title: Electrical Transport of Polymer TCNQ Complex Salts and Its Monomeric Model Compounds
Advisor: Yungwoo Park
Download: Master Thesis