[go: up one dir, main page]

KR101362529B1 - 비밀 분배 및 재분배 방법 및 시스템 - Google Patents

비밀 분배 및 재분배 방법 및 시스템 Download PDF

Info

Publication number
KR101362529B1
KR101362529B1 KR1020070030022A KR20070030022A KR101362529B1 KR 101362529 B1 KR101362529 B1 KR 101362529B1 KR 1020070030022 A KR1020070030022 A KR 1020070030022A KR 20070030022 A KR20070030022 A KR 20070030022A KR 101362529 B1 KR101362529 B1 KR 101362529B1
Authority
KR
South Korea
Prior art keywords
secret
authentication information
node
sub
new
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020070030022A
Other languages
English (en)
Other versions
KR20080087573A (ko
Inventor
임형규
김종택
박세웅
김영욱
Original Assignee
재단법인서울대학교산학협력재단
삼성전자주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 재단법인서울대학교산학협력재단, 삼성전자주식회사 filed Critical 재단법인서울대학교산학협력재단
Priority to KR1020070030022A priority Critical patent/KR101362529B1/ko
Publication of KR20080087573A publication Critical patent/KR20080087573A/ko
Application granted granted Critical
Publication of KR101362529B1 publication Critical patent/KR101362529B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/085—Secret sharing or secret splitting, e.g. threshold schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Storage Device Security (AREA)

Abstract

본 발명은 암호화 시스템에 있어서, 특정 비밀을 제1 서브 비밀들로 구분하여 분배하는 비밀 제공 노드와, 상기 비밀 제공 노드로부터 상기 제1 서브 비밀들 중 하나의 제1 서브 비밀을 분배받고, 상기 하나의 제1 서브 비밀을 제2 서브 비밀들로 구분한 후, 상기 제2 서브 비밀들 중 하나의 제2 서브 비밀을 재분배하는 적어도 하나의 이전 비밀 공유 노드와, 상기 적어도 하나의 이전 비밀 공유 노드로부터 상기 하나의 제2 서브 비밀을 재분배받는 적어도 하나의 신규 비밀 공유 노드를 포함하며, 상기 적어도 하나의 이전 비밀 공유 노드는 상기 하나의 제1 서브 비밀의 인증 정보인 제1 인증 정보 및 상기 하나의 제1 서브 비밀을 저장한 후, 상기 하나의 제2 서브 비밀, 상기 제1 인증 정보 및 상기 하나의 제2 서브 비밀의 인증 정보인 제2 인증 정보를 상기 적어도 하나의 신규 비밀 공유 노드로 송신함을 특징으로 한다.
암호화 알고리즘, VSS, VSR, 비밀 분배

Description

비밀 분배 및 재분배 방법 및 시스템{METHOD AND SYSTEM FOR DISTRIBUTING AND REDISTRIBUTING SECRET}
도 1은 본 발명의 실시예에 따른 FVSR을 이용한 비밀 분배 및 재분배를 도시한 도면
도 2는 본 발명의 실시예에 따른 FVSR을 이용한 비밀 분배 및 비밀 재분배 과정을 도시한 흐름도
본 발명은 암호화 방법에 관한 것으로서, 특히 비밀 분배 및 재분배를 이용한 암호화 방법 및 그 시스템에 관한 것이다.
무선 통신 및 인터넷 기술이 발전함에 따라 안전한 정보 교환에 대한 욕구도 높아져 가고 있다. 이에 따라 다양한 암호화 알고리즘들이 개발되고 있다.
상기 암호화 알고리즘들은 비밀 분배, 비밀 재분배 및 인증과 관련된다. 이러한 상기 암호화 알고리즘들 중 샤미르(Shamir)의 (n,m) 임계치 암호화 방법은 비 밀 분배에 관한 알고리즘이다. 상기 샤미르의 (n,m) 임계치 암호화 방법에서는 비밀을 부분 비밀로 나누고, 나누어진 부분 비밀을 다수의 비밀 공유자들에게 분배한다. 즉, n명이 비밀 k를 부분적으로 공유하며, 상기 비밀 k를 재구성(reconstruction)하기 위해서 비밀 공유자 n명 중 임의의 m명이 모여 각각이 가지고 있는 부분 비밀을 함께 이용한다. 상기 샤미르의 (n, m) 임계치 암호화 방법은 외부에 (m-1)명에 해당하는 부분 비밀이 노출되더라도 비밀 k를 알아낼 수 없게 된다.
하지만, 시간이 지날수록 부분 비밀이 외부에 노출될 가능성은 점차 높아지게 된다. 따라서, 주기적 혹은 필요에 의해 부분 비밀 자체를 변경하거나 아니면 부분 비밀을 가진 비밀 공유자를 변경할 필요가 있다. 상기와 같이 부분 비밀 혹은 비밀 공유자를 변경하는 것을 '비밀 재분배(secret redistribution)'라 한다.
비밀 재분배에서 가장 중요한 이슈는 중간에 재구성된 비밀 k가 외부에 노출될 우려가 있기 때문에 상기 비밀 k를 재구성하는 과정을 없애는 것이다.
따라서, 이전에 부분 비밀을 가지고 있던 비밀 공유자(이전 비밀 공유자(old shareholder))는 자신의 부분 비밀을 이용하여 새로운 부분 비밀을 가지게 될 비밀 공유자(새 비밀 공유자(new shareholder))가 새로운 부분 비밀을 생성할 수 있도록 정보를 주게 된다. 이 때, 이전 비밀 공유자 중 최대 (m-1)명은 악의적인 비밀 공유자일 수 있다. 따라서, 새 비밀 공유자들은 자신이 받은 정보가 올바른 정보인지 확인할 필요가 있다. 이러한 비밀 재분배 방법을 '확인 가능한 비밀 재분배(Verifiable Secret Redistribution, 이하 'VSR'이라 칭함)'라고 한다.
그러면, 비밀 분배, 비밀 재분배 및 인증 각각의 알고리즘에 대해 보다 상세히 알아보기로 한다.
먼저 비밀 분배 알고리즘인 샤미르의 임계치 암호화 방법에 대해 설명하기로 한다.
소수 p>n에 대해
Figure 112007024115699-pat00001
는 p차 유한 필드(finite field)라 가정한다. 예를 들어, p=19인 경우,
Figure 112007024115699-pat00002
이 된다. 샤미르의 (n,m) 임계치 암호화 방법에서는 하나의 전체 비밀
Figure 112007024115699-pat00003
가 n개의 부분 비밀로 나뉘어져 서로 다른 노드(node), 즉 비밀 공유자들에 분배된다. 비밀이 숫자가 아닌 경우에는 해쉬(hash) 함수와 같은 적절한 방법을 이용하여 그 비밀을 숫자로 나타낼 수 있다.
비밀 공유자
Figure 112007024115699-pat00004
의 부분 비밀 si는
Figure 112007024115699-pat00005
의 원소이다. 부분 비밀 중 임의의 m 개만 알면 k를 재구성할 수 있도록 한다. 이러한 성질을 만족시키도록
Figure 112007024115699-pat00006
를 계산하기 위해서는 계수
Figure 112007024115699-pat00007
를 이용한 m-1차 다항식
Figure 112007024115699-pat00008
이 사용된다. F(0)=k가 되고,
Figure 112007024115699-pat00009
로 계산된다. 상기 m-1차 다항식의 결과값이 18을 초과하는 경우 모듈로 p(modulo p) 연산에 의한 나머지 값이 상기 다항식의 결과값이 된다.
Figure 112007024115699-pat00010
을 (n, m) 임계치 암호화 방법에 의해 비밀 k가 분배된 n개 비밀 공유 자들의 집합이라 하자. 그러면
Figure 112007024115699-pat00011
인 임의의
Figure 112007024115699-pat00012
을 이용해 k를 하기 수학식 1과 같이 재구성할 수 있다.
Figure 112007024115699-pat00013
상술한 바와 같은 비밀 분배 및 비밀의 재구성까지의 과정을 예를 들어 설명하기로 한다.
소수 p=19 라 가정하면
Figure 112007024115699-pat00014
이 된다. 샤미르의 (5, 3) 임계치 암호화 방법을 이용하여 비밀 k=11을 다섯의 비밀 공유자들이 공유한다고 가정한다. 상기 비밀 공유자들 각각의 식별자는 1,3,8,10,15라 가정한다. 즉
Figure 112007024115699-pat00015
이다. 비밀을 분배할 때
Figure 112007024115699-pat00016
차 다항식
Figure 112007024115699-pat00017
을 이용하면, 각 비밀공유자에 분배되는 부분 비밀은 f(1)=18, f(3)=5, f(8)=5, f(10)=18, f(15)=7이 된다. 비밀 k를 재구성하기 위해서는 비밀 공유자들 중 임의의 3명의 비밀 공유자들이 가진 부분 비밀을 알면 된다. 1, 8, 10 비밀 공유자들의 부분 비밀을 이용해 비밀 k를 재구성하는 경우, 집합
Figure 112007024115699-pat00018
에 대해 비밀 k는 하기 수학식 2와 같이 재구성 될 수 있다.
Figure 112007024115699-pat00019
한편, 모듈로 p 연산에서 나눗셈은 곱셈의 역으로 계산 가능하다. 예를 들어,
Figure 112007024115699-pat00020
이므로
Figure 112007024115699-pat00021
이 된다.
다음으로, 비밀 재분배 알고리즘인 Desmedt and Jajodia의 비밀 재분배 방법에 대해 설명하기로 한다.
분배된 부분 비밀을 업데이트하거나 부분 비밀을 가진 비밀 공유자를 변경하거나 임계치를 변경하기 위해 사용되는 방법이 Desmedt and Jajodia 의 비밀 재분배이다.
상기 비밀 재분배 방법을 사용하면 (n, m) 임계치 암호화 방법으로 분배되었던 비밀 k를
Figure 112007024115699-pat00022
임계치 암호화 방법으로 재분배가 가능하게 된다. 상기 방법을 사용하게 되면 재분배 과정 중에 비밀 k를 재구성 할 필요가 없게 된다.
이를 위해
Figure 112007024115699-pat00023
인 임의의
Figure 112007024115699-pat00024
을 선택하여 이전 비밀 공유자 i(
Figure 112007024115699-pat00025
)는 자신의 부분 비밀
Figure 112007024115699-pat00026
에 대해 샤미르의
Figure 112007024115699-pat00027
임계치 암호화 방법을 이용하여 준부분 비밀(subshares)
Figure 112007024115699-pat00028
를 생성하고 이를 재분배한다. 그러면 새 비밀 공유자 j는 자신의 부분 비밀
Figure 112007024115699-pat00029
을 하기 수학식 3을 이용하여 생성할 수 있다.
Figure 112007024115699-pat00030
그러면, 비밀 재분배에 대해 예를 들어 보다 상세히 설명하기로 한다. 전술한 샤미르의 (5, 3) 임계치 암호화 방법에서 비밀 k=11이 1, 3, 8, 10 및 15의 식별자를 가지는 다섯의 이전 비밀 공유자들에게 부분 비밀로 분배되었다. 각 이전 비밀 공유자들은 (4, 2) 임계치 암호화 방법으로 2, 5, 7, 12의 넷의 새로운 비밀 공유자들에게 부분 비밀을 재분배한다고 가정한다.
따라서, 1번 이전 비밀 공유자는 다항식
Figure 112007024115699-pat00031
를 이용하여 준부분 비밀
Figure 112007024115699-pat00032
,
Figure 112007024115699-pat00033
,
Figure 112007024115699-pat00034
,
Figure 112007024115699-pat00035
를 계산하고, 계산된 준부분 비밀들을 2, 5, 7, 12의 식별자를 가지는 새로운 비밀 공유자들에게 전달한다. 새로운 비밀 공유자들 각각은 전달받은 상기 준부분 비밀들과 상기 수학식 3을 이용하여 자신의 부분 비밀을 계산할 수 있다.
다음으로, 인증을 위한 알고리즘인 펠드만의 VSS(Feldman의 VSS(Verifiable Secret Sharing)) 방법에 대해 설명하기로 한다.
샤미르의 임계치 암호화 방법을 사용하는 경우, 비밀 공유자 i는 비밀 분배자로부터 전달받은 부분 비밀이 유효한지를 확인할 수 없다. 따라서, 상기 비밀 분배자는 부분 비밀을 위한 인증 정보를 상기 비밀 공유자에게 전달하여야 한다. 즉, 상기 비밀 제공자는
Figure 112007024115699-pat00036
을 이용하여 해당 비밀 공유자에게 분배할 부분 비밀을 생성하고, 인증 정보로
Figure 112007024115699-pat00037
을 계산하여 비밀 공유자 모두에게 브로드캐스팅(broadcasting) 한다. 여기서, g는 Zp의 생성자이 다. 즉,
Figure 112007024115699-pat00038
를 연속하여 계산하게 되면 이것이 Zp의 0이 아닌 모든 원소를 생성해 낼 수 있음을 의미한다. 따라서, 비밀 공유자 i는 하기 수학식 4를 이용하여 자신이 전달받은 부분 비밀의 유효성을 확인할 수 있다.
Figure 112007024115699-pat00039
그러면, 인증의 유효성 판단에 대해 예를 들어 보다 상세히 설명하기로 한다.
상술한 바와 같이, 다항식
Figure 112007024115699-pat00040
을 이용하여 비밀을 분배한 경우, 생성자 g=2를 이용하면 인증 정보는
Figure 112007024115699-pat00041
가 된다. 비밀 공유자는 전달받은 부분 비밀과 인증 정보를 이용하여 상기 수학식 4가 만족되는지 확인한다. 상기 수학식 4가 만족되지 않는 경우, 상기 비밀 공유자는 전달받은 부분 비밀이 유효하지 않은 것으로 판정한다. 만약, 악의를 가진 공격자가 부분 비밀
Figure 112007024115699-pat00042
를 임의의
Figure 112007024115699-pat00043
로 조작하는 것이 가능하다고 해도
Figure 112007024115699-pat00044
가 되는
Figure 112007024115699-pat00045
를 찾는 것은 매우 어렵다. 따라서 유효하지 않은 부분 비밀은 상기 수학식 4를 만족시킬 수 없다.
상술한 바와 같은 알고리즘들을 이용하여 데오도르 M. 용(Theodore M. Wong)은 상기 VSR 방법을 제안하였다. 상기 VSR은 비밀 재분배 과정에서 생성된 준부분 비밀이 유효한 부분 비밀로부터 생성된 것인지 확인하는 방법이다. Desmedt and Jajodia의 비밀 재분배 방법에서는 비밀 재분배 과정에서
Figure 112007024115699-pat00046
가 자신의 부분 비밀
Figure 112007024115699-pat00047
에 대해 유효한 준부분 비밀
Figure 112007024115699-pat00048
를 생성했는지를 펠드만의 VSS 방법을 이용하여 확인하고 있다. 그러나, 악의적인 비밀 공유자 i가 부분 비밀
Figure 112007024115699-pat00049
자체를 조작하여 다른 값으로 재분배를 수행했을 경우에는 이를 판별해낼 수 없다는 문제점이 존재한다.
상기 VSR 은 이전 비밀 공유자들이 최초 비밀 분배시에 계산했던
Figure 112007024115699-pat00050
를 계속해서 보관하고 새로운 비밀 공유자에게 전달한다. 그리고 비밀 재분배 과정에서 전달되는
Figure 112007024115699-pat00051
값을 이용해 하기 수학식 5와 같은 검사를 실시한다.
Figure 112007024115699-pat00052
만약, 상기 수학식 5를 만족하지 않는다면 B의 어떤 노드
Figure 112007024115699-pat00053
가 유효하지 않은
Figure 112007024115699-pat00054
를 보낸 것이 된다.
이와 같은 VSR 방법도 다음과 같은 두 가지 문제들을 가지고 있다.
1. 지수 함수적 시간 소요
이전 비밀 공유자 중에 악의적인 비밀 공유자가 존재할 경우, 비밀 재분배 과정이 완료될 때까지 지수 함수적인 시간이 걸린다. 즉, 악의적인 비밀 공유자가 유효하지 않은
Figure 112007024115699-pat00055
를 다른 비밀 공유자에게 보낸 경우, VSR 방법에서는 악의적인 비밀 공유자가 누구인지 알아낼 방법이 없다. 따라서, VSR 방법에서는 이전 비밀 공유자 중 무작위로 m개의 비밀 공유자들을 선택한 후, 모든 비밀 공유자들이 유효한
Figure 112007024115699-pat00056
를 보낼때까지 무작위 선택을 반복한다. 최악의 경우 비밀 재분배 과정이 완료되기까지
Figure 112007024115699-pat00057
회의 반복이 필요하다.
2. 악의적인 새 비밀 공유자의 처리 불가
VSR 방법에서는 악의적인 의도를 가진 새로운 비밀 공유자는 없다고 가정하고 있다. 만약, 악의적인 의도를 가진 새로운 비밀 공유자가 존재하는 경우, 상기 새로운 비밀 공유자는 비밀 재분배 과정에서 중지(abort) 메시지를 브로드캐스팅 할 수 있다. 이렇게 되면 비밀 재분배 과정을 완료할 수 없게 된다.
본 발명에 실시예에 따른 암호화 시스템은, 특정 비밀을 제1 서브 비밀들로 구분하여 분배하는 비밀 제공 노드와, 상기 비밀 제공 노드로부터 상기 제1 서브 비밀들 중 하나의 제1 서브 비밀을 분배받고, 상기 하나의 제1 서브 비밀을 제2 서브 비밀들로 구분한 후, 상기 제2 서브 비밀들 중 하나의 제2 서브 비밀을 재분배하는 적어도 하나의 이전 비밀 공유 노드와, 상기 적어도 하나의 이전 비밀 공유 노드로부터 상기 하나의 제2 서브 비밀을 재분배받는 적어도 하나의 신규 비밀 공유 노드를 포함하며, 상기 적어도 하나의 이전 비밀 공유 노드는 상기 하나의 제1 서브 비밀의 인증 정보인 제1 인증 정보 및 상기 하나의 제1 서브 비밀을 저장한 후, 상기 하나의 제2 서브 비밀, 상기 제1 인증 정보 및 상기 하나의 제2 서브 비밀의 인증 정보인 제2 인증 정보를 상기 적어도 하나의 신규 비밀 공유 노드로 송신함을 특징으로 한다.
삭제
삭제
또한 본 발명의 실시예에 따른 특정 비밀을 분배하는 비밀 제공 노드와, 비밀을 재분배하는 적어도 하나의 이전 비밀 공유 노드와, 재분배되는 비밀을 제공받는 신규 비밀 공유 노드가 존재하는 시스템에서, 암호화 방법은, 상기 적어도 하나의 이전 비밀 공유 노드가 상기 비밀 제공 노드로부터 상기 특정 비밀이 구분된 제1 서브 비밀들 중 하나의 제1 서브 비밀을 분배받고, 상기 하나의 제1 서브 비밀을 제2 서브 비밀들로 구분한 후, 상기 제2 서브 비밀들 중 하나의 제2 서브 비밀을 재분배하는 과정과, 상기 적어도 하나의 신규 비밀 공유 노드가 상기 적어도 하나의 이전 비밀 공유 노드로부터 상기 하나의 제2 서브 비밀을 재분배받는 과정과, 상기 적어도 하나의 신규 비밀 공유 노드가 상기 하나의 제1 서브 비밀의 인증 정보인 제1 인증 정보 및 상기 하나의 제1 서브 비밀을 저장한 후, 상기 하나의 제2 서브 비밀, 상기 제1 인증 정보 및 상기 하나의 제2 서브 비밀의 인증 정보인 제2 인증 정보를 상기 적어도 하나의 신규 비밀 공유 노드로 송신하는 과정을 포함한다.
이하, 본 발명의 바람직한 실시예를 첨부된 도면을 참조하여 상세히 설명한다. 하기의 설명에서는 본 발명의 동작을 이해하는데 필요한 부분만을 설명하며 그 이외의 배경 기술은 본 발명의 요지를 흩트리지 않도록 생략한다.
본 발명에서는 고속 및 인증이 강화된 비밀 분배 및 재분배 방법 및 그 시스템을 제공한다. 이하에서는 고속 및 인증이 강화된 비밀 분배 및 재분배에 대해 설명하기로 하며, 특히 본 발명에서는 고속 및 인증이 강화된 비밀 재분배 알고리즘을 FVSR(Fast Verifiable Secret Redistribution)이라 정의하기로 한다.
도 1은 본 발명의 실시예에 따른 FVSR을 이용한 비밀 분배 및 재분배를 도시한 도면이다.
도 1을 참조하면, 비밀 제공자, 즉 비밀을 제공하는 노드(100)는 다수의 이전 비밀 공유(old shareholder) 노드들 중 이전 비밀 공유 노드들(102, 104 및 106)로 각 해당 노드별에 대응하는 부분 비밀 및 인증 정보를 송신하고, 상기 이전 비밀 공유 노드들(102, 104 및 106)은 신규 비밀 공유(new shareholder) 노드들(112, 114 및 116)로 부분 비밀 및 인증 정보를 재분배한다.
도 2는 본 발명의 실시예에 따른 FVSR을 이용한 비밀 분배 및 비밀 재분배 과정을 도시한 흐름도이다.
도 2를 참조하면, 암호화 방법은 크게 초기화 단계와 재분배 단계로 구분할 수 있다. 본 발명에 따른 암호화 방법을 살펴보면, 초기화 단계에서는 종래의 VSR 방법에서 초기화 단계들 중 일부 단계가 수정되었으며, 재분배 단계는 본 발명에서 제안하는 FVSR을 이용하여 비밀 재분배를 수행한다. 도 2의 구체적인 설명에 앞서 다음과 같은 정의 및 가정을 한다.
비밀 k는 집합
Figure 112007024115699-pat00058
를 구성하는 성분들 중 하나에 해당하며, p는 소수라 가정한다.
Figure 112007024115699-pat00059
을 (n, m) 임계치 암호화 방법에 의해 비밀 k가 분배된 n개의 노드 집합이라 정의한다. 따라서, 이전 비밀 공유 노드 i는 상기 집합
Figure 112007024115699-pat00060
에 포함된다. 초기에 비밀 제공 노드(100)는
Figure 112007024115699-pat00061
를
Figure 112007024115699-pat00062
에 분배하기 위해 202단계 및 204단계를 수행한다.
즉, 202단계는 초기화 1단계로, 상기 비밀 제공 노드(100)는 다항식
Figure 112007024115699-pat00063
를 이용하여 부분 비밀
Figure 112007024115699-pat00064
를 계산하고, 계산된 부분 비밀
Figure 112007024115699-pat00065
를 해당 이전 비밀 공유 노드
Figure 112007024115699-pat00066
에 전송한다.
204단계에서 상기 비밀 제공 노드(100)는 초기화 2단계로 생성자 g를 이용하여 인증 정보
Figure 112007024115699-pat00067
를 계산하고, 계산된 인증 정보를 모든 이전 비밀 공유 노드들(102, 104, 106)로 브로드캐스팅(broadcasting) 한다.
다음으로 206단계 및 208단계는 이전 비밀 공유 노드가 수행하는 초기화 3 및 4단계에 해당한다.
206단계에서 이전 비밀 공유 노드들(102, 104, 106) 각각은 상기 수학식 3에 해당하는
Figure 112007024115699-pat00068
을 만족하는지를 판단하여 부분 비밀
Figure 112007024115699-pat00069
의 유효성 여부를 확인한다. 만약, 만족하는 경우 해당 이전 비밀 공유 노드는 'commit' 메시지를 브로드캐스팅 하고, 만족하지 않는 경우 'abort' 메시지를 브로드캐스팅 한다.
208단계에서 이전 비밀 공유 노드들(102, 104, 106) 각각은 자신을 제외한 다른 모든 이전 비밀 공유 노드들(102, 104, 106)로부터 상기 commit 메시지를 수신하면 부분 비밀
Figure 112007024115699-pat00070
와 인증 정보
Figure 112007024115699-pat00071
를 저장한다.
종래의 초기화 단계에서는 각 이전 비밀 공유 노드들이 자신에게 해당하는 부분 비밀
Figure 112007024115699-pat00072
와 인증 정보
Figure 112007024115699-pat00073
만을 저장하였지만, 본 발명에서의 각 이전 비밀 공유 노드들은 부분 비밀
Figure 112007024115699-pat00074
와 인증 정보
Figure 112007024115699-pat00075
를 저장한다. 이와 같이 하는 이유는 신규 비밀 공유 노드들이 이전 비밀 공유 노드가 실제 가지고 있는 부분 비밀을 이용하여 비밀 재분배를 수행하였는지 여부를 확인하기 위해 필요하다.
다음으로 210단계 내지 216단계는 비밀 재분배 과정으로, 210단계 및 212단계의 동작은 이전 비밀 공유 노드가, 214단계 및 216단계의 동작은 신규 비밀 공유 노드가 수행한다.
210단계에서 이전 비밀 공유 노드들(102, 104, 106) 각각은 다항식
Figure 112007024115699-pat00076
를 이용하여 부분 비밀
Figure 112007024115699-pat00077
의 준부분 비밀
Figure 112007024115699-pat00078
를 계산하고, 계산된 준부분 비밀을 신규 비밀 공유 노드들(112, 114, 116)로 전송한다. 종래의 비밀 재분배를 살펴보면, 이전 비밀 공유 노드들 중 일부인 m개의 이전 비밀 공유 노드들만이 비밀 재분배에 참여하였으나, 본 발명에서는 이전 비밀 공유 노드 전부가 비밀 재분배에 참여한다. 예를 들어 설명하면, 이전 비밀 공유 노드들이
Figure 112007024115699-pat00079
의 세 노드들이 존재하고 (n, m) 임계치 암호화 방법(여기서, n은 3이고 m은 2라고 가정)을 사용하는 경우, 종래에는
Figure 112007024115699-pat00080
에서 두개의 노드들, 즉
Figure 112007024115699-pat00081
혹은
Figure 112007024115699-pat00082
혹은
Figure 112007024115699-pat00083
만이 비밀 재분배에 참여하였으나, 본 발명에서는
Figure 112007024115699-pat00084
와 같이 모든 이전 비밀 공유 노드들이 비밀 재분배에 참여한다.
Figure 112007024115699-pat00085
의 모든 이전 비밀 공유 노드들 중 과반수는 선의의 비밀 공유 노드들이다. 따라서, 상기 선의의 이전 비밀 공유 노드들은 동일한 인증 정보를 브로드캐스팅 하기 때문에 신규 비밀 공유 노드들은 정확한 인증 정보를 알 수 있게 된 다.
212단계에서 이전 비밀 공유 노드들 각각은 인증 정보
Figure 112007024115699-pat00086
을 계산한 후, 계산된
Figure 112007024115699-pat00087
와 저장하고 있던 인증 정보
Figure 112007024115699-pat00088
를 모든 신규 비밀 공유 노드들(
Figure 112007024115699-pat00089
)로 브로드캐스팅 한다.
214단계에서 신규 비밀 공유 노드들 각각은 모든 이전 비밀 공유 노드들(
Figure 112007024115699-pat00090
)로부터 받은 인증 정보
Figure 112007024115699-pat00091
중에서 m개 이상이 동일한 정보
Figure 112007024115699-pat00092
을 이용하여 하기 수학식 6 및 7의 조건을 만족하는지 판정한다.
Figure 112007024115699-pat00093
Figure 112007024115699-pat00094
이전 비밀 공유 노드는 신규 비밀 공유 노드로 인증 정보
Figure 112007024115699-pat00095
를 전송했고, 이 두 조건을 만족시킨 i 중 그 값이 가장 작은 m개의 집합을
Figure 112007024115699-pat00096
라 하자. 한편, 신규 비밀 공유 노드들은 이전 비밀 공유 노드들로부터 수신한 인증 정보
Figure 112007024115699-pat00097
를 알고 있기 때문에
Figure 112007024115699-pat00098
를 이용하여 이전 비밀 공유 노드의 부분 비밀
Figure 112007024115699-pat00099
에 대한 유효성 검사를 쉽게 할 수 있다. 상기 신규 비밀 공유 노드가 수행한 유효성 검사의 실패시 해당하는 이전 비밀 공유 노드가 악의적인 비밀 공유 노드임을 알 수 있게 된다.
216단계에서 신규 비밀 공유 노드들 각각은 하기 수학식 8로 나타낼 수 있는 새로운 부분 비밀
Figure 112007024115699-pat00100
을 생성한 후 저장한다.
Figure 112007024115699-pat00101
여기서 상기 새로운 부분 비밀을
Figure 112007024115699-pat00102
라 하면, 상기 신규 비밀 공유 노드들 각각은 새로운 인증 정보
Figure 112007024115699-pat00103
을 하기 수학식 9를 이용하여 계산한 후 저장한다.
Figure 112007024115699-pat00104
본 발명의 상세한 설명에서는 구체적인 실시예에 관해 설명하였으나, 본 발명의 범위에서 벗어나지 않는 한도 내에서 여러 가지 변형이 가능함은 물론이다. 그러므로 본 발명의 범위는 설명된 실시예에 국한되지 않으며, 후술되는 특허청구의 범위뿐만 아니라 이 특허청구의 범위와 균등한 것들에 의해 정해져야 한다.
상술한 바와 같이, 본 발명에 따른 새로운 암호화 알고리즘은 종래의 비밀 재분배시 지수 함수적 시간이 증가하는 문제를 해결할 수 있다. 또한, 보다 강화된 인증 절차를 통해 악의적인 노드를 찾아낼 수 있는 이점이 존재한다.

Claims (11)

  1. 암호화 시스템에 있어서,
    특정 비밀을 제1 서브 비밀들로 구분하여 분배하는 비밀 제공 노드와,
    상기 비밀 제공 노드로부터 상기 제1 서브 비밀들 중 하나의 제1 서브 비밀을 분배받고, 상기 하나의 제1 서브 비밀을 제2 서브 비밀들로 구분한 후, 상기 제2 서브 비밀들 중 하나의 제2 서브 비밀을 재분배하는 적어도 하나의 이전 비밀 공유 노드와,
    상기 적어도 하나의 이전 비밀 공유 노드로부터 상기 하나의 제2 서브 비밀을 재분배받는 적어도 하나의 신규 비밀 공유 노드를 포함하며,
    상기 적어도 하나의 이전 비밀 공유 노드는 상기 하나의 제1 서브 비밀의 인증 정보인 제1 인증 정보 및 상기 하나의 제1 서브 비밀을 저장한 후, 상기 하나의 제2 서브 비밀, 상기 제1 인증 정보 및 상기 하나의 제2 서브 비밀의 인증 정보인 제2 인증 정보를 상기 적어도 하나의 신규 비밀 공유 노드로 송신함을 특징으로 하는 암호화 시스템.
  2. 제1항에 있어서,
    상기 적어도 하나의 신규 비밀 공유 노드는,
    상기 제1 인증 정보 및 상기 제2 인증 정보를 이용하여 상기 하나의 제1 서브 비밀 및 상기 하나의 제2 서브 비밀에 대해 유효성 검사를 수행함을 특징으로 하는 암호화 시스템.
  3. 삭제
  4. 삭제
  5. 제1항에 있어서,
    상기 적어도 하나의 신규 비밀 공유 노드는 상기 제2 인증 정보를 이용하여 제3 서브 비밀을 생성함을 특징으로 하는 암호화 시스템.
  6. 특정 비밀을 분배하는 비밀 제공 노드와, 비밀을 재분배하는 적어도 하나의 이전 비밀 공유 노드와, 재분배되는 비밀을 제공받는 신규 비밀 공유 노드가 존재하는 시스템에서, 암호화 방법에 있어서,
    상기 적어도 하나의 이전 비밀 공유 노드가 상기 비밀 제공 노드로부터 상기 특정 비밀이 구분된 제1 서브 비밀들 중 하나의 제1 서브 비밀을 분배받고, 상기 하나의 제1 서브 비밀을 제2 서브 비밀들로 구분한 후, 상기 제2 서브 비밀들 중 하나의 제2 서브 비밀을 재분배하는 과정과,
    상기 적어도 하나의 신규 비밀 공유 노드가 상기 적어도 하나의 이전 비밀 공유 노드로부터 상기 하나의 제2 서브 비밀을 재분배받는 과정과,
    상기 적어도 하나의 신규 비밀 공유 노드가 상기 하나의 제1 서브 비밀의 인증 정보인 제1 인증 정보 및 상기 하나의 제1 서브 비밀을 저장한 후, 상기 하나의 제2 서브 비밀, 상기 제1 인증 정보 및 상기 하나의 제2 서브 비밀의 인증 정보인 제2 인증 정보를 상기 적어도 하나의 신규 비밀 공유 노드로 송신하는 과정을 포함하는 암호화 방법.
  7. 제6항에 있어서,
    상기 적어도 하나의 신규 비밀 공유 노드가 상기 제1 인증 정보 및 상기 제2 인증 정보를 이용하여 상기 하나의 제1 서브 비밀 및 상기 하나의 제2 서브 비밀에 대해 유효성 검사를 수행하는 과정을 더 포함하는 암호화 방법.
  8. 삭제
  9. 삭제
  10. 제6항에 있어서,
    상기 적어도 하나의 신규 비밀 공유 노드가 상기 제2 인증 정보를 이용하여 제3 서브 비밀을 생성하는 과정을 더 포함하는 암호화 방법.
  11. 삭제
KR1020070030022A 2007-03-27 2007-03-27 비밀 분배 및 재분배 방법 및 시스템 Expired - Fee Related KR101362529B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020070030022A KR101362529B1 (ko) 2007-03-27 2007-03-27 비밀 분배 및 재분배 방법 및 시스템

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020070030022A KR101362529B1 (ko) 2007-03-27 2007-03-27 비밀 분배 및 재분배 방법 및 시스템

Publications (2)

Publication Number Publication Date
KR20080087573A KR20080087573A (ko) 2008-10-01
KR101362529B1 true KR101362529B1 (ko) 2014-02-14

Family

ID=40150207

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020070030022A Expired - Fee Related KR101362529B1 (ko) 2007-03-27 2007-03-27 비밀 분배 및 재분배 방법 및 시스템

Country Status (1)

Country Link
KR (1) KR101362529B1 (ko)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106452745B (zh) * 2016-09-27 2019-07-02 中国农业大学 一种秘密数据共享的验证方法及装置
CN115913545A (zh) * 2022-12-08 2023-04-04 联想(北京)有限公司 一种处理方法和电子设备
JP7428335B1 (ja) * 2023-06-26 2024-02-06 株式会社リーディングエッジ 秘密分散方法、秘密分散システム、秘密分散プログラム

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001003365A1 (en) 1999-07-06 2001-01-11 Matsushita Electric Industrial Co., Ltd. Distributed group key management scheme for secure many-to-many communication
KR20020040741A (ko) * 1999-07-06 2002-05-30 추후제출 축소 가능한 보안 그룹 통신용의 이중 암호화 프로토콜
KR20050054772A (ko) * 2003-12-06 2005-06-10 한국전자통신연구원 송수신 암호키를 분리하여 키를 재사용하는 방법

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001003365A1 (en) 1999-07-06 2001-01-11 Matsushita Electric Industrial Co., Ltd. Distributed group key management scheme for secure many-to-many communication
KR20020040741A (ko) * 1999-07-06 2002-05-30 추후제출 축소 가능한 보안 그룹 통신용의 이중 암호화 프로토콜
KR20050054772A (ko) * 2003-12-06 2005-06-10 한국전자통신연구원 송수신 암호키를 분리하여 키를 재사용하는 방법

Also Published As

Publication number Publication date
KR20080087573A (ko) 2008-10-01

Similar Documents

Publication Publication Date Title
US11316676B2 (en) Quantum-proof multiparty key exchange system, quantum-proof multiparty terminal device, quantum-proof multiparty key exchange method, program, and recording medium
CN113254410B (zh) 一种可证明安全的可公开验证多级多秘密共享方法及系统
EP4340295A2 (en) Computer implemented method and system for transferring access to a digital asset
KR100845018B1 (ko) 인증 시스템 및 원격분산 보존 시스템
JP5637991B2 (ja) ネットワークにおけるセキュア通信に関する方法、通信デバイス、ネットワーク及びコンピュータプログラム
CN107615285B (zh) 包括物理不可克隆功能和阈值加密的认证系统和装置
EP3410633B1 (en) Device and system with global tamper resistance
KR20230024369A (ko) 비밀 공유의 생성
KR20180115701A (ko) 지갑 관리 시스템과 연계된 블록 체인 기반 시스템을 위한 암호키의 안전한 다기관 손실 방지 저장 및 전송
CN111526197B (zh) 一种云端数据安全共享方法
CN101425902A (zh) 一个具有前向安全的门限数字签名方法与系统
EP3496331A1 (en) Two-party signature device and method
CN102263787B (zh) 动态分布式ca配置方法
WO2017167402A1 (en) Method for providing a space puzzle
WO2017030111A1 (ja) 計算システム、計算装置、その方法、およびプログラム
EP4254856A1 (en) Encryption communication system, encryption communication apparatus, and encryption communication method
Jarecki et al. An attack on the proactive RSA signature scheme in the URSA ad hoc network access control protocol
CN112368974B (zh) 用于在分布式基础架构中确保数据交换安全的方法
JP4305049B2 (ja) 秘密分散方法、秘密分散システム、及び分散演算装置
KR101362529B1 (ko) 비밀 분배 및 재분배 방법 및 시스템
JP2018005089A (ja) 分散値更新装置及び分散値更新プログラム、分散値計算装置及び分散値計算プログラム、分散値検証装置及び分散値検証プログラム
EP2847923A1 (en) Byzantine fault tolerance and threshold coin tossing
JP4776378B2 (ja) 複数鍵認証端末装置及び複数鍵認証管理装置及び複数鍵認証システム及びプログラム
JP2024541936A (ja) 閾値署名スキーム
CN110737907A (zh) 基于联盟链的抗量子计算云存储方法及系统

Legal Events

Date Code Title Description
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

R18-X000 Changes to party contact information recorded

St.27 status event code: A-3-3-R10-R18-oth-X000

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

A201 Request for examination
PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

R18-X000 Changes to party contact information recorded

St.27 status event code: A-3-3-R10-R18-oth-X000

D13-X000 Search requested

St.27 status event code: A-1-2-D10-D13-srh-X000

D14-X000 Search report completed

St.27 status event code: A-1-2-D10-D14-srh-X000

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

E13-X000 Pre-grant limitation requested

St.27 status event code: A-2-3-E10-E13-lim-X000

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

FPAY Annual fee payment

Payment date: 20170125

Year of fee payment: 4

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

P22-X000 Classification modified

St.27 status event code: A-4-4-P10-P22-nap-X000

FPAY Annual fee payment

Payment date: 20180130

Year of fee payment: 5

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 5

LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20190207

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20190207