이산로그문제(DLP) in ZKP

 

• 유한한(finite) 그룹 G와 이항연산(binary operation)이 주어지고, 원소 a와 b가 주어졌을 때, a를 몇 번 연산하면 b가 되는가?

 

위 문제를 DLP(Discrete Logarithm Problem)라고 합니다. 먼저 DLP에 대해 알아봅시다.

 

이산로그문제(Discrete Logarithm Problem)

이산로그(discrete logarithm) 문제는 수학에서 중요한 문제 중 하나입니다. 이 문제는, 어떤 수 a와 b가 주어졌을 때, a^x ≡ b(mod p)를 만족하는 가장 작은 양의 정수 x를 찾는 문제입니다. 이 때 p는 소수이고, ≡ 기호는 모듈로(modulo) 연산을 나타냅니다.

 

좀 더 명확한 정의는 아래와 같습니다.

 

DLP의 정의는 위와 같습니다. DLP의 경우 어떤 이항연산을 정의하는지, 어떤 그룹에서 정의되는지에 따라 문제의 난이도가 결정됩니다.

 

위 그림에서 DLP 쉬운 문제와 같이 그룹 Fp와 덧셈 연산이 주어지면, DLP는 쉽게 해결됩니다.

하지만 DLP 어려운 문제와 같이 연산이 곱셈으로 정의된 그룹은 덧셈 연산처럼 쉽게 해결되지 않는 경우가 대다수입니다.

즉, 핵심은 해결하기 어려운 문제를 만들기 위해서는 어떤 그룹을 설정하고, 그 그룹의 연산을 어떻게 정의하느냐에 따라 달라집니다.

 

ZKP에서는 '어떤 그룹'을 ‘타원곡선’으로 선택하고, ‘어려운 문제’로서 사용됩니다.

 

 

 

 

출처 : https://hyun-jeong.medium.com/%ED%83%80%EC%9B%90%EA%B3%A1%EC%84%A0%EC%9D%98-%EA%B7%BC%EB%B3%B8%EC%A0%81%EC%9D%B8-%EC%88%98%ED%95%99-%EC%9D%B4%EC%95%BC%EA%B8%B0-2-14c72b5f158