KR0148300B1 - 복수의 정보 처리 장치를 구비하는 통신 시스템에서 비밀 정보의 분산, 디지탈 서명의 생성 및 인증의 수행 방법과 그 통신 시스템 - Google Patents

Abstract

본 발명의 요약서는 실제적인 계산량과 통신량으로 확인가능한 비밀 분산을 수행하는 것이다. 또, 이 프로세스를 사용해서 분산된 디지털 서명이 생성되거나 또는 분산된 인증 서버가 제공된다.

비밀 통신로와 방송용 통신로를 통해 다수의 정보 처리 장치들을 접속하는 통신 시스템에서, 정보 처리 장치(d)는 비밀 정보(s)로부터 비밀 행렬(11, ......, 1k)을 생성하고, 각 장치(i)에 대한 제1 정보 세그먼트를 추출하며, 이를 각 장치(i)로 비밀리에 전송한다. 정보 처리 장치(d)는 비밀 행렬 상에 해시 함수를 수행하고 그 출력값을 방송한다. 각 정보 처리 장치(i)는 난수를 생성 및 방송하는 반면, 정보 처리 장치(d)는 난수값에 따라 제2 정보 세그먼트를 부분 배열로부터 생성 및 방송한다. 각 정보 처리 장치(i)는 제1 정보 세그먼트 및 난수에 따라 제3 정보세그먼트를 생성하고, 비밀 정보가 제3 정보 세그먼트를 제2 정보 세그먼트와 비교하므로써 올바르게 분산되었는지를 확인한다. 이 비밀 정보 분산 방법을 사용하므로써 서명자 그룹에 속하는 장치들은 서명을 협동하여 생성하고, 인증 서버를 구성하는 다수의 장치들은 인증을 협동하여 제공한다.

Description

복수의 정보 처리 장치를 구비하는 통신 시스템에서 비밀 정보의 분산, 디지털 서명의 생성 및 인증의 수행 방법과 그 통신 시스템

제1도는 본 발명의 한 실시예에 따른 통신 시스템의 구성을 도시한 블럭도.

제2도는 각 가입자가 사용하는 정보 처리 장치의 구성을 도시한 블럭도.

제3도는 비밀과 부분 행렬간의 관계를 도시한 도면.

제4도는 일방향성 해시 기능 동작을 위한 처리를 도시한 도면.

제5도는 비밀 분산 처리를 위한 과정을 도시한 도면.

제6도는 비밀 복원 처리의 과정을 도시한 도면.

제7도는 분산과 계산처리를 설명하는 도면.

제8a도 내지 8c도는 입력 메시지로부터 해시 값을 얻기 위한 처리를 도시한 도면.

제9도는 디지탈 서명이 분산되면서 생성되는 통신 시스템을 도시한 블럭도.

제10a도 및 10b는 비밀 키 및 공개 키 생성 처리를 위한 과정을 설명하는 도면.

제11도는 분산된 비밀 선형 결합 처리를 위한 입력과 출력 관계를 설명하는 도면.

제12도는 분산된 서명 생성 처리의 과정을 설명하는 도면.

제13a도 및 13b도는 비밀 키 및 공개 키 생성 처리의 과정을 설명하는 도면.

제14도는 비밀 분산 승산 처리를 설명하는 도면.

제15도는 분산된 비밀 선형 결합 처리를 위한 입력과 출력 관계를 설명하는 도면.

제16도는 분산된 서명 생성 처리의 과정을 설명하는 도면.

제17도는 확인가능한 비밀 분산 승산 처리의 과정을 설명하는 도면.

제18도는 확인가능한 비밀 분산 승산 처리의 과정을 설명하는 도면.

제19도는 비밀 분산 승산 처리의 과정을 설명하는 도면.

제20도는 분산 서명 생성 처리의 과정을 설명하는 도면.

제21도는 분산이 인증을 위해 수행되는 통신 시스템의 구성을 도시한 블럭도.

제22도는 분산된 선형 결합 처리를 설명하는 도면.

제23a도 및 23b도는 의사 난수 발생 처리의 과정을 도시한 도면.

제24a도 및 24b도는 비밀 키 분산 및 암호 처리의 과정을 도시한 도면.

제25a도 및 25b도는 분산된 인증 프로토콜의 과정을 도시한 도면.

제26도는 오프 라인 의사 난수 발생처리의 과정을 도시한 도면.

제27도는 온 라인 비밀 키 전달 처리의 과정을 도시한 도면.

제28a 및 28b도는 분산된 인증 프로토콜의 과정을 도시한 도면.

제29a 및 29b도는 분산된 인증 프로토콜의 과정을 도시한 도면.

제30a 및 30b도는 분산된 인증 프로토콜의 과정을 도시한 도면.

제31a 및 31b도는 종래의 분산된 인증 프로토콜을 도시한 도면.

*도면의 주요 부분에 대한 부호의 설명

11 : 정보 처리 장치 12 : 방송 통신로

21 : 통신 장치 22 : 연산 처리 장치

23 : 난수 발생 장치 24 : 기억 장치

83 : 해시 연산 처리 장치 81 : 암호화 회로

[발명의 배경]

[이용 분야]

본 발명은 통신 시스템에서 통신로를 통해서 서로 연결되는 정보 처리 장치(이하, 가입자(subscriber)로 칭함) 중의 하나로 전송되는 비밀 정보를 가입자들 사이에서 분산(share)시킬 수 있는 방법과 이러한 방법을 채택하는 통신 시스템에 관한 것이다. 또, 본 발명은 수많은 다수의 가입자들로 구성되는 그룹을 위해 디지탈 서명을 분산 또는 생성시키는 방법과 이러한 방법을 채택하는 통신 시스템에 관한 것이다. 더우기, 본 발명은 정보가 적절한 송신기로부터 송신되었음(같은 경로의 다른 장치가 수정하지 않았음)을 정보 수신기로 하여금 검증할 수 있게 하는 인증 기능을 다수의 가입에게 분산시키는 방법과 이러한 방법을 채택하는 통신 시스템에 관한 것이다.

[종래 기술]

종래, 정보 통신 시스템의 신뢰성을 높이는 기술의 하나로서 정보의 리더던시(redundancy: 용장도라고도 함)를 증가시키는 코딩 기법이 알려지고 있다.

특히, 통신로에 에러가 발생해도 그 에러를 검출 또는 정정할 수 있는 에러정정코드는 신뢰성 높은 통신 시스템을 효율적으로 실현할 수 있는 기술로서 자주 사용되고 있다.

더우기, 통신 시스템에서 비밀 정보를 지키면서 신뢰성을 높이는 수단으로서도 비밀 정보를 분산시켜 리던던시를 증가시키는 코딩 기법이 유효하다는 것을 에이. 샤머(A. Shamir)가 표현하고 있다. (How to Share a Secret, Communications of the ACM, Vol. 22, 11, 1979 참조).

복수의 가입자 단말로 구성되는 통신 시스템에서, 비밀 정보를 분산하는 것(즉, 모든 가입자 간에 비밀 정보를 분산 유지하는 것)은 비밀 정보의 보호하는 측면에서 특정한 단일 가입자의 물리적인 안전성에만 의존하지 않으므로 다음과 같은 두가지 의미에서 신뢰성이 높아진다(폴트 톨러런스(fault tolerance: 고장 허용도)를 실현할 수 있다)고 생각된다.

하나는 비밀 정보가 분산되어도 누출되지 않고 보호된다는 의미와 신뢰도로서 이를 비밀성에 대한 폴트 톨러런스라고 한다. 또 하나는 분산된 비밀 정보에 부정이 행해져도 출력을 얻을 있다는 의미의 신뢰도로서 이를 정당성에 대한 폴트 톨러런스라고 한다. 여기서, 물리적인 안정성은 어떤 가입자가 갖고 있는 정보가 임의의 다른 가입자에게 누출되지 않는것 및 어떤 가입자가 수행하고 있는 계산이 다른 가입자에 의해서는 수행될 수 없는 것을 의미한다.

특히, 어떤 비밀 정보(x)가 모든 가입자간에 분산 유지되는 것은 이하의 조건(a), (b)를 만족시키도록 각 가입자(i)가 비밀정보(x)에 대응하는 정보 세그먼트를 생성하고 다른 가입자에게 분산하는 것을 의미한다.

(a) 비밀 정보(x)를 복원하기 위해서는 t+1인의 가입자의 정보 세그먼트가 필요하다. 이후, 이 비밀 정보를 복원하기 위한 필요한 가입자의 수(t+1)를 임계값이라고 한다.

(b) 가입자로부터 얻어진 부분 정보 세그먼트의 수가 임계값 미만(t 이하)이라면, 비밀 정보에 관한 어떤 데이타도 얻을 수 없다.

종래의 기본적인 비밀 분산 방식은 에이. 샤머(How to Share a Secret, Communications of the ACM, Vol. 22, 11, 1979)에 의해 제어되고 다음과 같이 실현되었다.

어떤 가입자의 정보를 복수의 가입자에게 비밀리에 분산하기 이해서 상수항이 상술한 비밀 정보가 되는 n차 다항식 f(x)를 임의로 선택하고, n개의 다른 값에 대한 이 다항식의 값 f(i)(i=1, ... , n)를 각 가입자에 분산한다. 각 가입자에게 분산되는 다항식의 값f(i)는 상숭한 정보 세그먼트가 된다. 이로써, 비밀정보는 t+1개의 정보 세그먼트를 이용한 다항식 보간에 의해 복원될 수 있다(t 이하의 정보 세그먼트에서는 비밀 정보에 관한 어떤 정보도 얻을 수 없다.)

이상과 같이 해서 비밀 정보를 분산하는 방식을 임계값 스킴(threshold scheme)이라고 하며, 상술한 비밀성에 대한 폴트 톨러런스를 실현할 수 있다고 고려된다. 여기서, 상술한 정의만으로는 비밀정보가 분산된 때, t+1이상의 가입자의 정보 세그먼트가 모여도 부정확한 정보 세그먼트가 있는 경우에는 원래의 비밀정보(x)를 복원할 수 없는 경우가 있다. 즉, 분산된 비밀 정보의 정당성(right of access)에 대한 폴트 톨러런스가 보증되지 않는 것을 알 수 있다. 따라서, 상술한 분산 시스템에서 완전하게 신뢰도를 높이기 위해서는 비밀성과 정당성에 대한 폴트 폴러런스를 동시에 고려할 필요가 있다.

어떤 에러를 발생시키는 가입자에 대해서도 대처할 수있는 비밀 분산 방식으로서 제안된 확인가능한 비밀분산은 상술한 임계값 스킴의 조건(a), (b)에 다음의 조건(c), (d)를 부가하므로써 정의되고 있다.

(c) 부정확한 정보 세그먼트가 올바른 정보 세그먼트와 혼재하고 있어도 t+1개의 올바른 정보 세그먼트가 있으면 원래의 비밀 정보를 복원하기에 충분하다.

(d) 모든 가입자가 이 비밀 정보 세그먼트를 받아들인 때, 이 정보 세그먼트가 어떤 비밀 정보(x)를 복원하기 위해 올바른 정보인지의 여부를 확인할 수 있다.

비밀 통신로를 갖는 통신 시스템에 대해서 에러가 있는 가입자의 수가 전가입자의 1/3보다 적으면, 어떤 에러가 있는 가입자에게도 대처할 수 있는 확인가능한 비밀 분산 방식(임계값 t가 t n/3을 만족한 경우)을 구성하기 위해서는 종래의 에러 정정 코딩 기법으로 충분하다는 것이, M. Ben-Or, S. Goldwasser, A. Wigderson(Completness Theorems for Non-Crytographic FaultTolerant Distributed Computation, ACM STOC 1988)에 의해 설명되고 있다.

더구나 전가입자의 1/2 보다 적은 수이면 어떤 에러가 있는 가입자에게도 대처할 수 있는 확인가능한 비밀 분산 방식을 구성하기 위해서는 조건을 더 부가할 필요가 있다. 모든 가입자가 같은 메시지를 수신한 것을 확인할 수 있는 방송형통신로를 모든 가입자가 갖는 다고 할 경우, 다음의 2가지의 구성방식이 알려지고 있다.

(1) 영지식 대화 증명 시스템(zero-knowledge proof system)(쯔지이 및 가사하라; 암호와 정보 시큐리티, 쇼코도, 1990 참조)에서 사용되고 있는 컷 앤드츄스(cut and choose)라고 하는 기술을 이용하여, 상술한 에이, 샤머의 기본적인 비밀 분산 방식으로 원래의 비밀(s)를 분산한 후에 분산된 정보 세그먼트 s_i(i=1, ... ,n)을 또 분산하는 방식.

특히, 확인 가능한 비밀 분산 시스템으로 분사된 모든 정보 세그먼트는 비밀 정보 세그먼트(s_i)에 대한 비밀 부분이 되도록 생성된 부분 행렬로 고려될 수 있다. 단, 상술한 컷 앤드 츄스기술을 이용하므로써 상술한 조건(d)에 의한 확인은 통계적 확인이 되고 비밀 정보를 복원할 수 있는 올바른 분산이 행해지고 있는지의 여부를 나타내는 판정 출력에 에러의 확률이 생긴다. 다만, 이 에러의 확률은 설정되는 안정성 파라미터에 의해 무시할 수 있는 정도까지 작아질 수 있다. 구체적인 예로는 T. Rabin, M. Ben-Or(Verifiable Secret Sharing and Multiparty Protocols with Honest Majority, ACM STOC 1989)에 의한 방식이 있다.

(2) 비대화형에서 특수한 대수학적 성질을 갖는 일방향성 함수를 이용하는 방법.

이와같이 구성된 비밀 분산 방식의 안전성은 그 대수학적 성질을 만족시키는 일방향성 함수의 역원을 계산하는 것이 곤란하다(실용적인 역원계산 방식이 존재하지 않음)고 하는 암호적인 가정을 할 필요가 있다. 구체적으로는 P. Feldman(A Practical Scheme for Non-Interactive Verifiable Secret Sharing, IEEE FOCS, 1987)에 의해서 제안되고 있다.

또한, 상술한 확인가능한 비밀 분산 방식을 이용하므로써 주어진 어떤 유한 집합(finite set)상의 분산 연산을 안전하게 실현하는 회로를 구성할 수 있다는 것이, T. Rabin, M. Ben-Or(Verifiable Secret Sharing and Multiparty Protocols with Hnoest Majority, ACM STOC, 1989), D Beaver(Secure Multiparty Protocols and Zero-Knowledge Proot Systems Tolerating a Faulty Minority, Journal of Cryptology, 1991, 4, pp. 75-122; Efficient Multiparty Protocols using Circuit Randomization, Advances in Crytology-Cryto '91, 1992) 및 M. Franklin, S. Haber(Joint Encryption and Message-Efficient Secure Computation. Advances in Crytology-Cryto '93, 1994)에 의해 표현되고 있다.

그러나, 상술한 대화 방식(1)에서는, 1비트를 분산하는데 필요한 통신량이 안전성 파라미터를 k(통상 100이라는 값이 사용됨)으로 표현한 경우 n개의 비밀 부분에 대해 n^3k ^2(여기서 a^b는 는 a^b를 의미함)의 차수(order)가 되는 것으로 알려지고 있으나, 효율적이지는 않다.

비대화형의 암호 방식(2)에서는 n개의 비밀 부분에 대해 n회의 차수의 특수한 일방향성 함수의 계산처리를 행할 필요가 있으며, 특히 비밀 분산 처리를 안전하게 분산 계산을 실행하기 위한 부분 계산을 실행하기 위한 부분 처리로 해서 이용하는 경우에는 실행해야 하는 비밀 분산 처리의 계수가 많아지고(예컨대, 분산 승산에서는 n²의 차수가 된다), 전체적으로는 비실용적 계산량이 된다.

이상과 같이 종래 기술에서 대화방식(1)은 통신량이 아주 커지고, 암호 방식(2)은 계산량이 아주 커지는 문제가 있다.

대부분의 종래의 통신 시스템에서는 정보를 호출된 패킷인 데이타 블럭 단위로 전송한다. 패킷이 목적지로 전송되는 경우에도 통신 시스템을 구성하는 모든 장치(가입자 단말)가 이 패킷을 수신할 수 있다. 더우기, 다수의 장치가 같은 통신로를 통해 접속되어 있기 때문에 패킷의 전송원을 지정하기는 곤란하다. 따라서, 이러한 통신 시스템은 다른 목적지로 전송되는 패킷을 부당하게 획득하는 도청 및 기만(deception)같은 침범에 속수무책이다. 여기서 어떤 장치는 다른 장치의 식별 사항을 부당하게 도용하고 있다.

전송된 정보가 전송 목적지로서 선택한 가입자에게만 제공되고 비인증 접근이 존재하지 않는다( 정보가 비밀로 유지됨)는 것을 보증하도록 위의 통신 시스템에 대한 보안을 제공하는 방법에 대해 논의하자. 암호기술(이께노 및 고야먀, Current Cryptology Theory, pp. 224-225, IEEE)은 공지된 유용한 기술중의 하나이다.

암호기술은 비밀 정보를 유지하는 기능은 물론, 수신된 정보를 확인하는 기능, 디지털 서명이라고 하는 기능, 즉 수신된 정보가 지정된 장치로부터 전송되었다는 것을 제 3자에게 확인하는 기능을 구현하는데 효과적이다. 디지탈 서명 방식의 암호 통신을 수행하므로써 도청과 기만은 방지될 수 있다.

공개 키 암호 시스템(예로서 A Method For Obtaining Digital Signatures and Piblic-Key Crytosystems, R. Rivest, A.Shamir, L. Adleman, Communications of the ACM, 21, 2, 1978, pp. 120-125, 또는 미국 특허 제 4, 405, 828호 참조)중의 하나인 RSA 암호 시스템을 사용하는 확인 및 디지탈 서명방법은 폭넓게 공지되어 있다.

RSA암호 시스템과는 다른 공개 키 암호 시스템을 사용하는 다른 디지탈 서명방법은 에이. 피아트(A. Fiat)와 에이. 샤머가 제안한 방식이다. (How to Probe Yourself; Practical Solutions to Identification and Signature Problems, Advances in Cryptology-Crypto '87, Lecture Notes In Computer Science, 263, Springer-Verlag, 1988, pp. 186-194, 또는 미국 특허 제 4, 748, 668호 참조). 이 방법에 따라 다음의 과정이 주어진 메시지에 대한 효율적인 식별과 디지탈 서명을 제공하도록 수행되다.

(1) 주어진 메시지에 대한 디지탈 서명을 처리하는 장치, 즉 통신 시스템을 위해 신뢰성 있는 센터로서의 역할을 하는 장치는 {1, ... , N-1}중에서 임의로 요소(a)를 선택하고(여기서 N은 두 소수, p 및 q의 곱이다), 선택한 요소는(a)는 서명을 처리하는 장치에 대한 비밀 정보로 고려된다.

(2) 비밀 요소(a)를 선택한 장치는 a¹mod N을 계산하고 (여기서 1은 gcd(1, 11ambda(N))=1을 만족하며, 1ambda(N)=1cm(p-1), gcd(a, b)는 최대 공약수, 및 1cm(a, b)는 최소 공배수), 장치에 의해 발생된 디지탈 서명을 확인하기 위해 이 결과를 공개 정보로서 채택한다.

(3) 주어진 메시지(m)에 대한 디지탈 서명을 발생시키는 장치가 수행하는 프로세스에서, R=r ^1 mod N은 1, ... , N-1 중에서 임의로 선택되는 비밀 요소(r)를 사용하여 얻어지고, R:m은 주어진 입력인 공개 메시지(m)을 연속하므로써 얻어지는 값이며, e=h(R:m)은 소정의 함수(h)를 사용하여 계산된다. 이후, 입력으로서 위의 값들을 사용하여 s=r^*a ^e(mod N)을 계산한다. 주어진 메시지에 대한 디지탈 서명으로서 얻어진 값(s, R)을 채택한다.

(4) 주어진 메시지(m)에 대한 디지탈 서명(s, R)을 확인하기 위해서, s ^1 mod N 및 R^*(a ^1) ^(h(R:m)) mid N이 계산되고 이 결과들이 같은 때 디지탈 서명이 확인된다.

효율적이 식별과 주어진 메시지에 대한 디지탈 서명을 얻기 위한 C. P. Schnorr에 의해 제안된 방법(Efficient Identification and Signatures For Smart Cards, Advances In Crytology-Crypto '89, Lecture Notes In Computer Science, 435, Springer-Verlag, 1900. pp. 239-252 또는 USP 4, 995, 082 참조)에 따르면, 다음의 과정이 수행된다.

(1) 주어진 메시지에 대한 디지탈 서명을 계산하는 장치 또는 통신 시스템에 대한 신뢰성 있는 센터로서 기능하는 장치는 1, ... , p (여기서는 p는 소수) 중에는 무작위로 원소 a를 선택하고 선택된 수 a는 서명을 계산하는 장치에 대한 비밀 정보로서 간주된다.

(2) 비밀원소 a를 선택하는 장치는 g^-a모드 q를 계산하고(여기서 q는 p는 q^-1의 제수이도록 하는 소수이고 유한 집합 GF(q)에 속하는 원소 q의 디지트의 수는 p이다), 장치에 의해 발생된 디지탈 서명을 검증하기 위한 공개 정보로서 이 결과를 이용한다.

(3) 주어진 메시지 m에 대한 디지탈 서명을 발생하기 위해 장치에 의해 수행되는 과정에서, 1, ..., p 중에서 무작위로 선택된 비밀 원소 r을 사용함으로서 얻어진 R=g^r모드 q, 및 주어진 공개 메시지 m을 연속시킴으로써 얻어진 값인 R:m은 입력으로서 간주되고, e=h(R:m)은 선정된 함수 h를 사용함으로써 계산된다. 그 다음에, s=r+a^*e(모드 p)는 상기 값을 입력으로 사용함으로써 계산된다. 얻어진 결과 S 및 R은 주어진 메시지에 대한 디지탈 서명으로서 이용된다.

(4) 주어진 메시지 m에 대한 디지탈 서명(s, R)을 검증하기 위해서, h(g ^s((g ^(-a) ^h(R:m))(mod q/m(R:m))이 계산되고(x＾y는 x^y를 나타냄), 디지탈 서명은 이 결과와 e가 동일한 때 학인된다.

효율적인 식별과 주어진 메시지에 대한 디지탈 서명을 획득하기 위한 T.ElGamal에 의해 제안된 방법 (A Public-key Crytosystem and A signature Scheme Based On Discrete Logarithms, IEEE Transactions n Information Theory, IT-31, 4, 1985, pp-469-472, American National Standard X9.30-199x, digital Signature Algorithm, Feb. 1992 참조)에 따르면, 다음의 과정이 수행된다.

(1) 주어진 메시지에 대한 디지탈 서명을 계산하는 장치, 또는 통신 시스템에 대해 신뢰성 있는 센터로서 가능한 장치는 {1, ..., p}(여기서 p는 소수)중에서 무작위로 원소 a를 선택하고, 선택된 원소는 a는 서명을 계산하는 장치에 대한 비밀 정보로서 간주된다.

(2) 비밀 원소를 선택한 장치는 g ^(-a)mod q를 계산하고 (여기서 q는 p가 q^-1의 제수이도록 하는 소수이고 유한 집합 GF(q)에 속하는 원소 q의 디지트의 수는 p이다), 장치에 의해 발생된 디지탈 서명을 검증하기 위한 공개 정보로서 이 결과를 이용한다.

(3) 주어진 메시지 m에 대한 디지탈 서명을 발생시키기 위해서 장치에 의해 수행된 과정에서, {1, ..., p} 중에서 무작위로 선택된 비밀 원소r을 사용함으로써 획득된 R=gR:mod q와, 선정된 함수 h에 의해 얻어진 값인 e=h(m)을 사용함으로써, 주어진 공개 메시지는 입력으로서 간주되면서, s=(e+R^*a)^*r^-1mod p가 계산된다. 얻어진 결과 s 및 R은 주어진 메시지에 대한 디지탈 서명으로서 이용된다.

(4) 주어진 메시지 m에 대한 디지탈 서명(s, R)을 검증하기 위해서, (q＾(-a))^ R(g＾r) s 및 g＾m(mod q)가 계산되고, 디지탈 서명이 이들 결과가 동일할 때 확인된다.

한편, 비밀을 유지하고 검증을 달성하는 상술한 정보 통신 시스템에 대해, Y, Desmedt와 Y. Frankel은 정보 비밀을 유지하면서 신뢰성을 증가시키는 수단으로서, 비밀 정보를 분산시키고 통신 경로에 의해 접속된 다수의 컴퓨터 중에서 주어진 메시지에 대한 디지털 서명의 계산을 분산시키는 방법을 제한하였다. (이들 컴퓨터는 서명자의 그룹이라고 하고, 그 그룹에 속하는 각 컴퓨터는 가입자라고 하며, 그룹내의 가입자의 수는 n으로 표시된다. (Threshold Cryptosystens, Advances in Crypology-Crypto '89, 435, Springer-Verlag, 1990, pp. 307-315; 및 Shared Generation of Authenticaltors and Signatures, Advances In Crytology-Crypto ’91, 576, Springer-Verlag, 1992, pp. 457-469 참조).

이 분산 디지탈 서명 방법의 기본적 골자는 앞서 언급된 요건(a) 및 (b)를 만족시키도록 상기 설명된 다수의 가입자로 구성된 컴퓨터 시스템에서 비밀 정보를 분산하는 것이다.

비밀 분산 방법에 기초하여 RSA 암호 시스템을 이용하는 Y. Desmedt와 Y. Frankel에 의해 제안된 분산형 디지탈 서명 방법은 다음 요건(1) 및 (11)를 만족시킨다.

(1) t+1 가입자의 상호동작은 주어진 메시지에 대한 서명자의 그룹의 디지탈서명을 발생시키기에 충분하다.

(11) 가입자의수가 임계값(즉 t이하)미만일 때 주어진 메시지에 대한 디지탈 서명이 발생될 수 없다.

그러나, 요건(1) 및 (11)만으로서, 디지탈 서명 발생 처리가 분산될 때, 서명의 발생이 상호 동작된 t+1 또는 그 이상의 가입자 중에서 정당하지 않은 가입자가 있는 경우에 수행될 수 없다.

한편, 임의 형태의 에러를 가지를 모든 가입자에 대한 디지탈 서명을 발생시키는 방법은 이전의 요건(a) 내지(d)에 의해 정의된 확인가능한 비밀 분산 시스템에 기초하여 제공될 수 있다는 것은 공지되어 있다. 바꾸어 말하면, 다음의 요건을 만족시키는 분산 디지탈 서명 시스템이 실현될 수 있다.

(Ⅰ') 주어진 메시지에 대한 디지탈 서명은 정당하지 않은 가입자가 정당한 가입자들 중에 존재하는 경우에도 t+1개의 정당한 가입자가 상호 동작하는 한 발생될 수 있다.

(Ⅱ') 주어진 메시지에 대한 디지탈 서명은 임계값 (즉 t이하) 미만의 가입자 수에 따라 발생될 수 없다.

이전에 설명된 다양한 디지탈 서명 방법을 위한 분산 및 생성 시스템은 상기 확인가능한 비밀 분산 방법을 이용하는 분산 및 계산 회로에 의해 설계될 수 있다는 것은 공지되어 있다.

상기 요건(Ⅰ) 및 (Ⅱ)를 만족시키는 분산 디지탈 서명 시스템에 필요한 통신량 및 계산량이 실제적이라는 것은 공지되어 있다. 그러나, 상술한 바와 같이, 서명 분산 및 생성 처리에 가담한 가입자가 정당하지 않은 작업을 수행할 때, 서명은 생성되지 않는다. 한편, 확인가능한 비밀 분산 방법과 분산 및 계산 회로를 사용하구 상술한 바와 같이 요건(Ⅰ') 및 (Ⅱ)를 만족시키는 분산 디지탈 서명 시스템에 관한한, 통신이 요구된 양은 대화형 확인가능한 비밀분산방법(1)에 따라 비실제적이고 계산이 요구된 양은 비 대화형 확인가능한 비밀분산방법(2)에 따라 비실제적이라는 것은 공지되어 있다.

상술한 바와 같이, 많은 통신은 종래의 기술을 이용함으로써 대화형 확인 가능한 비밀 분산 방법(1)에 기초한 분산 지탈 서명 시스템에 요구되고, 많은 계산 양은 종래의 기술을 이용함으로써 비대화형 확인가능한 비밀 분산 방법(2)에 기초한 분산 디지탈 서명 시스템에 요구된다. 도청 및 기만으로부터의 위험을 감소시키는 다른 대응책으로서, 적은 양의 계산을 필요로하는 공통 키 암호 시스템을 이용하는 케르베로스라고 하는 네트워크를 위한 공지된 인증방법(Garfinkel 과 G.Spafford가 저술하고 Hide Yamagachi에 의해 편집/ 번역된 Unix Security, ASCII, pp. 349-357 및 535-5421993 참조)이 있다.

Needham 및 Schroeder에 의한 인증 프로토콜(R. Needham과 M. D. Schroeder: Using Encryption for Authentication In Large Network of Computer, CACM21, 12, pp. 993-999, Dec. 1978 참조)과 Secure RPC(A. D. Birrell: Secure Communications Using remote Procedure Calls, ACM Transaction Computer Systems, Vol 3, No. 1, pp. 1-14. Feb. 1985 참조)에 기초한 케르베로스 용의 특정한 인증 프로토콜이 이제부터 설명된다.

일반적으로, 케르베로스에서 통신 시스템내의 모든 장치에 대한(비밀 키와 등가인) 비밀 정보를 관리하는 인증 서버가 있다. 인증 서버는 제 31a도에 도시한 바와 같이 개개의 장치 i와 비밀 키 pki를 공통으로 사용한다. 이후에, 증명을 요구하는 사람은 증명자라고 하고, 증명자에게 인증을 제공하는 사람은 인증자라고 한다.

제 31b도에 도시한 바와 같이, 증명자 A가 증명을 위해 인증B를 요청할 때, A는 형태 {A, B, R} 을 갖는 데이타(161)를 인증 서버에 전송한다. 주목할 것은 A 및 B가 증명자 A와 장치 또는 사용자 이름과 같은 인증자B를 지정하는 공개 식별정보 항목이고, R은 무작위로 선택된 수라는 것이다.

데이타(161)의 수신시에, 인증 서버는 {인중 원소, R, B, CK}^ pkA의 형태를 갖는 데이타(162)를 A에 복귀 시킨다. {M}^k는 키 k를 사용하여 메시지 M을 코딩함으로써 얻어진 데이타를 표시하고, 인증 원소는 시간 스탬프 T를 사용하여 {T, A, CK}^pkB로 구성된 데이타(163)이며, CK는 인증 서버에 의해 발생되고 이후 A와 B사이의 공통 키 암호 통신을 위해 사용되는 공통 키를 표시한다.

증명자와 인증자 사이의 공통 키 암호 통신을 위한 비밀 공통 키는 이하 통화 키 라고 한다. 그러므로 인증 서버는 통화 서버를 위한 전달 서버로서 가능하다. 마지막으로 증명자 A는 앞서 설명된 인증 요소(163)를 인증자B에 보낸다. 인증자 B는 A를 인증하기 위해 그 비밀 마스터 키 pkB와 수신된 인증 요소(163)를 합성한 다음 공동 통화 키 CK를 사용하여 암호 통신을 수행한다.

그러므로 케르베로스를 이용하는 인증 프로토콜에 의해 도청과 기만으로부터 위험이 감소될 수 있다.

그러나, 공개 키 암호 방법에 따르면, 512 비트 또는 그 이상인 정수의 멱급수의 레시듀의 계산이 수행되어야 하므로 계산량이 막대하다.

게다가, 공통 키 방법에서의 케르베로스를 위한 프로토콜에서 인증 서버는 통신 시스템을 구성하는 모든 장치에 대한 비밀 정보를 관리하기 때문에, 물리적 이유로 인해 완전히 신뢰성 있는 포함된 인증 서버가 또한 요구된다. (마찬가지로, 공개 키 암호 방법에서는, 모든 공개 키를 관리하는 집중 제어 센터가 요구된다). 그러므로, 보안성을 보장하기 위해서, 인증 서버는 허가 없이는 들어갈 수 없는 잠구어진 방안에 그것을 배치함으로써 엄격히 제어되어야 한다. 또한 인증 서버가 실패의 발생 또는 허가되지 않은 범죄행위로 인해 신뢰할 수 없을 때, 폴트 폴러런스는 완전한 시스템의 안전이 파괴하도록 감소된다.

본 발명의 목적은 필요한 계산량과 통화량이 상술한 대화형 시스템(1)과 암호 시스템(2)에 대해 필요한 것에 비해 크기의 실제차수를 구성하는 확인가능한 비밀 분산 방법을 제공하는 것이다.

본 발명은 대화형 시스템(1)과 비대화형 시스템(2) 사이의 중간에 놓이고, 필요한 계산량과 통시량이 크기의 실제 차수를 구성하는 확인가능한 비밀 분산 방법을 이용하고 요건(Ⅰ)(공인되지 않은 행위를 수행하는 가입자가 있을 때 서명을 발생하지 않는 시스템)과 요건(Ⅰ')(공인도지 않는 행위를 수행하는 가입자의 수가 특정 임계값과 같거나 낮을 때에도 서명을 생성할 수 있는 시스템)사이에 위치된 분산 디지탈 서명 시스템(공인되지 않는 행위를 수행하는 가입자의 수가 임계값과 같거나 클 때 서명을 발생하지 않지만 이러한 가입자를 식별하는 시스템)을 추구한다.

본 발명의 다른 목적은 인증 서버에 대한 신뢰성의 상기 설명된 문제를 극복하기 위해 비밀 정보를 분산하고 관리하는데 다수의 장치를 사용하는 분산 인증 서버를 제안하는 것이다.

분산 인증 서버에 대한 요구는 다음과 같다.

(1) 증명자와 인증자의 경우에, 분산 인증 프로토콜은 종래의 중앙 관리에 의해 제공되는 인증 프로토콜과 동일한 인증 기능을 수행한다.

(2) 증명자와 인증자의 경우에, 분산 인증 프로토콜은 종래의 중앙 관리에 의해 제공되는 인증 프로토콜과 동일한 인버터페이스(데이타 포멧)을 보장한다.

(3) 증명자와 인증자의경우에, 분산 및 인증 프로토콜은 종래의 중앙 관리에 의해 제공되는 인증 프로토콜에서 요구되는 것과 동일한 통신량을 수행함으로써 구현된다.

(4) 상기 설명된 요구는 분산 인증 서버를 구성하는 장치의 절반 이상이 신뢰성이 없을 때에 제외하고 만족된다.

한 특징에 따르면, 이들 목적을 달성하는 본 발명은 통신 시스템을 위한 기밀 정보 처리 방법에 관한 것인데, 여기서, 다수의 정보 처리 장치 비밀 통신로에 의해 접속되고, 이 통신로를 통해서 장치 각각은 임의의 나머지 장치들은 정보 비밀을 유지하면서 장치들 중 다른것과 정보를 교환하고 방송 통신로를 통해서 장치들은 다른 모든 포함된 장치들과 정보를 공통으로 교환하며, 비밀 정보 통신 방법은,

다수의 장치중 한 구성원이고 비밀 정보를 갖는 제1 장치를 이용하여 다수의 제2 장치를 위한 비밀 배열을 비밀 정보로부터 발생하는 단계,

제1 장치를 이용하여 제조 장치를 위한 비밀 배열부터 제1 정보 세그먼트를 추출하고, 제1 정보세그먼트를 제2 통신로를 통해 제2 장치로 전송하는 단계,

재1 장치를 이용하여 비밀 배열의 한 부분에 대한 선정된 함수를 수행하고, 얻어진 출력 값을 방송 통신로에 방송하는 단계,

제2 장치를 사용하여 난수를 발생하고, 방송 통신로를 통해 난수를 방송하는 단계,

비밀 배열로부터 그리고 방송한 난수와 일치하여, 제1 장치를 이용하여 제2 장치를 위한 제2 정보 세그먼트를 발생하고, 방송 통신로를 통해 제2 세그먼트를 방송하는 단계,

제2 장치를 이용하여, 수신된 제1 정보 세그먼트와 제2 장치에 의해 발생된 난수와 일치하는 제1 장치를 이용하여 제2 장치를 위한 정보 세그먼트로서 발생되는 제3 정보 세그먼트를 발생하는 단계, 및

제2 장치를 이용하여, 제3 정보 세그먼트와 방송한 제2 장치를 위한 제2 정보 세그먼트를 비교하여, 비밀 정보가 제1 장치에 의해 분산된 것을 확인하는 단계를 포함한다.

다른 특성에 다르면, 이들 목적을 달성하는 본 발명은 통신 시스템을 위한 서명 발생 방법에 관한 것이고, 여기서, 다수의 장치는 임의의 나머지 장치의 정보비밀을 유지하면서 다른 장치와 정보를 교환하는 비밀 통신로와, 장치 각각의 모든 다른 장치와 정보를 공통으로 교환하는 방송 통신로에 의해 접속되고, 서명 발생방법은,

서명자의 그룹에 속하는 장치 각각을 이용하여 제1 비밀 정보를 무작위로 선택하고, 상기 그룹내에 장치와 제1 비밀 정보를 비밀로 분산하는 단계,

장치를 이용하여 제1 비밀 정보에 대해 선정된 제1 함수를 수행하고 얻어진 출력값을 상기 그룹내의 장치 모두에 방송하는 단계,

상기 그룹내의 장치중에서 장치 각각으로부터의 제1 비밀 정보를 분산하고, 제1 비밀 정보를 가산하는 단계,

승산을 위해 상기 그룹내의 장치 중에서 출력 값을 분산하고 승산과 메시지에 의해 얻어진 결과에 대해 얻어진 선정된 제2 함수를 수행하는 단계,

상기 그룹내의 장치 중에서 제2 비밀 정보를 분산하고 제2 함수를 수행함으로써 얻어진 결과, 분산과 가산에 의해 얻어진 결과, 및 공개되는 원소를 이용함으로써 제2 비밀 정보를 계산하는 단계, 및

상기 그룹내의 모든 장치와 관련한 상호 동작 시도를 통하여, 분산된 제2 비밀 정보를 복원하고 분산과 승산에 의해 얻어진 결과와 함께 서명으로서 복원된 제2 비밀 정보를 출력하는 단계를 포함한다.

부수적인 특징에 따르면, 이들 목적을 달성하는 본 발명은 통신 시스템을 위한 인증 방법에 관한 것이고, 여기서, 다수의 장치가 접속되고, 특징 그룹에 속하는 것들 중의 장치들은 인증을 공통으로 제공하고, 인증 방법은

인증자의 장치로부터 인증을 요구하는 증명자의 장치로부터 증명자와 인증자를 위한 식별자를 포함하는 인증 요구 메시지를 특정 그룹의 장치 각각에 전송하는 단계,

특정 그룹에 속하는 장치 모두에 관련한 상호 동작 시도를 이용하여 인증 요구 메시지에 기초한 인증자에 관련된 비밀 키로 암호화된 인증 요소를 생성하고, 인증 요소를 증명자와 관련된 비밀 키로 암호화함으로써 인증 메시지를 발생하는 단계,

특정 그룹의 장치 각각으로부터의 인증 메시지를 증명자의 장치에 전송하는 단계,

인증 메시지의 수신시 증명자의 장치에서 인증 메시지를 복원하고, 복원된 인증 요소를 인증자의 장치로 전송하는 단계, 및

인증자의 장치에서 인증 요소를 복원하고 인증을 증명자에게 전송하는 단계를 포함한다.

다른 특징에 따르면, 이들 목적을 달성하는 본 발명의 다수의 통신 장치, 장치 각각의 임의의 나머지 장치의 정보 비밀을 유지하면서 다른 장치와 비밀로 정보를 교환할 수 있는 비밀 통신로, 및 장치 각각 모든 다른 장치에 정보를 공통으로 전송하는 방송 통신로를 포함하고, 다수의 정보 처리 장치의 제1 정보 처리 장치는

비밀 정보로부터 선정된 부분 배열을 발생하는데 제1 발생수단, 부분 배열로부터 임의의 나머지 정보 처리 장치에 대한 제1 정보 세그먼트를 추출하고 나머지 정보 처리 장치에 제1 정보 세그먼트를 전송하는 추출 수단,

제1 정보 세그먼트에 대한 선정된 함수를 수행하고 얻어진 출력 값을 방송 통신로를 통해 나머지 정보 처리 장치에 방송하는 함수 처리 수단, 및

나머지 정보 처리 장치에 의해 방송된 난수와 일치하는 제2 정보 세그먼트를 발생하고, 방송 통신로를 통해 제2 정보 세그먼트를 방송하는 제2 발생 수단을 포함하고, 나머지 정보 처리 장치 각각은 난수를 발생하고 방송 통신로를 통해 난수를 방송하는 난수 발생 수단,

제1 정보 처리 장치에 의해 제2 정보 세그먼트로서 발생될 제3 정보 세그먼트를 제1 정보 세그먼트 및 난수와 일치하게 발생하는 제3 발생 수단, 및

제3 정보 세그먼트를 방송된 제2 정보 세그먼트와 비교하여, 제1 정보 처리장치에 의해 수행된 비밀의 분산을 검증하는 검증 수단을 포함한다.

또 다른 특징에 의하면, 이들 목적을 달성하는 본 발명은 다수의 정보 처리 장치, 장치 각각이 임의의 나머지 장치의 정보 비밀을 유지하면서 다른 장치들과 비밀로 정보를 교환할 수 있는 비밀 통신로, 장치 각각이 다른 모든 장치에 정보를 공통으로 전송하는 방송 통신로를 갖는 통신 시스템에 관한 것이고, 서명자의 그룹에 속하는 다수의 장치중에서의 장치 각각은

제1 비밀 정보를 무작위로 선택하고 상기 그룹의 장치중에서 제1 비밀 정보를 비밀로 분산하는 분산 수단,

제1 비밀 정보에 대하나 선정된 제1 함수를 수행하고 얻어진 값을 상기 그룹의 모든 나머지 장치에 전송하는 방송 수단,

상기 그룹의 장치 중의 장치 각각에 의해 보유된 제1 비밀 정보를 분산하고 제1 비밀 정보를 가산하는 가산 수단,

상기 그룹의 장치들 중에서의 장치 각각에 의해 보유된 출력 값을 분산하여 이 출력 값을 곱하고, 승산과 메시지에 의해 얻어진 결과에 선정된 제2 함수를 수행하는 처리 수단,

승산 결과를 이용하여, 분산과 가산에 의해 얻어진 결과, 및 상기 그룹의 장치들 중에서 제2 정보를 분산하고, 제2 정보를 계산하기 위해 공개된 요소를 계산하는 계산 수단, 및

제2 비밀 정보가 분산되는 그룹의 장치 모두의 결합 시도에 의해 제2 비밀 정보를 복원하고, 분산과 승산에 의해 얻어진 결과와 함께 서명으로 복원된 제2 비밀 정보를 출력하는 복원 수단을 포함한다.

상기 설명된 것들 이외의 다른 목적 및 장점은 이후의 본 발명의 양호한 실시예의 설명으로부터 본 기술에 숙련된 자에게는 명백하다. 설명에 있어서, 본 발명의 일부를 형성하고 본 발명의 예를 도시한 첨부 도면이 참조된다. 그러나, 이러한 예는 본 발명의 다양한 실시예의 전부가 아니며, 본 발명의 범위를 결정하기 위해서는 설명 다음의 특허 청구의 범위를 참조하면 된다.

양호한 실시예에 대한 상세한 설명

이제, 첨부 도면을 참조하여 본 발명의 바람직한 실시예를 기술할 것이다.

[실시 예1]

먼저, 본 발명의 원리를 기술할 것이다.

제 3도는 비밀 s와 부분 행렬 S간의 관계를 도시한다.

이 제1 실시예에서, 비밀 s에 대한 부분 행렬 S는 비밀 세그먼트 nxn행렬 S=[s(i, j)](i, j=1, ..., n]이고, 차후에 기술하는 바와 같이 종래의 대화형 확인 가능 비밀 분산 시스템에 사용되는 부분 행렬에 요건들을 부가하므로써 얻어진다.

먼저, 각 열에 대한 벡터, S_r(i)=[s(i, 1), ... , s(i, n)](i=1, ..., n)는 비밀 s_r(i)에 대한 비밀 부분 벡터(소정 비밀을 분산하는 방법에 있어서 가입자 j의 비밀 부분인 요소 j를 가지는 백터)이고, 각 행에 대한 벡터, S_c(j)=[s(1, j), ... ,s(n, j)](j=1, ... , n)는 비밀 s-c(j)에 대한 비밀 부분 벡터이다.

비밀 s-r(i) 및 s-c(j)에 대한 각 벡터 [s_r(1), ... , s_r(n)] 및 [s_c(1), ... , s_r(n)]는 비밀 요소에 대한 비밀 부분 벡터이다. 비밀 분산 처리에서, 구조화된 부분 행렬의 행 벡터 i(i=1, ... , n)와 비밀 s_r(i)는 각 가입자 i에 대한 비밀 정보 세그먼트로서 가입자 i에게로 전송된다. 따라서, 비밀 복원처리시에 정보 세그먼트를 수신한 가입자가 비허가된 동작을 수해하지 않는 한, 개별 가입자가 방송하는 정보 세그먼트가 정확한지 여부에 대하여 상당히 높은 확률로서 증명이 가능하다.

이 실시예에 부가적으로, 원래의 비밀 정보를 보유하고 분산된 비밀 정보 세그먼트를 가지는 가입자가 비허가된 동작을 수행할 때에도 비밀 복원 처리에서 방송되는 정보 세그먼트가 정확한지 여부를 증명하기 위하여, 각 가입자 i(i=1, ... , n)에 대응하는 비밀 s_r(i)에 대한 요소로서 서비스하는 값은 비밀 정보 세그먼트가 분사되기 전에 일방향성 해시 함수(hash function)(Ikeno 및 Koyama에 의한 Modern Cryptological Theory, pp. 224-224, IEEE, 1986)에 의해서 발생된다.

일방향성 해시 함수를 설명할 것이다.

일방향성 해시 함수는 데이타 압축 스크램블을 수행하는 함수이고, 입력값으로부터 구해지는 출력값에 의한 계산은 용이하지만 출력값으로부터 구해지는 입력값에 의해 역계산은 어려운 함수이다. 그러나, 이 제1 실시예에서, 종래의 비대화형 확인가능 비밀 분산 시스템에 사용되는 일방향성 함수와 비교하면 특성 대수학 속성이 필요없으므로, 고속 계산을 제공하는 일방향성 해시 함수를 사용할 수 있다.

일방향성 해시 함수의 특정한 예를 들면, R. Merkel 은 DES(Data Encryption Standard)와 같은 블럭 암호문을 사용하는 일방향성 해시 함수(One-Way Hash Function And DES. Advances in Cryptology-Crypto '89, Lecture Notes In Computer Science, Vol. 435, Springer-Verlay, 1990을 참조)를 제안했다.

제 8a내지 제 8c도는 일방향성 해시 함수의 특정 구조를 설명하는 도면이다.

제 8a도는 DES를 사용하여 수행되는 블럭 암호화를 나타내고, 암호화 회로(81)는 64비트 입력 또는 56 비트 키로부터의 64-비트 출력을 제공한다.(DES는 제8A 내지 제8c도에서 E로 표시됨).

그 다음, 제8b도는 DES가 부분처리에 사용되는 동안 입력 길이 119 비트 및 출력 길이 112 비트인 함수 F에 대한 처리를 나타낸다. 참조 번호(82)는 함수 동작회로를 가리킨다. 이 처리는 다음과 같이 정의된다.

먼저, 입력은 두 부분k 및 x로 분리된다(부분 k의 길이는 55비트이고 나머지 부분x의 길이는 64비트임에 주목해야 한다). 그 다음, 부분 x는 DES에 대한 입력으로서 사용되는 반면, 부분 k와 'o'를 결합하므로써 얻어지는 값 'o'와 k는 56비트 키로서 사용된다. EXOR동작은 구해진 출력 및 x와 함께 수행되고, 얻어진 결과는 함수 F에 대한 출력에 좌측의 64비트로 간주된다. 동일한 방식으로, 동일부분 x는 입력으로서 사용되고, 나머지 부분 k와 '1'을 결합하므로써 얻어지는 값 '1', k는 키로서 사용된다. EXOR동작은 구해진 출력 및 x와 함께 수행된다.

결과 비트 64 비트중의 48비트는 함수 F에 대한 나머지 부분 (우측의 48비트)으로서 사용된다. 그후, 두개의 구해진 결과를 결합하므로써 제공되는 결과는 함수 F의 112비트 출력이다.

이에 후속한 제8c도는 소정의 메시지를 입력받아 일방향성 해시 함수값을 출력하는 처리를 도시하는데, 참조번호(83)는 해시 동작 장치를 가리킨다. 이 처리는 다음과 같이 수행된다.

소정의 메시지의 첫 119비트는 전술한 함수 F로부터 입력으로 사용되고 첫 112비트 출력을 발생한다. 그 후, 그 출력은 다시 112 비트 입력으로 사용되고, 이 후에 메시지의 나머지 7비트는 반복적으로 함수 F에 입력된다. 마지막으로, 모든 메시지가 입력되었을 때(메시지의 마지막 7비트를 입력하기에 너무 작은 비트가 있을시에는 필요한 대로 '0'이 부가된다) 구해지는 112 비트 출력은 메시지에 대한 해시 값으로 사용된다.

전술한 지시에서 R. Merkel이 제안한 전술한 바와 같이 계산되는 일방향성 해시 함수(즉, 상이한 입력 메시지를 획득했을 때 하나의 해시값이 주어질 때 얻어지는 동일한 해시 값을 얻는 것을 상당히 어렵게 만드는 인수)는 (입력이 일정하고 출력이 키로부터 얻어지는 임의 가변적 일때, 출력이 일정하고 입력은 키로부터 얻어지는 임의 가변적일 때) 전술한 바와 같이 사용한 DES와 같이 블럭 암호화의 안정성을 제공한다.

더우기, 동일한 저서에서, 전술한 해시 함수보다 효율적인 일방향성 해시 함수가 제안되었다. 또한, R. Rivest는 블럭 암호화를 사용하지 않는 효율적인 일방향성 해시 함수(The MD4 Messages Digest Algorithm, Advances In Cryptology-Crypto '90, Lecture Notes In Computer Science, Vol. 537, Springer-Verlag, 1991. Nist Federal Information Processing Standard For Secure Hash, American National Standard x9. 30-199x를 참조)를 제안하였다.

이 제1 실시예에서의 컷 앤트 츄스 처리를 기술 할 것이다.

비밀요소 s에 대한 부분 행렬 및 해시값을 분산시키고, 동시에 임의로 선택된 k비밀 11, ... , 1k 에 대한 부분 행렬 및 해시값을 분산시키므로써, 모든 가입자가 비밀 분산처리시에 수신했던 비밀 정보 세그먼트가 종래의 대화형 비밀 분산 시스템에서 수행되는 바와 같이, 확인가능 컷 앤 츄스와 같은 확인 가능 공유 비밀에 대한 정보 세그먼트일 수 있는지를 검사한다. 모든 가입자가 임의로 결정한 k/2 비밀[1i(1), ... , 1i(k/s)]에 관련된 모든 비밀 정보가 방송된다. 나머지 k/2 비밀 [1j(1), ... , 1j(k/2)]에 관하여, 1j (1)+s, ... , 1j(k/s)+s와 관련된 모든 비밀정보가 방송된다. 모든 방송 정보에서 에러 (errors)를 가지는 부분의 수가 t를 넘어설 때, 비밀 분산 처리가 틀렸다고 결정된다.

이러한 방식에서, 이러한 방법을 사용하므로써 종래의 확인가능 비밀 분산 방법의 요건(c) 및 (d)대신에 다음의 요건(c')(d')를 만족시키는 비밀 분산 방법이 제공될 수 있고, 분산 계약을 안전하게 수행하는 방법 및 통신 시스템이 실현될 수 있다.

(c')부정확한 정보 세그먼트가 정확히 정보 세그먼트와 혼합될 때, 원래의 비밀 세그먼트는 t+1의 정확한 정보세그먼트에서 복원되지 않을 수 있지만, 허가되지 않은 동작을 수행하는 가입자를 식별할 수 있다.

(d') 비밀 및 정보 세그먼트의 내용에 대하여 개별 가입자가 수신한 정보 세그먼트가 비밀 세그먼트 x의 복원시에 정확하지 않았을 때, 복원처리 동안 허가되지 않은 동작을 수행하는 가입자를 식별할 수 있다.

종래의 방법에서, 위반 가입자가 있을시 비밀은 복원되지 않는다. 즉 에러정정을 수행할 수 없을지라도, 이들 요건은 위반 가입자의 식별, 즉 에러 검출이 가능하다. 위반 가입자가 있을 때 조차 분산 동작 요건(c)및 (d)를 가지고 수행될 수 있다(타당성에 대한 폴트 폴러런스가 실현된다). 그러나, 위반 가입자의 검출 요건은(c')는 전환하므로써 가능하다. 경고(warning)가 해제된 후에 처리는 다시 수행되고, 정확한 출력이 얻어지고, 타당성에 대한 폴트 허용범위가 실현 될 수 있다.

따라서, 이 제1 실시예에서 분산된 비밀이 이러한 가입자가 존재할 때 분산된 비밀이 복원될 수 없을지라도, 비허가된 동작을 수행하는 가입자를 식별할 수 있는 확인가능 비밀 분산 방법이 제안되었다. 따라서, 대화형 방법(1)과 전술한 암호화 방법(2)사이에 위치하고, 상당한 계산과 절대값 실체 차수내의 상당량의 통신을 요구하는 확인 가능 비밀 분산 방법을 제공하는 것이 가능하다.

제1도는 분산 정보 처리 장치를 포함하는 본 발명의 제1 실시예에 따르는 정보 처리 시스템을 도시한다.

제1도에서, 정보 처리 장치(11)는 시스템의 가입자에 의해 사용된다. 후속하는 설명에서, 각 장치와 이를 사용하는 가입자는 동일한 것으로 간주되며, 장치(11)는 가입자로 불린다. 방송 통신로(12)는 모든 가입자(11)에게 정보를 개방하는데 사용되고, 비밀 통신로(13)는 각 가입자(11)의 비밀 통신에 사용된다.

제2도는 정보처리장치(11)의 구조를 도시하는 블럭도이다. 제2도에서, 방송 장치(21)는 방송 통신로(12) 또는 비밀 통신로(13)를 가로질러 다른 장치(11)와 통신하는데 사용된다. 산술 연산 처리 장치(22)는 일방향성 해시 함수와 같은 각종 산술 연산과, 메모리 장치(24)에서의 프로그램에 따르는 판정 처리를 수행하고, 개별 섹션을 제어한다. 난수 발생 장치(23)는, 예를 들면 의사 난수 발생기(pseudo random number generator)이고, 임의 값을 발생하는데 사용된다. 메모리장치(24)는 프로그램을 저장하는데 사용되는데, 이 프로그램은 산술 처리 장치(22), 처리 동안 발생되는 산술 연산 결과와 같은 정보, 다른 장치로부터 수신되는 정보 및 각종 파라미터에 의해 실행된다.

이제, 소정의 한정된 세트 F에서의 비밀의 확인가능한 분산을 수행하는 방법을 명확히 기술할 것이다.

먼저, 비밀 s에 대한 부분 행렬 X를 특히 기술할 것이다.

소정의 한정된 세트에서 비밀 요소 s에 대한 부분 행렬 S=[s(i, j)](i, j=1, ... , n)에서, 각 행 벡터의 요소 S_r(i)=[s(i, 1), ... , s(i, n)](i=1, ... , n)는 일정한 항으로서의 s_r(i)를 가지는 t^th승까지 각 다항식 fi의 n이 상이한 값, i1,....,in에 대하여, 값 fi(i1),..., fi(in)이다. 각 열 벡터 S_c(j)=[s(1,j),................s(n,j)](j=1,....,n)의 요소는 상수항으로서의 s_r(i)를 가지는 t^th승까지 다항식 gi의 n의 상이한 값, j1,.......jn에 대하여, 값 gj(j1),....,gj(jn)이다. 또한, 두 벡터[s_r(1),.......s_r(n)] 및 [s_r(1),.......s_c(n)]는 상수항으로서의 비밀 요소 s를 가지는 t^th승까지 각 다항식 f 및 g의 값 f(i1,.....,in)및 g(j1,.....jn)이다.

이 제1 실시예의 처리를 2가지 처리로 분류하여 기술할 것이다; 모든 가입자에게 소정의 한정된 세트의 비밀을 분산시키므로써 가입자간의 비밀이 분산되고 보유되도록 하기 위한 비밀 분산 처리와; 모든 가입자에게 분산된 비밀을 복원하거나, (비허가된 동작이 발생시에)허가되지 않은 동작을 수행한 가입자를 식별하기 위한 비밀 복원 처리.

(1) 비밀 분산 처리는 비밀 요소 s를 보유하는 가입자 d가 그의 비밀 부분을 분산시키는 처리이다. 제5도는 이 처리에 대한 절차가 도시한다. 제5도에서, 처리 Rj, i는 라운드 j(Round_j)에서 가입자 i애 의해 수행되는 처리이다. 이후로부터, h는 (고속 계산 방법을 포함하는) 효율적인 일방향성 해시 함수를 표시한다. 예를 들면, 고속 블럭 암호화 기능에 의해 형성되는 해시 함수(전술한 Modern Cryptological Theory를 참조)가 사용된다. 안정선 파라미터 k는 소정의 상수 k'에 대하여 k=nk를 만족시킨다. 이러한 경우, 비밀 분산 처리의 검증이 실패할 확률은 컷 앤 츄스처리에 따라 2 ^(-k'(t+1))이다. (T. Rabin 및 M. Ben-Or)의 Verifiable Secret Sharing And Multiparty Protocols With Honest Majority 참조).

(라운드 1) 가입자 d는 난수 발생 장치(23)를 사용하여 비밀요소 s와, 소정의 한정된 세트에서 임의로 선택되는 비밀요소 11, ... , 1k에 대하여 각각 부분 행렬 S, L1, ... , Lk를 발생한다. 제4도에 도시된 바와 같이, 비밀값 s_r(1), ... , s_r(n), 11_r(1), ... 11_r(n), ... , 1k_r(1), ... , 1k_r(n)에 대한 일방향성 해시 함수 s^*는 해시 함수 연산 처리 장치(83)에 의해 얻어진다.

가입자 d는 비밀 통신로(13)를 가로질러 각 발생된 부분 행렬의 칼럼 벡터S_c(i), L1_c(i), ... , Lk_c(i) 및 비밀 s_r(i), 11_r(i), ... , 1k_r(i)(정보 B1. i)를 각 가입자 i(그 자신을 제외한 i-1, ... , n)에게로 전송한다. 해시값 s^*(정보 B1. d)은 방송 통신로(12)를 가로질러 모든 가입자에게로 방송된다(처리 R1. d).

(라운드 1) 각 가입자 S(i_1, ... , n)는 난수 발생 장치(23)를 사용하여 임의로 선택된 k'비트(정보 B2..i)를 방송한다(처리 R2. i). 임의로 선택된 k' 비트는 각각 Bi_1, ... , Bi_k로 참조되고, 총 n 가입자들까지의 비트는 각각 B1, ... , Bk로 참조된다.

(라운드 3) 라운드 2에서 방송되는 각 비트 Bj(j=1, ... , k)가 1인 경우, 가입자 d는 라운드 1에서 가입자 d가 발생하는 부분 행렬 Lj를 방송한다. Bj가 0인 경우, 가입자 d는 한정된 세트로 발생되는 부분 행렬 S와 Lj의 각 요소들을 가산하므로써 얻어지는 (S+Lj로 기록된) 결과를 방송한다(처리 R3. d). 가입자 d가 방송하는 정보는 제 5도에서 B3. d로서 표현된다.

(라운드 4) 라운드 1에서 비밀리에 수신된 정보 B1, i의 각 값j(j=1, ... , k)에 대하여, 각 가입자 i(i=1, .. , n)는 (라운드 1에서 방송되는 비트 Bj가 1인 경우) 열 벡터 Lj_c(i) 및 Lj_r(i) 또는 (비트 Bj가 0인 경우) Lj_c(i)+S_c(i) 및 1j_r(i)+s-r(i)가 열 벡터 및 라운드 3에서 방송되는 부분 행렬의 비밀값과 동일한지의 여부를 확인한다. 그들이 값 j에 대하여 동일하지 않은 경우, 가입자 d의 판정 메시지(정보 B4. i)는 방송된다(처리 R4. i).

(라운드 5) 판정 메시지(정보 B4. i)가 라운드 4에서 방송될 때, 가입자 d는 라운드 1에서 비밀리에 전송되었던 정보 B1, j를 판정 메시지 방송했던 개별 가입자 j에게로 방송한다(처리 R5. d).

(사후처리) 라운드 5에서 방송되었던 정보가 정확하지 않을 때 또는 라운지 4에서 방송되었던 판정 메시지의 수가 임계값 t보다 클 경우, 각 가입자 i=(i=1, ... , n)은 허가되지 않은 동작을 수행하는 가입자 d를 판정한다.

각 가입자 i가 라운드 1 내지 라운드 5에서 수신했던 총정보는 s_i로서 표시된다.

(2) 비밀 복원 처리

비밀 복원 처리는 전술한 비밀 분산 처리를 통하여, 개별 가입자가 보유하는 정보 s_i로부터 모든 가입자에 의해 비밀 요소 s를 획득하기 위한 처리이다. 제6 도는 이 처리에대한 절차를 도시한다.

(라운드 1) 각 가입자 i(i=1, ... , n)는 정보 세그먼트 s_i에 포함되는 비밀값 s_c(i) 및 s_r(i)를 방송한다(처리 R1.i).

(라운드 2) 각 가입자 i(i=1, ... , n)는 라운드 1에서 방송되는 값으로부터 t+1 값 s_c(i, 1), ... ,s_c(i, t+1) 및 s_r(i, 1),...., s_r(i,t+1)를 선택한다. 그 후, 결과 s(c) 및 s(r)는 다항식의 보간법(interpolation)에 의해 구해진다. 가입자 i는 두 결과가 동일한지의 여부를 확인하고, 나머지 방송 값이 값 s(c)=(r)에 부합하는 다항식에 대한 정확한 값인지의 여부를 확인한다. 모든 값이 정확할 경우, 비밀 요소 s는 s(c)=s(r)과 동일하게 결정되고, 복원처리는 종료된다. 동일한 다항식에 부합하지 않는 값이 방송되는 경우, 정보 세그먼트 s_i에 포함되는 열 벡터 S_c(i)(정보 B2. i)가 방송된다. (처리 R2. i).

(라운드 3) 각 가입자 i(i=1, ... , n)는 라운드 2에서 방송되는 열 벡터 S_c(j)(j=1, ... ,n)로부터 부분 행렬 S'를 발생한다. 그 후, 가입자 i는 1, ... , n으로 구성되는 t+1 상이한 값을 포함하는 총 모든 세트 t1, ... , tm(m=nCt₊₁=n!/(t+1)!(n-t-1)!)세트에 관하여 열 벡터 세트 T1, ... , Tm을 선택한다. 다항식의 보간법에 의해 각 행 및 열에 대한 결과 s'_r(1),...,s'_r(n) 및 s'_c(1)..., s'_c(n)이 구해진다. 또한, 결과 s'(r) 및 s'(c)는 전술한 값에 대한 다항식의 보간법에 의해 구해진다. 가입자 i는 이들 두 결과가 동일한지의 여부를 확인하고, 이들 열 벡터의 모든 요소는 값 s'_c(1)_, ... ,s'_c(n) 및 s'_r(1), ... ,s'_r(n)에 부합하는 다항식에 대한 올바른 값인지의 여부를 확인한다.

따라서, 확인된 t+1 열 벡터를 포함하는 세트 T1, ... , Tm중에, 상이한 정확한 부분 행렬에 대응하는 세트 수는 최대 t+1이고 부분행렬은 S_1, .. ,S_T(여기서 T t+1)로 참조 된다. 단지 하나의 정확한 부분 행렬(T=1)이 있을 경우, 그 행렬에 대한 비밀 s는 원래의 비밀과 동일하다고 판정되며, 대응하지 않는 열 벡터는 허가되지 않은 동작을 수행하는 가입자를 나타낸다. 2 또는 그 이상의 정확한 부분 행렬이 있을 경우, 각 가입자 i(i=1, ... n)는 그가 보유하고 있는 모든 정보 세그먼트(정보 B3. i)를 방송한다(처리 R3. i).

(사후 처리) 각 가입자 i(i=1, ... , n)는 라운드 3에서 방송되는 정보 s_j(j=1, ... , n)를 사용하여 전술한 비밀 분산 처리에서 사용한 바와 같은 동일한 일방향성 해시 함수를 계산한다. 그 후, 가입자 i는 모든 방송 정보가 정확한지의 여부와, 분산처리에서 라운드 1에서 방송되는 값 s^*에 부합하는지의 여부를 확인한다. 따라서, 최대 단지 하나일 수 있는 정확한 부분 행렬에 대응하는 비밀 s'는 비밀 요소 s와 동일하다고 판정된다. 다른 한편으로, 정확한 부분 행렬이 발견되지 않은 경우, 비밀 분산 가입자 d는 허락되지 않은 동작을 수행한 것으로 판정된다(처리 Pi).

전술한 바와 같이, 종래의 대화형 방법(1)이 n ^3k ^2 차수 (여기서, n은 가입자의 수이고, k는 안정성 파라미터임)의 통신량을 요구하는 반면에 이 실시예는 n ^2k 차수의 통신량을 요구한다. 또한, 종래의 비대화형 방법(2)이 n차수의 특정한 일방향성 함수의 계산을 요구하는 반면, 이 실시예는 일방향성 해시 함수의 단지 하나의 시간 계산만이 요구된다. 따라서, 통신량 및 계산량이 종래의 방법에 비하여 실용적인 방법이 제공될 수 있다.

[실시예 2]

제1 실시예에서와 같이 확인가능한 비밀 분산 처리 및 비밀 복원 처리는 종래의 안전한 분산된 계산 방법(예를 들면, Secure Multiparty Protocols And Zero-Knowledge Proof Systems Tolerating A Faulty Minority, D. Beaver, Journal of Crytology 1991 또는, A Note On Multiparty Protocols To Compute Multiplicative Inverse, M. Cerocedo, T. Matsumoto, 및 H. Imai, SCIS '94, Biwako, Japan, 1994년 1월을 참조)에 대한 부분 처리로서 사용되므로써 보다 효율적인 분산 동작 처리 시스템이 제공될 수 있다.

분산 동작 시스템이란, 분산 및 승산 처리와, 분산 및 가산 처리는 기본적인 부분 처리에 사용되고, 부분 가산 처리는 부분 승산 처리 동안 부분 처리로서 사용된다. 또한, 소정의 한정된 세트에서 통상적인 산술 연산은 분산 및 승산 처리와, 분산 및 가산 처리를 사용하여 수행될 수 있다. 제1 실시예의 처리를 사용하여 연산을 수행하는 경우에 제7도를 참조하면서 모든 처리에 대하여 기본적인 부분처리인 분산 및 가산 처리를 기술 할 것이다.

소정의 한정된 세트에서 두 비밀 요소 x 가 분산될 때(이때, 각 가입자 i는 비밀 요소 x 및 y에 대응하는 비밀 부분 x_i 및 y_i를 보유함), 통신은 수행되지 않고, 소정의 한정된 세트에서 x+y에 대응하는 비밀 부분(x+y)_i가 다음과 같이 계산된다.

먼저, 열 벡터 X_c(i) 및 Y_c(i)의 요소와, 각 가입자가 보유한 부분 행렬의 비밀값 x_r(i)및 y_r(i)(제1 실시예 참조)의 요소가 가산된다. 이것은, 가산 결과 X-c(i)+Y_c(i) 및 x_r(i)+y_r(i) 가 x+y에 관하여 부분 행렬에 대한 열 벡터 및 비밀값인 부분 행렬 (행 및 열의 요소는 다항식의 값임)로부터 명백히 알 수 있다.

비밀 복원 처리에서 정보 세그먼트를 확인하기 위하여 사용되는 일방향성 함수값 x^*및 y^*이 저정된다. 이들 값은 복원 처리가 가산 결과 x+y 상에 수행될 때 필요하므로, 비밀 x+y에 대응하는 행렬 Y+Y가 확인된다.

통상적인 분산 산술 연산 시스템은 부분처리로서 전술한 분산 및 가산 처리를 사용하므로써 제공될 수있다.

본 발명은 전술한 실시예에서 개시된 부분 행렬 차원의 수로 제한되지 않으며, 다수 차원 부분 배열일 수 있다. 또한 사용되는 함수는 일방향성 특성의 획득을 보장하는 일방향성 해시 함수와 다른 함수이다. 컷 앤 츄스 기법을 고려하면, 실시예 1에서 상세히 설명된 절차로 제한되지 않지만, 비밀을 누설하지 않으면서 타당성을 확인하는 방법을 사용하는것과 관계될 수있다.

전술 바와 같이, 이 실시예에 따라서 허가되지 않은 동작을 수행하는 가입자가 식별될 수 있을시 (에러가 검출될 수 있을시) 비밀 정보를 처리하는 방법 및 시스템은 효율적인 통신량 및 효율적인 계산량에 의해 제공될 수 있다.

또한, 비일 분산처리의 반복적인 수행을 요구하는 안전한 분산 동작 처리와 같은 처리에 대하여, 통신 및 계산량은 종래의 경우에 요구되는 것보다 작을 수 있으므로, 통신 시스템 내에 통신량은 감소하고 작은 통신량으로 인하여 통신 비용은 감소될 수 있고, 처리는 소량의 계산으로 인해 고속으로 수행될 수 있다.

서명자(signers) 그룹에 속하는 다수의 가입자에 의해 수행되는 디지탈 서명 분산을 발생하는 방법은 전술한 비밀 분산 방법을 사용하므로써 기술될 것이다.

이 제2 실시예에서, 전술한 확인 가능한 비밀 분산 방법이 사용된다. 서명자 그룹에 속하는 가입자는 그룹의 모든 이들 간으로부터 임의로 선택되는 비밀 요소를 분산하고, 입력으로서 분산된 입력을 사용하여 분산된 산술 연산의 실행에 의해 구해지는 분산된 출력의 복원 처리동안 서명을 생성한다.

따라서, 이 제2 실시예에서, 허가되지 않은 동작을 수행하는 가입자의 식별이 가능하며, 계산량 및 통신량은 절대값의 실제 차수이다.

제9도는 이 제2 실시예에 대한 통신 시스템을 도시한다.

제9도에서, 시스템 사용에 가입하는 정보 처리 장치(11), 방송 통신로(12) 및 비밀 통신로(13)는제1도에 있는 것과 동일하다. 여기서, 가입자 A, B 및 C 는 서명자 그룹으로 구성된다. 정보 처리 장치(11)의 블럭구조는 제2도에서 도시된 바와 같다.

이러한 배치를 가지고 분산된 디지탈 서명을 실현하는 방법을 상술할 것이다.

[제3 실시예]

이 제3 실시예에서, 이제 C. P. Schnorr가 제안한 전술한 디지탈 서명 방법을 구현하는 특정 구조를 기술 할 것이다.

먼저, {1, ... , p-1} 중으로부터 비밀 요소 s는 전술한 확인가능한 비밀 분산 방법에 의해 분산된다. 비밀 요소11, ..., 1k는 {1, ... ,p-1} 로부터 임의로 선택된다. 이러한 방식으로, 처리는 서명자 그룹중의 소정 가입자가 보유한 비밀 요소가 분산되고, 그룹의 모든 가입지가 보유할 시에 수행된다.

이제, 분산된 디지탈 서명 시스템에서, 비밀 분산 방법 비밀 정보(발생된 서명을 확인하기 위하여 사용되는 공개키와 동등한 공개 정보)에 대응하는 공개 정보 및 그룹의 비밀 정보(서명자 그룹에서 모든 가입자에게도 분산되는 비밀 키와 동등한 것)를 발생하는 처리를 기술 할 것이다.

키 발생처리(제10a 및 제10b도를 참조)

(라운드 1 내지 5) 각 가입자 i는 {1, ... , p-1}로부터 임의로 비밀 요소a(i)를 선택하고, 이는 전술한 비밀 분산 처리를 수행하므로써 서명자 그룹의 모든 가입자들간에 분산된다. 또한, 각 가입자 i는 g ^(r(i))mod q(여기서, q는 전술한 방식으로 선택된 소수)을 계산하고, 방송 통신로를 통해 이를 방송한다.

(라운드 6) 비밀 분산 처리의 사후 처리가 수행된다. 입력으로서 올바르게 분산된 비밀 요소 r(i)(i=1, ... , n)을 사용하므로써, 제7도를 참조하여 설명되는 분산된 가산으로 구해지는 분산 출력은 비밀 정보 a로서 정의된다. 또한, 올바르게 분산된 비밀 요서a(i)에 관한 사전처리의 라운드 1내지 5에서 방송되는 값 A(i)=g^(a(i))mod q가 승산된다. 구해진 결과 A=g ^a mod q는 공개 정보(공개 키)로서 사용되어 그룹이 발생한 서명을 검증한다.

분산된 가산과 동일한 방식으로 하나의 분산된 비밀 요소x 및 공개 요소 a의 분산된 승산을 수행하기 위하여, 가입자가 보유한 부분 행렬의 각 요소를 곱하므로써 구해지는 결과는 x^*a에 관한 부분 행렬의 요소이다.

따라서, 두 분산된 비밀 요소x 및 y와 공개요소 a의 공개요소 a의 선형결합 a^*x+b^*y의 분산된 계산은 그룹의 가입자들간의 대화없이도 수행될 수 있다. 선형 결합 처리하는 제11도에 도시되어 있다. 제11도에는 수행할 처리의 타이틀(title)과 이 처리 동안 각 가입자에 대한 입력 및 출력이 도시되어 있음을 주목해야 한다. 가입자 i(i=, ... , n)의 입력은 분산된 비밀 요소 x 및 y와 공개 요소 a 및 b에 관한 정보 세그먼트 x_i 및 y_i이다. 출력은 선형 결합 처리의 결과 x 에 관한 정보 세그먼트 z_i이다.

전술한 처리를 통하여 얻을 수 있는 비밀 키를 사용하므로써, 소정의 메시지 m은 디지탈 서명은 다음과 같이 분산 되는 그룹에 의해 발생된다.

서명 발생 처리(제12도 참조)

(라운드 1 내지 5) 각 가입자 i는 {1, ... , p-1} 로부터 임의로 비밀 요소 r(i)를 선택하고, 이 선택은 전술한 분산 처리를 수행하므로써 서명자 그룹의 모든 가입자와 함께 분산된다. 또한, 각 가입자 i는 g＾(r(i))mod q(여기서, q는 전술한 방식으로 선택된 소수)를 계산하고, 방송 통신로를 통하여 방송한다.

(라운드 6) 비밀 분산 처리의 사후 처리가 수행된다. 입력으로서 올바르게 분산된 비밀 요소 r(i)(i=1, ..., n)으로써, 분산된 결과 r은 분산된 가산을 수행하므로써 구해진다. 또한, 올바르게 비밀 요소 r(i)에 관한 라운드 1내지 5에서 방송되는 값 R(i)=g＾(r(i))mod q의 승산인 R=g＾r mod q가 계산된다.

(라운드 7) 각 가입자는 라운드 6에서 구해진 소정의 메시지 m과 값 R을 결합하므로써 얻어지는값 R:m을 입력으로서 사용하여, 전술한 사전 결정된 함수 h의 출력 e=h(R:m)을 계산한다. 그 후, s=r+h(R:m)^*a는 분산되고, 분산된 선형결합처리의 수행에 의해 서명자 그룹의 모든 가입자들에 걸쳐 계산된다.

(라운드 8 내지 10) 분산된 비밀 s는 비밀 분산 방법에 대한 비밀 복원 처리에 의해 복원된다. 소정의 메세지에 대한 서명은 (R, S)로서 정의된다. 발생된 서명은 공개키 a를 사용하므로써, 디지탈 서명 방법에 대한 서명 검증 처리를 수행하므로써 검증된다. 서명이 올바르지 않은 경우, 허가되지 않은 동작을 수행한 가입자가 있다고 판정된다. 이러한 가입자를 식별하기 위하여 비밀 분산 방법의 비밀 복원 처리가 수행된다

[실시예 4]

이제, A. Fiat 및 A. Schamir 가 제안한 전술한 디지탈 서명 방법을 사용하는 분산된 디지탈 서명 방법을 구현하는 특정 구조를 기술할 것이다. 먼저, {1, ..., N-1}의 비밀 요소를 확인가능하게 분산시키는 특정 배치를 기술한다.

소정의 비밀 s에 대한 부분 행렬을 상세히 설명할 것이다(제3도 참조). {1, ..., N-1}중으로부터 특정한 비밀 s에 관한 부분 행렬 S=[s(i, j)(i, j=1, ..., n)는 각 행 벡터(S⁺_r(i)=[s(i,1), ...,s(i, n)], s=1, ..., n)의 요소가 다음과 같이 정의될 시에 하나이다.

s(i,j)=s_r(i)^*q_r(i,1)^(J)^*q_r(i, 2)^(j^2)^*.....^*q_r(i, t)^(j^t)mod N(j=1, ....n).

요소 q_r(i,1),.... q_r(i,t)는 {1, ..., N-1}로부터 선택되어 다음의 요건을 만족한다. 각 열 벡터 (s_c(j)=[s(i, j)...., s(n,j)] j=1, ...., n)의 요소는 다음과 같이 정의된다 :

s(j,i)=s_c(j)^*q_(j,1)^(k)^*q_c(j,2)^(i^2)^*,....

*q_c(j,t)^(i^t)mod N(i=1, ...., n).

요소 q_c(j,1),...., q_c(j,t)는 {1, ..., N-1}로부터 선택되어 다음의 요건을 만족한다. 또한 전술한 값을 가지는 두 벡터[s_r(1), ...., s_r(n)] 및 (s_c(1), ...., s_c(n)]는 {1, ..., N-1} 중으로 부터의 q_r(1),...., q_r(t), q_c(1), ...., q_c(t)에 대한 다음의 요건을 만족한다.

s_r(j)=s^*q_r(1)^(j)^*q_r(2)^(j^2)^*...

*q_r(t)^(j^t) mod N (i=1, ... n),

과

s_c(i)=s^*q_c(1)^(i)^*q_c(2)^(i^2)^*...

^*q_c(t)^(i^t) mod N(i=1, ...., n),

여기서, s는 원래의 비밀을 나타낸다.

비밀 부분을 분산시키는 비밀 분산 처리에서 비밀요소는 s는 분산되고, 서명자 그룹에 속하는 모든 서명자에 의해 보유되며, 분산된 비밀을 복원하거나 허가되지 않은 동작(이러한 동작이 발생하는 경우)을 수행하는 가입자를 식별하는 비밀 복원처리는 실시예 1에서의 처리(1) 및 (2) 가 수행되는 것과 동일한 방식으로 수행된다. 비밀 복원 처리에서, 다항식 보간법 대신에 다음에 계산되어, 각 행 벡터(s_r(i)=[s(i,1),...., s(i,n)], I=1, ..., n)에 포함되는 t+1 요소(s(i, jo), ...., s(i, jt))로부터 값 s-r(i)를 얻는다.

s_r(i)^(n!)=Prod_k(s_(i, jk)^(Prod_1(1^*n!/(1-k)))) mod N

여기서, Prod_k(f(k))는 k= j0, ..., jt인 동안 값 f(k)의 승산을 나타내고, Pord_1(g(1))는 1=j0., ...., jt(1≠k)에 대한 값 g(1)의 승산을 나타낸다.

이와 같이, 각 열 벡터(S_c(i)=[sc1, j), ...., s(n, j)], j=1, ...., n)에서 t+1 요소 (s(i0, j), ...., s(it, j))로부터 값 s-c(j)를 구하기 위하여, 다음의 계산이 수행된다.

s_c(j)^(n!)=Prod_k(s(ik,j)^(Prod_1(1^*n!/(1-k)))) mod N

부분 벡터[s_r(1)^(n!), ...., s_r(n)^(n!) 또는 [s_c(1)^(n!), ....,

s_c(n)^(n!))의 t+1요소(s_r(i0)^(n!), ...., s_r(it)^(n!) 또는 (s-c(j0)^(n!),....,

s_c(jt)^(n!))로부터 비밀 s를 얻기 위하여, (s_r(i)^(n!)일 때) 다음의 계산이 수행된다.

s^(n!^*n!)=Prod_k(s_r(k)^(n!^*Prod_1(1^*n!/1-k)))) mod N

s=(s (n!^*n!) u^*(s 1)^v mod N.

그러나, A. Fiat 및 A. Shamir이 제안한 디지탈 서명 방법에 사용되는 1이 선택되어 u^*n!^*n +v^*1=1을 만족시키는 u및 v를 제공한다. 분산된 비밀 s에 대한 값 s 1 mod N은 차후에 기술할 설명 발생 처리에서 계산된다.

이러한 방식으로, 서명자 그룹의 소정 가입자가 보유하는 비밀 요소가 분산되고 그룹의 모든 가입자에 의해 보유될 수 있을 시, 처리가 제공될 수 있다. 그 다음, 비밀 키와 동등하며, 그룹의 모든 가입자에게로 분산될 수 있는 서명자 그룹에 대한 비밀 정보와(공개 키와 동등하며, 그룹에 발생하는 서명을 검증하는데 사용되는) 비밀 정보에 대한 공개 정보를 발생하기 위해 이 비밀 분산 방법을 사용하는 분산된 디지탈 서명 시스템의 처리를 기술할 것이다.

(라운드 1 내지 5) 각 가입자 i는 {1, ..., N-1}로부터 임의로 비밀 요소 a(i)를 선택하고, 이 선택은 전술한 비밀 분산 처리를 수행하므로써 서명자 그룹의 모든 가입자들에게 분산될 수 있다. 또한, 각 가입자 i는 a(i) 1 mod N(여기서 1은 전술한 방식으로 선택되는 요소)를 계산하고, 방송 통신로를 통해 방송한다.

(라운드 6) 비밀 분산 처리의 차후 처리가 수행된다. 올바르게 분산된 비밀 요소a(i)(i=1, ..., n)를 입력으로 사용하므로써, 다음의 분산된 승산에 의해 구해지는 분산된 출력은 비밀 정보 a로서 정의 된다. 또한, 올바르게 분산된 비밀 요소 a(i)에 관한 사전처리의 라운드 1내지 5에서 방송되는 값 A(i)=a(i) 1 mod N이 승산된다. 구해진 결과 A=a 1 mod N은 공개 정보(공개 키)로서 사용되어 그룹이 발생하는 서명을 검증한다.

라운드 6에서 사용된 분산 승산 처리에 대해서 제 14도를 참조하면서 설명하기로 한다.

{1, ..., N-1} 에 있는 두개의 비밀 요소 x및 y가 비밀 분산 처리에 이해 분산되면 (각 가입자 i는 비밀 요소 x 및 y에 관련된 비밀 부분 x_i 및 y_i를 보유한다), 통신은 행해지지 않으며, {1, ..., N-1} 에 포함된 곱 x^*y에 대한 비밀 부분(x^*y)은 다음과 같이 계산된다.

부분행렬의 정의로부터, 각 가입자가 보유하는 부분행렬의 열 벡터 X_c(i)와 Y_c(i)와, 비밀값 x_r(i)와 y_r(i)의 승산에 의해 얻어진 결과치 X_c(i)^*Y_c(i)와, x_r(i)^*y_r(i)가 x^*y에 대한 부분행렬의 열벡터 및 비밀값이라는 것을 알 수 있다. 비밀 복원 처리에 정보 세그먼트의 확인을 위해 사용되는 일방향성 해시 함수값 x^*및 y^*모두가 기억되어 있다. 승산결과 x^*y에 대한 암호화 처리시에, 부분행렬 X^*Y가 비밀 x*y와 일치하는 가를 확인하는데 이들 함수값을 사용한다.

동일하게, 하나의 분산 비밀 요소 x와 공개요소 a의 지수 승산이 분사되므로, 각 가입자가 보유하는 부분행렬의 요소들과 공개 요소 a의 지수 승산으로 얻어진 결과치는 x^a에 대한 부분행렬의 요소들 이다. 따라서, 상기 처리에서 분산되어진 두 비밀 요소 x 및 y와, 공개 요소 ab의 결합 x ^a^*y ^b를 그룹에 참가하는 가입자간에서의 대화를 필요로하지 않고도 분산하게 계산할 수 있다. 이러한 처리에대해서는 제 11도에서와 같이 제 15도로 도시되어 있다.

상기처리를 통해서 얻어진 비밀 키는 주어진 메시지 m에 대해 분사된 디지탈 서명을 생성하기 위한 그룹에서 다음과 같이 사용된다.

서명 생성 처리(제 16도 참조)

(라운드 1 내지 라운드 5) 각 가입자 i는 {1, ..., N-1} 로부터 임의로 비빌요소r(i)를 선택하고, 그 선택된 비밀 요소가 상기 비밀분산처리를 행하여 서명자 그룹의 모든 가입자에게 분산된다. 또한, 각 가입자 i는 r(i) 1 mod N(여기서 1은 상기와 같은 방법으로 선택된 요소)을 계산하여, 방송 통신로를 통해 방송한다.

(라운드 6) 비밀 분산 처리의 사후 처리가 수행된다. 입력으로서 정확하게 분산된 비밀 요소 r(i)(i=1, ..., n)의 사용하는 경우, 상기 분산 승산을 행함으로써 분산 결과치 r이 얻어진다. 또한, 정확하게 분산된 비밀 요소 r(i)에 대하여 라운드 1내지 5에서 방송되는 R(i)=r(i) ^mid n의 승산치인 R=r ^1 mon N이 계산된다.

(라운드 7) 각 가입자가 입력으로서 라운드 6에서 얻어진 R값과 주어진 메시지 m을 결합시켜 얻어진 값 R:m을 사용하고, 상술된 소정의 함수 h의 출력 e=h(R:m)를 계산한다. 다음에, 분산된 선형 결합 처리를 행하여 서명자 그룹의 모든 가입자들에게 s=r^*a (h(R:m))를 분산하고 계산한다.

(라운드 8내지 10) 분산된 비밀 s는 비밀 분산 방법의 비밀 암호화 처리에 의해 암호화 된다. 주어진 메시지에 대한 서명은 (R, s)로 정의된다. 생성된 서명은 공개키를 사용하고 디지탈 서명 방법의 서명 확인 처리를 행함으로써 확인된다. 이 서명이 정확하지 않으면, 부정을 행한 가입자가 있는 것으로 판단한다. 비밀 분산 방법의 비밀 암호화 처리는 이러한 가입자를 식별해내기 위해 행해지는 것이다.

[실시예 5]

이 실시예에서는 T. ElGamal에 의해 제안된 디지탈 서명 방법(American National Standard, Digital Signature Algorithm)을 이용하는 분산 디지탈 서명 방법을 구현하는 특정 구조에 대해 설명하고자 한다.

실시예 1에서 기술된 방법은 서명자 그룹의 어느 가입자에 의해 선택된 비밀 요소를 분산하여 그 그룹의 모든 가입자가 보유하기 위한 특정 방법으로서 사용된다. 지금부터 그룹의 비밀 정보(서명자 그룹의 모든 가입자에게 분산되어 있는 비밀키와 등가)와 그 비밀 정보에 대한 공개 정보(공개키와 등가이며 생성된 서명을 확인하기 위해 사용되는 공개 정보)를 생성하기 위해 비밀 분산 방법을 사용하는 분산 디지탈 서명 시스템의 처리에 대해 설명하고자 한다.

키 생성 처리(제10a 및 10b도 참조).

(라운드 1 내지 5) 각 가입자는 i는 {1, ... p-1}로부터 임의의 비밀 요소 a(i)를 선택하고, 그 선택된 비밀 요소가 상기 비밀 분산처리를 행하여 서명자 그룹의 모든 가입자에게 분산된다. 또한, 각 가입자 i는 g^(a(i)) mod q(여기서 q는 상기와 같은 방법으로 선택된 소수)을 계산하여, 방송 통신로를 통해 방송한다.

(라운드 6) 비밀 분산 처리의 사후 처리가 수행된다. 입력으로서 정확하게 분산된 비밀 요소 a(i) (i=1, ...., n)를 사용함으로써 다음의 분산 가산으로 얻어진 분산 출력을 비밀 정보 a로 정의한다. 또한, 정확하게 분산된 비밀 요소 a(i)에 대하여 라운드 1 내지 5에서 방송되는 값 A(i)=g^(a(1)) mod q가 승산된다.

얻어진 결과치 A=g^a mon q는 그룹에서 생성된 서명을 확인하기 위한 공개 정보(공개 키)로서 사용된다.

1, ...., p-1에서 두 개의 비밀 요소 x 및 y가 비밀 분산 처리에 의해 분산되면 (각 가입자 I는 비밀 요소 x 및 y에 관련된 비밀 부분 x_i 및 y_i를 보유한다), 통신은 행해지지 않으며, 1, ...., p-1에 포함된 합 x+y에 대한 비밀 부분(x+y)_i는 실시예 1에 기술된 방법과 동일하게 계산된다.

{1, ... p-1}에서 두 개의 비밀 요소 x 및 y가 비밀 분산 처리에 의해 분산되면 (각 가입자 I는 비밀 요소 x 및 y에 관련된 비밀 부분 x_i 및 y_i를 보유한다). 통신은 행해지지 않으며, {1, ... p-1}에 포함된 합 x+y에 대한 비밀 부분 (x+y)_1는 실시예 1에 기술된 방법과 동일하게 계산된다.

{1, ... p-1}에서 두 개의 비밀 요소 x 및 y가 비밀 분산처리에 의해 분산되면 (각 가입자는 i는 비밀 요소 x 및 y에 관련된 비밀 부분 x_i 및 y_i를 보유한다), 통신은 행해지지 않으며, {1, ... p-1}에 포함된 곱 x^*y에 대한 비밀 부분 (x^*y)_i은 다음과 같이 계산된다.

특정 가입자 d가 {1, ... p-1}에서 비밀 s에 대해 확인 가능한 분산을 행하므로, 그 가입자는 비밀 s와 이전에 분산된 x의 분산된 곱 s^*x를 안전하게 계산한다.

이러한 처리를 확인 가능한 비밀분산 및 승산처리라 칭한다.

확인 가능한 비밀 분산 및 승산 처리(제17 및 18도 참조)

이하에서, h는 실시예 1에서와 같이 효율적인 일방향성 해시 함수를 나타낸다. 안전 파라미터 k는 특정 상수 k'에 대해 k=nk'를 만족한다.

(라운드 1) 가입자 d는 난수발생 장치(23)를 이용하여 비밀요소 s와 {1, ... p-1}에서 임의로 선택된 비밀요소 11, ...., 1k에 대한 부분행렬을 생성한다.

비밀값 s_r(1), ...., s_r(n), 11_r(1),...., 11,r(n), ...., 1k_r(1),..., 1k_r(n)에 대한 일방향성 해시 함수값 s^*가 계산된다(제4도 참조).

가입자 d는 생성된 각 부분행렬의 열벡터 S_c(i), L1_c(i), ..., Lk_c(i)와 비밀 s-r(i), 11_r(i), ...., 1k_r(i)을 비밀 통신로를 통해 각 가입자 i(i는 그 자신을 제외한 1, ...., n)에게 전달한다. 그리고 해시 함수값 s^*(제17도에서 B1. d)는 방송 통신로를 통해 (제17도에서 처리 R1, d로서 표시된) 모든 가입자에게 방송한다.

(라운드 2)

각 가입자 i(i=1, ...., n)는 입력으로서, 라운드 1에서 수신된 비밀 s_r(i), 11_r(i), ...., 1k_r(i)와, x에 대해 이전에 분산된 x_r(i)를 사용하여, t_r(i)=s_r(i)^*x_r(i), ml_r(i)=1l_r(i)^*x_r(i), ...., mk_r(i)^*x_r(i)mod N이 계산되어진다. 난수발생 장치(23)는 얻어진 결과치에 대한 부분행렬(T(i), M1(i), ...., Mk(i)라 칭하며, 반면에 이전에 분산된 비밀 x의 부분 x_r(i)에 대한 부분행렬은 x(i)라 칭함)을 생성하는데 사용된다. 다음에, 비밀값 t(i)_r(1),...., t(i)_r(n), m1(i)_r(1)...., m1(i)_r(n),...., mk(i)_r(1),...., mk(i)_r(n)에 대한 해시 함수값 s^*이 계산된다(제4도 참조). 각 가입자 T는 생성된 각 부분행렬의 열벡터 T_c(i), ...., Mk_c(i)와 비밀 t(i)_r(j), ml(i)_r(j),...., mk(i)_r(j)을 비밀 통신로를 통해 각 가입자 j(j는 그 자신을 제외한 1, ..., n)에게 전달한다. 그리고 해시 함수값 s^*는 방송 통신로를 통해(제17도에서 처리 R2. i로 표시된) 모든 가입자에게 방송된다. 가입자 i가 방송한 정보는 제17도에서 Bs.i로 표시된다.

(라운드 3) 각 가입자 i(i=1,..., n)는 난수 생성 수단을 사용하여 임의로 선택된 비트를 방송한다(제17도에서 처리 R3. I). 임의로 선택된 k' 비트를 각각 Bi_1, ..., Bi_k'라 칭하며, 전체 n가입자에 대한 비트를 B1, ..., Bk라 칭한다. 가입자 i가 방송한 정보는 제17도에서 B3.i로 표시도이다.

(라운드 4) 라운드 3에서 방송된 각 비트 Bj(j=1, ...., k)가 1이면 가입자 d는 라운드 1에서 가입자 d에 의해 생성된 부분행렬 Lj를 방송한다. Bj가 0이면, 가입자 d는 유한 집합에서 생성된 부분행렬 S와 Lj의 각 요소를 가산시켜 얻어진 결과치(S+Lj로 표시)를 방송한다(제17도에서 처리 R4.d). 가입자 d가 방송하는 정보를 제17도에서 B4.d로 표시한다.

(라운드 5) 라운드 1에서 비밀리에 수신된 정보 B1.i의 각 값 j(j=1, ...., k)에 대하여, 각 가입자 i(i=1, ...., n)는 (라운드에 2에서 비트 Bj 방송이 1인 경우) 열벡터 Lj_c(i) 및 1j_r(i)또는 (Bj가 0인 경우) Lj_c(i)+S_c(i) 및 1j_r(i) + S_r(i)가 라운드 4에서 방송하는 부분행렬의 열 벡터와 비밀값과 동일한가를 확인한다. 이들이 임의값 j에 대해 동일하지 않으면 가입자 d가 판정 메시지를 방송한다(제17도에서 처리 R5.i). 가입자 i가 방송하는 정보를 제17 및 18도에서 B5.i로 표시하고 있다.

(라운드 6) 라운드 3에서 방송되는 각 비트 Bj(j=1, ...,k)가 1이면, 각 가입자 I는 라운드 2에서 가입자 i에 의해 생성되는 부분행렬 Mj(i)를 방송한다.

Bj가 0인 경우, 가입자 d는 유한 집합(mod P)에서 생성된 부분행렬 T(i) 및 Mj(i)의 각 요소를 가산시켜 얻어진 결과치(T(i) + Mj(1)로 표기)를 방송한다(제18도에서 처리 R6.i). 또한, 가입자 d는 라운드 5에서 결정된 가입자 I로부터의 열 벡터를 방송한다. 가입자 d가 방송하는 정보를 제18도에서 B6.i로 표시하고 있다.

(라운드 7) 각 j(j=1, ..., k)에 대하여, 가입자 i는 라운드 5 및 6에서 방송되는 정보를 확인한다. 정확한 행렬의 수가 임계치 t 이상이고 라운드 3에서 방송되는 비트 Bj(j=1, ..., k)가 1이면, 다음의 부분행렬이 방송된다. 즉

(1j_r(i))^(-1)^*Mj(i) - X(i)

Bj가 0이면, 다음의 부분행렬이 방송된다. 즉

(S_r(i)+1j_r(i))^(-1)^*(T(i)+Mj(i))-X(i)(제18도에서 처리 R7.1). 부분행렬의 선형결합은(각 요소마다)상술된 바와 같이 행해진다. 가입자 i가 방송한 정보는 제18도에서 B7.i로 표시되어 있다.

(라운드 8) 각 j, o(j, 0=1, .....k)에 대하여, 각 가입자 i(i=1, ....n)는 라운드 4에서 방송되는 정보를 사용한다. Bo가 1인 경우, 0j_r(o)를 암호화하고, 다음의 열벡터를 계산하고, 그 열벡터를 계산하여 얻어진 결과치가 동일하여 0값과 일치한다는 것이 확인된다.

(1j_r(o))^(-1)^*Mj(o)_r(i)-X(o)_r(i).

결과치가 주어진 값 o에 대응한 것으로 확인될 수 없으면, 가입자 o대해 판정 메시지가 반송된다(제18도에서 처리 R8. i). 가입자 i가 방송한 정보는 제18도에서 B8.i로 표시하고 있다.

(라운드 9) 라운드 8에서 판정 메시지가 가입자 o에게 방송되면, 그 가입자는 그 열벡터를 방송한다.(제18도에서 처리 R9.o). 가입자 i가 방송한 정보는 제18도에서 B9.i라 표시되어 있다.

(라운드10) 각 가입자 i는 모든 방송정보를 확인하여, 부정을 행한 가입자 o에 대해 판정 메시지를 송한다(제18도에서 처리 R10. i). 가입자 i가 방송한 정보는 제18도에서 B10. i로 표시되어 있다.

(사후처리) 정확하게 분산된 부분행렬 S(i)^*X(i)의 분산 선형 결합은 모든 가입자에 의해 수행되어지고(각 가입자 i의 처리는 wp18도에서 처리 Pi라 표시). 따라서 정확한 부분행렬 S^*X가 분산 및 계산된다. 이 행렬이 부정행위로 인해 생성되지 않으면, 위반행위 가입자를 식별하여 그 결과를 방송한다.

상기 처리를 통해, 특정 가입자 i가 {1, ... p-1} 에서 임의로 선택한 비밀요소 s를 확인 가능하게 분산하며, 동시에 비밀요소 s와 이전에 확인가능하게 분산된 비밀요소 X의 곱 s^*x를 계산한다. 다음에, 상기 처리를 행하여 분산된 두 비밀요소 x와 y의 곱을 얻기 위한 계산처리에 대하여 기술하고자 한다. 이러한 처리는 제19도에서 도시되어 있다.

(라운드 1 내지 10) 각 가입자 i는 {1, ... p-1}에서 비밀 요소 r(i)를 임의로 선택하고, 선택된 요소에 대해 상기 확인가능한 분산처리를 수행하며, 동시에 r(i)^*y를 계산한다.

(라운드 11) 확인가능한 분산이 정확히 행해지는 모든 가입자 j1(1=1, ...m)에 대한 비밀 r=r(j1)+r(j1)+...+r(jm)과 r^*y=r^*y=r(j1)^*y+r(j2)^*y+...+r(jm)^*y의 계산을 상기 분산가산을 이용하여 행한다.

(라운드 12) 분산 가산은 비밀가산 y=x-r에 대해 행해진다.

(라운드 13 내지 15) 비밀 u는 모든 가입자에 의해 암호화 되어진다.

(라운드 16) 분산 계산은 비밀 선형 결합 z=r^*y-u^*y=x^*y에 대해 행해진다.

상기 처리를 통해, 분산된 두 비밀요소 x 및 y의 곱 x^*y는 그 그룹에 참가하는 가입자에게 분산되고 계산되어진다. 상기 처리에 의해 얻어진 비밀키를 사용하므로써, 주어진 메시지 m에 대한 디지털 서명이 그 그룹에 분산되어 다음과 같이 생성된다(제20도 참조).

(라운드 1내지 라운드 5) 각 가입자는데 i는 {1, ... p-1}로부터 임의로 비밀 요소 r(i)를 선택하고, 선택된 요소가 상기 비밀 분산처리를 행하여 서명자 그룹의 모든 가입자에게 분산된다. 또한 각 가입자 i는 g^(r(i)) mod q(여기서 q는 상기와 같은 방법으로 선택된 소수)을 계산하여, 방송 통신로를 통해 방송한다.

(라운드 6) 비밀 분산처리의 사후 처리가 수행된다. 입력으로서 정확하게 분산된 비밀 요소 r(i) (i=1, ..., n)의 경우, 상기 분산 가산을 행함으로써 분산 결과치 r이 얻어진다. 또한, 정확하게 분산된 비밀 요소 r(i)에 대하여 라운드 1내지 5에서 방송되는 값 R(i)=g^(r(i)) mod q의 승산치인 R=g^r:mod q가 계산된다.

(라운드 7) 각 가입자는 입력으로서 주어진 메시지 m을 이용하여 상술된 소정의 함수 h의 출력 e=h(m)을 계산한다. 다음에, 분산 선형 결합 처리를 행함으로써 서명자 그룹의 모든 가입자들 사이에서 b=(e+R^*a)가 분산되고 계산된다.

(라운드 8 내지 17) 여기서, s=b^*r^-1)는 상기 분산 승산을 이용하여 서명자 그룹의 모든 가입자들 사이에서 분산되고 계산된다. r^(-1)에 대한 분산 역원 처리를 피하기 위해, 난수 생성 처리시에 g^(r(i)) mod q 대신에 g^((r(i))^(-1)) mod q가 계산된다(라운드 1내지 5 참조).

(라운드 18 내지 20) 분산된 비밀 s는 비밀 분산 방법의 비밀 복원 처리에 의해 복원된다. 주어진 메시지에 대한 서명은 (R, s)로 정의된다. 생성된 서명은 공개 키 a를 사용하고 디지털 서명 방법의 서명 확인 처리를 행함으로써 확인된다. 서명이 정확하지 않으면, 부정한 행동을 한 가입자가 있는 것으로 판단한다. 비밀 분산 방법의 비밀 복원 처리는 이러한 가입자를 식별하기 위해 행해지는 것이다.

본 발명은 상기 실시예 3내지 5에서 기술된 부분 행렬의 차원수에 한정되지 않고 다차원 부분 배열이 될 수 있다. 또한, 사용된 함수는 일반향상 해시 함수 이외에 일방향성 특성을 확실히 얻을 수 있는 함수일 수 있다. 컷 앤드 츄스 기술의 경우, 실시예 1에서 상술한 처리과정에 한하지 않고 비밀 누설 없이 타당성을 확인하는 임의 방법을 사용할 수 있다.

상술된 바와 같이, 본 발명에 의하면, 통신 시스템을 통해 접속된 다수의 컴퓨터(서명자)로 구성되는 그룹의 정확한 서명자수가 임계치 t이상이며 서명자가 부정을 행할 때, 이러한 서명자를 식별할 수 있는 분산 디지털 서명 방법을 제공할 수 있다. 부정행위가 발생하더라도 정당한 서명이 생성되는 종래 기술의 분산 디지털 서명과 비교해 보면, 이 실시예의 방법은 효율적인 통신량 및 계산량 만을 필요로 한다.

또한, 위반행위 가입자를 식별하지도 서명을 생성할 수도 없는 종래의 분산 디지털 서명 방법과 비교해 보면, 본 발명의 방법이 이 방법으로 위반 행위 서명자를 식별할 수 있기 때문에 보다 안전하다.

보다 상술하자면, 최대 계산량을 필요로 하는 처리가 지수 승산이므로, 서명자 그룹에 참가하는 각 서명자마다 필요로 하는 계산량은 나중에 기술된 종래의 디지털 서명 방법에서 필요로 되는 계산량과 거의 동일한 것으로 가정된다. 각 서명자마다 필요로 하는 통신량은 1^*n^2^*k 차수이며(여기서, n은 가입자의 수, k는 안전 파라미터, 1은 사용한 정수길이), 먼저 기술된 종래 디지털 서명 방식에서 필요한 것보다 실제적이다.

비밀 암호와 처리(실시예 1에서 비밀 분산처리의 라운드 3 참조) 시에 m=n!/((t+1)!(n-t-1)!)의 t+1의 여러 열벡터를 포함하는 세트수와 일치하여, n이 매수 작지 않다면(n20), 위반행위 가입자를 주기적으로 식별하는 것은 곤란한 것으로 여겨진다. 따라서, 이 실시예에 따른 비밀 분산 방법은 가입자의 수가 소수일 때 효과적이다. 그러나, 종래의 확인 가능한 비밀분산 방법에서는 가입자의 수가 소수일 경우에도 비실제적인 통신량과 계산량을 필요로 한다.

상술된 바와 같이, 이 실시예의 서명 생성 방법을 사용함으로써 필요한 통신량 및 계산량을 감소시킬 수 있다. 또한, 통신량의 감소로 인하여 통신 시스템의 트래픽과 통신 요금이 감소되고, 계산량의 감소로 인하여 고속의 처리를 행할 수가 있다.

[실시예 6]

지금부터 통신 시스템의 다수의 장치에 의해 분산된 인증을 행하는 실시예에 대해 기술하기로 한다.

제21도는 본 발명의 일실시예에 따라 인증을 분산하고 행하는 정보처리 장치를 갖는 통신 시스템을 나타낸다.

제21도에서, 방송 통신로(12)와 비밀 통신로(13)는 제1도에서 도시된 기능과 동일 기능을 갖는다. 장치(14)는 분산된 인증서버인 장치 AS(1)..., AS(k)(이하 부재라 칭함)이다. 이 경우에 부재의 수는 효율성을 위해 비교적 작은 수 20 또는 그 이하로 정해진다.

통신 시스템을 구성하는 전체 장치의 수는 부재의 수보다 상당히 많을 수 있으며, 비밀 통신로(13)를 통해 부재에 접속된다. 장치들 간의 통신은 정규(비신뢰성) 통신로(16)를 통해 행해진다. 이후, 어느 한 장치가 다른 장치가 갖고 있는 서비스(예를 들어, 파일 전송, 원격 절차 호출 등)에 대한 요청을 전달할 때, 요청을 하는 장치를 클라이언트라 칭하고, 그 요청을 수신하여 서비스를 제공하는 장치를 서버라 칭한다. 제21도에서, 장치(15)는 이러한 클라이언트 및 서버로서 동작하는 장치 C/S(1), .... C/S(n)이다. 부재는 클라이언트 또는 서버일 수 있다는 것에 주목해야 한다.

이 실시예에서, 클라이언트와 서버는 상호 인증과 통신내용의 인증을 위해 사용된다. 또한, 클라이언트와 서버는 비밀 통신을 행하기 위해 비밀키를 분산시킨다. 또한, 비밀정보는 이 정보를 제어하고 계산하기 위한 부재들 간에서 분산되어 있으므로, 이 실시예의 인증서버는 종래 기술의 인증서버 보다 신뢰성이 높다.

클라이언트가 서비스를 위해 그 자신의 구별을 위한 인증 요청을 서버에게 요청할 때, 인증을 요청하는 클라이언트를 증명자(testifier)라 칭하고, 인증을 제공하는 서버를 인증자(authenticator)라 칭한다. 부재를 포함하여 통신 시스템의 개별 장치들은 제2도에서 도시된블럭 구조로 배열되어 있다.

분산된 인증 프로토콜의 기본 부분은 상술된 VSS(확인 가능한 비밀 분산) 프로토콜이다.

[분산된 비밀 선형 결합 처리]

주어진 유한집합중 두 비밀요소 x 및 y가 상기 확인가능한 비밀 분산 처리에 의해 분산되면(동시에, 각 가입자 i는 비밀 요소 x 및 y각각에 대응하는 비밀부분 x_i 및 y_i를 보유), 통신은 행해지지 않고, 주어진 유한집합의 합 x+y에 대응하는 비밀부분(x+y)_i이 다음과 같이 계산된다.

우선, 각 가입자가 보유하는 부분 행렬의 열벡터 X_c(i) 및 Y_c(i)의 요소들과, 비밀값 x_r(i)와 y_r(i)의 요소들이 가산된다. 부분행렬의 정의(행과 열의 요소들은 다항식의 값임)으로부터 가산결과치 X_c(i)+Y_(i)와 x_r(i)+y_r(i)는 x+y에 관한 부분 행렬에 대한 열벡터와 비밀값이다.

비밀 암호와 처리시에 정보 세그먼트를 확인하는데 사용되는 일방향성 해시 함수값 x^*및 y^*이 기억되어 있다. 이들 값은 가산결과치 x+y에 대해 복원 처리가 행해질 때 필요한 경우 사용된다. 따라서, 비밀 x+y에 대응하는 부분 행렬 X+Y가 검증된다.

또한, 하나의 분산된 비밀요소 x와 공개 요소 a 분산 승산을 해하기 위해, a를 가입자가 보유하는 부분행렬의 각 요소로 승산시켜 얻어진 결과치가 x^*a에 대한 부분행렬의 요소들이다. 따라서, 상기 처리를 통해, 두 비빌 요소 x 및 y가 공개 요소들 a 및 b의 선형 결합 a^*x+b^*y의 분산 계산을 그룹의 가입자들 간에서의 대화없이도 행할 수 있다.

상술된 방법에서, 비밀은 확인 가능한 방법을 이용하여 부재들 사이에서 분산될 수 있다.

다음에, 부재들간에서 분산된 의사 난수 생성을 위한 분산된 의사 난수 생성 프로토콜에 대해 기술하고자 한다.

[분산된 의사 난수 생성 프로토콜]

분산된 인증서버로서 동작하는 부재 AS(1), ..... AS(k)는 분산된 의사 난수 r의 비밀 부분 r(i)(i=1,....k)을 r을 제어하기 위한 부재 AS(i)로 출력시킨다. 프로토콜은 제23a 및 23b도에서 도시된 바와 같이 실현된다.

각 부재 AS(i)는 유한집합에서 요소로서 표현된 의사 난수를 ri를 생성한다(처리 81).

AS(i)는 상술된 확인가능한 비밀 분산 처리를 행하여 의사 난수 ri를 비밀로 분산시킨다. 각 부재가 이러한 처리를 행하므로, 각 부재 AS(j)(j=1, ...., k)는 개별 부재의 비밀부분 rl(j), ..., rm(j)를 보유한다. m(≤k)은 비밀 분산이 정당하게 행해진 것을 입증하는 부재의 수인 것에 주목해야 한다(처리 82).

각 부재 AS(j)는 비밀부분을 모두 가산시켜, AS(j)에 관한 의사 난수 r의 비밀부분인 r(j)=rl(j)+....+rm(j)을 발생시킨다(처리 83).

의사 난수 r은 부재의 과반수가 함께 플로트되지 않는 한 어느 누구도 알 수 없는 수이다. 분산된 의사 난수는 상술된 바와 같이 생성되며 생성된 의사 난수를 증명자와 인증자에 대한 대화키로서 사용할 수 있다.

지금부터 부재들 사이에서 분산 비밀키 암호화 처리를 행하는 프로토콜에 대해 설명하기로 한다. 처리는 비밀키 암호화용 데이터가 분산된 비밀 데이터이고 이 데이터가 공개 데이터인 경우에 따라 변한다.

[분산된 비밀 데이터에 대한 분산된 비밀키 암호화/복호화]

제24a도는 이러한 프로토콜을 설명하는 선도이다. 길이 N을 갖는 N블럭, m1..., mN으로 형성된 베시지는 m으로 정의된다. VSS 프로토콜은 유한집합 GF(2^L)에서 실행된다는 것에 주목해야 한다. 비밀 부분 ml(i), ..., mN(i)은 부재들 AS(i)사이에서 비밀리에 분산되는 것으로 가정한다. 또한, 메시지 m과 동일한 길이를 갖는 비밀키 pk는 또한 길이 L을 각각 갖는 N 블록, pk1, ...., pkN으로 분할된다. 이들 블록은 상기 부재들 간에서 비밀리에 분산되어, 부재 AS(i)는 개별 비밀부분 pk(i), ..., pkN(i)를 갖는다.

비밀 키 pk를 이용하여 메시지 m에 대한 비밀 키 암호화 처리를 행하기 위해서, 각 부재 AS(i)는 주어진 유한집합에서 각 블록마다 다음과 같은 가산을 행한다. 즉,

cl(i)=ml(i)+pkl(i), ... , cN(i)=mN(i)=pkN(i).

VSS 프로토콜의 형성은 절반 동일하므로, cl(i), ...., cN(i)는 암호화문 c를 길이 L을 각각 갖는 N블럭으로 분할시켜 얻어진 cl, ..., cN의 비밀부분에 대응한다. 따라서, 암호화문 c는 상술된 비밀 복원처리를 행하여 복원되어 공개된다.

비밀 키 pk를 갖는 통신 시스템의 장치들은 공개 암호화문 c로부터 원시 메시지 m을 복원시킬 수 있다. 비밀 키 pk를 단지 한번만 사용하고 다시는 사용하지 않는다는 것에 주목해야 한다.

[공개 데이터용 분산 비밀 키 암호화/복호화]

공개 메시지 m에 대해,

상기 암호화 프로토콜을 사용하면, 비밀키 pk는 공개된 암호화문 c로부터 메시지 m을 감산시킴으로써 제3자에게 공개될 수 있다. 따라서, 제24b도에 도시된 프로토콜은 공개 데이터에서 사용된다.

이전의 경우뿐 아니라 메시지 m은 길이 L을 각각 갖는 N 블록 ml, ..., mN으로 형성된다. 메시지 m의 내용은 부재에게 알려진 공개 데이터이다. 비밀 키 pk는 메시지 m인 동안 2회 사용되며 길이 L의 2N 블록 pk1_1, pk1_2,..., pkN_1, pkN_2으로 분할된다. pk는 부재들간에서 비밀리에 분산되고, 부재 AS(i)는 각각 비밀부분 pk1_1(i), pk1_2(i), .... pkN_1(i), pkN_2(i)를 보유한다.

비밀 키 pk를 사용하여 메시지 m에 대한 비밀 키 pk 암호화 처리를 실현하기 위해 각 부재 AS(i)는 각 블록마다 주어진 유한집합에서 다음의 연산 처리를 행한다. 다음의 식에서, ·은 승산을, +는 가산을 나타낸다. 즉

cl(i)=ml·pkl_l(i)+pkl_2(i), ..., cN(i)=mN·pkN_l(i)+pkN_2(i).

VSS 프로토콜의 형성이 선형 조합의 경우 절반 동일하므로, Cl(i), ..., cN(i)는 암호화문 c를 길이 L을 각각 갖는 N블럭으로 분할하여 얻어진 cl, ...., cN의 비밀부분에 대응한다. 따라서, 암호화문 c는 상술된 비밀 복원 처리를 행하여 복원되어 공개된다.

상술 바와 같이, 프로토콜이 두 유형의 키, pkj_l 및 pkJ_2(j=l,...., N)를 사용하므로, 메시지 m이 공개 데이터인지 여부에 관계 없이 비밀 키 pk를 누설시킬 기회는 없다. 비록 암호화가 길이 L이 짧은 경우에 용이하더라도, 위반 행위자가 암호화문 c를 잘못 암호화문 c'로 변경시켜 잘못된 메시지 m'를 제공하는 확률은 2^-L로서 L은 안전상의 이유로서는 매우 작지 않을 수있다. 따라서, L은 약 32가 적합하다.

복호화의 경우, 비밀 키를 공통으로 사용하는 통신 시스템의 장치들은 각 길이 L마다 비밀 키 pk와 상호화문 c를 디스어셈블하고, pkj_1, pkj_2 및 cj(cj=pkJ_2)/pkj_1을 연산처리를 행하여 mj를 얻는다. 이러한 처리를 통해, 원시 메시지 m을 복원시킬 수 있다. 비밀 키 pk는 이 경우에도 단지 한번만 사용되고 다시는 사용되지 않는다.

[인증 프로토콜]

공통 키에 의한 인증은 종래의 집중화된 인증서버 대신에 분산된 인증 서버에 의해 상기 프로토콜을 사용하여 다음과 같이 실현된다.

인증 프로토콜은 증명자가 분산 인증 서버로부터 인증 메시지를 수신하는 통신과 증명자가 인증자에게 인증 데이터를 제공하는 통신을 포함한다. 이것을 온-라인 처리라 칭한다.

온-라인 처리의 수행을 위한 전제로서, 분산 인증서버와 증명자 또는 인증자로서 동작하는 장치간의 비밀 키 분산처리와 분산 인증서버에 의한 대화 키 생성처리가 필요하다. 이것을 오프-라인 처리라 칭한다. 오프-라인 처리는 비밀키 또는 대화 키가 온-라인 처리 중에 필요할 때마다 행해질 수 잇지만, 온-라인 처리와 통신 주기에 필요한 시간은 연장된다.

오프-라인 처리가 온-라인 처리에 앞서 행해지면, 온-라인 처리를 효율적으로 행할 수 있다. 오프-라인 처리와 온-라인 처리에 대해서 지금부터 제25a 및 25b도를 참조하면서 기술하고자 한다.

[오프-라인 처리]

분산 인증서버인 부재들 사이에서 미리 분산되어진 정보는 모든 장치에 대한 비밀키에 관련된 정보이다. 그러나, 분산 비밀키 암호화/복호화 프로토콜에서 설명된 바와 같이, 증명자와 분산인증 서버간에서 사용된 비밀키는 메시지의 암호화 또는 복호화가 완료된 후에 배치되어야 한다. 따라서, 많은 키가 발생되어야 한다. 이러한 처리는 다음의 비밀 키 전달 처리로 행해진다. 증명자와 인증자 사이에서 대화키로서 사용되는 분산 의사 난수 생성 처리 또한 오프-라인 처리중에 다음과 같이 행해진다.

[비밀 키 전달 처리]

인증을 요청하는 통신 시스템의 장치 j는 미리 비밀 분산 처리를 행하여 부재들간에서 임의로 선택된 충분히 많은 수 M인 의사 난수 pkJ_1,...., pkj_M을 분산시킨다. 따라서 장치 AS(i)는 의사 난수의 비밀부분 pkj(i), ..., pk_M(i)을 수신한다. 장치 j가 비밀을 정확하게 분산시키지 않으면, 장치 j는 그 자신의 비밀 키 pkj를 이용하여 인증 서비스를 수신하지 못한다. 따라서, 분산된 정보가 정확한 지의 여부를 검증하는 사후 처리가 이 경우에 반드시 행해질 필요는 없다. 또한 모든 부재들이 j가 잘못된 구문을 만들지 않은 것을 검증하는 방송 통신로가 반드시 장치 j와 부재 사이에 제공될 필요는 없다(제27조 참조).

이러한 처리중에, j는 충분히 큰 비밀 키 pkj_i(i=1, ...., M)를 리스트로서 보유하며, 한편 각 부재 h(h=1, ..., k)는 비밀 부분 pkj_i(h)(i=l, ..., M)을 리스트로서 보유한다. 비밀 키가 상술된 바와 같이 단지 한번만 사용되므로, j와 각부재 h는 다음에 사용되는 키의 리스트 상의 위치를 표시하는 인덱스 pkj와 pkj(h)를 보유한다. 장치 j는 새로운 비밀 키가 제공될 수 있으면 새로운 비밀 키를 생성하고, 통신 시스템이 비사용중일 때 키의 비밀을 분산시키고 갱신을 속행한다.

[의사 난수 생성 처리]

제26도에서 도시된 바와 같이, 비밀 키 전달 처리에서와 같이 증명자와 인증자 사이에서 사용된 대화 키인 분산 의사 난수 rl, ..., rQ가 오프-라인 처리중에 생성되어 리스트에 보유된다. 분산 의사 난수 생성의 경우, 분산 의사 난수 생성 프로토콜에서 기술된 바와 같이, 모든 부재들은 의사 난수에 대한 분산 처리를 행할 필요가 있다. 그러나, 모든 부재들이 그 처리를 동시에 행할 필요는 없기 때문에, 처리를 행하지 않고 통신 시스템이 비사용중이 아닐 때 처리를 행하고, 생성된 의사 난수를 다른 부재에 분산시킬 수 있다. 다음에, 각 부재들은 리스트로서, 사용을 위한 위치를 표시하는 인덱스와 함께 분산의사 난수 rl(j), ...., rQ(j)를 보유한다.

[온-라인 처리]

분산 인증 서버로부터 통신 시스템의 클라이언트 P(증명자)가 서버 V(인증자)에 전달하는 인증요소를 얻기 위한 온-라인 인증 프로토콜은 다음의 단계 S1 내지 S4에 의해 수행될 것이다.

(단계 1) 클라이언트 P는 정규 통신로를 통해 AUTH_REQUEST로 표시된 정보 id_P, id_V, s를 포함하는 요청 메시지(101, 제28a도 참조)를 분산인증 서버인 부재로 전달한다. id_P는 클라이언트 P를, id_V는 서버 V를 지정하는 데이터를, s는 임의로 선택된 난수를 나타낸다.

(단계 2) AUTH_REQUEST를 수신한 부재는 다음의 단계(S21 내지 S26, 제28b도 참조)에서의 절차를 수행한다.

(단계 21) 현재 시각을 나타내는 타임 스탬프가 방송되고 공통시간이 확인된다.

(단계 22) 분산 비밀 데이터에 대한 분산 비밀 키 암호와 프로토콜을 사용하는 동안 증명자와 인증자 사이에서 대화 키 ck1, ..., cka로서 사용되는 의사난수 rz, ...., rz+a-1가 pkV_x, ...., pkV_x+a-1을 비밀 암호화 키로서 정의함으로써 암호화된다. 여기서 a는 의사 난수의 개수를, z와 x는 의사 난수 리스트와 비밀키 pk 리스트의 시작을 표시하는 인덱스를 나타낸다. 이 때, z와 x는 z=z+a와 x=x+a로 갱신된다. 암호화로 얻어진 결과는 CT_1, .... CT_a이다.

(단계 23) 공개 데이터에 대한 분산 비밀 키 암호화 프로토콜이 사용되고, 공개 타임 스탬프와 증명자의 식별자인 id_P가 단계(S22)에서 사용된 비밀 키 pk 리스트로부터의 2b 비밀키 pkV_x,..., pkV_x+2b에 의해 암호화 된다. 다음에, 인덱스 x가 x=x+2b+1로 갱신된다. 암호화로 얻어진 결과는 CT-a+1, ..., CT_a+b이다. 이 결과와 단계(S22)에서 얻어진 결과와 함께 가산되어 CT_1,..., CT_a+b가 제공 되는데, 이것은 갱신이 단계(S22)에서 행해지기 전인 인덱스 x에 가산된다.

얻어진 결과는 인증요소로서 정의된다.

(단계 24) 분산 비밀 데이터에 대한 분산 비밀 키 암호화 프로토콜이 사용되며, 단계(S23)에서 얻어진 인증자에 대한 암호화문 CT_1,...., CT_a+b와 단계(S22)에서 사용된 공동 키 ck1, ...., cka가 2a+b 비밀 키 pkP_k,..., pkP_y+2a+를 암호화 키로서 사용함으로써 암호화 된다. 여기서 y는 증명자에 대한 비밀 키 리스트의 시작을 표시하는 인덱스를 나타내며, y=y+2a+b+1로 갱신되어짐에 주목해야 한다. 이와 같이 암호화된 결과가 CCT_1, ..., CCT_2a+b이다.

(단계 25) 공개 데이터에 대한 분산 비밀 키 암호화 프로토콜이 사용되고, 단계(S1)에서 공개되어진 의사 난수 s와 인증자의 식별자인 id_V는 단계(S24)에서 사용된 비밀 키 리스트로부터의 2c 비밀 키 pkP_y,...., pkP_y+2c에 의해 암호화 된다. 인덱스 y는 y=y+2c+1로 갱신된다. 이와 같이 암호화된 결과가 CCT_2a+b+1,..., CCT_2a+b+c이다. 이들 결과가 단계(S24)에서의 결과에 가산되어 최종 결과는 CCT_1, ... CCT_2a+b+c이다.

(단계 26) 비밀 복원 처리는 비밀리에 분산된 CCT_1,...., CCT_2a+b+c를 복원하기 위한 것이다. 복원으로 얻어진 결과가 단계(S24)에서 갱신되기 전인 인덱스 y와 함께 정규 통신로를 통해 인증 메시지(102) 로서 증명자인 클라이언트 P로 전달된다.

(단계 3) 증명자 P는 수신된 인덱스 Y와 그 비밀 키 리스트 내에 포함된 비밀키 pkP_y, ..., pkP_y+2a;b;2c를 참조하며 공개 데이터에 대한 분산 비밀 키 복원 프로토콜을 사용하여 수신된 데이터 CCT_1, ..., CCT_2as+b+c로부터의 의사 난수 ck를 복원한다. 다음에, 증명자 P는 복원된 s와 id_V가 올바른지를 확인한다.

이들이 확인되면, 복원된 의사 난수 ck는 인증자에 대한 공통키로서 기억되어 복원된 인증요소(103)를 인증자 V로 전달시킨다(제29a도 참조).

(단계 4) 인증 요소에 포함된 인덱스 x와, 그 비밀 키 리스트에 포함된 비밀 키 pkV_y, ..., pkV_y+a;2b를 참조함으로써, 인증자 V는 공개 데이터에 대한 분산 비밀 키 복원 프로토콜을 사용하여 수신된 인증요소로부터 타임 스탬프 및 증명자의 식별자 id_P를 복원하고, 분산 비밀 데이터에 대한 분산 비밀 키 복원 프로토콜을 사용하여 의사 난수 ck를 복원시킨다. 다음에 인증자는 복원된 타임 스탬프와 복원된 식별자 id_P가 올바르다는 것을 확인한다. 이들이 확인될 때, 증명자 P에 인증이 제공되며, 복원돼 의사 난수 ck가 인증자에 대한 공통키로서 기억된다(제29b도 참조).

[실시예 7]

실시예 6에서 위반 행위자는 증명자가 인증자로 전달하는 인증요소에 대한 도청을 행하여 그 인증요소를 기억하면, 위반행위자는 인증자에 인증요소를 제출하여 증명자가 의도하지 않은 서비스를 위해 인증자를 요청할 수 있다. 따라서, 증명자는 혼동되어진다. 이러한 행위를 리플레이 어텍(replay attack)이라 칭한다.

따라서, 이 실시예에서는 리플레이 어택을 방지시키기 위해, 교환되는 시간 정보를 실시예 6에서 온-라인 처리의 단계(S3)에서 증명자가 인증자로 전달하는 인증요소에 추가로 제공한다. 이들 처리과정을 제30a 및 30b도에서 도시하고 있다.

이 실시예에서의 처리는, 단계(S3' 및 S4')에서의 처리가 온-라인 처리의 단계(S3 및 S4)에서의 처리에 부가되어 행해지는 것을 제외하고는 실시예 6에서와 동일하다.

(단계 S3') 실시예 6의 단계(S3) 에서의 처리가 행해진 후, 증명자는 얻어진 대화 키 ck를 사용하여 증명자의 새로운 타임 스탬프 T2와 식별자 id_P를 암호화시켜 {T2, id_P}^ck를 얻는다. 증명자는 인증자에 {T2, id_P}^ck와 인증요소를 전달한다.

(단계 S4') 인증자는 실시예 6의 단계(S4)에서의 처리를 이용하여 인증요소를 복원시키고, 얻어진 대화 키 ck를 사용하여 부속 메시지 {T2, id_P}^ck를 복원시킨다. 다음에 인증자는 증명자의 타임 스탬프 T2와 식별자 id_P를 확인하여, T2가 이전값일 때는 서비스 요청을 받아들이지 않는다.

상술한 바와 같이, 이 실시예에 의하면 종래의 집중화된 관리 인증 서버보다 신뢰성이 높고 안정이 높은 인증서버를 제공할 수 있다.

분산 인증서버인 장치들 대다수가 신뢰성을 가질 때, 다음의 것을 제공할 수 있다.

분산 인증 프로토콜에 의해, 종래의 집중화된 관리로 제공된 인증 프로토콜의 것과 동일한 인증 함수가 증명자와 인증자에 제공되어 높은 폴트 톨러런스를 실현할 수 있다.

분산 인증 프로토콜의 온-라인 처리는 증명자와 인증자에 대해 종래 인증 포로토콜과 동일한 인터페이스(데이타 포맷)를 보증하므로, 종래의 인증서버를 이 실시예의 인증서버로 용이하게 대체시킬 수 있다.

증명자와 인증자에 대해서, 분산 인증 프로토콜의 온-라인 처리는 종래의 인증 프로토콜에서 필요한 계산량과 동일한 계산량을 갖을 수 있다.

비록 본 발명이 상기 실시예들에 대해서만 기술 및 도시되어 졌더라도, 본 발명의 사상 및 범주를 벗어나지 않는 한 여러 변형 실시예가 가능하다. 따라서, 본 발명은 상술된 실시예에만 한정되지 않고, 첨부된 청구범위가 모든 변형 실시예를 포함한다는 것은 말할 필요도 없다.

Claims (31)

1. 다수의 정보 처리 장치가 임의의 나머지 장치들의 정보 비밀을 유지하면서 장치들 중 다른 것과 정보를 교환하는 비밀 통신로 및 장치들은 다른 모든 포함된 장치들과 정보를 공통으로 교환하는 방송 통신로에 의해 접속되는 비밀 정보 처리 방법에 있어서, 상기 다수의 장치 중 한 구성원이고 상기 비밀 정보를 갖는 제1 장치를 이용하여 다수의 제2 장치를 위한 비밀 배열을 비밀 정보로부터 발생하는 단계, 상기 제1장치를 이용하여 상기 제2 장치를 위한 상기 비밀 배열로부터 제1 정보 세그멘트를 추출하고, 상기 제1 정보 세그멘트를 상기 제2 통신로를 통해 제2 장치로 전송하는단계. 상기 제1 장치를 이용하여 상기 비밀 배열의 한 부분에 대한 소정의 함수를 수행하고, 얻어진 출력값을 상기 방송 통신로를 통해 방송하는 단계, 상기 제2 장치를 사용하여 난수를 발생하고, 상기 방송 통신로를 통해 상기 난수를 방송하는 단계, 비밀 배열로부터 그리고 방송된 난수에 따라 상기 제1 장치를 이용하여 상기 제2 장치를 위한 제 2정보 세그멘트를 발생하고, 상기 방송 통신로를 통해 상기 제2 정보 세그멘트를 방송하는 단계, 상기 제2 장치를 이용하여, 수신된 제1 정보 세그멘트와 상기 제2 장치에 의해 발생된 난수와 일치하는 상기 제1 장치를 이용하여 상기 제2 장치를 위한 제2 정보 세그멘트로서 발생되는 제3 정보 세그멘트를 발생하는 단계, 및 상기 제2 장치를 이용하여, 상기 제3 정보 세그멘트와 방송된 상기 제2 장치를 위한 상기 제2 정보 세그멘트를 비교하여, 상기 제1 장치에 의해 분산된 상기 비밀 정보를 비교하는 단계를 포함하는 것을 특징으로 하는 비밀 정보 처리 방법.
2. 제1항에 있어서, 확인을 위한 상기 단계에서 상기 비교 결과가 일치하지 않는 경우에 상기 제2 장치들은 상기 방송용 통신로를 통해 메시지를 방송하고 방송된 상기 메시지의 합을 기초로해서 확인을 수행하는 것을 특징으로 하는 비밀 정보 처리 방법.
3. 제1항에 있어서, 상기 제2 장치들로 전송되는 상기 제1 정보 세그먼트를 기초로 해서 상기 모든 제2 장치들로 상기 비밀 정보를 복원하는 복원 단계를 부가로 포함하는 것을 특징으로 하는 비밀 정보 처리 방법.
4. 제3항에 있어서, 상기 복원 단계에서 상기 제2 장치들은 개별적으로 상기 수신된 제1 정보를 기초로 해서 계산(cumputation)을 수행하고 이 계산 결과를 기초로 해서 복원을 수행하는 것을 특징으로 하는 비밀 정보 처리 방법.
5. 제1항에 있어서, 상기 비밀 배열은 상기 비밀 정보와 임의로 선택된 비밀 요소에 대해 결정되고, 상기 행렬의 행 백터와 열 백터는 상기 제1 정보 세그먼트로서 규정되는 것을 특징으로 하는 비밀 정보 처리 방법.
6. 제 1항에 있어서, 상기 소정의 함수는 일방향성 함수인 것을 특징으로 하는 비밀 정보 처리 방법.
7. 제 1항에 있어서, 상기 비밀 정보는 유일한 집합내의 요소이고, 상기 발생 단계에서 상기 요소의 계산이 유한 집합에서 수행되는 것을 특징으로 하는 비밀 정보 처리 방법.
8. 다수의 장치는 임의의 나머지 장치의정보 비밀을 유지하면서 다른 장치와 정보를 교환하는 비밀 통신로와, 장치 각각이 모든 다른 장치와 정보를 공통으로 교환하는 방송 통신로에 의해 접속되는 통신 시스템용 서명 생성 방법에 있어서, 서명자의 그룹에 속하는 상기 장치 각각을 이용하여 제1 비밀 정보를 무작위로 선택하고, 상기 그룹내의 상기 장치와 제1 비밀 정보를 비밀로 분산하는 단계, 상기 장치들을 이용하여 상기 제1 비밀 정보에 대해 선정된 제1 함수를 수행하고 얻어진 출력값을 상기 그룹내의 상기 장치들 모두로 방송하는 단계, 상기 그룹내의 상기 장치들중의 상기 장치들 각각으로부터의 상기 제1 비밀정보를 분산하고, 상기 제1 비밀 정보를 가산하는 단계, 승산을 위해 상기 그룹내의 상기 장치들 중에 출력 값을 분산하고 승산과 메시지에 의해 얻어진 결과에 대해 선정된 제2 함수를 수행하는 단계, 상기 그룹내의 상기 장치들 중에 상기 제2 비밀 정보를 분산하고 상기 제2 함수를 수행함으로써 얻어진 결과, 분산과 가산에 의해 얻어진 결과, 및 공개되는 요소를 이용함으로써 제2 비밀 정보를 계산하는 단계, 및 상기 그룹내의 상기 장치들과 관련한 상호 동작을 시도를 통하여, 분산된 제2 비밀 정보를 복원하고 분산과 승산에 의해 얻어진 결과를 함께 서명으로 복원된 제2 비밀 정보를 출력하는 단계를 포함하는 것을 특징으로 하는 서명 생성 방법.
9. 제8항에 있어서, 상기 계산 단계에서 상기 제2 비밀 정보에 대한 선형 결합 처리가 수행되는 것을 특징으로 하는 서명 생성 방법.
10. 제 8항에 있어서, 상기 계산 단계에서 상기 제2 비밀 정보에 대한 지수 승산을 포함하는 곱을 사용하여 결합 처리가 수행되는 것을 특징으로 하는 서명 생성 방법.
11. 제8항에 있어서, 상기 계산 단계에서 상기 제2 정보의 선형 결합 처리와 승산이 수행되는 것을 특징으로 하는 서명 생성 방법.
12. 제8항에 있어서, 상기 제2 함수는 일방향성 함수인 것을 특징으로 하는 서명 생성 방법.
13. 제 8 항에 있어서, 상기 제 1 비밀 정보는 유한 집합 내의 요소이고, 상기 유한 집합에서의 가산은 상기 가산 단계에서 수행되는 것을 특징으로 하는 서명 생성 방법.
14. 제8항에 있어서, 상기 제1 비밀 정보를 분산하는 상기 단계는, 상기 서명자 그룹에 속하고 상기 제1 비밀 정보를 점유하는 제1 장치를 사용하므로써 다수의 제2 장치에 대한 비밀 배열을 상기 제1 비밀 정부로부터 생성하는 단계; 상기 제1 장치를 사용하므로써 상기 제2 장치에 대한 상기 비밀 배열로부터 제1 정보 세그먼트를 추출하고, 상기 제1 정보 세그먼트를 상기 비밀 통신로를 통해 상기 제2 장치들로 전송하는단계; 상기 제1 장치를 사용하므로써 사기 비밀 배열의 부분 상에 소정의 함수를 수행하고, 얻어진 출력값을 상기 방송 통신로를 통해 방송하는 단계; 상기 제2 장치를 사용하므로써 난수를 생성하고, 상기 난수를 상기 방송 통신로를 통해 방송하는 단계; 방송된 상기 난수에 따라 상기 제1 장치를 사용하므로써 상기 비밀 배열수부터 상기 제2 장치에 대한 제2 정보 세그먼트를 생성하고, 상기 제2 정보 세그먼트를 상기 방송용 통신로를 통해 방송하는 단계; 수신된 상기 제1 정보 세그먼트와 상기 제2 장치가 생성한 상기 난수에 따라 상기 제1 장치를 사용하므로써 상기 제2 장치에 대한 상기 제2 정보 세그먼트로서 생성된 제3정보 세그먼트를 상기 제2 장치를 사용하므로써 생성하는 단계; 및 상기 제3 정보를 방송된 상기 제2 장치에 대한 상기 제2 정보 세그먼트와 상기 제2 장치를 사용하므로써 비교하고, 상기 비밀 정보가 사기 제1 장치에 의해 분산되는 것을 확인하는 단계를 포함하는 것을 특징으로 하는 서명 생성 방법.
15. 다수의 장치가 접속되고, 지정 그룹에 속하는 것들 중의 장치들은 인증을 공통으로 제공하는 인증 방법에 있어서, 인증자의 장치로부터 인증을 요구하는 증명자의 장치로부터 증명자와 인증자를 위한 식별자를 포함하는 인증 요구 메시지를 상기 특정 그룹의 장치 각각에 전송하는 단계, 상기 특정 그룹에 속하는 장치 모두에 관련한 상호 동작 시도를 이용하여 인증 요구 메시지에 기초한 상기 인증자에 관련된 비밀 키로 암호화함으로써 인증 메시지를 발생하는 단계. 상기 특정 그룹의 상기 장치 각각으로부터의 상기 인증 메시지를 증명자의 상기 장치에 전송하는 단계, 상기 인증 메시지의 수신시 상기 증명자의 장치에서 상기 인증 메시지를 복원하고, 상기 복원된 인증 요소를 상기 인증자의 상기 장치에 전송하는 단계, 및 상기 인증자의 상기 장치에서 상기 인증 요소를 복원하고 인증을 상기 증명자에게 전송하는 단계를 포함하는 것을 특징으로 하는 인증 방법.
16. 제15항에 있어서, 상기 지정 그룹 내의 상기 장치들로부터 증명자 및 인증자의 상기 장치들로 상기 두 장치들 사이에서 암호와 통신을 위해 사용되는 공동키(common key)를 협동적으로 전송하는 단계를 부가로 포함하는 것을 특징으로 하는 인증 방법.
17. 제15항에 있어서, 상기 인증 메시지를 전송하는 단계에서 상기 증명자와 상기 인증자의 상기 장치들 사이에서 암호화 통신용으로 사용되고 상기 인증 메시지에 포함되는 공통 키는 상긴 증명자의 상기 장치로 전송되는 것을 특징으로 하는 인증 방법.
18. 제15항에 있어서, 상기 인증 메시지를 전송하는 단계에서 상긴 증명자와 상기 인증자의 상기 장치들 사이에서 암호화 통신용으로 사용되고 상기 인증 메시지에 포함되는 공통 키는 상기 인증자의 상기 장치로 전송되는 것을 특징으로 하는 인증 방법.
19. 제15항에 있어서, 확인가능한 비밀 분산 처리를 사용하는 단계와, 상기 지정 그룹의 상기 장치들로 상기 증명자 및 상기 인증자의 상기 장치들 사이에서 암호화 통신용으로 사용되는 공통키를 분산된 의사 난수 비밀로서 협동적으로 생성하는 단계를 부가로 포함하는 것을 특징으로 하는 인증 방법.
20. 제15항에 있어서, 상기 생성 단계에서 비밀 키에 의한 암호화는 다수의 블럭으로 암호화 하도록 데이터를 분할하고, 소정의 유한 집합 상에서 상이한 키들을 상기 블럭에 가산하므로써 수행되는 것을 특징으로 하는 인증 방법.
21. 제15항에 있어서, 상기 생성 단계에서 비밀 키에 의한 암호화는 다수의 블럭으로 암호화 하도록 데이터를 분할하고, 소정의 유한 집합 상에서 상이한 비밀 키들을 상기 블럭에 승산하며, 상이한 비밀 키를 이 승산 결과에 더 가산하므로써 수행되는 것을 특징으로 하는 인증 방법.
22. 제15항에 있어서, 통신 시스템의 각 장치와 관련되는 비밀 키를 상기 지정 그룹의 각 장치들을 분산 및 배포하기 위해 비밀 분산 처리를 수행하는 단계를 부가로 포함하는 것을 특징으로 하는 인증 방법.
23. 제15항에 있어서, 상기 생성 단계에서 상기 인증 요소는 상기 증명자와 상기 인증자의 상기 장치들을 위한 공통키를 사용하여 타임 스탬프와 함께 암호화되고 그 결과 전송되며, 상기 인증자의 상기 장치는 상기 공통키를 사용하여 상기 증명자의 상기 장치로부터 수신된 정보를 복원하고 상기 타임 스탬프를 확인하는 것을 특징으로 하는 인증 방법.
24. 다수의 통신 장치, 장치 각각이 임의의 나머지 장치의 정보 비밀을 유지하면서 다른 장치와 비밀로 정보를 교환할 수 있는 비밀 통신로 및 장치 각각이 모든 다른 장치에 정보를 공통으로 전송하는 방송 통신로를 포함하는 통신 시스템에 있어서, 다수의 정보 처리 장치의 제1 정보 처리 장치는, 비밀 정보로부터 선정된 부분 배열을 발생하는 제1 발생수단, 부분 배열로부터 임의의 나머지 정보 처리 장치에 대한 제1 정보 세그먼트를 추출하고 상기 나머지 정보 처리 장치에 상기 제1 정보 세그멘트를 전송하는 추출수단, 상기 제1정 보 세그먼트에 대해 소정의 함수를 수행하고 얻어진 출력 값을 상기 방송 통신로를 통해 나머지 정보 처리 장치에 방송하는 함수 처리 수단, 및 상기 나머지 정보 처리 장치에 의해 방송된 난수와 일치하는 제2 정보 세그멘트를 발생하고, 상기 방송 통신로를 통해 상기 제2 세그멘트를 방송하는 제2 발생 수단을 포함하고, 상기 나머지 정보 처리 장치 각각은 난수를 발생하고 상기 난수를 방송하는 난수 발생수단, 상기 제1 정보 처리 장치에 의해 상기 제2 정보 세그멘트로서 발생될 제3 정보 세그멘트를 상기 제1 정보 세그멘트와 상기 난수와 일치하게 발생하는 제3 발생수단, 및 상기 제3 정보 세그멘트를 방송된 상기 제2 정보 세그멘트와 비교하여, 상기 제1 정보 처리장치에 의해 수행된 비밀의 분산을 확인하는 수단을 포함하는 것을 특징으로 하는 통신 시스템.
25. 제24항에 있어서, 상기 정보 처리 장치들은 상기 비교 결과가 일치하지 않는 경우에 메시지를 상기 방송용 통신로를 통해 방송하는 메시지 방송 수단을 포함하며, 상기 확인 수단은 방송된 상기 전체 메시지를 기초로 해서 확인을 수행하는 것을 특징으로 하는 통신 시스템.
26. 제24항에 있어서, 상기 정보 처리 장치들은 전송된 제1 정보 세그먼트를 기초로 해서 상기 모든 정보 처리 장치들을 사용하여 상기 비밀 정보를 복원하는 복원 수단을 구비하는 것을 특징으로 하는 통신 시스템.
27. 제24항에 있어서, 상기 정보 처리 장치들은 전송된 상기 제1 정보 세그먼트를 기초로 해서 계산을 수행하는 계산 수단을 구비하며, 상기 복원 수단은 상기 계산 결과를 기초로 해서 상기 비밀 정보를 복원하는 것을 특징으로 하는 통신 시스템.
28. 제24항에 있어서, 상기 부분 배열은 상기 비밀 정보와 임의로 선택한 비밀 요소들에 대해 결정되는 부분 행렬이고, 상기 부분 행렬의 행 벡터 및 열 벡터는 대응하는 비밀들에 대한 비밀 부분들이며, 상기 헹 벡터의 요소들은 상기 행 및 열 벡터의 비밀 부분들인 것을 특징으로 하는 통신 시스템.
29. 제24항에 있어서, 상기 소정의 함수는 일방향성 함수인 것을 특징으로 하는 통신 시스템.
30. 제24항에 있어서, 상기 비밀 정보는 유한 집합 상의 요소이며, 상기 생성수단은 상기 유한 집합 상에서 계산을 수행하는 것을 특징으로 하는 통신 시스템.
31. 다수의 정보 처리 장치, 장치 각각이 임의의 나머지 장치의 정보 비밀을 유지하면서 다른 장치들과 비밀로 정보를 교환할 수 있는 비밀 통신로, 및 장치 각각이 다른 모든 장치에 정보를 공통으로 전송하는 방송 통신 통신로를 갖는 통신 시스템에 있어서, 서명자의 그룹에 속하는 다수의 장치 중에서의 장치 각각은 제1 비밀 정보를 무작위로 선택하고 상기 그룹의 상기 장치들중에 상기 제1 비밀 정보를 비밀로 분산하는 분산 수단, 상기 제1 비밀 정보에 대해 선정된 제1 함수를 수행하고 얻어진 값을 상기 그룹의 모든 나머지 장치들로 전송하는 방송 수단, 상기 그룹의 상기 장치들 중의 장치 각각에 의해 보유된 제1 비밀 정보를 분산하고 상기 제1 비밀 정보를 가산하는 가산 수단, 상기 그룹의 상기 장치들 중에서의 장치 각각에 의해 보유된 상기 출력 값을 분산하여 상기 출력 값을 승산하고, 승산과 메시지에 의해 얻어진 결과에 선정된 제2 함수를 수행하는 처리 수단, 승산 결과를 이용하여, 분산과 가산에 의해 얻어진 결과, 및 상기 그룹의 상기 장치들중에 제2 정보를 분산하고, 상기 제2 정보를 계산하기 위해 공개된 요소를 계산하는 계산 수단 및 상기 제2 비밀 정보가 분산되는 상기 그룹의 상기 장치 모두의 결합 시도에 의해 상기 제2 비밀 정보를 복원하고, 분산과 승산에 의해 얻어진 결과와 함께 서명으로서 복원된 제2 비밀 정보를 출력하는 복원 수단을 포함하는 것을 특징으로 하는 통신 시스템.