리스트 서명을 생성하기 위한 방법과 시스템 document_id A220623044150

본 발명은 특히 투표, 여론 조사, 신청의 전자적인 서비스들 또는 익명의 경쟁(anonymous competition)에 적용되나, 이러한 것들만을 대상으로 하는 것은 아니다. 또한 본 발명은 접근(access) 티켓에 의하여 교통 서비스, 영화 서비스 같은 유료 서비스에의 접근을 통제하는 것, 제한된 횟수만큼 사용자들의 접근을 허용하는 것에도 적용된다. 접근 횟수가 제한 값에 도달하자마자, 사용자는 더 이상 자신의 티켓을 이용할 수 없다. 이러한 유형의 응용들에서는, 사용자의 신원(identity)을 알 필요가 없다. 접근하는 동안에 사용자가 접근 권리를 갖고 있다는 것을 증명할 수 있는 것으로 충분하다. 전자 서명은 이른바 비대칭 또는 공개키 암호 방식의 범주에 속하는 메커니즘이다. 이러한 메커니즘에서는, 서명자는 비밀 또는 개인키 및 관련된(associated) 공개키를 갖는다. 사용자는 자신의 비밀키를 이용하여 암호화 알고리즘을 메시지에 적용함으로써 메시지에 대한 서명을 생성한다. 검증기는 대응하는 공개키를 이용하여 동일한 암호화 알고리즘을 적용함으로써 서명을 검증할 수 있다. 그룹 서명의 개념은 이미 제안되었으며, 이것은 그룹의 각 멤버가 서명을 생성하는 것을 가능하게 하여, 그 결과 적당한 공개키를 갖는 검증기가 서명자의 신원을 결정함이 없이 그룹의 멤버에 의해 송신된 서명을 검증할 수 있다. 이러한 개념은 예를 들어 하기의 문서들에 기술된다. [1] Springer-Verlag 출판사의 Advances in Cryptology - CRYPTO 2000(편집자 M. Bellare)에 있어서 LNCS의 Vol.1880에서 p.255-270에 기재된 G. Ateniese, J. Camenisch, M. Joye 및 G. Tsudik의 "A Practical and Provably Secure Coalition-Resistant Group signature Scheme" [2] Springer-Verlag 출판사의 Advances in Cryptology - EUROCRYPTO 97(편집자 B. Kaliski)에 있어서 LNCS의 Vol.1294에서 p.410-424에 기재된 J. Camenisch 및 M. Stadler의 "Efficient Grouop signature Scheme for Large Groups" 그룹 서명 개념의 기초에 있어서, 일반적인 원리는 그룹의 각 멤버에 대하여 공통되는 어려운 문제에 대한 특별한 해결책과 관련되어 있으며, 그/그녀가 등록한 때에, 이러한 해결책이 그룹의 새로운 각 멤버에게 권한을 부여받은 인증 기관에 의해 제공된다. 그/그녀가 등록하는 동안에, 멤버는 그/그녀에 대해 특유한 서명 개인키를 계산하며, 이러한 어려운 문제에 대해 그/그녀 자신의 해결책을 획득하기 위하여 인증 기관과 상호 작용을 한다. 멤버와 인증 기관은 또한 멤버 인증서를 계산하며, 이러한 멤버 인증서는 멤버의 개인키와 가능하게는 멤버에게 알려진 문제의 해결책과 강하게 관계가 있다. 그룹 대신에 메시지에 서명하기 위하여, 멤버는 인증 기관의 공개 암호화 키를 이용하여 그/그녀의 인증서를 암호화하고, 그/그녀가 그룹 멤버의 개인키, 어려운 문제에 대한 해결책 및 암호화된 텍스트 내에 포함된 평범한 텍스트와 관련된(그룹에 속한다는 증거) 멤버 인증서를 알고 있다는 것을 증명한다. 여기서 기초는 암호 작성법이고, 특히 그룹 서명들에 대해 요구되는 성질들을 획득하기 위한 지식에 대한 증거(evidence of knowledge)이다. 그룹 서명의 검증은 지식의 증거를 검증하는 것으로 구성되고, 한편 서명을 공개(open)하는 것은 인증서를 복호화하는 것으로 구성된다. 그러나, 이러한 그룹 서명 개념에서는, 인증 기관은 언제라도 서명의 익명성을 해제(lift)시킬 수 있다. 즉, 서명을 송신한 그룹에 속하는 개인의 신원을 결정할 수 있다. 나아가, 이러한 유형의 서명은 "넌 링커블(non-linkable)"이라고 한다. 즉, 서명의 익명성을 해제함이 없이 두 개의 서명이 동일한 개인에 의하여 송신되었는지 여부를 결정하는 것이 불가능하다. 그러므로 그룹 서명은 전자 투표에 대하여 매우 적합한 것은 아니다. 리스트의 멤버들이 서명을 생성하는 것을 가능하게 하여 멤버의 신원을 결정 가능함이 없이 검증기가 서명이 리스트의 멤버에 의해 생성되었는가를 인식할 수 있는 리스트 전자 서명들이라 불리는 것이 또한 존재한다. 예를 들어, 본 출원인에 의해 제출된 프랑스 특허 출원 2 842 680에서 기술된 리스트 서명 개념에 따르면, 시간은 미리 정의된 유효한 기간을 갖는 시퀀스 표본(sequence representative)에 의해 표시되는 시퀀스들로 분할된다. 시퀀스 동안에, 리스트의 각 멤버는 서명들을 생성할 권한을 부여받으며, 검증기는 이러한 서명들로부터 서명자의 신원에 접근 가능함이 없이, 두 개의 서명이 리스트의 동일한 멤버에 의해 송신되었는지 여부를 결정할 수 있다. 따라서, 서명자의 신원을 결정 가능함이 없이, 동일한 시퀀스 동안에 리스트의 멤버가 두 개의 서명들을 생성한 경우를 검출할 수 있다. 따라서 리스트 서명은 전자 투표 또는 전자 여론조사에 매우 적합하다. 왜냐하면 각 유권자는 그/그녀의 투표에 대하여 리스트 서명을 생성할 수 있고, 이 리스트 서명은 그/그녀의 익명성을 보장하는 한편 동일한 소정의 선거(시퀀스) 동안에 동일한 개인에 의해 송신된 투표들이 검출될 수 있기 때문이다. 또한, 리스트 서명은 교통 티켓들 또는 영화 티켓들 같은 접근 티켓들(access tickets)에 대해서도 매우 적합하다. 왜냐하면 그/그녀가 접근할 자격이 주어져 접근할 때마다, 사용자는 리스트 서명을 생성할 수 있고, 이 리스트 서명은 그/그녀의 익명성을 보장하는 한편, 지불된 총액에 상응하는 특정 횟수만큼 그/그녀에게 서비스에 접근할 권한을 주기 위해, 소정의 시퀀스 동안에 이미 송신된 서명들의 개수가 결정될 수 있다. 그러나, 어떤 리스트 서명들은 "공개가능(openable)"이라고 한다. 즉, 인증 기관이 서명으로부터 서명자의 신원을 결정할 수 있다. 더욱 구체적으로, 리스트에 그/그녀의 등록을 하는 동안에, 리스트의 각 멤버는 개인키를 계산하고 인증 기관으로부터 리스트의 멤버 인증서 뿐만 아니라 어려운 문제에 대한 해결책을 획득한다. 리스트 서명 개념은 익명성이 해제되는 것을 허용하지 않는다. 즉, 서명의 생성에 관해 어떠한 암호화도 포함하지 않는다. 소정의 시퀀스의 개시시에, 인증 기관은 시퀀스가 지속되는 동안 배타적으로 유효한 시퀀스 표본을 생성한다. 서명을 생성하는 때에, 그룹 서명에서와 마찬가지로, 리스트의 멤버는 그/그녀가 개인키, 어려운 문제에 대한 해결책 및 리스트 멤버의 인증서를 알고 있다는 증거를 제공한다. 그/그녀는 또한 시퀀스 표본에 대한 멱을 계산하며, 여기에서 지수는 개인키가 된다. 소정의 시퀀스에 대하여, 리스트의 동일 멤버에 의해 생성되는 두 개의 서명들을 연결시키는 것이 가능하며, 이는 시퀀스의 표본과 개인키는 이 시퀀스에 대하여 설정되기 때문이다. 그러므로, 동일 시퀀스 동안 리스트의 멤버들 각각에 의해 송신된 서명들의 개수가 카운트될 수 있다. 이러한 유형의 개념들 모두의 주요한 단점은 상당한 계산들을 필요로 한다는 사실에 기인한다. 실제로, 생성된 서명 각각에 대하여, 실제로 많은 모듈러 멱승을 사용하고, 계산 시간에 있어서, 특히 난수들(random numbers)을 생성하는데, 많은 희생이 따르는 지식의 증거의 단편들을 생성하는 것이 필요하다. 즉, 암호 프로세서를 갖춘 칩카드는 모듈러 멱승마다 약 1초가 걸린다. 계산 시간의 희생 문제에 대한 해결책은 본 출원인에 의해 출원된 프랑스 특허 출원 2 834 403에서 그룹 서명들에 대하여 제안되었다. 칩카드(암호 프로세서)의 사용으로 구성된 이 해결책은 그룹 서명들의 단점을 갖는다. 즉, 서명의 익명성을 해제함이 없이 소정의 멤버에 의해 송신된 서명들을 연결시키는 것이 불가능하다.