L'unico problema di registro discreto è difficile nel modello di gruppo generico?
Nel Generic Group Model (GGM), un gruppo ciclico concreto di ordine (noto) $n$viene sostituito con una versione idealizzata: viene scelta una codifica casuale per gli elementi del gruppo e l'avversario ottiene solo l'accesso alla forma codificata di qualsiasi elemento del gruppo di input (come il generatore / chiave pubblica / ...) e un oracolo da applicare l'operazione di gruppo su di loro. La codifica è unica, quindi è possibile verificare l'uguaglianza degli elementi del gruppo. Può essere visto come l'analogo del modello Oracle casuale per i gruppi invece degli hash.
È noto che il problema del logaritmo discreto è difficile nel GGM: Shoup ha dimostrato che qualsiasi algoritmo generico necessita$\Omega(\sqrt{p})$ operazioni di gruppo, dove $p$ è il più grande fattore primo di $n$.
La mia domanda è se l'one-more problema del logaritmo discreto (OMDL) è anche difficile nel GGM. Per infrangere OMDL, viene dato un avversario$k+1$ elementi del gruppo casuale, possono fare $k$ interroga un oracolo DL e deve quindi riuscire a trovare il logaritmo discreto di tutti $k+1$ ingressi.
Risposte
Sì, questo è stato dimostrato in un recente lavoro di Coretti et al [CDG]. In parole povere, il limite inferiore afferma che un avversario che fa al massimo$T$ le query all'oracolo GGM riescono con probabilità al massimo $T^2/N$, dove $N$è la dimensione del gruppo. Considerano infatti un modello più forte in cui all'avversario è consentito un pre-calcolo arbitrario nel GGM. Vedere §5 per dichiarazioni più precise e la Tabella 2 per un riepilogo dei risultati.
[CDG]: Coretti, Dodis e Guo, Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher e Generic-Group Models , Crypto'18