https://github.com/EasyCrypt/easycrypt
Raw File
Tip revision: 17d639410a78b8b6dd6e66a4f11bd93d2809a6d9 authored by Alley Stoughton on 29 March 2021, 13:09:27 UTC
An axiom-free formalization of well-founded relations, induction and recursion.
Tip revision: 17d6394
PRG.eca
type output.
op dout:output distr.

module type RG = {
  proc init(): unit
  proc next(): output
}.

module type RGA = { proc next(): output }.

module type Distinguisher(G:RGA) = { proc distinguish(): bool }.

module IND(G:RG,D:Distinguisher) = {
  module D = D(G)

  proc main(): bool = {
    var b;

    G.init();
    b <@ D.distinguish();
    return b;
  }
}.

module PRGi:RG,RGA = {
  proc init(): unit = { }
  proc next(): output = { var r; r <$ dout; return r; }
}.

(** Advantage of a distinguisher against a PRG G:
      Adv_G(D) = `|IND(G,D) - IND(PRGi,D)|        **)
back to top