동형 비밀 공유

Homomorphic secret sharing

암호학에서 동형 비밀 공유는 동형 암호화를 통해 비밀이 암호화된 비밀 공유 알고리즘의 일종이다.동형성(同形性)은 하나의 대수적 구조에서 구조가 보존되도록 같은 유형의 다른 구조로 변형하는 것이다.중요한 것은, 이것은 원본 데이터의 모든 종류의 조작에 대해, 변환된 데이터의 상응하는 조작이 있다는 것을 의미한다.[1]

테크닉

동형 비밀 공유는 다음과 같이 여러 수신자에게 비밀을 전달하는 데 사용된다.

  1. 동음이의어를 사용하여 "비밀"을 변형하십시오.이것은 종종 비밀을 조작하거나 저장하기 쉬운 형태로 만든다.특히 단계 (2)에서 요구하는 대로 새로운 형태를 '분할' 수 있는 자연스러운 방법이 있을 수 있다.
  2. 변환된 비밀을 여러 부분으로 나누십시오. 각 수신자마다 하나씩.비밀은 모든 부분 또는 대부분의 부분이 합쳐져야만 되찾을 수 있는 방식으로 쪼개져야 한다.(비밀 공유 참조)
  3. 비밀의 일부를 각 수신자에게 나누어 주어라.
  4. 각 수신자의 부품을 결합하여 지정된 시간에 변환된 암호를 복구하십시오.
  5. 동형식을 뒤집어서 원래의 비밀을 되찾는다.

예

한 공동체가 분산 투표 프로토콜을 사용하여 선거를 수행하기를 원하지만, 투표 상담자들이 결과에 대해 거짓말을 하지 않도록 보장하기를 원한다고 가정합시다.샤미르의 비밀 공유로 알려진 일종의 동질성 비밀 공유 방식을 사용하여, 공동체의 각 구성원은 자신의 표를 조각으로 쪼개진 형태에 추가할 수 있으며, 각 작품은 다른 투표장에 제출된다.이 조각들은 각 조각에 대한 어떠한 변경사항들이 전체 조각에 어떤 영향을 미칠지 예측할 수 없도록 설계되어 있어, 투표자들이 자신의 조각들을 조작하는 것을 방해한다.모든 투표가 접수되면 투표 상담원들이 이를 결합해 총선거 결과를 회복할 수 있게 된다.

세부적으로 다음 항목을 사용하여 선거를 실시한다고 가정해 보십시오.

  • 두 가지 가능한 결과, 예스 또는 아니오.우리는 그 결과를 각각 +1과 -1로 수치로 나타낼 것이다.
  • 다수의 권위자인 k는 표를 셀 것이다.
  • 많은 유권자들, n, 누가 투표를 제출할 것인가.
  1. 사전에 각 기관은 공개적으로 사용할 수 있는 숫자 키 x를k 생성한다.
  2. 각 투표자는 다음 규칙에 따라 다항식 p로n 자신의 표를 암호화한다.다항식에는 k-1 등급이 있어야 하며, 일정 기간은 +1 또는 -1이어야 하며("예" 또는 "아니요" 투표에 대응하며), 다른 계수는 무작위로 생성되어야 한다.
  3. 각 투표자는 각 기관의 공개 키 x에서k 자신의 다항식 p의n 값을 계산한다.
    • 이렇게 하면 각 당국마다 하나씩 k 포인트가 생성된다.
    • 이러한 k 포인트는 투표의 "부분"이다.모든 포인트를 알고 있다면 다항식 pn(따라서 유권자가 어떻게 투표했는지 알 수 있다)를 파악할 수 있다.그러나 일부만 알고 있으면 다항식을 알 수 없다.(그 이유는 도-n-1 다항식을 결정하기 위해서는 n개의 점이 필요하기 때문이다.두 점이 선을 결정하고, 세 점이 포물선 등을 결정한다.)
  4. 유권자는 각 당국에게 권한의 키를 사용하여 생산된 가치를 보낸다.
  5. 각 당국은 그가 받는 가치를 수집한다.각 권위는 각 유권자로부터 오직 하나의 가치만을 얻기 때문에, 그는 주어진 유권자의 다항성을 발견할 수 없다.게다가, 그는 제출물을 바꾸는 것이 투표에 어떤 영향을 미칠지 예측할 수 없다.
  6. 일단 유권자들이 그들의 표를 제출하면, 각 당국은 그가 받은 모든 가치들의 합계 A를k 계산하여 발표한다.
  7. k 합계가 있다, A가k 있다. 합치면 고유한 다항식 P(x)-구체적으로 모든 유권자 다항식의 합: P(x) = p1(x) + p2(x) + + pn(x) + p(x)를 결정한다.
    • P(x)의 상수 항은 개별 p의n 상수 항을 합한 것이기 때문에 P(x)의 상수 항은 사실상 모든 표의 합이다.
    • 따라서 P(x)의 상수 기간은 총선거 결과를 제공한다: 긍정적이면 -1보다 +1에 투표하는 사람이 더 많고 부정적이면 +1에 투표하는 사람이 더 많다.
A table illustrating the voting protocol
투표 프로토콜의 예.각 열은 특정 유권자의 투표 내용을 나타낸다.각 행은 특정 기관이 받은 작품을 나타낸다.

특징들

이 프로토콜은 모든 권한이 부패하지 않는 한 작동하며, 만일 그러한 권한이 있다면, 그들은 각 유권자에 대해 ( ) 을(를) 재구성하고, 이후 표도 변경할 수 있다.

프로토콜은 t+1 권한을 완성해야 하므로 N>t+1 권한이 있을 경우 N-t-1 권한을 손상시킬 수 있어 프로토콜에 어느 정도 건전성을 부여한다.

의정서는 유권자의 ID(ID는 투표와 함께 제출됨)를 관리하므로 합법적인 유권자만이 투표했는지 확인할 수 있다.

t에 대한 가정 하에:

  1. 투표용지는 신분증으로 되돌아갈 수 없으므로 유권자의 사생활이 보호된다.
  2. 유권자는 그들이 어떻게 투표했는지 증명할 수 없다.
  3. 투표를 검증하는 것은 불가능하다.

그 의정서는 암묵적으로 투표용지의 부패를 방지한다.각 기관이 투표용지 몫만 갖고 있고, 이 몫의 변경이 결과에 어떤 영향을 미칠지 모르기 때문에 당국이 투표용지를 변경할 동기가 없기 때문이다.

취약성

  • 유권자는 자신의 투표가 제대로 기록되었는지 확신할 수 없다.
  • 당국은 투표권이 합법적이고 동등한지 확신할 수 없다. 예를 들어 유권자는 유효한 옵션이 아닌 값(예: -20, 50 등)을 선택할 수 있다.

참고 항목

참조

  1. ^ Schoenmakers, Berry (1999). "A simple publicly verifiable secret sharing scheme and its application to electronic voting". Advances in Cryptology. 1666: 148–164. CiteSeerX 10.1.1.102.9375.