일반 그룹 모델에서 하나 이상의 이산 로그 문제가 어렵습니까?
일반 그룹 모델 (GGM)에서 (알려진) 순서의 구체적인 순환 그룹 $n$이상화 된 버전으로 대체됩니다. 그룹 요소에 대한 임의 인코딩이 선택되고 공격자는 입력 그룹 요소 (예 : 생성기 / 공개 키 / ...)의 인코딩 된 형식에만 액세스 할 수 있으며 적용 할 오라클 그들에 대한 그룹 작전. 인코딩은 고유하므로 그룹 요소가 동일한 지 테스트 할 수 있습니다. 해시 대신 그룹에 대한 Random Oracle Model의 유사점으로 볼 수 있습니다.
GGM에서는 이산 로그 문제가 어렵다는 것은 잘 알려져 있습니다. Shoup 은 모든 일반 알고리즘에$\Omega(\sqrt{p})$ 그룹 작업, 여기서 $p$ 가장 큰 소인수입니다 $n$.
제 질문은 하나 이상의 이산 로그 문제 (OMDL)가 GGM에서도 어려운지 여부입니다. OMDL을 깨기 위해 적이 주어진다$k+1$ 무작위 그룹 요소, 만들 수 있습니다 $k$ DL 오라클에 쿼리 한 다음 모든 이산 로그를 찾는 데 성공해야합니다. $k+1$ 입력.
답변
네, 이것은 Coretti et al [CDG]의 최근 연구에서 보여졌습니다. 느슨하게 말하면 하한선은$T$ GGM 오라클에 대한 쿼리는 최대 확률로 성공합니다. $T^2/N$, 어디 $N$그룹의 크기입니다. 실제로 그들은 GGM에서 적이 임의의 사전 계산을 허용하는 더 강력한 모델을 고려합니다. 보다 정확한 진술은 §5를, 결과 요약은 표 2를 참조하십시오.
[CDG] : Coretti, Dodis 및 Guo, Random-Permutation, Ideal-Cipher, Generic-Group Models의 Non-Uniform Bounds , Crypto'18