[논문]1-라운드 양자간 키 교환 프로토콜

정익래; 이동훈

[국내논문] 1-라운드 양자간 키 교환 프로토콜
One-round Protocols for Two-Party Authenticated Key Exchange 원문보기

정보과학회논문지. Journal of KIISE. 시스템 및 이론, v.33 no.1/2, 2006년, pp.110 - 118

정익래 (고려대학교 정보보호센터) , 이동훈 (고려대학교 정보보호대학원)

초록
AI-Helper

양자간 암호학 프로토콜 디자인에서 잘 고려되지 않는 사항 중에 동시 메시지 전송이 있다. 즉, 듀플렉스(duplex) 채널을 사용해서 통신하는 두 파티는 동시에 메시지를 보낼 수 있다. 하지만 대부분의 양자간 키 교환 프로토콜은 두 파티가 교대로 메시지를 보내는 하프 듀플렉스(half-duplex) 채널을 가정해서 디자인되었다. 이 논문에서 우리는 듀플렉스 채널을 사용할 경우에 동시 메시지 전송을 사용해서 좀 더 효율적인 양자간 키 교환 프로토콜을 설계할 수 있음을 보인다 이 논문에서는 세 개의 안전성 증명 가능한 1-라운드 양자간 키 교환 프로토콜들을 제안한다. 첫 번째 프로토콜은 가장 효율적이며, 세션키 독립성(key independence)을 보장한다. 두 번째 프로토콜은 세션키 독립성과 더불어 전방위 안전성(forward secrecy)을 보장한다. 세 번째 프로토콜은 두 번째 프로토콜과 같은 안전성을 보장하지만, 표준모델(standard model)에서 안전성이 증명된다. 우리가 제안하는 프로토콜들은 최초의 안전성 증명이 가능하면서 전방위 안전성을 제공하는 1-라운드 양자간 키 교환 프로토콜이다.

Abstract ▼ AI-Helper

Cryptographic protocol design in a two-party setting has of tel ignored the possibility of simultaneous message transmission by each of the two parties (i.e., using a duplex channel). In particular, most protocols for two-party key exchange have been designed assuming that parties alternate sending their messages (i.e., assuming a bidirectional half-duplex channel). However, by taking advantage of the communication characteristics of the network it may be possible to design protocols with improved latency. This is the focus of the present work. We present three provably-secure protocols for two-party authenticated key exchange (AKE) which require only a single round. Our first, most efficient protocol provides key independence but not forward secrecy. Our second scheme additionally provides forward secrecy but requires some additional computation. Security of these two protocols is analyzed in the random oracle model. Our final protocol provides the same strong security guarantees as our second protocol, but is proven secure in the standard model. This scheme is only slightly less efficient (from a computational perspective) than the previous ones. Our work provides the first provably- secure one-round protocols for two-party AKE which achieve forward secrecy.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

따라서 키 교환 프로토콜의 계산량이나 주고 받는 메시지의 개수 및 라운드 수가 매우 중요하며, 지금까지 많은 연구가 이루어져오고 있다. 이 논문에서는 인증된 키 교환 프로토콜에 국한하여 논의한다. 인증된 키 교환을 위한 일반적인 방법은 각 사용자가 인증된 공개키-개인키 쌍을 가지고 키 교환을 하는 방식이다.
하지만 만약 우리가 네트웍의 기능을 이용해서 프로토콜을 설계한다면 더욱 효율적인 프로토콜 설계가 가능할 것이다. 이 논문에서는 듀플렉스 채널에서 가능한 동시 메시지 전송 기능을 사용해서 어떻게 효율적인 키 교환 프로토콜을 설계하는지에 대해서 연구한다. 예를 들어서 전통적인 Diffie- Hellman 키 교환 프로토콜에 대해서 생각해보자.
기존 연구와의 관련성을 논하기 전에 먼저 키 교환 프로토콜에서의 안전성 개념에 대해서 살펴보자. 엄밀한 정의는 다음절에 나온다.
각 사용자는 공개키-개인키 쌍을 가지고 있으며 키 교환 프로토콜에서 인증을 위해서 사용한다. 우리는 이 논문에서 양자간 키 교환 프로토콜을 고려하며, 이를 위한 모델을 설명한다. 오라클 는 4의 번째 인스턴스를 의미한다.

가설 설정

키 교환의 안전성을 정의하기 위해서 [1]에서 매칭 대화(mat가ling conversation)라는 개념을 명시적으로 정의하였으며, 이후에 키 교환의 안전성 분석을 위해서 널리 사용되었다[2]. 이 매칭 대화는 양자간 키 교환 프로토콜에서 두 사용자가 서로 메시지를 번갈아 주고 받는 것을 가정한다. 달리 말하면, 사용자들이 하프-듀플렉스(half-duplex) 채널을 이용한다고 가정한 것이다.
이 매칭 대화는 양자간 키 교환 프로토콜에서 두 사용자가 서로 메시지를 번갈아 주고 받는 것을 가정한다. 달리 말하면, 사용자들이 하프-듀플렉스(half-duplex) 채널을 이용한다고 가정한 것이다. 하지만 많은 경우에 있어서 두 사용자는 동시에 메시지를 주고 받을 수 있다.
안전성 개념을 정의하기 위해서 우리는 먼저 공격자의 능력을 정의한다. 우리는 공격자가 일련의 오라클 쿼리(query)를 통해서 통신상에서 흐르는 모든 메시지의 흐름을 제어한다고 가정한다. 공격자의 성공 확률인 어드벤티지를 정의하기 위해서 우리는 실험을 수행하며, 이 실험에서 공격자는 오라클들에게 쿼리를 던지며, 오라클들은 이 쿼리에 응답한다.
(1) 프로토콜은 기본적으로 Reveal이나 Corrupt 쿼리를 허용하지 않을 때 안전해야 한다.
Ne 실험에서 최대 사용자의 수이며, %는 실험에서 최대 세션의 수이다. CDH 문제에 대한 (t, e) 안전성이란 어떤 공격자도 시간 *안에 €이상의 확률로 CDH문제를 풀 수 없다는 가정이다.
Ne 실험에서 최대 사용자의 수이며, #는 실험에서 최대 세션의 수이다. CDH 문제에 대한 #안전성이란 어떤 공격자도 시간 七안 에 €이상의 확률로 CDH문제를 풀 수 없다는 가정이다. 증명.
DDH. 문제에 대한 &4) 안전성이란 어떤 공격자도 시간 t안에 4이상의 확률로 DDH문제를 풀 수 없다는 가정이다.
. Initiate 쿼리는 번째 쿼리를 제외하고는 정상적 으로 수행된다. 曲번째 I, ** j nitiated)에 대해서 X와MAC값인 t를 돌려준다.

제안 방법

예를 들어 [1, 3]의 인증된 키 교환 프로토콜들은 위에서와 같은 방식으로 라운드 수를 줄이는 것이 불가능하다. 우리는 이 논문에서 1 라운드를 필요로 하는 인증된 방식의 키 교환 프로토콜을 설계하며 안전성을 분석한다. 우리가 제안하는 프로토콜은 인터넷과 같은 듀플렉스 채널에서 통신하던 두 사용자가 키를 만들 필요가 있거나 또는 기존의 키를 대체할 새로운 키를 만들 필요가 있을 경우에 일 라운드로 새로운 키를 생성할 수 있다.
명시적 인증성이란 파트너가 이 세션키를 만들었음을 확인할 수 있음을 말한다. 암시 적 인증성은 질문-응답(challenge-response)을 사용해서 항상 명시적 인증성으로 바꿀 수 있으므로 우리는 이 논문에서 암시적 인증성만을 고려해서 프로토콜을 설계한다.
우리는 먼저 가장 간단한 TS1 이라는 프로토콜을 제안한다. 이 프로토콜은 키 독립성은 보장하지만 전방위 안전성은 보장하지 못한다.
두 프로토콜 모두 키 독립성을 보장하지만, TS1 이 좀더 효율적이며, 또한 두 사용자가 같은 계산량을 수행한다는 면에서 대칭적이다. 다음으로 우리는 TS2라는 프로토콜을 제안한다. TS2는 키 독립성과 전방위 안전성 두 가지 모두 보 장하는 1 라운드 프로토콜이다.
우리는 공격자가 일련의 오라클 쿼리(query)를 통해서 통신상에서 흐르는 모든 메시지의 흐름을 제어한다고 가정한다. 공격자의 성공 확률인 어드벤티지를 정의하기 위해서 우리는 실험을 수행하며, 이 실험에서 공격자는 오라클들에게 쿼리를 던지며, 오라클들은 이 쿼리에 응답한다. 오라클 쿼리들은 현실 세계에서 공격자가 행하는 공격을 모델링한다.

이론/모형

우리는 [1]에서 정의된 키 교환 모델을 사용하며, 15]에서와 같이 전방위 안전성을 고려한다. 우리는 키교환 시스템에서의 사용자 수를 7V이라 놓고, 각각의 사용자 ID을 R로 놓는다.

성능/효과

우리는 이 논문에서 1 라운드를 필요로 하는 인증된 방식의 키 교환 프로토콜을 설계하며 안전성을 분석한다. 우리가 제안하는 프로토콜은 인터넷과 같은 듀플렉스 채널에서 통신하던 두 사용자가 키를 만들 필요가 있거나 또는 기존의 키를 대체할 새로운 키를 만들 필요가 있을 경우에 일 라운드로 새로운 키를 생성할 수 있다.
(3) 전방위 안전성(Forward Secrecy): 공격자는 Reveal 쿼리는 할 수 없으나 Corrupt 쿼리는 할 수 있다. 이런 공격자들에 안전한 프로토콜은 전방위 안전성을 보장한다고 한다.

후속연구

키 교환 프로토콜은 사용자들간에 공통된 세션키를 만들며, 이런 세션키들은 안전하지 않은 네트웍을 통해서도 안전한 통신을 가능하게 해준다. 그러므로 안전한 키 교환 프로토콜은 좀 더 복잡하고 안전한 상위 레벨의 어플리케이션을 위한 기본적인 툴로 사용될 수 있다. 따라서 키 교환 프로토콜의 계산량이나 주고 받는 메시지의 개수 및 라운드 수가 매우 중요하며, 지금까지 많은 연구가 이루어져오고 있다.

참고문헌 (28)

M. Bellare and P. Rogaway. Entity Authentication and Key Distribution. Adv. in Cryptology-Crypto '93
S. Blake-Wilson, D. Johnson, and A. Menezes. Key Agreement Protocols and their Security Analysis. 6th IMA Intl, Conf. on Cryptography and Coding, 1997
M. Bellare, R. Canetti, and H. Krawczyk. A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols. STOC '98
D. Denning and G. M. Sacco. Timestamps in Key Distribution Protocols. Comm. ACM 24(8): 533-536 (1981)

상세보기
W. Diffie, P. van Oorschot, and M. Wiener. Authentication and Authenticated Key Exchanges. Designs, Codes, and Cryptography 2(2): 107-125 (1992)

상세보기
W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Information Theory 22(6): 644-654 (1976)

상세보기
L. Law, A. Menezes, M. Qu, J. Solinas, and S. Vanstone. An Efficient Protocol for Authenticated Key Agreement. Technical report CORR 98-05, University of Waterloo, 1988
T. Matsumoto, Y. Takashima, and H. Imai. On Seeking Smart Public-Key Distribution Systems. Trans. of the IECE of Japan, E69, pp.99-106, 1986
National Security Agency. SKIPJACK and KEA Algorithm Specification. Version 2.0, May 29, 1998
S. Blake-Wilson and A. Menezes. Authenticated Diffie-Hellman Key Agreement Protocols. Selected Areas in Cryptography, 1998
R. Ankney, D. Johnson, and M. Matyas. The Unified Model. Contribution to ANSI X9F1, October 1995
C. Boyd and J.M.G. Nieto. Round-Optimal Contributory Conference Key Agreement. Public Key Cryptography, 2003
J. Katz and M. Yung. Scalable Protocols for Authenticated Group Key Exchange. Adv. in Cryptology - Crypto 2003
M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated key agreement secure against dictionary attacks. In Proc. of EUROCRYPT '00
G. Ateniese, M. Steiner, and G. Tsudik. New Multi-Party Authentication Services and Key Agreement Protocols. IEEE J. on Selected Areas in Communications 18(4): 628-639 (2000)

상세보기
M. Bellare, A. Boldyreva, and S. Micali. PublicKey Encryption in a Multi-User Setting: Security Proofs and Improvements. Adv. in Cryptology Eurocrypt 2000
R. Bird, I. Gopal, A. Herzberg, P. Janson, S. Kutten, R. Molva, and M. Yung. Systematic Design of Two-Party Authentication Protocols. IEEE J. on Selected Areas in Communications 11(5): 679-693 (1993)

상세보기
C. Boyd. On Key Agreement and Conference Key Agreement. ACISP 1997
E. Bresson, O. Chevassut, and D. Pointcheval. Provably Authenticated Group Diffie-Hellman Key Exchange-The Dynamic Case. Adv. in CryptologyAsiacrypt 2001
E. Bresson, O. Chevassut, and D. Pointcheval. Dynamic Group Diffie-Hellman Key Exchange under Standard Assumptions. Adv. in Cryptology- Eurocrypt 2002
E. Bresson, O. Chevassut, D. Pointcheval, and J.- J. Quisquater. Provably Authenticated Group Diffie-Hellman Key Exchange. ACM Conf. on Computer and Communications Security, 2001
M. Burmester and Y. Desmedt. A Secure and Efficient Conference Key Distribution System. Advances in Cryptology - Eurocrypt '94
R. Canetti and H. Krawczyk. Universally Composable Notions of Key Exchange and Secure Channels. Adv. in Cryptology - Eurocrypt 2002
I. Ingemarasson, D.T. Tang, and ex. Wong. A Conference Key Distribution System. IEEE Trans. on Information Theory 28(5): 714-720 (1982)

상세보기
M. Just and S. Vaudenay. Authenticated Multi-Party Key Agreement. Adv. in CryptologyAsiacrypt '96
V. Shoup. On Formal Models for Secure Key Exchange. Available at http://eprint.iacr.org
M. Steiner, G. Tsudik, and M. Waidner. Diffie-Hellman Key Distribution Extended to Group Communication. ACM Conf. on Computer and Communications Security, 1996
W.-G. Tzeng. A Practical and Secure-FaultTolerant Conference-Key Agreement Protocol. Public Key Cryptography, 2000

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증