Timeline for How small is the negligible advantage for DDH?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2022 at 9:45 | comment | added | meshcollider | No, I'm not aware off the top of my head. It sounds like it would be a weird algorithm. | |
| Mar 3, 2022 at 8:27 | comment | added | Napoleon | I agree that all of those error are theoretically possible, but practically -- are you aware for example about a distinguisher with advantage $n^{-\log \log n}$? | |
| Mar 3, 2022 at 7:58 | comment | added | meshcollider | Theoretically, any of those things could exist, the security assumption says nothing about it. We just draw the line at "negligible" and leave it there. | |
| Mar 3, 2022 at 7:55 | comment | added | Napoleon | I agree that with the specific machine $M$ you mentioned, that simply guesses elements, has $1/2^{O(n)}$ advantage. Nevertheless, there might be other PPTs that do something different, and able to gain better advantage, say, $1/n^{\log n}$, which is still negligible. My question concerns more how much negligible the advantage can be: $n^{-\log \log n}, n^{-\log n}, 2^{-O(n)}$? | |
| Mar 3, 2022 at 7:31 | history | answered | meshcollider | CC BY-SA 4.0 |