The sky is the limit.

Proof of knowledge of Discrete Logarithm in DAA :: 2011/03/14 23:10

수학적으로 어려운 문제(NP문제)로 알려진 다음 문제를 가장 많이 사용

ⓐ 소인수분해 문제(Factorization Problem) : 주어진 합성수 n의 소인수들을 찾는 문제, n의 자리수가 매우 큰 경우(10¹⁵⁰이상)에는 n의 소인수를 효율적으로 찾는 알고리즘이 아직까지 존재하지 않음

   ⓑ 이산대수 문제(Discrete Logarithm Problem) : 소수 p가 주어지고 y = g^x (mod p)인 경우, 역으로 x = log_gy·(mod p)인 x를 계산하는 문제, 여기서 x를 법 p상의 y의 이산대수라 하고, y, g, p가 주어졌을 때, x를 구하는 문제는 어려움.

ⓒ 2차 잉여 문제(Quadratic Residuosity Problem) : gcd(x,n) = 1인 정수 x에 대하여, 평방 합동식 w² = x(mod n)가 해를 가질 때, 이 합동식이 해를 가지지 않을 때, x를 법 n에 관한 평방 비잉여(quadratic nonresidue). x,n에 대하여 x가 평방 잉여 인지 평방 비잉여 인지를 결정하는 문제를 법x상의 평방 잉여 문제라 함. 이 문제는 소인수분해 문제와 동치.

출처 : http://dragon1307.egloos.com/4902500

DAA에서는 discrete logarithm을 기본으로 하여 zero-knowledge proof를 이용하여 비밀키를 보존한다.

Prover    Verifier
random r
t = a^r t
---------------------------------->
   c    random c
<----------------------------------
s = r - cx    s
---------------------------------->
t = y^ca^s

위와 같은 프로토콜을 사용하여 비밀키 x를 노출시키지 않으면서 prover가 비밀키 x를 알고 있는지를 증명하는 과정을 거치게 된다.

출처 : http://en.wikipedia.org/wiki/Schnorr_signature