Advanced
Broadcast Encryption System Using Secret Sharing and Subset Difference Methods
Broadcast Encryption System Using Secret Sharing and Subset Difference Methods
Journal of Broadcast Engineering. 2015. Jan, 20(1): 92-109
Copyright © 2015, The Korean Society of Broadcast Engineers
  • Received : July 28, 2014
  • Accepted : December 01, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
재환 이
종환 박
jhpark@smu.ac.kr

Abstract
브로드캐스트 암호시스템은 한명의 송신자가 다수의 수신자에게 메시지를 암호화하여 안전하게 전송하는 기법이다. 2001년 Naor, Naor, Lotspiech가 유사난수생성기와 Subset Difference(SD) 방식을 이용하여 제안한 브로드캐스트 암호시스템이 가장 효율적인 기법으로 알려지고 있다. 본 논문에서는 비밀분산(secret sharing) 기법과 SD 방식을 이용하여 새로운 브로드캐스트 암호시스템을 제안한다. 새로운 기법은 효율성 측면에서 전체 사용자 수 n 명, 탈퇴자 수 r 명에 대해 O ( r ) 전송량, O (log 2 n ) 비밀키 저장량, O (1) 복호화 연산량을 제공한다. 기존 SD 기법이 복호화 시 O (log n )의 유사난수생성기 계산이 필요한데 비해, 새로운 기법은 복호화 계산량이 n r 에 관계없다는 장점을 갖는다. 안전성 측면에서는 증명과정에서 나타나는 안전성 손실(security loss)을 비교할 때, 새로운 기법이 기존 SD 기법에 비해 약 O ( n log n )정도 안전성 손실이 더 적다는 장점도 갖는다. 또한 이론적으로 본 논문의 결과는 Complete Subtree 방식처럼 정보 이론적으로 안전한 키 분배방식을 이용하면서도 SD 방식의 효과를 내는 것이 가능하다는 것을 보인다.
Keywords
Ⅰ. 서 론
브로드캐스트 암호시스템 [1] 은 한 명의 송신자가 정당한 수신자 집합 S 에게 메시지를 암호화하여 전송하는 방법이다. 메시지를 받은 수신자 u u S 인 경우에만 메시지를 복호화할 수 있고, u S 인 경우는 메시지에 대한 어떠한 정보도 얻을 수 없다. 이러한 성질은 정당한 권한이 있는 수신자 집합을 S 로 한정함으로써 해당 사용자들만이 메시지에 접근할 수 있는 일종의 접근권한을 부여하는 것으로 볼 수 있다. 실제 브로드캐스트 암호시스템은 접근권한 관리가 필요한 위성 TV, pay-per-view TV, DRM(Digital Right Management) 등에 사용될 수 있는데, 먼저 요금을 지불한 사용자에게 비밀키를 부여하여 콘텐츠에 접근할 권리를 주고 일정 시간이 경과하여 권리가 소멸되면 브로드캐스트 암호시스템의 배제(revocation) 기능을 이용하여 권리가 소멸된 이후의 콘텐츠에 대해서는 접근하지 못하도록 하는 것이다.
이러한 브로드캐스트 암호시스템의 안전성은 S 에 속하지 않은 사용자들의 공모공격(collusion attack)에 안전하도록 설계되어야 한다. 즉 전체 사용자 중 S 에 속하지 않은 사용자들이 자신들의 비밀키를 서로 공유하여 권한이 없는 콘텐츠를 복호화하려는 공격에도 안전해야 한다. 종종 시스템 설계 시 공모자의 수가 t 명으로 한정되는 경우가 있는데, 이 경우는 t 명보다 많은 공모자들이 공격하면 시스템의 안전성이 깨진다는 단점이 있다. 당연히 공모자의 수에 제한이 없는 기법이 바람직하다. 또한 브로드캐스트 암호시스템은 과거 전송기록에 대한 정보를 저장할 필요가 없는 비상태(stateless) 기반의 기법이 바람직하다. 이는 탈퇴자가 발생하여 전송기록이 바뀌더라도 사용자는 초기에 주어 진 비밀키를 이용하여 복호화를 수행할 수 있는 환경에 적합하다. 브로드캐스트 암호시스템의 효율성은 암호문의 전송량, 수신자의 비밀키 저장량, 그리고 복호화를 위한 수신자의 계산량 측면에서 분석된다. 대부분의 브로드캐스트 암호시스템은 세 가지 효율성 요소 간에 trade-off 기능을 제공하는데, 대표적으로 전송량을 줄이면 계산량 또는 저장량이 증가하는 경향을 보인다. 또한 브로드캐스트 암호시스템은 지정된 송신자만이 암호문을 전송하는 대칭키 방식 [2] 과 시스템 상의 누구나 공개키를 이용하여 송신자가 될 수 있는 공개키 방식 [3] [4] 이 있다.
현재까지 제안된 브로드캐스트 암호시스템 중 가장 효율적인 것은 2001년 Naor, Naor, Lotspiech [2] 가 제안한 SD(Subset Difference) 기법이다. SD 기법은 비상태 기반으로 공모자의 수에 제한이 없는 대칭키 방식의 브로드캐스트 암호시스템이다. 기법 설계의 핵심 아이디어는 전체 사용자를 이진트리의 leaf 노드에 배치하고 수신자 집합 S 가 결정될 때마다, S 를 부분집합들로 분할하는 것이다. 전체 사용자 수를 n 이라 하고 배제된 사용자 수를 r 이라 할 때, SD 기법은 공모자의 수에 제한이 없는 대칭키 방식으로 O ( r ) 전송량, O (log 2 n ) 저장량, 그리고 O (log n ) 연산량을 갖는다. SD 기법은 각 사용자별 비밀키와 부분집합별 그룹키를 생성하기 위해 유사난수생성기(PRG: Pseudorandom generator)의 일방향성을 이용하여 키를 분배하는 것이 핵심이다. 이후 PRG 기반의 SD 기법(이하에서는 SDPRG 기법으로 표기함)은 후속연구에 영향을 주어 다양한 변형 기법들 [5] [6] [7] 이 제안되었다. 특히 최근 연구 [7] 에서는 이진트리를 k 진트리로 확장하여 PRG 기반의 SD 기법을 일반화하는 방법을 소개하면서, k 값에 따른 전송량과 저장량과의 관계를 제시하였다. 그 결과 전송량 측면에서는 k 값에 관계없이 (worst case로서) SDPRG 기법과 동일하다는 것과, 평균적인 경우에는 비밀키 저장량을 증가시켜서 전송량을(average case로서) 어느 정도로 줄일 수 있는지를 구체적인 수식으로 제시하였다. 그러나 최악의 경우(worst case)에는 여전히 SDPRG 기법이 가장 우수한 성능을 보임을 보였다.
본 논문에서는 PRG와 다르게 새로운 키 생성방식을 이용한 SD 기법을 제안한다. 새롭게 제안된 방식 역시 SD기법과 같이 비상태 기반으로 공모자의 수에 제한이 없는 대칭키 기반의 기법이다. 새로운 방식은 키 생성을 위해 이진트리 위에서 Shamir의 (2, n )-비밀분산(Secret Sharing)을 이용하는 것이다. (2, n )-SS는 Zp 상에서 선택된 1차 다항식 f ( x ) = ax + b 를 이용하여 n 개의 share들을 f ( i 1 ),..., f ( in ) 계산한 후, n 개 중 최소 2개의 share가 모이면 상수항 b 를 복구할 수 있는 방법이다. 핵심 아이디어를 간단히 설명하면, n 명의 사용자들에게는 함수값 f ( ij ) 를 각자의 비밀키로 준다. 이후 사용자 ik 가 탈퇴된 경우, 전체 사용자들에게 f ( ik ) 값을 전송하면 ik 가 아닌 사용자들은 f ( ik )와 자신의 비밀키 f ( ij )을 이용하여 상수항 b 를 복구할 수 있다. 그러나 탈퇴자 ik 는 결국 share가 한 개이므로 상수항을 복구할 수 없게 된다. 이 아이디어를 이진트리의 계층별 노드에 적용하여 SD 기법의 효과를 낼 수 있다. 1) 여기서 상수항 b 는 메시지 암호를 위한 그룹키로 사용하게 된다.
SS를 이용한 SD 기법(이하에서는 SDSS 기법으로 표기함)은 효율성 측면에서 O ( r ) 전송량, O (log 2 n ) 저장량, 그리고 O (1) 연산량을 갖는다. 최악의 경우 2) 를 고려하여 SDPRG 기법과 비교하면, 먼저 복호화 계산량 측면에서는 SDSS 기법이 전체 사용자 수 n 이나 배제된 사용자 수 r 에 관계없이 항상 일정하다는 장점을 갖는다. 구체적으로는 SDPRG 기법이 최대 log n 번의 PRG 계산이 필요한 데 비해, SDSS 기법은 Zp 상에서 두 개의 함수값에 대해 Lagrange 보간법을 이용한 상수항을 계산하므로 매우 효율적이다. 반면 전송량 측면에서는 각 부분집합별로 암호문 이외에 해당 부분집합에 대응하는 함수값을 추가로 전송해야 하므로 실제 전송량이 SDPRG 기법에 비해 길어진다는 단점이 있다. 구체적으로는 (이후에 설명하는 안전성 손실을 고려하지 않는 경우에는) SDSS 기법이 약 1.7배 더 긴 전송량을 갖는다.
그러나 SDSS 기법의 안전성을 증명하기 위해서는 기존보다 약화된 안전성 모델을 필요로 한다. SDPRG 기법이 증명되는 안전성 모델에서는, 전체 사용자 집합 N 에서 비밀키가 노출된 탈퇴자 집합 R 을 시스템에서 지속적으로 배제하면서도, 각 메시지를 전송할 때 수신자 집합 S N R 에 포함되는 임의의 부분집합으로 설정할 수 있다. 즉 N R 에 포함되면서도 동적으로 메시지에 따른 수신자 집합을 구성하는 것이 가능하다. 그러나 SDSS 기법이 증명되는 안전성 모델에서는, 전체 사용자 집합 N 에서 탈퇴자 집합 R 을 시스템에서 지속적으로 배제하면서 그와 동시에 수신자 집합 S N R 으로 결정되는 것이다. 즉 약화된 안전성 모델에서는 한번 배제된 사용자는 그대로 탈퇴자가 되며, 이후의 수신자 집합에 포함되지 않는다는 것이다. 두 모델간의 차이를 그림으로 표현하면 [ 그림 1 ]과 같다. 본 논문에서는 약한 모델을 기본으로 고려하면서, 대부분의 브로드캐스트 응용환경에서 충분하다고 간주되는 CCA1(Chosen-ciphertext and launch-time attack) 공격 모델(이를 weak CCA1이라 명명할 것임)에서 SDSS 기법의 안전성을 증명할 것이다.
PPT Slide
Lager Image
안정성 모델의 비교 Fig. 1. User sets defined in two compared security models
약화된 모델이라 하더라도 실제 응용환경에서는 충분히 적용 가능하다. 예를 들어 위성 TV의 경우, 수신 권한을 부여한 후 일정 시간이 지나서 기간이 만료되면 탈퇴자(=배제자)로 처리된다. 이후 다시 가입을 할 경우에는 이전에 발급한 비밀키를 재사용할 수 없고 새로운 비밀키를 발급해야 한다. 이것은 (전체 사용자 수 n을 크게 설정함으로써) N R 에 속하지만 아직 사용되지 않은 비밀키를 발급함으로써 해결할 수 있다. 이 경우 가입자의 기간 만료 시점을 이용하여 이진트리의 leaf 노드들을 관리할 수 있다. 즉 예상되는 시점의 탈퇴자들을 이진트리의 지정된 부분으로 집중시켜서 관리하게 되면, 실제 전송량을 줄이는 데 상당한 효과를 볼 수 있게 된다. 기존 모델을 사용하게 되면, 재가입 시 탈퇴자가 아닌 경우, 기존에 발급된 키를 재사용할 수 있는 장점이 있다. 그러나 그 경우 배제자들이 이진트리의 일정 부분에 집중되지 않고 분산되므로 SD 기법 상 부분집합으로 분할하는 것이 더 복잡해진다. 결국 이는 실제 전송량의 증가로 이어질 수 있다.
또한 안전성 증명 과정에서 SDPRG 기법이 O ( mw 2 )의 안전성 손실(security loss)이 발생한다. 여기서 m 은 Subset Cover를 구성하는 부분집합의 최대 개수이고, w 는 전체 이진트리에서 생성될 수 있는 부분집합의 최대 개수이다. 반면 SDSS 기법은 O ( mw )의 안전성 손실이 발생되어 SDPRG 기법보다 약 O ( w )의 안전성 손실이 덜 발생한다는 장점을 가진다. 이는 전체 사용자 수 n 명에 대해 w 의 개수는 약 O ( n log n )이므로, 예를 들어 n = 2 25 인 경우 SDPRG 기법은 O ( n log n ) ≈ 2 30 에 의해 약 30bits의 안전성 손실이 더 발생한다. 그러므로 SDSS 기법이 n = 2 25 을 다루면서 128bits의 안전성을 갖도록 설계할 경우, SDPRG 기법이 동일한 안전성을 가지려면 30bits의 안전성 손실을 만회하기 위해 약 158bits의 안전성을 갖도록 설계해야 함을 의미한다. 이는 실제 전송량, 저장량, 연산량 측면에서 SDPRG 기법에는 불리하고 SDSS 기법에는 유리한 영향을 미칠 것이다. Table 1 는 지금까지 간략히 설명한 효율성과 안전성 측면에서 SDPRG SDSS 기법의 비교를 보여준다.
기존SDPRG기법과 새로운SDSS기법의 비교Table 1. Comparison between the previousSDPRGscheme and our newSDSSscheme
PPT Slide
Lager Image
m : Subset Cover를 구성하는 부분집합의 최대 개수. w : 전체 이진트리에서 생성될 수 있는 부분집합의 최대 개수.
암호 이론적으로는 SDPRG 기법이 비밀키와 그룹키를 분배하는데 계산적으로 안전한(computationally secure) PRG를 이용하는 것에 비해, SDSS 기법은 정보 이론적으로 안전한(information-theoretically secure) 비밀분산 방식을 이용하는 것이 차이점이다. 이 차이로 인해 안전성 증명과정에서 나타나는 security loss에도 차이가 발생한다. 이전에 제시된 기법 중 암호 이론적으로 안전한 키 분배를 이용한 것은 Naor, Naor, Lotspiech [2] 가 제안한 CS(Complete Subtree) 기법이 있다. CS 기법은 전체 사용자 수를 n , 배제된 사용자 수를 r 이라 할 때, O ( r log( n / r )) 전송량, O (log n ) 저장량, 그리고 O (1) 연산량을 갖는다. 당연히 전송량에서 비효율성을 갖는다는 것을 알 수 있다. 따라서 본 논문에서 제시하는 새로운 방법은 암호 이론적으로 안전한 키 분배를 이용하면서도 CS 기법의 전송량 단점을 극복하고, SD 기법과 유사한 효과를 낼 수 있다는 것에서 이론적으로 중요성을 갖는다.
브로드캐스트 암호시스템은 내부 공모자를 추적할 수 있는 traitor tracing [8] [9] [10] 기능까지 제공할 수 있다. traitor tracing 기능이란, 정당한 수신자가 자신의 비밀키를 이용하여 불법으로 복호화할 수 있는 복제기를 만드는 경우, 해당 복제기에 내장된 사용자의 ID 정보를 추적할 수 있는 것이다. 가장 이상적인 시스템은 브로드캐스트 암호시스템으로 탈퇴자를 관리하다가, 불법 복제기가 발견되는 경우 traitor tracing 기능으로 복제기를 만든 사용자 ID를 추적하고 이후의 브로드캐스트에서 탈퇴시키는 것이다. SDPRG 기법은 이진트리의 사용자 집합을 작은 단위로 분할해가는 과정을 통해 traitor tracing 기능을 줄 수 있다. SDSS 기법역시 같은 동작 원리로 traitor tracing 기능을 줄 수 있다는 것은 쉽게 보일 수 있다.
보다 자세한 아이디어 설명은 Ⅲ.1절을 참조.
위에서 언급했듯, 이 경우에는 기존 SDPRG 기법이 가장 우수한 성능을 보인다.
Ⅱ. 브로드캐스트 암호시스템과 안전성 정의
- 1. 브로드캐스트 암호시스템
양의 정수 n 은 전체 사용자 수라고 하고, N 을 전체 사용자 집합이라고 하자. 브로드캐스트 암호시스템에 속한 사용자는 1부터 n 가운데 하나의 수로 특정된다. 이 경우 N = {1,2,..., n }이다. R N 의 부분집합으로서 복호화를 할 수 없는 탈퇴자들의 집합이라 하자. 이 경우 R N 이다. 브로드캐스트 암호의 목표는 전송 메시지 M R 에 속하는 탈퇴자는 복호화할 수 없도록 하고, N R 에 속하는 사용자는 복호화할 수 있도록 하는 것이다. 즉, 약화된 안전성 모델을 고려하여 이하의 서술에서는 탈퇴자=배제자 임을 상기하자.
브로드캐스트 암호시스템은 세 가지 알고리즘 - 초기설정(setup), 암호화(Encryption), 복호화(decryption) - 으로 구성되어 있다.
  • (1) Setup(λ,n): 시스템 파라미터 λ와 전체 사용자 수n을 입력받은 후, 시스템에 속하는 사용자u(u= 1,...,n) 에게 비밀키du를 부여한다.
  • (2) Encryption(R,M): 탈퇴자 집합R과 메시지M을 입력받은 후,R에 한 탈퇴자들이 복호화하지 못하도록 암호문CT를 생성한다. 이 경우CT는R을 포함하는 것으로 본다.
  • (3) Decryption(CT,du): 사용자u는N╲R에 속한다고 하자. 암호문CT와 사용자의 비밀키du를 입력받은 후, 암호문을 복호화하여 메시지M을 출력한다.
- 2. Subset Cover 방식에 기반한 브로드캐스트 암호시스템
Subset Cover 방식은 먼저 전체 사용자 집합 N 에서 탈퇴자 집합 R 을 제외한 집합, 즉 N R 을 서로 겹치지 않은 disjoint 부분집합들의 모임인 S i1 ,..., Sim 으로 분리된다. 즉
PPT Slide
Lager Image
가 된다. 이러한 부분집합을 찾는 알고리즘을 CoverFinding 알고리즘이라 하고, CoverFinding ( R ) = { S i1 ,..., Sim } 으로 표현하자. 각각의 부분집합 Sj 들은 그에 대응하는 그룹키 Lj 가 할당되고, Sj 안의 모든 수신자는 Lj 를 유도해 낼 수 있다. 그리고 메시지를 암호화하기 위한(일회용) 키 K S i1 ,..., Sim 들에 대응하는 그룹키 L i1 ,..., Lim 들로 암호화되고, 전송하고자 하는 메시지는 K 를 이용하여 암호화된다. 보다 구체적으로 설명하면, Subset Cover 방식 하에서는 두 가지 종류의 대칭키 암호시스템이 사용된다.
  • (1)로 메시지M을 메시지 암호키K로 암호화하는 대칭키 암호
  • (2)EL: {0,1}t↦ {0,1}t로 분할된 subset에 대응하는 그룹키L로 메시지 암호키K를 암호화하는 대칭키 암호
이러한 Subset Cover 방식에 기반한 브로드캐스트 암호시스템은 다음의 세 알고리즘으로 설명할 수 있다.
- 2.1 초기설정(Setup)
모든 수신자 u 는 비밀키 du 를 받는다. Si 에 속한 모든 수신자 u 는 자신의 비밀키 du 를 이용하여 Si 에 대응되는 그룹키 Li 를 유도할 수 있다. 여기서 그룹키 Li 는 각각의 그룹 별로 독립적이고 랜덤한 값으로 할당하거나, 유사난수생성기(PRG: Pseudo-random generator)를 이용하여 할당하는 등 비독립적으로 할당할 수도 있다.
- 2.2 암호화(Encryption)
  • (1) 메시지 암호키K를 랜덤하게 선택한다.
  • (2) 주어진탈퇴자집합R에 대해 알고리즘CoverFinding(R)을 수행하여 부분집합들Si1,...Sim를 구하고 각각의 부분집합에 대응하는 그룹키Li1,...,Lim를 구한다.
  • (3) 메시지 암호키K와Li1,...,Lim를 이용하여 메시지M을 다음과 같이 암호화한다.
PPT Slide
Lager Image
- 2.3 복호화(Decryption)
수신자 u 는 다음과 같은 암호문을 수신하면, 자신의 비밀키 du 를 이용하여 복호화 절차를 실행한다.
  • CT= < [i1,i2,...,im,C1,C2,...,Cm],C>
  • (1)u∈Sij가 되는ij를 찾는다.u∈R의 경우에는ij를 찾을 수 없다.
  • (2)du로 부터 대응하는 그룹키Lij을 유도한다.
  • (3)DLij(Cj)로 복호화하여 메시지 암호키K를 얻는다.
  • (4)로 복호화하여 메시지M을 얻는다.
- 3. 브로드캐스트 암호시스템의 안전성
본 논문에서 고려하는 브로드캐스트 암호시스템은 정당한 수신자의 집합 S = N R 에 암호문을 전송하는 경우, 집합 R 에 속하는 탈퇴자들이 자신들의 비밀키를 이용하여 공모공격(collusion attack)을 하는 경우에도 암호문에 대응하는 평문의 내용을 알 수 없어야 한다. 또한 탈퇴자들이 평문에 대응하는 암호문을 수집할 수 있는 능력뿐만 아니라, 암호문에 대응하는 평문을 수집할 수 있는 능력까지 고려할 수 있다. 단, 암호 질의 및 복호 질의에 사용된 탈퇴자 집합은 이후의 공격에서도 계속해서 탈퇴된 자들의 집합에 포함되어야 된다는 조건을 필요로 한다. 이러한 조건은 서론에서 설명한 것처럼, R 에 속한 사용자들은(시스템이 유지되는 한) 계속해서 탈퇴자로 남고, 메시지 전송 시 정당한 수신자 집합은 N R 로 결정되어야 한다는 것이다. 즉 N R 에 속하는 부분집합으로서 수신자 집합 S 를 동적으로 선택하는 것은 고려되지 않는다는 것을 의미한다.
본 논문은 대부분의 응용환경에서 충분히 안전하다고 간주되는 선택 암호문 중간공격(CCA1: Chosen ciphertext and launch-time attack) [2] 과 위에서 언급한 조건을 고려한다. 이를 weak CCA1 이라 하자. 그 weak CCA1 안전성은 공격자 A 와 챌린저 B 사이의 (다음과 같은) 게임으로 정의 된다.
  • - Setup.B가 Setup(λ,n) 알고리즘을 수행하여 사용자u(u∈U) 각각에 대한 비밀정보를 생성한다.
  • - Adversarial Action.B는 초기 탈퇴자 그룹R을 Ø로 설정한다.A는 다음의 세 가지 질의를 할 수 있다. (1)A가 사용자u'의 비밀키du'를 요청한다. 이때R←R⋃u'로 갱신된다. (2)A가 집합R'과 메시지M을B에게 보내면, 대응하는 암호문을 받는다. 이때R←R⋃R'로 갱신된다. (3)A가 집합R'하에서 생성된 암호문과 임의의u∈R'를B에게 보내면,u의 비밀키로 암호문을 복호화하여 얻은 메시지를 받는다. 이때R←R⋃R'로 갱신된다.
  • - Challenge.A는 메시지M*과 그때까지의 탈퇴자 집합R*=R을B에게 보낸다.B는 랜덤한 bitb∈ {0,1}을 선택한다. b=1인 경우에는 Encrypt(R*,M*)의 결과를 암호문으로서A에게 준다. b=0인 경우는M*와 같은 길이를 갖는 랜덤 메시지RM를 선택하여 Encrypt(R*,RM)의 결과를 암호문으로서A에게 준다.
  • - Guess.A는 추측한b'∈ {0,1}를 내보낸다.
위의 게임에서 A 가 bit b를 정확하게 추측한 상황을 CGuess 로 나타내자. 시스템 파라미터 λ에 대해 A 의 advantage는
PPT Slide
Lager Image
로 정의된다.
  • 정의 1. 브로드캐스트 암호시스템이 weak CCA1 공격 환경에서 공격자A가 가지는가 무시할 만한(negligible) 수준이라면, ‘브로드캐스트 암호시스템이 weak CCA1 공격에 안전하다’라고 말한다.
- 4. 메시지 암호키를 암호화하는 대칭키 암호의 안전성
각각의 부분집합에 대응하는 그룹키 하에서 메시지 암호키 K 를 암호화하기 위해 필요한 대칭키 암호시스템 SKE = ( E , D )의 안전성을 정의한다. CCA1 공격에 안전한 브로드캐스트 암호시스템을 설계하기 위해서는 SKE 역시 CCA1 공격에 안전해야 된다. 대칭키 암호의 CCA1 안전성은 공격자 A 와 챌린저 B 사이의 (다음과 같은) 게임으로 정의된다.
  • - Setup.B가SKE의 비밀키 공간에서 랜덤한 비밀키L을 생성한다.
  • - Adversarial Action.A는 다음의 두 가지 질의를 할 수 있다. (1)A가 선택한 메시지mi을B에 보내서 그에 대응하는 암호문EL(mi) 을 받는다. (2)A가 선택한 암호문Ci를B에 보내서 복호화된 메시지DL(Ci)를 받는다.
  • - Challenge.A는 메시지m*을B에게 보낸다.B는 랜덤한 bitb∈ {0,1}을 선택한다. b=1인 경우에는EL(m*)를A에게 준다. b=0인 경우는m*와 같은 길이를 갖는 랜덤 메시지RM를 선택하여EL(RM)를A에게 준다.
  • - Guess.A는 추측한b'∈ {0,1}를 내보낸다.
위의 게임에서 A 가 bit b를 정확하게 추측한 상황을 CGuess 로 하자. 안전성 상수 λ에 대해 A 의 advantage는
PPT Slide
Lager Image
로 정의된다.
  • 정의 2. 대칭키 암호시스템이 CCA1 공격 환경에서 공격자A가 가지는이 무시할 만한(negligible) 수준이라면, 우리는 ‘대칭키 암호시스템이 CCA1 공격에 안전하다’라고 말한다.
- 5. 메시지를 암호화하는 대칭키 암호의 안전성
메시지 암호키 K 가 결정되면 메시지 M 은 다른 대칭키 암호시스템
PPT Slide
Lager Image
을 이용하여 암호화된다. CCA1 공격에 안전한 브로드캐스트 암호시스템을 설계하기 위해서는
PPT Slide
Lager Image
가 one-time 선택 평문 공격(CAP: chosen-plaintext attack)에 안전해도 충분하다. 3) 대칭키 암호의 onetime CPA 안전성은 공격자 A 와 챌린저 B 사이의 (다음과 같은) 게임으로 정의된다.
  • - Setup.B가SKE의 비밀키 공간에서 랜덤한 비밀키K을 생성한다.
  • - Challenge.A는 메시지M*을B에게 보낸다.B는 랜덤한 bitb∈ {0,1}을 선택한다. b=1인 경우에는EK(m*)를A에게 준다. b=0인 경우는m*와 같은 길이를 갖는 랜덤 메시지RM를 선택하여EK(RM)를A에게 준다.
  • - Guess.A는 추측한b'∈ {0,1}를 내보낸다.
위의 게임에서 A 가 bit b를 정확하게 추측한 상황을 CGuess 로 하자. 안전성 상수 λ에 대해 A 의 advantage는
PPT Slide
Lager Image
로 정의된다.
  • 정의 3. 대칭키 암호시스템이 one-time CPA 공격 환경에서 공격자A가 가지는이 무시할 만한(negligible) 수준이라면, 우리는 ‘대칭키 암호시스템이 one-time CPA 공격에 안전하다’라고 말한다.
- 6. 비밀분산 기법
본 논문에서 필요한 비밀분산(SS: Secret Sharing) 기법은 Shamir의 다항식 기반 (2, n )-SS 기법이다. p 를 소수 (prime)라 할 때, 1차 다항식 f ( x ) = ax + K Zp [ x ]를 선택한다. 여기서 a Zp 는 랜덤하게 선택된 값이고, 상수항 K Zp 는 공유하고자 하는 비밀값이라 하자. 서로 다른 n 개의 값 x 1 ,..., xn 에 대하여 f ( x 1 ),..., f ( xn )을 share라 하면, 비밀값 K 는 전체 n 개의 share 중 2개 이상의 값을 알면 복구할 수 있다. 여기서 K 를 효율적으로 복구하기 위해 Lagrange 보간법을 사용할 수 있다.
이에 반해 1개 이하의 share 값을 아는 경우에는 K 에 대한 어떠한 정보도 정보 이론적으로(information-theoretically) 알 수 없다. 이를 보다 더 정확하게 정의하기 위해, 공격자 A 와 챌린저 B 사이에서 이루어지는 게임을 고려한다. B 는 랜덤 bit b ∈ {0,1}을 선택한다. b=1인 경우에는 ( f ( xj ), xj , K )를 A 에게 주고, b=0인 경우는 랜덤한 RK Zp 를 선택하여 ( f ( xj ), xj , RK )를 A 에게 준다. 여기서 j ∈ {1,..., n }는 A 가 임의로 선택한 값이다. 이 게임에서 A 가 bit b를 정확하게 추측한 상황을 CGuess 로 하자. 이 경우 f ( xj )는 정보 이론적으로 K 에 대한 어떠한 정보도 노출하지 않으므로, |Pr[ CGuess ]-1/2| = 0 이 된다. 이를 아래와 같은 식으로 동일하게 표현할 수 있다.
  • |Pr[A(f(xj),xj,K) = 1] - Pr[A(f(xj),xj,RK) = 1]| = 0 .
이것은 IV장의 안전성 증명으로 확인될 것이다.
Ⅲ. 제안하는 브로드캐스트 암호시스템
- 1. Secret Sharing 기반의 SD 기법 아이디어
Naor, Naor, Lotspiech [2] 가 제안한 SDPRG 기법은 이진트리 구조에서 leaf 노드를 각 사용자로 지정하고, 탈퇴자 집합 R 에 대해 N R 에 속하는 정당한 사용자들만 포함하는 서로 disjoint한 부분집합들 S i1,j1 , S i2,j2 ,..., Sim,jm 로 분할한다. 즉 CoverFinding 알고리즘의 표현으로 CoverFinding ( R ) = { S i1 ,..., Sim }이다. 각 부분집합에는 그에 대응하는 그룹키 Li,j 가 있어서, 그 Li,j 를 이용하여 메시지 암호키 K 를 암호화할 수 있다. 여기서 중요한 점은 부분집합 Sij i 노드를 root로 하는 subtree에서 j 노드 아래의 후손들을 제외하는 방식으로 결정될 수 있다는 것이다. [2] 에 의하면 이때 발생하는 부분집합의 개수는 탈퇴자 수 r 에 대해 최대 2 r -1개까지 생길 수 있다. 이러한 Subset Difference 기법이 가능하도록, [2] 에서는 각 사용자의 비밀키 및 각 부분집합에 대응하는 그룹키를 생성하기 위해 유사난수생성기(PRG: Pseudo-random generator) G : {0,1} k →{0,1} 3k 의 일방향성을 이용하는 독창적인 키 분배 방식을 제안하였다.
본 논문에서는 PRG 방식과는 다르게 비밀분산(SS: Secret Sharing) 방식을 사용하여 SD 기법에 필요한 그룹키 및 비밀키를 부여한다. 여기서 사용하는 SS 방식은 Shamir의 다항식 기반 SS 방식으로 1차 다항식 f ( x ) = ax + K Zp [ x ]를 이용한 (2, n )-SS을 이용한다. 즉 임계치 값을 2로 고정함으로써 두 개의 함수값이 주어지면 상수항으로 설정된 비밀값 K 를 복구할 수 있다. [ 그림 2 ]를 통하여 이 과정을 보다 구체적으로 설명한다. 먼저 소수 p 는 전체 사용자에게 공유되고, 이진트리의 노드들은 Zp 상의 (서로 다른) 값들로 표현된다고 가정하자. 각 subtree의 root인 i 노드를 기준으로 하위 레벨의 depth l 마다 1차 다항식 fi,l ( x ) = ai,lx + ki,l Zp [ x ]을 선택한다. 여기서 ai,l ki,l Zp 에서 각 다항식마다 랜덤하게 선택된 값이다. 다항식이 정해지면 leaf 노드(예를 들어 u 노드)에 대응되는 사용자에게 주어지는 비밀값 di,u 은 다음과 같다. 먼저 i 노드에서 leaf 노드 u 에 이르는 경로상의 (root 노드 i 를 제외한) 노드들의 집합을 Pnodes ( i u )라 하자. 예를 들어, wl 가 하위 레벨의 depth l 에 대응하는 경로상의 노드라 하면 Pnodes ( i u ) = { w 1 , w 2 , w 3 , w 4 }이 되고, 이 때 leaf 노드 u 의 사용자에게주어지는 비밀값은 di,u = { f i,1 ( w 1 ), f i,2 ( w 2 ), f i,3 ( w 3 ), f i,4 ( w 4 )}가 된다. 이러한 비밀값 분배는 wl ( l = 1,2.3)을 root로 하는 subtree에서 1차 다항식들을 새롭게 설정하고, Pnodes ( wl u )에 속한 노드 값들을 다항식에 대입하는 방식으로 dwl,u ( l = 1,2,3)을 구하게 된다. 결국 leaf 노드 u 의 사용자에게 주어지는 비밀값은 { di,u , d w1,u , d w2,u , d w3,u }이 된다.
PPT Slide
Lager Image
SS 기반 SD 기법의 비밀키 할당 예시 Fig. 2. Example of key assignment in SDss
다음으로 탈퇴자를 제외하는 복호화 과정을 설명하기 위해, [ 그림 2 ]에서 노드 n 1 을 root로 하는 subtree의 노드들이 모두 탈퇴되었다고 하자. 이 경우 SD 기법에서 복호화 권한이 있는 사용자들은 S i,n1 으로 표현된다. 송신자는 f i,3 ( n 1 ) ∈ Zp 값을 전송하고 k i,3 값을 S i,n1 에 대응하는 그룹키로 사용한다. 즉 암호문을 복호화하기 위해서는 k i,3 를 복구해야 한다. S i,n1 에 속한 사용들은 자신들이 보유한 비밀값 중 함수 f i,3 에 대응하는 값과 전송된 f i,3 ( n 1 )을 이용하여 (2, n )-SS을 풀 수 있고, 결국 상수항 k i,3 를 복구하게 된다. 그러나 탈퇴자들은 자신들이 보유한 값 f i,3 ( n 1 )과 전송된 값이 같기 때문에 (2, n )-SS을 풀 수가 없게 된다. 이후에 [ 그림 2 ]에서 n 2 노드가 추가적으로 탈퇴하게 되면, SD 기법에 의해 두 개의 부분집합들로 분할되고 각각의 부분집합 하에서 새로운 다항식을 이용한 (2, n )-SS을 적용할 수 있다. 정당한 사용자가 그룹키를 구하기 위해 필요한 연산은, 사용자가 자신이 속한 부분집합을 구하는 CoverFinding 알고리즘을 수행할 필요가 없다고 가정하면, 두 개의 다항식 값을 가지고 Lagrange 보간법을 이용하여 그룹키를 구하는 연산뿐이다. 즉 전체 사용자 수 n 또는 탈퇴자 수 r 에 관계없이 항상 O (1)의 연산을 갖게 된다. 이러한 연산량은 SDPRG 기법이 그룹키를 구하기 위해 O (log n )의 PRG 연산을 수행하는 것에 비해 효율적이다.
- 2. 제안하는 기법
설명의 편의를 위해 다음을 가정한다. 1) 안전성 파라미터 λ는 전체 사용자가 공유한다. 2) 메시지 암호키를 암호화하기 위한 대칭키 암호시스템 SKE = ( E , D )와 메시지를 암호화하기 위한 대칭키 암호시스템
PPT Slide
Lager Image
는 전체 사용자가 공유한다. 3) (AES 대칭키 암호를 사용하기 위해) 128 비트의 소수(prime) p 는 전체 사용자가 공유한다. 4) 전체 사용자 수는 n = 2 k 이라 하자. 5) n 명을 leaf노드에 대응시키는 완전이진트리(full binary tree)를 구성하고, 이진트리의 모든 노드들은 Zp 상의 원소에 고유하게 4) 대응된다.
- 1.1 초기설정(Setup)
PPT Slide
Lager Image
leaf 노드 u에 대응하는 비밀키 할당 Fig. 3 Key assignment corresponding to the leaf node u
  • (1)i노드를 root로 하는 subtree에서 하위 레벨의 depthl에 대응하는 1차 다항식fi,l(x) =ai,lx+ki,l∈Zp[x]을 선택한다. 여기서ai,l과ki,l은Zp에서 랜덤하게 선택된다.
  • (2) (1)의 과정을 root 노드i0에서부터 하위 레벨의 depth가 -1 + logn이 될 때까지 중간단계의 모든 노드들에 대해 반복 수행한다.
  • (3) root 노드i0에서 leaf 노드 사용자u에 의해 결정되는Pnodes(i0→u)를 구한다. 예를 들어Pnodes(i0→u) = {i1,...,ik} 라 하자.
  • (4) root 노드i0에 대응되는 비밀값di0,u= {fio,1(i1), ...,fio,k(ik)}을 계산한다.
  • (5) 노드i1부터ik-1을 subtree의 root 노드로 할 때의 비밀값di1,u,...,dik-1,u을 (4)의 과정으로 구한다.
  • (6) 사용자u에 부여하는 비밀키du는du= {k,di0,u,di1,u,...,dik-1,u} 로 구성된다. 여기서k∈Zp는 탈퇴자가 없는 경우에 사용되는 랜덤한 비밀키이다.
각 사용자가 저장해야 하는 비밀키 du 의 사이즈는
PPT Slide
Lager Image
개의 128비트 값이 된다. 그 이유는 dij,u 의 원소 개수는 log n - j 개가 되고, j 는 0부터 log n - 1 까지 포함하므로, 전체 개수는
PPT Slide
Lager Image
로 구할 수 있다. 이것은 SDPRG 기법의 비밀키 사이즈와 같으며, 결국 O (log 2 n )의 비밀키 저장량을 갖게 된다.
반면 키생성기관(송신자)가 저장해야 하는 값은 각 다항식에 대응되는 ai,l ki,l 값들이다. 이 경우 ai,l 값들의 개수는
PPT Slide
Lager Image
로 계산되고, ki,l 값들까지 합하면
PPT Slide
Lager Image
이 된다. 그러나 V 장에서 PRF 를 사용하여 송신자의 저장량을 O (1) 으로 줄이는 방법을 소개한다.
- 1.2 암호화(Encryption)
탈퇴자 집합 R 과 메시지 M 을 입력받으면, 송신자는
PPT Slide
Lager Image
를 사용하여 아래와 같이 암호문을 생성한다.
  • (1) 메시지 암호화용 세션키K를 {0,1}t에서 랜덤하게 선택한다.
  • (2)SDPRG기법과 동일하게 탈퇴자 집합R에 대해서CoverFinding(R) = {Si1,j1,...,Sim,jm}을 구한다.
  • (3) 각 부분집합Si,j에서i노드를 시작으로 하는 subtree에서j노드에 이르는 depth에 정의된 함수fi,l(x) =ai,lx+ki,l∈Zp의 상수항ki,l를Si,j의 그룹키Ki,l로 하고,j노드에 할당된 값을 대입한 함수값fi,l(j)을 구한다.
  • (4) (3)의 과정을 분할된 부분집합들Si1,j1,Si2,j2,...,Sim,jm에 각각 적용한다.
  • (5) 메시지 암호화키K를 그룹키Ki,l로 각각 암호화하고 각Si,j마다 구한 함수값fi,l(j)과 암호문EKi,l(K)을 암호문에 포함시킨다.
  • (6) 메시지M을 메시지 암호키K로 암호화한를 암호문에 포함시킨다.
  • (7)Si1,j1,Si2,j2, ...,Sim,jm을 특정할 수 있도록 (i1,j1), ..., (im,jm)를 index로 암호문에 포함시킨다. 사용자는 자신이 속한 부분집합을 바로 확인하고 복호화할 수 있다.
  • (8) 암호문은이다.
전송량 측면에서 SDPRG 기법과 비교할 때 가장 큰 차이점은 그룹키 Ki,l 로 메시지 암호키 K 를 암호화하는 과정에서 발생한다. SDPRG 기법은 EKi,l ( K )인데 비해, 본 논문에서는 ( fi,l ( j ), EKi,l ( K ))로써 각 부분집합별로 함수값 fi,l ( j )를 추가적으로 전송해야 한다. 따라서 전송량 측면에서는 SDPRG 기법에 비해 약간 길어진다는 단점을 보인다.
- 1.3 복호화(Decryption)
수신자 u 는 다음과 같은 브로드캐스트 암호문을 수신하고 복호화 절차를 실행한다.
PPT Slide
Lager Image
  • (1) 사용자u는 index (i1,j1), ..., (im,jm)를 통해 자신이 속한 부분집합Si,j를 확인한다.
  • (2)Si,j가 확인되면 대응하는 [fi,l(j),C]를 가져온다.
  • (3)fi,l(j)와du에서 (i,j)에 대응하는 함수값fi,l(ĵ)값(여기서j≠ĵ임)을 가지고 Lagrange 보간법을 이용하여 그룹키Ki,l를 구한다. 참고로x1≠x2인 두 개의 1차 다항식 함수값 (x1,y1), (x2,y2)를 통해 상수항인 그룹키f(0) =Ki,l를 구하는 식은 아래와 같다.
PPT Slide
Lager Image
  • (4)Ki,j를 복구해낸 후DKi,j(C)로 복호화하여 메시지 암호키K를 얻는다.
  • (5)로 복호화하여 메시지M을 얻는다.
SDPRG 기법과 비교하면, 복호화 연산은 (3)번 과정에서 차이를 보인다. SDPRG 기법이 O (log n )의 PRG 연산을 수행하여 그룹키를 구하는 반면, 본 논문에서는 Zp 상에서의 간단한 modular 연산을 필요로 한다. 더구나 (3)번 과정에 필요한 연산은 전체 사용자 수 n 이나 탈퇴자 수 r 에 관계없이 수행된다.
- 2. Secret Sharing 기반의 LSD 기법
Halevy, Shamir [5] 가 제안한 LSD(Layered Subset Difference) 기법은 SDPRG 기법의 변형으로서 전송량을 증가시키면서 비밀키 저장량을 SDPRG 기법의 O (log 2 n )에서 O (log 3/2 n )으로 줄이는 기법이다. 핵심 아이디어는 전체 이진트리에서 i , k , j 의 각 노드가 leaf 노드부터 root까지 하나의 경로 상에 있다고 하면, Si,j 는 disjoint한 두 부분집합 Si,j = Si,k Sk,j 으로 분할하는 것이다. 따라서 암호문 구성에 필요한 부분집합의 수는 증가하지만, 대신 사용자들이 저장하는 비밀키 사이즈는 감소하게 된다. 여기서 비밀키 및 그룹키의 분배는 PRG의 일방향성을 이용하므로 SDPRG 기법과 동일하다.
LSD 기법의 분할가능성을 이용하여 비밀키 저장량을 낮출 수 있는 방법은 비밀분산(SS: Secret Sharing) 기반의 브로드캐스트 암호시스템에도 그대로 적용될 수 있다. 우선 이진트리를
PPT Slide
Lager Image
의 레벨로 layer를 나누는 것과
PPT Slide
Lager Image
의 depth를 갖는 special 레벨로 나누는 기존 LSD 기법과 동일하다. 비밀키 분배에서는 (2, n )-SS 기법을 이용하여 함수값을 설정한다. 따라서 사용자 u 가 보유하는 함수값들은, 각 subtree의 root 노드가 special level가 아닌 경우에 사용자는 그 root 노드와 같은 layer에 속한 노드들에 대한 함수값만을 갖고, root 노드가 special level인 경우는 SS 기반의 SD 기법과 같이 사용자는 subtree의 root 노드부터 u 에 이르는 경로 상에 있는 노드들에 할당된 함수값을 갖는다. 그러므로 SS 기반의 LSD 기법도 기존 LSD 기법처럼 비밀키 저장량을 O (log 2 n )에서 O (log 3/2 n )로 줄일 수 있다. 전송량 측면에서는 기존 LSD 기법의 부분집합 개수가 탈퇴자 수 r 에 대해 최악의 경우 4 r -2을 보이므로, SS 기반의 LSD 기법에서는 각 그룹키 Ki,l 로 메시지 암호키 K 를 암호화한 4 r -2개의 EKi,l ( K )과는 별도로 4 r -2개의 함수값 fi,l ( j )까지 전송하게 된다.
n 명의 사용자에 대해 전체 이진트리가 2n-1개의 노드를 가짐으로 각 노드를 ⌈log2(2n-1)⌉ bit로 표현할 수 있으며 루트노드를 0 으로 시작하여 다음레벨의 왼쪽부터 1씩 증가시켜나가는 방식으로 마지막 오른쪽 leaf노드까지 각각 고유한 값을 할당할 수 있다.
Ⅳ. 제안하는 브로드캐스트 암호시스템의 안전성 증명
  • 정리 4. 대칭키 암호시스템이SKE= (E,D)이 CCA1 공격에 안전하고, 대칭키 암호시스템이 onetime CPA 공격에 안전하다고 가정하자. 이 경우 제안한 브로드캐스트 암호시스템은 weak CCA1 공격에 안전하다.
  • 구체적으로A는 브로드캐스트 암호시스템에 대한 weak CCA1 공격 알고리즘이고,B는SKE에 대한 CCA1 공격 알고리즘 또는에 대한 one-time CPA 공격 알고리즘이라 하면,
PPT Slide
Lager Image
  • 여기서m은 Subset Cover를 구성하는 부분집합의 최대 개수이고,w는 전체 이진트리에서 생성될 수 있는 부분집합의 최대 개수이다.
증명) 브로드캐스트 암호시스템의 weak CCA1 안전성을 공격하는 공격자를 A 라 하자. 증명에서는 A 를 이용하여 SKE = ( E , D )의 CCA1 안전성을 공격하거나
PPT Slide
Lager Image
의 one-time CPA 안전성을 공격하는 알고리즘 B 를 설계할 것이다. 이를 위해 A 가 받는 챌린지 암호문 CT* 의 변화를 이용하여 다음과 같은 하이브리드 게임을 고려한다.
PPT Slide
Lager Image
여기서 R i1,j1 ,..., Rim,jm SKE 의 비밀키 공간에서 선택한 난수들이고, R 1 ,..., Rm SKE 의 메시지 공간에서 선택한 난수들이다. RM* 는 챌린지 메시지 M* 와 같은 길이를 갖는 난수로 선택된 메시지이다.
각 게임 Gi 에서 공격자 A 가 정확하게 추측할 확률을 Pr[ Gi ]라 하자. 게임 G 0 는 메시지 M* 에 대한 암호문이 주어진 것으로 브로드캐스트 암호시스템의 weak CCA1 공격 환경과 같다. 반면 게임 GF 는 난수 메시지 RM* 에 대한 암호문이 주어진 것으로 A 는 메시지에 대한 어떠한 정보도 얻을 수 없는 공격 환경이다. 안전성 증명은 G 0 에서 GF 로 전이하는 과정에서 A 가 가지는 advantage가 무시할 만한(negligible) 것임을 보이는 것으로 이루어진다.
  • Claim 1. Pr[G0] - Pr[G1] = 0
증명) A 는 브로드캐스트 암호시스템에 대한 weak CCA1 공격을 수행한다. B S i1,j1 에 대응하는 그룹키를 제외하고 setup 과정과 동일하게 비밀키를 생성한다. B 는 챌린지로 받은 ( f ( j 1 ), j 1 , T ) 값을 S i1,j1 에 대응하는 질의에 이용한다. (여기서 j 1 B 가 선택한 값이다.) S i1 i 1 을 root로 하는 subtree의 leaf 노드 사용자 집합이라 하자. 1) 사용자 u u S i1 인 경우, u 의 비밀키 질의는 B 가 (관련된 키를 알고 있으므로) 쉽게 응답할 수 있다. u u S i1 이고 u S j1 인 경우, u 의 비밀키 질의는 j 1 노드가 속한 레벨에 대응하는 다항식 값으로 f ( j 1 )을 이용한다. 2) u u S i1 인 경우, A 의 암호(복호) 질의는 B u 의 비밀키를 생성하여 대응한다. u u S i1 이고 u S j1 인 경우, A 의 암호(복호) 질의는 T 을 비밀키로 이용하여 응답한다.
A u 의 비밀키 질의 시 u S i1 이고 u S j1 인 경우, j 1 노드의 레벨에 대응하는 (계수를 모르는) 다항식 f (·)를 이용하여 비밀키를 응답해야 한다. B a × j 1 + b = T Zp 를 만족하는 a , b Zp 를 랜덤하게 선택한 후, j 1 노드의 레벨에 대응하는 다항식을 f ( x ) = ax + b 로 사용한다. 이러한 비밀키 질의가 발생하면 S i1,j1 는 더 이상 챌린지 단계에서 사용되지 않고, S i1,j1 가 두 개의 부분집합으로 분할된다. 그러므로 이후의 게임진행은 ( S i1,j1 가 두 개의 부분집합으로 분할된) G 0 G 1 B 의 챌린지 값 ( f ( j 1 ), j 1 , T )과는 무관하게 동일한 (statistically identical) 게임으로 된다. 5) 또한 암호(복호) 질의 시 수반되는 탈퇴자 집합들을 누적하는 과정에서 그때까지의 총 탈퇴자 집합이 u S i1 이고 u S j1 인 사용자 u 를 적어도 한명 포함하는 경우에는, 위와 같이 임의의 a , b Zp 로 다항식을 f ( x ) = ax + b 로 결정한 후 게임을 진행한다. 그 이유는 weak CCA1 안전성모델의 조건에 의해 이후의 게임은 G 0 G 1 B 의 챌린지 값 ( f ( j 1 ), j 1 , T )과는 무관하게 동일한 게임으로 되기 때문이다.
챌린지 단계에서 A 가 탈퇴자 집합 R* M* 를 보내면, B CoverFinging ( R* )를 수행하여 S i1,j1 , S i2,j2 ,..., Sim,jm 을 구한다. S i1,j1 에 대한 그룹키를 암호화할 때 B 는 자신이 챌린지로 받은 ( f ( j 1 ), j 1 , T ) 값을 이용한다. 다른 부분집합들에 대해서는 메시지 암호키 K 를 랜덤하게 선택한 후 다음과 같이 CT* 를 구성한다.
PPT Slide
Lager Image
1차 다항식 f ( j 1 )의 일차항과 상수항은 B 에게 알려지지 않았다는 것을 유의하자. T f ( j 1 )의 상수항이면 A S i1,j1 의 그룹키가 K i1,l1 G 0 에서 공격을 수행하는 것이고, T 가 다항식의 상수항과 관계없는 난수이면 A S i1,j1 의 그룹키가 R i1,j1 G 1 에서 공격을 수행하는 것이다. 따라서 G 0 G 1 을 구별하는 A 의 공격능력은 비밀분산 기법의 상수항을 구분하는 B 의 능력으로 전환된다. 그러나 비밀분산 기법의 상수항을 구분하는 문제는 A 의 능력과 관계없이 advantage의 차가 0이다. (II. 6절 참고) □
PPT Slide
Lager Image
증명) A 는 브로드캐스트 암호시스템에 대한 weak CCA1 공격을 수행한다. B S i1,j1 에 대응하는 그룹키를 제외하고 setup 과정과 동일하게 비밀키를 생성한다. S i1,j1 에 대응하는 그룹키는 B 가 CCA1 공격을 하는 대칭키 암호시스템 SKE 의 비밀키로 한다. 1) 사용자 u u S i1 인 경우, u 의 비밀키 질의는 B 가 (관련된 키를 알고 있으므로) 쉽게 응답할 수 있다. u u S i1 이고 u S j1 인 경우, u 의 비밀키 질의는 j 1 노드의 레벨 l 1 에 대응하는 임의로 선택된 다항식 f i1,l1 ( x )을 이용하여 응답한다. 그리고 j 1 노드의 레벨 l 1 에 대응하는 그룹키는 SKE 의 비밀키임을 상기하자. u u S i1 이고 u S j1 인 경우, B 는 모르는 SKE 의 비밀키가 상수항이 되도록 다항식 f i1,l1 ( x )의 값을 결정할 수 없으므로 게임을 중단(abort)한다. 2) u u S i1 인 경우, A 의 암호(복호) 질의는 B u 의 비밀키를 이용하여 대응한다. u u S i1 이고 j 1 노드의 레벨에 대응하는 그룹키를 이용하암호(복호)화 할 경우, B 는 자신의 챌린저에게 암호(복호) 질의를 하고 그 결과를 A 에게 보낸다. u u S i1 이고 j 1 노드의 레벨에 대응하지 않는 그룹키를 이용할 경우 B 는 (관련된 키를 알고 있으므로) 쉽게 응답할 수 있다.
챌린지 단계에서 A 가 탈퇴자 집합 R* M* 를 보내면, B CoverFinding ( R* )를 수행하여 S i1,j1 , S i2,j2 ,..., Sim,jm 을 구한다. S i1,j1 에 대한 암호문을 생성하기 위해 B 는 메시지 암호키 K 를 랜덤하게 선택한 후 B 의 챌린저에게 K 를 챌린지 값으로 보낸다. 그 결과로 받은 암호문을 T 라 하자. 이를 이용하여 B CT* 를 다음과 같이 구성한다.
PPT Slide
Lager Image
T K 를 암호화한 것이면 A G 1 에서 공격을 수행하는 것이고, T K 와 같은 길이의 난수 R 1 을 암호화한 것이면 A
PPT Slide
Lager Image
에서 공격을 수행하는 것이다. 따라서 위의 게임 중단(abort)가 발생하지 않으면, G 1
PPT Slide
Lager Image
을 구별하는 A 의 공격능력은 SKE 에 대한 CCA1공격을 하는 B 의 능력으로 전환된다. 여기서 abort가 발생할 확률은 전체 부분집합의 개수 w 에서 한 개를 선택하는 것이므로 1/ w 가 된다. 즉
PPT Slide
Lager Image
일 경우 A 의 공격능력을 B 의 공격능력으로 전환할 수 있다. □
PPT Slide
Lager Image
증명) Claim 1과 유사하게 증명할 수 있다. □
위 Claim 1, Claim 2, Claim 3의 증명을 이용하여 이후의 하이브리드 게임들에 대한 아래의 Claim 4, Claim 5, Claim 6에 대한 증명을 쉽게 완성할 수 있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
증명) A 는 브로드캐스트 암호시스템에 대한 weak CCA1 공격을 수행한다. B 는 setup 과정과 동일하게 비밀키를 생성한다. 메시지를 암호화하는
PPT Slide
Lager Image
의 비밀키에 대해 B 가 one-time CPA 공격을 하는 것임을 상기하자. B 가 (관련된 키를 알고 있으므로) 사용자 u 에 대한 비밀키 질의와 암호(복호)와 질의를 쉽게 응답할 수 있다.
챌린지 단계에서 A 가 탈퇴자 집합 R* M* 를 보내면, B CoverFinding ( R* )를 수행하여 S i1,j1 , S i2,j2 ,... Sim,jm 을 구한다. B 는 각 부분집합에 대응하는 메시지 암호키 R 1 ,..., Rm 을 선택한 후, M* B 의 챌린저에게 챌린지 값으로 보낸다. 그 결과로 받은 암호문을 T 라 하자. 이를 이용하여 B CT* 를 다음과 같이 구성한다.
CT* = < [( i 1 , j 1 ),..,( im,jm ), f i1,l1 ( j 1 ), E Ki1,l1 ( R 1 ), ..., fim,jm ( jm ), EKim,jm ( Rm )], T >
T M* 를 암호화한 것이면 A
PPT Slide
Lager Image
에서 공격을 수행하는 것이고, T 가 랜덤 메시지 RM* 을 암호화한 것이면 A GF 에서 공격을 수행하는 것이다. 따라서
PPT Slide
Lager Image
GF 을 구별하는 A 의 공격능력은
PPT Slide
Lager Image
에 대한 one-time CPA공격을 하는 B 의 능력으로 전환된다. □
위에서 전개한 하이브리드 게임은 랜덤 메시지 RM* 을 암호화한 것을 유지하면서 다시 각 부분집합에 대응하는 메시지 암호키를 Ri 에서 K 로 전환시키는 게임을 추가함으로써 완성된다. 이는 랜덤 메시지 RM* 을 암호화한 것을 유지하면서 G 0 에서 GF 로 변환되는 과정을 반대로 전개하면 된다. 이 경우 Gi 에 대응하는 게임을
PPT Slide
Lager Image
라 하자. 마지막 게임
PPT Slide
Lager Image
G 0 와 같으면서도 M* 대신 RM* 을 암호문이 된다. 결국 위 하이브리드 게임들을 종합하면 다음과 같은 식을 얻는다.
PPT Slide
Lager Image
즉,
PPT Slide
Lager Image
으로 정리 4의 증명이 완성된다. ■
정리 4의 하이브리드 게임을 이용한 증명 기법은 SS 기법을 활용한 LSD 기법에도 유사하게 적용된다. 차이점은 special layer와 local layer에 따른 비밀키 분배와 하나의 부분집합을 두 개의 부분집합으로 분할하는 것뿐이다. 자세한 증명은 생략한다.
더 엄밀하게는 이진트리를 구성하는 모든 w 개의 부분집합에 대해서 그룹키를 (independently) 랜덤한 값으로 변화시키는 하이브리드 게임을 진행시키는 것으로 생각할 수 있다.
Ⅴ. 기존 기법과의 비교분석
안전성과 효율성 측면에서 기존 SD(LSD) 기법과 본 논문에서 제안한 (2, n )-SS 기반의 SD, LSD 기법을 비교 분석한다. 편의상 SS 기반의 SD 기법을 SDss , SS 기반의 LSD 기법을 LSDss 로 표기한다.
- 1. 안전성 측면의 비교
먼저 안전성 측면에서는 기존 SD(LSD) 기법이 PRG 기반에서 설계된 것에 비해, 본 논문에서 제안한 기법은 (2, n )-SS 기반으로 설계되었다. 이 차이로 인해 증명 상에서 나타나는 안전성 손실(security loss)은 기존 SD 기법이 O ( mw 2 )인데 비해, SDss 기법은 O ( mw )이다. 여기서 m 은 Subset Cover를 구성하는 부분집합의 최대 개수이고, w 는 전체 이진트리에서 생성될 수 있는 부분집합의 최대 개수이다. 따라서 기존 SD 기법이 SDss 기법에 비해 O ( w )만큼의 안전성 손실이 더 발생하게 된다. 전체 사용자 수 n 에 대해 w O ( n log n )의 개수가 가능하므로 결국 O ( n log n )만큼의 안전성 손실이 더 발생한다는 것이다. 예를 들어 n = 2 20 라 하면, 기존 SD 기법은 약 25bits의 안전성 손실이 SDss 기법보다 더 발생하게 된다. 따라서 128bits의 안전성 레벨에서 SDss 기법이 설계되었다면, 동일한 안전성을 추구하기 위해 기존 SD 기법은 128+25=153bits의 안전성 레벨에서 설계되어야 함을 의미한다. 반면, 기존 SD(LSD) 기법은 CCA1 모델에서 안전성이 증명되는 데 비해, SDss ( LSDss ) 기법은 약화된 weak CCA1 모델에서 안전성이 증명된다는 것이다. 양자의 차이는 CCA1 모델의 경우 탈퇴자를 제외한 집합 N R 에서 동적으로 수신자 집합을 매번 다르게 설정할 수 있는 반면, weak CCA1 모델의 경우 탈퇴자를 제외한 집합 N R 이 그대로 수신자의 집합이 된다는 것이었다.
- 2. 효율성 측면의 비교
일반적으로 브로드캐스트 암호시스템의 효율성은 1) 암호문 전송량, 2) 수신자의 비밀키 저장량, 3) 복호화 시 필요한 계산량 측면에서 분석된다. 엄밀한 분석을 위해서는 증명상에 나타난 안전성 손실을 고려해야 하나, 본 논문에서는 (제안기법에 오히려 더 유리한) 그 손실을 고려하지 않기로 한다. Table 4 은 CS 기법, PRG 기반의 SD [2] , LSD [5] 기법과 본 논문에서 제안한 SS 기반의 SD, LSD 기법의 효율성을 세 가지측면에서 비교한 것이다.
기존 기법들과의 효율성 비교Table 4. Performance comparison to the previous PRG-based SD and LSD methods
PPT Slide
Lager Image
기존 기법들과의 효율성 비교 Table 4. Performance comparison to the previous PRG-based SD and LSD methods
- 2.1 암호문 헤더 전송량
SDss 기법의 암호화 알고리즘은 ( R , M )을 입력받아 CoverFinding ( R ) = { S i1,j1 ,..., Sim,jm }을 수행한 후 아래와 같은 암호문을 생성한다.
CT = < [( i 1 , j 1 ),...,( im,jm ), f i1,l1 ( j 1 ), E Ki1,l1 ( K ),..., fim,jm ( jm ), EKim,lm ,( K )], EK ( M ) >
여기서 대괄호 [ ] 안의 값을 암호문 헤더(header)라 한다. 전송량 비교에서는 메시지 M 에 대한 암호문 EK ( M )을 제외하고, 암호문의 헤더 길이만을 고려한다. SD (LSD) 기법과 비교하면, 제안된 SDss ( LSDss )기법은 암호문 헤더에서 복호화를 위한 함수값 fi,l ( j )이 추가된 것만큼 길어진다. 즉 부분집합에 대한 index와 메시지 암호키 K 를 그룹키로 암호화한 것은 기존 SD (LSD) 기법과 동일하다.
부분집합의 index 정보를 전송하는 방식은 1) R 에 속한 탈퇴자 정보를 전송하거나, 2) CoverFinding 알고리즘을 수행한 결과인 ( i 1 , j 1 ),...,( im,jm )을 전송하는 것이 있다. 전자의 방식은 모든 수신자들이 R 을 받은 후 각각 CoverFinding ( R )을 수행하여, 자신이 어느 부분집합에 속하는지를 결정하여야 한다. 후자의 방식은 복호화 연산 시 CoverFinding 알고리즘을 추가적으로 수행할 필요는 없으나, index 정보가 전자에 비해 두 배로 증가하는 단점이 있다. 본 논문에서는 복호화 연산의 효율성을 강조하기 위해 후자의 방법으로 전송량을 비교 분석한다.
SD(LSD) 기법의 경우 부분집합 Si,j 마다 이를 표현하는 index는 i 노드와 j 노드를 한 쌍 ( i , j )으로 표현한다. 총사용자 n 명이 leaf노드로 대응되는 완전이진트리에서 총 노드의 수는 2 n -1개가 되므로, 하나의 노드를 표현하는데 ⌈log(2 n -1)⌉ 의 bits가 필요하다. 따라서 하나의 Si,j 는 두개의 노드 ( i , j )로 표현됨으로, 하나의 Si,j 에 대한 index 길이는 2⌈log(2 n -1)⌉ bits가 된다. SD 기법에서 탈퇴자수 r 에 대해 최악의 경우 2 r -1개의 부분집합이 생길 수 있으므로 총 index의 사이즈는 2⌈log(2 n -1)⌉×(2 r -1) bits가 된다. 이는 SDss ( LSDss )기법에서도 동일하다. 현재 상용화된 AES 대칭키 암호시스템을 고려하여 메시지 암호키를 128bits라 하자. 이 경우 SD 기법은 각 부분집합별 128bits의 암호문이 추가되므로 총 암호문 헤더의 길이는 (2⌈log(2 n -1)⌉ + 128)×(2 r -1) bits가 된다. 그러나 SDss 기법은 각 부분집합 별 128bits의 암호문 외에 128bits의 다항식 값을 더하므로 총 암호문 헤더의 길이는 (2⌈log(2 n -1)⌉ + 256)×(2 r -1) bits가 된다. LSD 기법과 LSDss 기법의 경우 최대 4 r -1개의 부분집합이 생긴다는 것과 CS 기법의 경우 최대 O ( r log⌈ n / r ⌉)의 부분집합이 생긴다는 것을 이용하면 Table 4 에 나타난 전송량 비교 결과를 얻을 수 있다.
실제 수치를 대입하여 암호문 헤더 길이를 비교하기 위해, 전체 사용자수를 n = 2 31 이고 탈퇴자 수를 r = 2 12 이라 하자. 이 경우 CS 기법의 암호문 헤더는 12451840bits, SD 기법은 1572672bits, LSD 기법은 3145344bits인데 비해, SDss 기법은 2621120bits, LSDss 기법은 5242240bits 이다. 따라서 CS 기법에 비해 SDss 기법은 약 12451840/2621120 ≈ 4.8배 더 짧은 암호문 헤더를 갖고, SD (LSD)기법에 비해서는 SDss ( LSDss ) 기법이 전송량 측면에서 약 2621120/1572672 ≈ 1.7배 더 긴 암호문 헤더를 갖는다.
- 2.2 저장량
사용자 u 가 저장하는 비밀키 사이즈는 SD 기법의 경우
PPT Slide
Lager Image
개의 128bits 스트링을 저장해야 하고, SDss 기법에서는 같은 개수의 128bits 함수값을 저장하여야 한다. 결국 두 기법들은 동일한 비밀키 저장량을 갖는다. 마찬가지로 LSD 기법과 LSDss 기법도 동일한 O (log 3/2 n )의 비밀키 저장량을 갖는다.
SDss ( LSDss ) 기법에서 송신자는 부분집합에 대응하는 그룹키와 대응하는 함수값을 알고 있어야 한다. 즉 모든 일차 다항식 fi,l ( x ) = ai,lx + ki,l Zp 의 계수 ai,l ki,l 을 알고 있어야 한다. 모든 다항식은 ai,l ki,l 가 랜덤하게 정의되어야 하나 송신자의 저장량을 줄이기 위해 유사난수함수 PRF : Key × {0,1} ≥2|p| →{0,1} 2|p| 를 이용한다. PRF 의 입력은 setup알고리즘이 랜덤하게 선택한 키 k Key i ǁ d 값이다. 여기서 i 는 해당 root노드의 index이고, l i 노드에서 하위 레벨의 깊이를 나타낸다. PRF 의 출력은 2| p | bits 가 되며, 이를 이등분하여 계수 ai,l ki,l 로 사용한다. 이런식으로 송신자는 모든 다항식의 계수를 PRF 로 유도할 수 있고, 결국 송신자가 저장해야 하는 값은 키 k Key 뿐이다. 이 경우 안전성 증명은 정리 4의 하이브리드 게임 전개에서 G 0 이전에 새로운 게임
PPT Slide
Lager Image
을 생각한다. 여기서
PPT Slide
Lager Image
은 모든 다항식의 계수를 PRF 를 이용해서 생성하는 것이다.
PPT Slide
Lager Image
G 0 을 구분하는 공격자의 능력은 그대로 PRF 의 유사난수성을 공격하는 능력으로 전환됨을 쉽게 보일 수 있다.
- 2.3 복호화에 필요한 연산량
복호화에 필요한 연산량은 기존 SD, LSD 기법이 최대 log n 번의 PRG 함수를 계산해야 하는 것에 비해, SDss LSDss 기법은 Lagrange 보간법을 이용하여 Zp 에서 (2, n )-SS 기법을 풀면 된다. 즉 전체 사용자 수 n 이나 탈퇴자수 r 에 관계없이 O (1)의 복호화 연산량을 요구하므로 매우 빠른 복호화 시간을 보장할 수 있다. SDss LSDss 기법과 같이 CS 기법도 O (1)의 복호화 연산량을 갖는다. 그러나 Table 4 에 나타나듯 CS 기법은 비밀키 저장량과 복호화 연산량 측면에서는 상당히 효율적이지만 기타의 기법에 비해 전송량 측면에서 상당히 비효율적이다.
Ⅶ. 결 론
본 논문에서는 기존의 유사난수생성기(PRG)를 이용하여 키를 분배하는 SD 기법과는 달리, 비밀분산(Secret Sharing) 방식을 이용하여 키를 분배하는 SD 기법을 제시하였다. 비밀분산을 이용한 키 분배는 암호 이론적으로 안전한 키 분배방식으로써, 이러한 방식을 통해 SD 기법의 효과를 낼 수 있다는 것이 이론적으로 중요한 점이었다. 이 결과는 기존의 (암호 이론적으로 안전한 키 분배 방식으로 설계된) CS 기법이 가진 전송량의 한계를 극복할 수 있다는 것이었다. 안전성 측면에서는 제안된 기법이 기존보다 약화된 (그러나 여전히 현실적인) 모델에서 증명되었다. 효율성 측면에서는 본 논문에서 제시된 기법이 기존 SD 기법에 비해 약 1.7배 더 긴 전송량을 갖으나 복호화 연산량이 전체 사용자 또는 탈퇴자 수에 관계없이 일정하다는 장점을 가졌다. 또한 제시된 기법은 Layered SD 기법의 아이디어를 그대로 적용하여 사용자의 비밀키 저장량을 줄이도록 변형도 가능하였다.
이후의 연구는 비밀분산 방식을 일반화하고 그에 대응되는 브로드캐스트 암호시스템을 설계하는 것이 흥미로울 것이다. 일반화하는 방향으로는 다항식의 차수를 올리거나, 이진트리에서 n -ary 트리로 확장하는 것이 될 것이다. 특히 흥미로운 것은 SD 방식에 표현 가능한 부분집합이 Si,j ( i 노드를 루트로 하고 그 아래 노드 중 j 노드를 루트로 하는 subtree를 제거하는 집합)인데 비해, 이를 확장하여 Si,j,k ( i 노드를 루트로 하고 그 아래 노드 중 j k 노드를 루트로 하는 두 개의 subtree들을 제거하는 집합)으로 표현하는 것이다. 이것이 가능하다면 비밀분산을 이용하면서도 전송량 측면에서 기존 SD 기법과 유사한 (여전히 복호화 연산량의 장점은 유지하면서) 브로드캐스트 암호시스템의 설계가 가능할 것이다.
BIO
이 재 환
- 2009년 3월 ~ 현재 : 상명대학교 컴퓨터과학과 학사과정
- ORCID : http://orcid.org/0000-0001-5580-416X
- 주관심분야 : 브로드캐스트 암호, 전자서명 등
박 종 환
- 1999년 2월 : 고려대학교 이과대학 수학과 (학사)
- 2004년 2월 : 고려대학교 정보보호대학원 정보보호학과 (석사)
- 2008년 8월 : 고려대학교 정보경영공학전문대학원 정보보호학과 (박사)
- 2009년 6월 ~ 2011년 5월 : 경희대학교(국제) 응용과학대학 학술연구교수
- 2011년 6월 ~ 2013년 8월 : 고려대학교 BK21정보보호사업단 연구교수
- 2013년 9월 ~ 현재 : 상명대학교 컴퓨터과학과 조교수
- ORCID : http://orcid.org/0000-0003-2742-6119
- 주관심분야 : 인증암호, ID-based 암호, 브로드캐스트 암호, 암호프로토콜 등
References
Fiat A. , Naor M. 1993 "Broadcast encryption," Proceedings of the CRYPTO'93 volume 773 of LNCS 480 - 491
Naor D. , Naor M. , Lotspiech J. 2001 "Revocation and tracing schemes for stateless receivers," Proceedings of the CRYPTO 2001 vol. 2139 of LNCS 41 - 62
Dodis Y. , Fazio N. 2002 "Public key broadcast encryption for stateless receivers," Proceedings of the Digital Rights Management Workshop vol. 2696 of Lecture Notes in Computer Science 61 - 80
Boneh D. , Gentry C. , Waters B. 2005 "Collusion resistant broadcast encryption with short ciphertexts and private keys," Proceedings of the CRYPTO 2005 vol. 3621 of LNCS 258 - 275
Halevy D. , Shamir A. 2002 "The LSD broadcast encryption scheme," Proceedings of the CRYPTO 2002 vol. 2442 of LNCS 47 - 60
Goodrich M.T. , Sun J.Z. , Tamassia R. 2004 "Efficient tree-based revocation in groups of low-state devices," Proceedings of the CRYPTO 2004 vol. 3152 of LNCS 511 - 527
Bhattacherjee S. , Sarkar P. 2013 “Tree based symmetric key broadcast encryption” IACR Cryptology ePrint Archive Report 2013/786
Chor B. , Fiat A. , Naor M. 1994 "Tracing traitors," Proceedings of the CRYPTO'94 vol. 839 of LNCS 257 - 270
Kim ChongHee , Hwang YongHo , Lee PilJoong 2003 "An efficient public key trace and revoke scheme secure against adaptive chosen ciphertext attack," Proceedings of the ASIACRYPT 2003 vol. 2894 of LNCS 359 - 373
Boneh D. , Waters B. 2006 "A fully collusion resistant broadcast, trace, and revoke system," Proceedings of the ACM CCS 06 211 - 220