Glossaire
protocole d’accord byzantin
https://en.wikipedia.org/wiki/Verifiable_random_function
Fonctions qui demande un temps de résolution déterminé et qui sont facilement vérifiables. Ces fonctions sont utilisées dans de nombreux mécanismes. Leur évaluation requiert un nombre connu d'étapes, une certaine rapidité d'exécution et la possibilité de vérifier publiquement et rapidement (à faible coût) le résultat de l'évaluation de la fonction. Par ailleurs il est requis que le résultat de l'évaluation ne puisse être altéré une fois évalué. Evidemment, pour chaque valeur x, il ne peut exister qu'une unique valeur de sortie y = f(x).
On considère qu'une VDF est composée de 3 algorithmes :
- Setup(λ,t) : initialisation de la fonction avec 2 paramètres, un de sécurité λ qui définit le domaine et un de délai t. Il produit un paramètre de sortie pp qui fixe le domaine l'intervall de la fonction, (et qui peut inclure dautres paramètres nécessaires à l'évaluation ou la vérification)
- Eval(pp, x) takes an input x from the domain and outputs a value y in the range and (optionally) a short
proof π.
- Verify(pp, x, y, π) efficiently verifies that y is the correct output on x.
Considérant un délai t, une fonction vérifiable à délai f doit être:
Séquentielle : n'importe qui peux evaluer f(x) en un nombre t d'étapes successive, mais un attaquant disposant d'une forte puissance de calcul ne peut faire la différence entre le résultat de f(x) et un nombre aléatoire de manière nécessitant un nombre inférieur d'étapes significatif.
Efficacement vérifiable; considérant y le résultat de l'évaluation de la fonction, n'importe quel observateur doit pouvoir vérifier que y = f(x) en temps relativement court ( précisément log(t)). La vérification doit être significativement plus rapide que l'évaluation.
Informally, a VDF scheme should satisfy the following properties:
− sequential: honest parties can compute (y, π) ← Eval(pp, x) in t sequential steps, while no
parallel-machine adversary with a polynomial number of processors can distinguish the output
y from random in significantly fewer steps.
− efficiently verifiable: We prefer Verify to be as fast as possible for honest parties to compute;
we require it to take total time O(polylog(t)).
− unique: for all inputs x, it is difficulty to find a y for which Verify(pp, x, y, π) = Yes, but
y ∕= Eval(pp, x).
Bibliographie :
https://blog.trailofbits.com/2018/10/12/introduction-to-verifiable-delay-functions-vdfs/
https://eprint.iacr.org/2018/601.pdf
Sources publiques de nombres aléatoires - balises aléatoires (Randomness beacon)
non prévisible, non manipulables, infalsifiables et contrôlables a posteriori
(a) Elle doit émettre périodiquement, à intervalle de temps fixé, des nombres aléatoires que des entités éloignées peuvent observer (par Internet) simultanément en ayant la certitude d’observer la même chose.
(b) La source doit être impossible à prédire et à truquer ; autrement dit, il faut qu’interviennent dans le résultat des éléments que personne (ni l’émetteur ni les joueurs) ne puisse anticiper ou manipuler.
(c) Il faut que chacun puisse vérifier après une émission quels nombres ont été émis, pour chaque date d’émission et cela avec la certitude que rien n’a été modifié après l’émission, ni par la balise elle-même ni bien sûr par un acteur étranger à la balise. C’est la vérifiabilité a posteriori.
Fonction aléatoire vérifiable
Les fonctions aléatoires vérifiables (VRF) ont été développées par Silvio Micali, Michael Rabin et Salil Vadhan en 1999, puis améliorées par Yevgeniy Dodis et Aleksandr Yampolskiy en 2005https://en.wikipedia.org/wiki/Verifiable_random_function
Fonctions vérifiable à délai
- (Verifiable Delay Function)Fonctions qui demande un temps de résolution déterminé et qui sont facilement vérifiables. Ces fonctions sont utilisées dans de nombreux mécanismes. Leur évaluation requiert un nombre connu d'étapes, une certaine rapidité d'exécution et la possibilité de vérifier publiquement et rapidement (à faible coût) le résultat de l'évaluation de la fonction. Par ailleurs il est requis que le résultat de l'évaluation ne puisse être altéré une fois évalué. Evidemment, pour chaque valeur x, il ne peut exister qu'une unique valeur de sortie y = f(x).
On considère qu'une VDF est composée de 3 algorithmes :
- Setup(λ,t) : initialisation de la fonction avec 2 paramètres, un de sécurité λ qui définit le domaine et un de délai t. Il produit un paramètre de sortie pp qui fixe le domaine l'intervall de la fonction, (et qui peut inclure dautres paramètres nécessaires à l'évaluation ou la vérification)
- Eval(pp, x) takes an input x from the domain and outputs a value y in the range and (optionally) a short
proof π.
- Verify(pp, x, y, π) efficiently verifies that y is the correct output on x.
Considérant un délai t, une fonction vérifiable à délai f doit être:
Séquentielle : n'importe qui peux evaluer f(x) en un nombre t d'étapes successive, mais un attaquant disposant d'une forte puissance de calcul ne peut faire la différence entre le résultat de f(x) et un nombre aléatoire de manière nécessitant un nombre inférieur d'étapes significatif.
Efficacement vérifiable; considérant y le résultat de l'évaluation de la fonction, n'importe quel observateur doit pouvoir vérifier que y = f(x) en temps relativement court ( précisément log(t)). La vérification doit être significativement plus rapide que l'évaluation.
Informally, a VDF scheme should satisfy the following properties:
− sequential: honest parties can compute (y, π) ← Eval(pp, x) in t sequential steps, while no
parallel-machine adversary with a polynomial number of processors can distinguish the output
y from random in significantly fewer steps.
− efficiently verifiable: We prefer Verify to be as fast as possible for honest parties to compute;
we require it to take total time O(polylog(t)).
− unique: for all inputs x, it is difficulty to find a y for which Verify(pp, x, y, π) = Yes, but
y ∕= Eval(pp, x).
Bibliographie :
https://blog.trailofbits.com/2018/10/12/introduction-to-verifiable-delay-functions-vdfs/
https://eprint.iacr.org/2018/601.pdf
Sources publiques de nombres aléatoires - balises aléatoires (Randomness beacon)
non prévisible, non manipulables, infalsifiables et contrôlables a posteriori
(a) Elle doit émettre périodiquement, à intervalle de temps fixé, des nombres aléatoires que des entités éloignées peuvent observer (par Internet) simultanément en ayant la certitude d’observer la même chose.
(b) La source doit être impossible à prédire et à truquer ; autrement dit, il faut qu’interviennent dans le résultat des éléments que personne (ni l’émetteur ni les joueurs) ne puisse anticiper ou manipuler.
(c) Il faut que chacun puisse vérifier après une émission quels nombres ont été émis, pour chaque date d’émission et cela avec la certitude que rien n’a été modifié après l’émission, ni par la balise elle-même ni bien sûr par un acteur étranger à la balise. C’est la vérifiabilité a posteriori.
Commentaires
Enregistrer un commentaire