브로드캐스트 암호시스템은 한명의 송신자가 다수의 수신자에게 안전하게 메시지를 전송하는 기법이다. 제안된 브로드캐스트 암호 시스템 중 가장 효율적인 것은 트리구조에서 Subset Difference(SD) 기법을 이용한 것으로, 이를 구체화하기 위해 유사난수생성기(PRG: Pseudo-Random Generator)와 비밀분산(SS: Secret Sharing) 방식을 이용한 두 가지 방법이 존재한다. 2-SD 기법은 SD 기법을 일반화하는 것으로 하나의 집합에서 두 개의 부분집합을 동시에 탈퇴시킬 수 있는 방법이다. 2-SD 기법의 장점으로는 SD 기법에 비해 전송량을 더 줄일 수 있다는 것이다. 그러나 현재까지 PRG나 SS 기반에서 2-SD 기법을 설계한 결과는 알려지지 않았다. 본 논문에서는 2014년 Jae Hwan Lee [9] 등이 제시한 SS 기반의 SD 기법을 확장하여 SS 기반의 2-SD 기법을 설계한다. 제안된 기법은 기존 SS 기반의 SD 기법에서 요구하는 암호문 헤더 전송량의 약 25% 줄이는 효과가 있다. 또한 암호 이론적으로 본 논문의 결과는 증명 가능한 2-SD 기법을 최초로 제시한 것이다. 브로드캐스트 암호시스템 [1] 은 한명의 송신자가 다수의 권한이 있는 수신자에게 메시지를 안전하게 전송할 수 있는 방법이다. 정당한 권한이 없는 사용자는 메시지를 암호화한 암호문에 접근하더라도 내용을 알 수 없어야 하는데, 이를 위해 브로드캐스트 암호시스템에서는 정당한 권한이 있는 사용자들만 구할 수 있는 그룹키를 이용하여 메시지를 암호화한다. 이러한 접근 제어 기능은 위성 TV, PPV (pay-per-view TV), DRM(Digital Right Management) 등의 실제 시스템에 적용되고 있다. 브로드캐스트 암호시스템의 효율성은 암호문 전송량, 사용자의 비밀키 저장량, 그리고 그룹키 계산을 위한 연산량 측면에서 분석이 된다. 세 가지 효율성 요소 중 짧은 전송량을 갖는 것이 가장 중요한 것으로 간주되는데, 그 이유는 일반적으로 브로드캐스트 암호시스템이 대규모 사용자(예를 들어 10 ⁶ ~10 ⁸ 명)를 대상으로 하므로 암호문의 전송량이 전체 네트워크 트래픽에 주는 영향이 크기 때문이다. 물론 전송량을 줄이더라도 나머지 저장량과 연산량이 적당한 범위 내에서 용인되어야 한다. 또한 브로드캐스트 암호시스템은 (공개키 없이) 지정된 송신자만 전송할 수 있는 대칭키 기반 기법 [2] 과 공개키를 이용하여 누구나 송신자가 될 수 있는 공개키 기반 기법 [3] [4] [5] 으로 분류된다. 지금까지 제안된 대칭키 기반 브로드캐스트 암호시스템 중 가장 효율적인 것으로는 2001년 Naor, Naor, Lotspiech [2] 가 제안한 이진트리 기반의 SD(Subset Difference) 기법(이하에서는 SD^PRG 기법으로 표기함)이다. 이 기법은 전체 사용자 수 n , 탈퇴자 수를 r 이라 할 때 O ( r )전송량, O (log ² n ) 저장량, 그리고 O (log n )연산량을 갖는다. SD 기법은 사용자의 비밀키와 Subset에 따른 그룹키를 생성하기 위해 유사난수생성기(PRG: Pseudo-random generator)의 일방향성을 이용하여 키를 분배한다. 이후 PRG를 이용한 키 분배 방식을 변형하여 세 가지 효율성 요소 간에 trade-off를 제공하는 기법들 [6] [7] [8] 이 제안되었다. 최근에는 이재환 등[9]이 Shamir의 (2, n )-비밀분산(Secret Sharing) 기법을 이용하여 키 분배를 하는 SD 기법(이하에서는 SD^SS 기법으로 표기함)을 제시하였다. 기존 PRG 기반에 비해 암호문 전송량의 길이는 다소 증가하지만 증명과정에서 나타나는 안전성 손실(security loss)이 적고, 그룹키 계산을 위한 연산량이 O (1)으로 전체 사용자 수나 탈퇴자 수에 무관하다는 장점이 있었다. 암호 이론적으로는 SD 기법의 키 분배를 위해 PRG가 아닌 새로운 접근방법 - 정보 이론적으로 안전한 비밀분산 기법 - 을 이용한 것이 의미 있는 결과였다. SD 기법에서는 탈퇴자 집합이 [ 그림 1 ]의 왼쪽처럼 S_i,j 형태의 부분집합들로 분할된다. 여기서 S_i,j 의미는 i 를 root로 하는 subtree에서 j 를 root로 하는 subtree를 제외한 집합이 수신자들이란 것이다. 이를 일반화하면 [ 그림 1 ]의 오른쪽처럼 S_i,j,k 형태의 부분집합들로 분할할 수 있다. 비슷하게 S_i,j,k 의미는 i 를 root로 하는 subtree에서 j 와 k 를 root로 하는 두 개의 subtree를 제외한 집합이 수신자임을 나타낸다. 2-SD 기법에서는 하나의 부분집합으로 두 개의 subtree를 처리하므로 직관적으로도 SD 기법에 비해서 전송량을 거의 절반으로 줄일 수 있을 것이라고 예상된다. 2006년 장지용 등 [10] 은 Naor 등이 제시한 SD^PRG 기법을 변형하여 2-SD 기법을 제안하였다. 그 2-SD 기법은 SD^PRG 기법에 비해 저장량과 연산량을 거의 희생시키지 않고 전송량을 1/2로 줄일 수 있다는 놀라운 결과를 제시하였다. 그러나 2014년 이재환 등 [11] 은 장지용 등이 제안한 2-SD 기법이 브로드캐스트 암호시스템 안전성 모델에서 기본적인 공격인 공모공격(collusion attack)에 전혀 안전하지 않다는 것을 보였다. 최근 Bhattacherjee 등 [8] 은 2-SD 기법과는 다른 접근방법으로, 이진트리를 k 진트리로 확장하여 PRG 기반의 SD 기법을 일반화하는 방법을 소개하였다. [8] 에서는 동일한 부모 아래 오직 같은 레벨에 있는 k 개의 자손 중 임의의 두 개 자손이 탈퇴되는 경우를 처리한다는 점에서 2-SD 기법과 비슷하다. 그러나 2-SD 기법은 ( k 진트리로 확장하더라도) 서로 다른 레벨에 있는 자손 중 임의의 두 개 자손을 탈퇴시킬 수 있다는 점에서 [8] 에서 제안한 기법보다 더욱 일반적이다. 더구나 [8] 은 worst case에 SD^PRG 기법보다 전송량을 줄이는 효과를 전혀 내지 못하고 있다. 현재까지 2-SD 기법을 구현한 브로드캐스트 암호시스템은 제안되지 않고 있다. 본 논문에서는 [9] 에서 소개된 비밀 분산 방식의 키 분배 아이디어를 확장하여 최초로 2-SD 기법을 설계하고자 한다. 새롭게 제안되는 2-SD 기법(이하에서는 2- SD^ss 기법으로 표기함)은 (2, n )-비밀분산과 추가적으로 (3, n )-비밀분산 방식을 도입하고, (3, n )-비밀분산을 이진트리의 서로 다른 레벨에 적용하여 키를 분배하는 방식을 도입한다. 2- SD^ss 기법은 O ( r )전송량, O (log ³ n ) 비밀키 저장량, O (1)복호화 연산량을 갖는다. SD^ss 기법과 비교하면 비밀키 저장량은 증가하지만, SD^ss 기법에서 요구하는 전송량의 약 1/4을 줄일 수 있는 효과가 있다. 또한 SD^ss 기법과 마찬가지로 전체 사용자 수나 탈퇴자 수에 관계없이 항상 일정한 O (1) 복호화 연산량을 제공한다. 예를 들어 SD^PRG 기법과 전송량을 비교하면, 전체 사용자수를 n =2 ³¹ , 탈퇴자 수를 r =2 ¹² 이라 할 때, SD^PRG : SD^ss : 2- SD^ss = 1 : 1.7 : 1.25의 비율을 보인다. [ 표 1 ]에서는 안전성과 효율성 측면에서 SD^PRG , SD^ss , 2- SD^ss 기법들을 비교한다. 암호 이론적으로는 기존 PRG 기반에서 설계할 수 없었던 2-SD 기법이 비밀분산 기반에서 설계가능하다는 것을 보이는 최초의 결과이다. 양의 정수 n 은 브로드캐스트 암호시스템이 수용하는 전체 사용자 수라고 하고, N 을 전체 사용자 집합이라고 하자. 즉 N ={1,2,..., n }이다. 브로드캐스트 암호시스템에 속하는 사용자는 1부터 n 가운데 하나의 수로 특정된다. R 은 N 의 부분집합으로서 탈퇴자들의 집합이라 하자. 브로드캐스트 암호의 목표는 전송 메시지 M 을 R 에 속하는 탈퇴자는 복호화할 수 없도록 하고, N ╲ R 에 속하는 사용자는 복호화할 수 있도록 하는 것이다. 약화된 안전성 모델에서는 탈퇴자=배제자임을 상기하자. 브로드캐스트 암호시스템은 세 가지 알고리즘 - 초기설정(setup), 암호화(Encryption), 복호화(decryption) - 으로 구성되어 있다. Subset Cover 방식은 먼저 전체 사용자 집합 N 에서 탈퇴자 집합 R 을 제외한 집합, 즉 N ╲ R 을 서로 겹치지 않은 disjoint 부분집합들의 모임인 S _i1 ,..., S_im 으로 분리된다. 즉 가 된다. 이러한 부분집합을 찾는 알고리즘을 CoverFinding 알고리즘이라 하고, R 을 입력받아 부분집합을 출력하는 것을 CoverFinding ( R )={ S _i1 ,..., S_im }으로 표현하자. 각각의 부분집합 S_j 들은 그에 대응하는 그룹키 L_j 가 할당되고, S_j 안의 모든 수신자는 L_j 를 유도해 낼 수 있다. 그리고 메시지를 암호화하기 위한 (일회용) 키 K 는 S _i1 ,..., S_im 들에 대응하는 그룹키 L _i1 ,..., L_im 들로 암호화되고, 전송하고자 하는 메시지는 K 를 이용하여 암호화한다. 보다 구체적으로 설명하면, Subset Cover 방식 하에서는 두 가지 종류의 대칭키 암호시스템이 사용된다. 이러한 Subset Cover 방식에 기반한 브로드캐스트 암호시스템은 다음의 세 알고리즘으로 설명할 수 있다. 모든 수신자 u 는 비밀키 d_u 를 받는다. S_i 에 속한 모든 수신자 u 는 자신의 비밀키 d_u 를 이용하여 S_i 에 대응되는 그룹키 L_i 를 유도할 수 있다. 여기서 그룹키 L_i 는 각각의 그룹 별로 독립적이고 랜덤한 값으로 할당하거나, 유사난 수 값을 이용하여 할당할 수도 있다. 수신자 u 는 다음과 같은 암호문을 수신하면, 자신의 비밀키 d_u 를 이용하여 복호화 절차를 실행한다. 본 논문에서 고려하는 브로드캐스트 암호시스템의 안전성 모델은 [9] 에서 제안하였고, 약화된 선택 암호문 중간공격(weak CCA1)이다. 선택 암호문 중간공격(CCA1: Chosen ciphertext and launch-time attack) [2] 은 대부분의 브로드캐스트 응용환경에서 충분하다고 간주되는 공격이다. 이 공격에서는 정당한 수신자의 집합 S = N ╲ R 에 암호문을 전송하는 경우, 집합 R 에 속하는 탈퇴자들이 자신들의 비밀키를 이용하여 공모공격(collusion attack)을 하더라도 암호문에 대응하는 평문의 내용을 알 수 없어야 한다. 또한 선택 암호문 공격이므로 공격자는 평문에 대응하는 암호문을 수집할 수 있는 능력뿐만 아니라, 암호문에 대응하는 평문을 수집할 수 있는 능력까지 주어진다. 단, weak CCA1 모델에서는 암호 질의 및 복호 질의에 사용된 탈퇴자들은 이후의 공격에서도 계속해서 탈퇴된 자들의 집합에 포함되어야 한다는 것이 일반적인 CCA1과 다른 점이다. 부연하면 R 에 속한 사용자들은 (시스템이 유지되는 한) 계속해서 탈퇴자로 남고, 메시지 전송 시 정당한 수신자 집합은 N ╲ R 로 결정되어야 한다. 따라서 수신자 집합 S 를 N ╲ R 에 속하는 부분집합으로서 동적으로 선택하는 것은 고려되지 않는다. 이러한 weak CCA1 안전성은 공격자 A 와 챌린저 B 사이의 (다음과 같은) 게임으로 정의된다. A 가 bit b를 정확하게 추측한 상황을 CGuess 로나타내자. 시스템 파라미터 λ 에 대해 A 의 advantage는 로 정의된다. 정의 1. 브로드캐스트 암호시스템이 weak CCA1 공격 환경에서 공격자 A 가 가지는 가 무시할 만한(negligible) 수준이라면, ‘브로드캐스트 암호시스템이 weak CCA1 공격에 안전하다’라고 말한다. 각각의 부분집합에 대응하는 그룹키 하에서 메시지 암호키 K 를 암호화하기 위해 필요한 대칭키 암호시스템 SKE =( E , D )의 안전성을 정의한다. CCA1 공격에 안전한 브로드캐스트 암호시스템을 설계하기 위해서는 SKE 역시 CCA1 공격에 안전해야 된다. 대칭키 암호의 CCA1 안전성은 공격자 A 와 챌린저 B 사이의 (다음과 같은) 게임으로 정의된다. A 가 bit b를 정확하게 추측한 상황을 CGuess 로 하자. 안전성 상수 λ 에 대해 A 의 advantage는 로 정의된다. 정의 2. 대칭키 암호시스템이 CCA1 공격 환경에서 공격자 A 가 가지는 이 무시할 만한(negligible) 수준이라면, 우리는 ‘대칭키 암호시스템이 CCA1 공격에 안전하다’라고 말한다. 메시지 암호키 K 가 결정되면 메시지 M 은 다른 대칭키 암호시스템 을 이용하여 암호화된다. CCA1 공격에 안전한 브로드캐스트 암호시스템을 설계하기 위해서는 가 one-time 선택 평문 공격(CAP: chosen-plaintext attack)에 안전해도 충분하다. 대칭키 암호의 one-time CPA 안전성은 공격자 A 와 챌린저 B 사이의 (다음과 같은) 게임으로 정의된다. A 가 bit b를 정확하게 추측한 상황을 CGuess 로 하자. 안전성 상수 λ 에 대해 A 의 advantage는 로 정의된다. 정의 3. 대칭키 암호시스템이 one-time CPA 공격 환경에서 공격자 A 가 가지는 이 무시할 만한(negligible) 수준이라면, 우리는 ‘대칭키 암호시스템이 onetime CPA 공격에 안전하다’라고 말한다. 본 논문에서 필요한 비밀분산(SS: Secret Sharing) 기법은 Shamir의 다항식 기반 (2, n )-SS과 (3, n )-SS기법이다. p 를 다항식 설정을 위한 소수(prime)라 하자. (2, n )-SS의 경우, 1차 다항식 f ( x )= ax + K ∈ Z_p [ x ]를 선택한다. 여기서 a ∈ Z_p 는 랜덤하게 선택된 값이고, 상수항 K ∈ Z_p 는 공유하고자 하는 비밀값이라 하자. 서로 다른 n 개의 값 x ₁ ,..., x_n 에 대하여 f ( x ₁ ),..., f ( x_n )을 share라 하면, 비밀 값 K 는 전체 n 개의 share 중 2개 이상의 값을 알면 복구할 수 있다. 여기서 K 를 효율적으로 복구하기 위해 Lagrange 보간법을 사용할 수 있다. (3, n )-SS 기법에서는 2차 다항식 g ( x )= bx ² + cx + K ∈ Z_p [ x ]를 선택한다. 여기서 b , c ∈ Z_p 는 랜덤하게 선택된 값이고, 상수항 K ∈ Z_p 는 공유하고자 하는 비밀값이다. 이 경우 n 개의 share g ( x ₁ ),..., g ( x_n ) 중 3개 이상의 값을 갖는 경우에만 비밀키 K 값을 복구할 수 있고, 2개 이하의 share 값을 아는 경우에는 K 에 대한 어떠한 정보도 정보 이론적으로 알 수 없다. 이러한 K 의 안전성은 공격자 A 와 챌린저 B 사이에서 이루어지는 다음과 같은 게임으로 정의된다. B 는 랜덤 bit b ∈{0,1}을 선택한다. (2, n )-SS의 경우, b=1인 경우에는 ( f ( x_i ), x_i , K )를 A 에게 주고, b=0인 경우는 랜덤한 R_K ∈ Z_p 를 선택하여 ( f ( x_i ), x_i , R_K )를 A 에게 준다. 여기서 x_i 는 A 가 임의로 선택한 값이다. 이 게임에서 A 가 bit b를 정확하게 추측한 상황을 CGuess 로 하자. 다항식 f 는 A에게 정보 이론적으로 K 에 대한 어떠한 정보도 노출하지 않는다. 따라서 |Pr[ CGuess ]-1/2|=0이 된다. 따라서 다음과 같은 식을 얻는다. 마찬가지로 (3, n )-SS의 경우에도, ( g ( x_j ), g ( x_k ), x_j , x_k , K )와 ( g ( x_j ), g ( x_k ), x_j , x_k , R_K )이 주어지는 게임을 고려할 수있다. 여기서 x_j 와 x_k 는 반드시 달라야 하고, x_i , x_j , x_k 는 A 가 임의로 선택한 값이다. 다항식 g 는 정보 이론적으로 K 에 대한 어떠한 정보도 노출하지 않으므로 |Pr[ CGuess ]-1/2|=0이 된다. 따라서 다음과 같은 식을 얻는다. 각 사용자는 이진트리 구조에서 leaf노드에 대응된다고 하자. 본래 Naor, Naor, Lotspiech [2] 가 제안한 SD(Subset Difference) 기법은 임의의 subtree에서 그 내부에 있는 하나의 노드를 root로 하는 부분집합을 탈퇴시키는 것이었다. 그러나 2-SD 기법은 임의의 노드를 root로 하는 subtree에서 두개의 부분집합을 동시에 탈퇴시킬 수 있는 기법이다. [ 그림 2 ]에서 보면, i 노드를 root로 할 때 j 와 k 노드를 root로 하는 두 개의 부분집합을 탈퇴시킬 수 있음을 의미한다. 2-SD 기법의 장점으로는 하나의 ( i 노드에 대응하는) 그룹키로 두 개의 부분집합을 처리할 수 있기 때문에, 그룹키에 대응하는 부분집합의 개수가 줄어들고 이는 결과적으로 SD 기법에 비해 암호문의 길이가 짧아진다는 것이다. 2-SD 기법이 SD 기법의 한 가지 확장된 형태로 볼 수 있으나, 2-SD 기법을 설계하는 것은 그리 간단하지 않다. 현재까지 SD 기법을 설계하는 방법으로는 유사난수생성기(PRG: Pseudo-random generator)를 이용한 것과 비밀분산(SS: Secret Sharing)을 이용한 두 가지 방법이 있다. SD 기법에 필요한 사용자의 비밀키 및 각 부분집합에 대응하는 그룹키를 생성하기 위해, PRG를 이용한 방법은 각 root노드에서 하위 노드로 향하는 경로 상에서 PRG의 일방향성을 이용하였고, SS를 이용한 방법은 각 root노드에서 하위 depth별로 독립적인 일차 다항식을 설정하고 (2, n )-SS를 이용하였다. 이에 비해 2-SD 기법을 설계하는 방법은 현재까지 제안되지 않고 있다. Bhattacherjee 등이 [8] 에서 제시한 기법은 PRG를 이용한 매우 제한적인 형태의 2-SD 기법으로서, 삼진트리 위에서 하나의 노드 아래에 있는 동일한 레벨의 3개 자손노드 중 두 개의 노드만을 (또는 그 두 개의 노드를 root로 하는 부분집합들을) 탈퇴시키는 형태이다. 본 논문에서는 SS를 이용하여 2-SD 기법을 설계할 수 있음을 보인다. [9] 에서 제시된 SD^ss 기법을 확장하여 2-SD 기법에 맞도록 새로운 키 분배방식과 Coverfinding 알고 리즘을 제안한다. 제안된 2- SD^ss 기법은 전체 사용자 수를 n , 탈퇴자 수를 r 이라 할 때, O ( r )의 전송량, O (log ³ n )의 비밀키 저장량, 그리고 O (1)의 복호화 연산량을 보인다. 이 결과는 SD^ss 기법이 O ( r )의 전송량, O (log ² n )의 비밀키 저장량, 그리고 O (1)의 복호화 연산량을 갖는 것에 비하면, 저장량 측면에서 더 나빠진 성능을 갖는 것으로 보일 수 있다. 그러나 실제 전송량은 보안 파라미터 k 에 대해 최악의 경우(worst case) 2- SD^ss 기법이 약 3 r × k bits인데 비해, SD^ss 기법이 약 4 r × k bits를 갖게 되어, 2- SD^ss 기법이 SD^ss 기법에 비해 약 25% 짧아진 전송량을 갖게 된다. 2- SD^ss 기법을 설계하는 핵심 아이디어는 이진트리 구조에서 2차 다항식 f ( x )= ax ² + bx + K ∈ Z_p [ x ]를 이용한 (3, n )-SS를 도입하는 것이다. [ 그림 2 ]과 같이 i 노드를 root로 하는 subtree에서 j 노드와 k 노드 아래의 후손들을 제외하는 경우를 생각하자. 이 경우 탈퇴자를 제외한 수신자 집합을 S_i,j,k 로 표현하자. 여기서 중요한 점은 1) j 노드와 k 노드는 동일한 레벨에 존재하지 않아도 된다는 것, 2) j 노드를 root로 하는 subtree는 i 노드의 왼쪽 자손 쪽에, 그리고 k 노드를 root로 하는 subtree는 i 노드의 오른쪽 자손 쪽에 위치한다는 것이다. 즉 i 노드를 기준으로 왼쪽과 오른쪽 자손에 각각 하나의 탈퇴자 집합이 있다. 1) S_i,j,k 를 위해서는 j 노드와 k 노드의 후손들을 배제하는 하나의 그룹키를 생성하는 것이 필요한데, 이를 위해 2차 다항식 f ( x )= ax ² + bx + K ∈ Z_p [ x ]를 이용한다. 이 다항식은 [ 그림 2 ]에서 빨간색 점선으로 표시된, i 노드의 왼쪽인 j 노드 레벨과 i 노드의 오른쪽인 k 노드 레벨에 대응하는 다항식이다. 또한 상수항 K 는 i 노드에서 j 노드와 k 노드 레벨에 대응하는 그룹키로 설정된다. 각 사용자는 해당 레벨에 대응하는 노드의 함수값을 사전에 받게 되고, 암호문 생성 시 S_i,j,k 를 위해서는 [ f ( j ), f ( k ), E_K ( K ′)]의 값이 계산된다. 여기서 K ′는 메시지 암호화 키이다. 이 경우 S_i,j,k 에 속하는 사용자는 자신이 받은 ( j 노드와 k 노드에 대응되지 않는) 함수값과 f ( j ), f ( k )를 이용하여 그룹키 K 를 복구할 수 있고, j 노드와 k 노드 아래의 탈퇴자들은 두 개의 함수값만 갖게 되어 K 를 복구할 수 없게 된다. 위에서 기술한 아이디어는 기존 SD^ss 기법에서 1차 다항식을 이용한 (2, n )-SS을 확장한 것으로 볼 수 있다. SD^ss 기법이 root노드인 i 노드에서 동일한 depth에 있는 레벨만을 (2, n )-SS로 다룬 것에 비해, 2- SD^ss 기법에서는 i 노드 기준으로 좌우의 서로 다른 (또는 동일한) depth에 있는 레벨을 (3, n )-SS로 다루는 것이다. 당연히 i 노드에서 동일한 depth에 있는 레벨을 ((3, n )-SS로) 다루는 것도 포함한다. 그러나 S_i,j,k 부분집합은 (3, n )-SS을 이용하게 됨으로 [ f ( j ), f ( k ), E_K ( K ′)]에서 보듯, 복호화 연산을 위해 2개의 함수값을 전송해야 한다. 이는 SD^ss 기법이 [ f ( j ), E_K ( K ′)]처럼, S_i,j 부분집합별로 하나의 함수값을 전송하는 것에 비해 f ( k )와 같은 함수값을 추가로 전송하는 부담이 있다. 그 러나 2- SD^ss 기법에서는 암호문 작성에 필요한 부분집합의 개수가 상당히 줄어들게 되어, 결과적으로 암호문 전송량이 줄어드는 효과를 가진다. S_i,j,k 처럼 N ╲ R 을 disjoint한 부분집합으로 분할하기 위 해서는 새로운 Coverfinding 알고리즘이 필요하게 된다. 새로운 Coverfinding 알고리즘 역시 기존 SD^ss 기법에서처럼 탈퇴자 집합 R 을 입력받아 N ╲ R 의 사용자들을 disjoint한 부분집합으로 분할한다. 기본적으로 새로운 Coverfinding 알고리즘이 S_i,j,k 형태의 부분집합을 출력하지만, 특수한 경우에는 기존 SD^ss 기법에서처럼 S_i,j 형태의 부분집합도 출력한다. 여기서 특수한 경우는 임의의 i 노드를 root로 하는 subtree에서 i 노드의 왼쪽 자식노드 ( i.lchild 로 표기) 또는 오른쪽 자식노드( i.rchild 로 표기)가 탈퇴자 집합의 노드를 가리킬 때이다. 이 경우는 S_i,j,k 보다 S_i.rchild,j 또는 S_i.lchild,j 집합으로 암호문을 구성하는 것이 암호문 길이를 줄일 수 있기 때문이다. 2) 이것은 다음의 세 가지를 의미한다. 1) 사용자의 비밀키를 부여할 때, S_i,j,k 형태에 대응하는 2차 다항식을 이용한 비밀키 뿐만 아니라 S_i,j 형태에 대응하는 1차 다항식을 이용한 비밀키를 생성해야 한다. 2) 사용자의 비밀키를부여할 때, i 노드기준으로 i.lchild 노드 레벨과 오른쪽 편 레벨에 대응하는 2차 다항식들은 고려할 필요가 없다는 것이다. 마찬가지로 i.rchild 노드 레벨과 왼쪽 편 레벨에 대응하는 2차 다항식들은 고려할 필요가 없다는 것이다. 3) 3) 2- SD^ss 기법의 Coverfinding 알고리즘은 S_i,j 형태의 집합들( S 1으로 표기)과 S_i,j,k 형태의 집합들( S 2로 표기)이 출력된다. 이를 Coverfinding ( R )={ S 1, S 2}로 표현하기로 하자. 더 구체적으로 S 1={ S _i1,j1 , S _i2,j2 ,...., S _iu,ju }이고 S 2={ S _i1,j1,k1 , S _i2,j2,k2 ,...., S _iw,jw,kw }의 모습으로 부분집합들을 포함하게 될 것이다. Coverfinding 알고리즘이 탈퇴자 집합 R 을 입력받게 되면 root노드와 탈퇴자에 해당하는 leaf노드들, 그리고 연결되는 내부 경로에 포함된 노드들로 구성된 Steiner Tree ST ( R )를 구성하고, 최종적으로 탈퇴자 처리된 root노드만 남을 때까지 반복 작업을 수행하여 N ╲ R 을 disjoint한 부분집합들로 분할하게 된다. 자세한 과정은 아래 2.1절에 유사코드로 서술되어 있다. let T := ST ( R ) let S 1:= ∅ let S 2:= ∅ while( root.state ≠ revocation ) { } return { S 1, S 2} 위 Coverfinding 알고리즘에서 while 반복문을 한번 수행할 때마다 두 개의 탈퇴자노드를 처리하고 한 개의 탈퇴자 노드가 새롭게 생성된다. 그러면서 1개의 부분집합이 S 1또는 S 2에 추가된다. 반복문은 root노드가 탈퇴자노드가 될 때까지 수행된다. root노드가 탈퇴자가 되려면 while문이 최소 r -1번 수행되어서 남아있는 탈퇴자수를 1개로 줄여야 한다. 그것이 root노드가 아니라면 한 번 더 수행하여 root노드를 탈퇴자 노드로 만들고 알고리즘을 종료한다. 따라서 while문은 최대 r 번 수행될 수 있다. worst case로 반복문이 수행될 때마다 S 1또는 S 2에 부분집합이 1개 추가된다고 하면, r 명의 탈퇴자에 대해 최대 r 개의 부분집합이 출력된다. 설명의 편의를 위해 다음을 가정한다. 1) 안전성 파라미터 λ 는 전체 사용자가 공유한다. 2) 메시지 암호키를 암호화하기 위한 대칭키 암호시스템 SKE =( E , D )와 메시지를 암호화하기 위한 대칭키 암호시스템 는 전체 사용자가 공유한다. 3) (AES 대칭키 암호를 사용하기 위해) 128 비트의 소수(prime) p 는 전체 사용자가 공유한다. 4) 전체 사용자 수는 n =2 ^k 이라 하자. 5) n 명을 leaf노드에 대응시키는 완전이진트리(full binary tree)를 구성하고, 이진트리의 모든 노드들은 Z_p 상의 원소에 고유하게 대응된다. 각 사용자가 저장하는 비밀값 d_u 의 사이즈를 분석하면, 의 원소 개수는 log n - j 개가 되고, j 는 0부터 log n -1까지 포함하므로, 전체 개수는 로 구할 수 있다. 의 원소 개수는 (log n - j -1) ² 개가 되고, j 는 0 부터 log n -2까지 포함하므로, 로 구할 수 있다. 결과적으로 , 즉 O (log ³ n )의 비밀키 저장량을 가지게 된다. 탈퇴자 집합 R 과 메시지 M 을 입력받으면, 송신자는 Ё_K ={0,1} ^t ↦{0,1} ^* 와 E_L ={0,1} ^l ↦{0,1} ^l 를 사용하여 아래와 같이 암호문을 생성한다. 전송량 측면에서 기존 SD^ss 기법과 비교할 때, 우선 Coverfinding 알고리즘이 달라짐으로 암호문 생성에 필요한 부분집합이 달라진다. 2- SD^ss 기법의 Coverfinding 알고리즘의 결과로 탈퇴자수 r 에 대하여 최악의 경우 r 개의 부분집합이 발생한다. 기존 SD^ss 기법의 2 r -1개에 비해 부분집합 개수를 대폭 줄였지만, S 2에 속하는 S_i,j,k 형태의 부분집합은 ( f_i,l,m ( j ), f_i,l,m ( k ), E _Ki,l,m ( K ))로 2개의 함수값을 전송하는 것을 고려해야한다. 수신자 u 는 다음과 같은 브로드캐스트 암호문을 수신하고 복호화 절차를 실행한다. N ╲ R 에 속하는 권한을 가진 사용자의 경우 2-4 과정 또는 6-8 과정 둘 중 하나를 통하여 그룹키를 구할 수 있으며, 두 개의 과정 모두 복호화 시 전체 사용자 수 n 이나 탈퇴자 수 r 에 관계없이 간단한 modular 연산을 필요로 한다. 정리 4. 대칭키 암호시스템이 SKE =( E , D )이 CCA1 공격에 안전하고, 대칭키 암호시스템 이 one-time CPA 공격에 안전하다고 가정하자. 이 경우 제안한 브로드캐스트 암호시스템은 weak CCA1 공격에 안전하다. 구체적으로 A 는 브로드캐스트 암호시스템에 대한 weak CCA1 공격 알고리즘이고, B 는 SKE 에 대한 CCA1 공격 알고리즘 또는 에 대한 one-time CPA 공격 알고리즘이라 하면, 여기서 v 은 A 가 선택하는 탈퇴자 집합에 의해 생성되는 부분집합의 최대 개수이고, w 는 2-SD의 setup 하에서 설정되는 전체 그룹키 개수이다. 증명) 브로드캐스트 암호시스템의 weak CCA1 안전성을 공격하는 공격자를 A 라 하자. 증명에서는 A 를 이용하여 SKE =( E , D )의 CCA1 안전성을 공격하거나 의 one-time CPA 안전성을 공격하는 알고리즘 B 를 설계할 것이다. 증명의 편의상 공격자가 선택한 탈퇴자 집합 R ^* 에 대해 CoverFinding ( R )={ S 2}라고 하자. 4) A 가 받는 챌린지 암호문 CT ^* 의 변화를 이용하여 다음 식 (11)과 같은 하이브리드 게임을 고려한다. 여기서 R _i1,l1m1 ,..., R _iv,lvmv 은 SKE 의 비밀키 공간에서 선택한 난수들이고, R ₁ , ... , R_m 은 SKE 의 메시지 공간에서 선택한 난수들이다. R _M^* 은 챌린지 메시지 M ^* 와 같은 길이를 갖는 난수 메시지이다. 각 게임 G_i 에서 공격자 A 가 정확하게 추측할 확률을 Pr[ G_i ]라 하자. 게임 G ₀ 는 메시지 M ^* 에 대한 암호문이 주어진 것으로 브로드캐스트 암호시스템의 weak CCA1 공격 환경이다. 반면 게임 G_F 는 난수 메시지 R _M^* 에 대한 암호문이 주어진 것으로 A 는 메시지에 대한 어떠한 정보도 얻을 수 없는 공격 환경이다. 안전성 증명은 G ₀ 에서 G_F 로 전이하는 과정에서 A 가 가지는 advantage가 무시할 만한(negligible) 것임을 보이는 것으로 이루어진다. 증명) A 는 브로드캐스트 암호시스템에 대한 weak CCA1 공격을 수행한다. B 는 S _i1,j1,k1 에 대응하는 그룹키를 제외하고 setup 과정과 동일하게 비밀키를 생성한다. B 는 챌린지로 받은 ( f ( j ₁ ), f ( k ₁ ), j ₁ , k ₁ , T ) 값을 S _i1,j1,k1 에 대응하는 질의에 이용한다. (여기서 j ₁ , k ₁ 은 B 가 선택한 값이다.) S_i 은 i 을 root로 하는 subtree의 leaf 노드 사용자 집합이라 하자. 1) 사용자 u 가 u ∉ S _i1 인 경우, u 의 비밀키 질의는 B 가 (관련된 키를 알고 있으므로) 쉽게 응답할 수 있다. u 가 u ∈ S _i1 이고 ( u ∈ S _j1 또는 u ∈ S _k1 )인 경우, u 의 비밀키 질의는 j ₁ 노드가 속한 레벨에 대응하는 다항식 값으로 f ( j ₁ )을 이용하고 k ₁ 노드가 속한 레벨에 대응하는 다항식 값으로 f ( k ₁ )을 이용한다. 2) u 가 u ∉ S _i1 인 경우, A 의 암호 복호) 질의는 B 가 u 의 비밀키를 생성하여 대응한다. u 가 u ∈ S _i1 이고 ( u ∈ S _j1 또는 u ∈ S _k1 )인 경우, A 의 암호(복호) 질의는 T 를 그룹키로 응답한다. A 가 u 의 비밀키 질의 시 u ∈ S _i1 이고 ( u ∉ S _j1 그리고 u ∉ S _k1 )인 경우, j ₁ 노드와 k ₁ 노드 레벨에 동시에 대응하는 (계수를 모르는) 다항식 f ( • )를 이용하여 비밀키를 응답해야 한다. 이 경우 B 는 a × ( j ₁ ) ² + b × j ₁ + c = T ∈ Z_p 와 a × ( k ₁ ) ² + b × k ₁ + c = T ∈ Z_p 를 만족하는 a , b , c ∈ Z_p 를 랜덤하게 선택한 후, j ₁ 과 k ₁ 노드 레벨에 대응하는 다항식을 f ( x )= ax ² + bx + c ∈ Z_p [ x ]로 사용한다. 이러한 비밀키 질의가 발생하면 S _i1,j1,k1 는 더 이상 챌린지 단계에서 사용되지 않고, S _i1,j1,k1 가 두 개의 부분집합으로 분할된다. 그러므로 이후의 게임진행은 ( S _i1,j1,k1 가 두 개의 부분집합으로 분할된) G ₀ 와 G ₁ 이 B 의 챌린지값 ( f ( j ₁ ), f ( k ₁ ), j ₁ , k ₁ , T )과는 무관하게 동일한 (statistically identical) 게임이 된다. 5) 또한 암호(복호) 질의 시 수반되는 탈퇴자 집합들을 누적하는 과정에서 그때까지의 총 탈퇴자 집합이 u ∈ S _i1 이고 ( u ∉ S _j1 그리고 u ∉ S _k1 )인 사용자 u 를 적어도 한명 포함하는 경우에는, 위와 같이 임의의 a , b , c ∈ Z_p 로 다항식을 f ( x )= ax ² + bx + c ∈ Z_p [ x ]로 결정한 후 게임을 진행한다. 이 경우에도 weak CCA1 안전성 모델에서는 G ₀ 와 G ₁ 이 B 의 챌린지 값 ( f ( j ₁ ), f ( k ₁ ), j ₁ , k ₁ , T )과는 무관하게 동일한 게임이 되기 때문이다. 챌린지 단계에서 A 가 탈퇴자 집합 R ^* 와 M ^* 를 보내면, B 는 CoverFinding ( R ^* )를 수행하여 S _i1,j1,k1 ,...., S_iv,jv,kv 을 구한다. S _i1,j1,k1 에 대한 그룹키로 암호화할 때 B 는 자신이 챌린지로 받은 T 값을 이용한다. 다른 부분집합들에 대해서는 정상적인 그룹키로 메시지 암호키 K 를 랜덤하게 선택한 후 다음과 같이 CT ^* 를 구성한다. T 가 ( f ( j ₁ ), f ( k ₁ ))의 상수항이면 A 는 S _i1,j1,k1 의 그룹키가 T = K _i1,l1,k1 인 G ₀ 에서 공격을 수행하는 것이고, T 가 다항식의 상수항과 관계없는 난수이면 A 는 S _i1,j1,k1 의 그룹키가 R _i1,j1,k1 인 G ₁ 에서 공격을 수행하는 것이다. 따라서 G ₀ 와 G ₁ 을 구별하는 A 의 공격능력은 2차 다항식 비밀분산 기법의 상수항을 구분하는 B 의 능력으로 전환된다. 그러나 비밀분산 기법의 상수항을 구분하는 문제는 A 의 능력과 관계없이 advantage의 차가 0이다. (II. 6절 참고) 증명) A 는 브로드캐스트 암호시스템에 대한 weak CCA1 공격을 수행한다. B 는 S _i1,j1,k1 에 대응하는 그룹키를 제외하고 setup 과정과 동일하게 비밀키를 생성한다. S _i1,j1,k1 에 대응하는 그룹키는 B 가 CCA1 공격을 하는 대칭키 암호시스템 SKE 의 비밀키로 한다. 1) 사용자 u 가 u ∉ S _i1 인 경우, u 의 비밀키 질의는 B 가 (관련된 키를 알고 있으므로) 쉽게 응답할 수 있다. u 가 u ∈ S _i1 이고 ( u ∈ S _j1 또는 u ∈ S _k1 )인 경우, u 의 비밀키 질의는 j ₁ 노드의 레벨 l ₁ 과 k ₁ 노드의 레벨 m ₁ 에 대응하는 임의로 선택된 다항식 f _i1,l1,m1 ( x )을 이용하여 응답한다. 여기서 레벨 l ₁ 과 레벨 m ₁ 에 대응하는 그룹키는 SKE 의 비밀키임을 상기하자. u 가 u ∈ S _i1 이고 ( u ∉ S _j1 그리고 u ∉ S _k1 )인 경우, B 가 모르는 SKE 의 비밀키가 상수항이 되도록 다항식 f _i1,l1,k1 ( x )의 값을 결정할 수 없으므로 게임을 중단(abort)한다. 2) u 가 u ∉ S _i1 인 경우, A 의 암호(복호) 질의는 B 가 u 의 비밀키를 이용하여 대응한다. u 가 u ∈ S _i1 이고 j ₁ 노드와 k ₁ 노드의 레벨에 대응하는 그룹키를 이용하여 암호(복호)화 할 경우, B 는 자신의 챌린저에게 암호(복호) 질의를 하고 그 결과를 A 에게 보낸다. u 가 u ∈ S _i1 이고 j ₁ 노드와 k ₁ 노드의 레벨에 대응하지 않는 그룹키를 이용할 경우 B 는 (관련된 키를 알고 있으므로) 쉽게 응답할 수 있다. 챌린지 단계에서 A 가 탈퇴자 집합 R ^* 와 M ^* 를 보내면, B 는 CoverFinding ( R ^* )를 수행하여 S _i1,j1,k1 ,...., S_iv,jv,kv 을 구한다. S _i1,j1,k1 에 대한 암호문을 생성하기 위해 B 는 메시지 암호키 K 를 랜덤하게 선택한 후 B 의 챌린저에게 K 를 챌린지 값으로 보낸다. 그 결과로 받은 암호문을 T 라 하자. 이를 이용하여 B 는 CT ^* 를 다음과 같이 구성한다. T 가 K 를 암호화한 것이면 A 는 G ₁ 에서 공격을 수행하는 것이고, T 가 K 와 같은 길이의 난수 R ₁ 을 암호화한 것이면 A 는 에서 공격을 수행하는것이다. 따라서 위의 게임중단(abort)이 발생하지 않으면, G ₁ 와 을 구별하는 A 의 공격능력은 SKE 에 대한 CCA1공격을 하는 B 의 능력으로 전환된다. 여기서 abort가 발생하지 않을 확률은 2-SD의 setup 하에서 전체 그룹키 개수 w 중 한 개를 SKE 의 비밀키로 선택하는 것이므로 1/ w 가 된다. 즉 일 경우 A 의 공격능력을 B 의 공격능력으로 전환할 수 있다. 증명) Claim 1과 유사하게 증명할 수 있다. 탈퇴자 집합 R ^* 로 생성되는 부분집합의 최대 개수를 v 개 하면, v 개의 부분집합 각각에 대해 위 Claim 1, Claim 2, Claim 3의 증명을 유사하게 적용할 수 있다. 그 결과 이후의 하이브리드 게임들에 대해 아래의 Claim 4, Claim 5, Claim 6을 쉽게 증명할 수 있다. 증명) A 는 브로드캐스트 암호시스템에 대한 weak CCA1 공격을 수행한다. B 는 setup 과정과 동일하게 비밀키를 생성한다. 메시지를 암호화하는 의 비밀키에 대해 B 가 one-time CPA 공격을 하는 것임을 상기하자. B 가 (관련된 키를 알고 있으므로) 사용자 u 에 대한 비밀키 질의와 암호(복호)와 질의를 쉽게 응답할 수 있다. 챌린지 단계에서 A 가 탈퇴자 집합 R ^* 와 M ^* 를 보내면, B 는 CoverFinding ( R ^* )를 수행하여 S _i1,j1,k1 ,...., S_iv,jv,kv 을 구한다. B 는 각 부분집합에 대응하는 메시지 암호키 R ₁ ,..., R_m 을 선택한 후, M ^* 를 B 의 챌린저에게 챌린지 값으로 보낸다. 그 결과로 받은 암호문을 T 라 하자. 이를 이용하여 B 는 CT ^* 를 다음과 같이 구성한다. T 가 M ^* 를 암호화한 것이면 A 는 에서 공격을 수행하는 것이고, T 가 랜덤 메시지 R _M^* 을 암호화한 것이면 A 는 G_F 에서 공격을 수행하는 것이다. 따라서 와 G_F 을 구별하는 A 의 공격능력은 에 대한 one-time CPA공격을 하는 B 의 능력으로 전환된다. 위에서 전개한 하이브리드 게임은 랜덤 메시지 R _M^* 을 암호화한 것을 유지하면서 다시 각 부분집합에 대응하는 메시지 암호키를 R_i 에서 K 로 전환시키는 게임을 추가함으로써 완성된다. 이는 랜덤 메시지 R _M^* 을 암호화한 것을 유지하면서 G ₀ 에서 G_F 로 변환되는 과정을 반대로 전개하면 된다. 이 경우 G_i 에 대응하는 게임을 라 하자. 마지막 게임 은 G ₀ 와 같으면서도 M ^* 대신 R _M^* 을 암호화한 암호문이 된다. 결국 위 하이브리드 게임들을 종합하면 다음과 같은 식 (15)를 얻는다. 즉, 으로 정리 4의 증명이 완성된다. 제안한 2-SD 기법의 효율성을 기존 기법들과 비교한다. 편의상 PRG(Pseudo-Random Generator) 기반의 SD 기법 [2] 을 SD^PRG , SS(Secret Sharing) 기반의 SD 기법을 SD^ss [9] , 그리고 SS(Secret Sharing) 기반의 2-SD 기법을 2- SD^ss 로 표기한다. [ 표 2 ]는 1) 암호문 전송량, 2) 수신자의 비밀키 저장량, 3) 복호화 시 필요한 계산량 측면에서 SD^PRG , SD^ss , 2- SD^ss 기법들 간의 효율성을 비교한 것이다. 2- SD^ss 기법의 암호화 알고리즘은 ( R , M )을 입력받아 CoverFinding ( R )={ S ₁ , S ₂ }을 수행한 후 아래와 같은 암호문을 생성한다. 여기서 대괄호 [] 안의 값을 암호문 헤더(header)라 한다. 전송량 비교에서는 메시지 M 에 대한 암호문 Ё_K ( M )을 제외하고, 암호문의 헤더 길이만을 고려한다. SD^PRG 나 SD^ss 기법과 달리, 2- SD^ss 기법은 변형된 Coverfinding 알고리즘을 사용함으로써 탈퇴자 수 r 에 대해 최대 r 개의 부분집합이 (worst case로) 발생한다. r 개의 부분집합은 S 1 집합에 포함되는 S_i,j 형태로 또는 S 2 집합에 속하는 S_i,j,k 형태로 결정된다. S_i,j,k 형태의 부분집합은 S_i,j 에 비해 암호문 헤더에 1개의 함수값을 더 전송해야하며 index도 1개 더 전송되므로 overhead가 커지게 된다. 2- SD^ss 기법에 가장 불리하도록 암호문 길이를 분석하기 위해 부분집합이 모두 S_i,j,k 형태가 된다고 가정하자. 이 경우 암호문 헤더는 위 식 (17) 로 결정된다. S_i,j,k 형태의 부분집합은 S_i,j,k 마다 이를 표현하는 index는 i 노드와 j 노드 그리고 k 노드를 묶어 ( i , j , k )으로 표현한다. index 정보들 {( i_q , j_q , k_q )}는 [9] 와 마찬가지로 암호문 헤더에 포함되어 전송된다고 하자. 암호문 헤더에 포함되는 각 원소의 사이즈는 다음과 같다. 먼저 각index 원소를 표현하기 위해서는 ⌈log(2 n -1)⌉의 bits가 필요하다. 그 이유는 사용자 n 명이 leaf노드로 대응되는 완전이진트리에서 총 노드의 수는 2 n -1개가 되므로 하나의 노드를 표현하는데 ⌈log(2 n -1)⌉bits면 충분하기 때문이다. 따라서 index ( i , j , k )는 3⌈log(2 n -1)⌉ bits로 표현된다. 다음으로 각 부분집합에 주어지는 ( f_i,l,m ( j ), f_i,l,m ( k ), E_Ki,l,m ( K ))의 길이를 분석하면, 현재 상용화된 AES-128 대칭키 암호시스템을 고려하여 메시지 암호키 K 를 128bits로 할 때, K 를 표현하는 함수값도 동일한 128bits가 된다. 또한 E_Ki,l,m ( K )은 AES를 이용하여 128bits 길이의 한 개 block 암호화로 해결할 수 있으므로 128bits가 된다. 결과적으로 index ( i , j , k )와 ( f_i,l,m ( j ), f_i,l,m ( k ), E_Ki,l,m ( K ))의 길이는 (3⌈log(2 n -1)⌉+2×128)bits가 되고 Cover- finding 알고리즘이 worst case로 r 개의 부분집합을 생성할 수 있으므로 2- SD^ss 기법의 총 헤더 전송량은 (3⌈log(2 n -1)⌉+384× r bits를 갖는다. 2- SD^ss 기법의 이러한 암호문 헤더길이는 SD^ss 기법에 비해 확실히 더 짧아진 값이다. 이를 확인하기 위해 전체 사용자수를 n =2 ³¹ 이고 탈퇴자 수를 r =2 ¹² 이라 하자. 이 경우 SD^PRG 기법은 1572672bits(≈192KB), SD^ss 기법은 2621120bits(≈320KB)인데 비해 2- SD^ss 기법은 1966080 bits(≈240KB)이다. 즉 2- SD^ss 기법은 SD^ss 기법과 비교할 때, SD^ss 기법의 약 (320-240=80)/320 = 1/4의 암호문 헤더를 줄이는 효과를 볼 수 있다. 이러한 비율은 암호문 헤더 전송량의 기울기 값이 SD^PRG < SD^ss <2- SD^ss 이므로 탈퇴자의 수가 증가함에 따라서 더 커지게 된다. SD^PRG 기법과 비교하면, SD^ss 기법에서 약 320/192=1.7배 길었던 암호문 헤더를 2- SD^ss 기법에서는 약 240/192=1.25배 긴 암호문 헤더로 줄이게 된다. 사용자 u 가 저장하는 비밀키 사이즈는 3장에서 기술한 대로 개의 함수값을 저장해야 한다. 이 값은 SD^PRG 와 SD^ss 기법이 저장하는 개에 비해 증가한 값이다. 실제 저장량을 비교하기 위해 전체 사용자수를 n =2 ³¹ 이라 하고, 각각의 함수값을 128bits라 하자. SD^PRG 와 SD^ss 기법은 63616bits(≈7.8KB)인데 비해 2- SD^ss 기법은 1234176bits(≈151KB)로 약 151/7.8=19.4배의 저장량을 가져야 한다. 복호화에 필요한 연산량은 기존 SD^PRG 기법이 최대 log n 번의 PRG 함수를 계산해야 하는 것에 비해, SD^ss 와 2- SD^ss 기법은 Lagrange 보간법을 이용하여 Z_p 에서 (2, n )-SS 또는 (3, n )-SS 연산을 수행하면 된다. 여전히 전체 사용자 수 n 이나 탈퇴자 수 r 에 관계없이 O (1)의 복호화 연산량을 요구하므로 매우 빠른 복호화 시간을 보장할 수 있다. 본 논문에서는 [9] 에서 소개된 (2, n )-비밀분산과 SD(Subset Difference) 기법의 아이디어를 확장하여 2-SD 기법을 설계하는 방법을 제시하였다. 2-SD 기법 설계를 위해서는 (2, n )-비밀분산에서 확장된 (3, n )-비밀분산 기법을 이용하여 그룹키를 분배하는 아이디어를 새롭게 도입하였고, 2-SD 기법에 맞도록 Coverfinding 알고리즘을 수정하였다. 효율성 측면에서 새로운 2-SD 기법은 기존 SD^ss 기법에 비해 전송량을 약 25% 줄일 수 있는 효과를 보였다. 이는 SD^PRG 기법에 비해 (worst case로) 약 1.25배 긴 전송량을 갖는 것으로서 기존 SD^ss 기법이 1.7배 긴 전송량을 가진 것에 비해 개선된 결과이다. 이렇게 전송량을 줄이기 위해서는 저장량이 증가하는 단점이 있으나 최근 디바이스의 저장량을 고려하면 큰 문제가 되지는 않는다. 사용자의 복호화 연산량은 [9] 와 마찬가지로 여전히 O (1)으로 사용자 수나 탈퇴자의 수에 관계없다는 장점을 가진다. 이론적으로 본 논문의 결과는 비밀분산 기법을 이용하여 (안전성을 약화시키면서) 2-SD 기법을 설계할 수 있음을 보인다. 이후의 흥미 있는 연구는 유사난수생성수(PRG)를 이용하여 2-SD 기법을 설계할 수 있느냐 하는 것으로, 이 결과는 SD^PRG 기법을 새로운 각도에서 일반화하는 것이 될 것이다. 이 재 환 - 2009년 3월 ~ 현재 : 상명대학교 컴퓨터과학과 학사과정 - 주관심분야 : 브로드캐스트 암호, 전자서명 등 박 종 환 - 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 암호, 브로드캐스트 암호, 암호프로토콜 등