Chapter 5 - Cryptography (Applied Cryptography)

Secret Sharing alogirithms

중요한 secret key를 분산하여, n명이 모여야 원래의 secret key를 복원할 수 있게 하는 암호화 기법

신뢰할 수 있는 제3자가 없는 상황에서 중요한 데이터를 안전하게 분배하고 관리할 수 있는 방식

 

방식

secret S를 n개로 쪼개어 S1, S2, ..., Sn으로 나눈 뒤, 일정 k개 이상 모이면 S를 만들 수 있게 설계

이를 (k, n) secret sharing이라고 한다.

 

1. shamir의 secret sharing

• 비밀 S를 원래 값으로 갖는 상수항을 포함하여 k-1차 다항식을 세운다.

• 각 참여자 i에게 n개의 (x_i,f(x_i)) 점을 준다.
• 최소 k개의 점이 모이면, 다항식을 완성할 수 있다.

예시>

Blind Signatures

개인의 프라이버시를 보장하면서 메시지에 대한 디지털 서명을 생성할 수 있는 암호화 기법

사용자는 서명 내용을 모르게 하면서, 서명자는 해당 메시지에 대해 유효한 서명을 할 수 있게 한다.

 

동작 과정

• 메시지 블라인드

1. Bob(서명자)의 공개키 (e,n) 개인키 (d,n)이라고 할 때, Alice는 1 < k < n인 random number를 구한다.

2. Alice는 m*k^e mod n으로 블라인드한 m'을 Bob에게 전송한다. (서명 요청)

(k^e = blind factor)

• 서명 생성

1. Bob(서명자)는 s = m' ^ d mod n 을 수행한다. => (m^d * k^ed) mod n = k* m^d mod n

2. Alice는 서명된 메시지를 s로 받아 원래 메시지에 대한 서명을 얻기 위해 s * k^−1 를 수행한다. = m^d mod n

 

즉, m = s / k mod n

 

-> 위 과정에서 Bob(서명자)은 원래 Message를 알 수가 없다.