signatures.mli 5.88 KB
Newer Older
Stephane Glondu's avatar
Doc  
Stephane Glondu committed
1
(** Signatures *)
Stephane Glondu's avatar
Stephane Glondu committed
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

(** A group suitable for discrete logarithm-based cryptography. *)
module type GROUP = sig
  (** The following interface is redundant: it is assumed, but not
      checked, that usual mathematical relations hold. *)

  type t
  (** The type of elements. Note that it may be larger than the group
      itself, hence the [check] function below. *)

  val check : t -> bool
  (** Check group membership. *)

  val one : t
  (** The neutral element of the group. *)

  val g : t
  (** A generator of the group. *)

  val q : Z.t
  (** The order of [g]. *)

  val ( *~ ) : t -> t -> t
  (** Multiplication. *)

  val ( **~ ) : t -> Z.t -> t
  (** Exponentiation. *)

  val ( =~ ) : t -> t -> bool
  (** Equality test. *)

  val invert : t -> t
  (** Inversion. *)

36 37 38
  val to_string : t -> string
  (** Conversion to string. *)

39 40 41
  val hash : string -> t array -> Z.t
  (** Hash an array of elements into an integer mod [q]. The string
      argument is a string that is prepended before computing the hash. *)
Stephane Glondu's avatar
Stephane Glondu committed
42 43 44

  val compare : t -> t -> int
  (** A total ordering over the elements of the group. *)
Stephane Glondu's avatar
Stephane Glondu committed
45 46
end

47 48
(** Monad signature. *)
module type MONAD = sig
Stephane Glondu's avatar
Stephane Glondu committed
49 50 51
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
52
  val fail : exn -> 'a t
53
end
Stephane Glondu's avatar
Stephane Glondu committed
54

55 56 57
(** Random number generation. *)
module type RANDOM = sig
  include MONAD
Stephane Glondu's avatar
Stephane Glondu committed
58 59 60

  val random : Z.t -> Z.t t
  (** [random q] returns a random number modulo [q]. *)
61 62 63 64
end

(** Ballot box. *)
module type BALLOT_BOX = sig
65 66
  type 'a m
  (** The type of monadic values. *)
Stephane Glondu's avatar
Stephane Glondu committed
67 68 69 70 71 72 73

  (** {2 Election-specific operations} *)

  type ballot
  (** The type of ballots. The monad is supposed to keep track of all
      cast ballots (e.g. in a database). *)

74 75 76 77
  type record
  (** The type of log records. *)

  val cast : ballot -> record -> unit m
Stephane Glondu's avatar
Stephane Glondu committed
78 79
  (** Cast a ballot. *)

80 81 82 83 84 85 86 87 88
  val fold_ballots : (ballot -> 'a -> 'a m) -> 'a -> 'a m
  (** [fold_ballots f a] computes [(f bN ... (f b2 (f b1 a))...)],
      where [b1 ... bN] are all cast ballots. *)

  val fold_records : (record -> 'a -> 'a m) -> 'a -> 'a m
  (** Same as [fold_ballots] for records. *)

  val turnout : int m
  (** Number of cast ballots. *)
Stephane Glondu's avatar
Stephane Glondu committed
89 90
end

Stephane Glondu's avatar
Stephane Glondu committed
91 92 93 94 95
(** Parameters for an election. *)
module type ELECTION_PARAMS = sig
  module G : GROUP
  (** The group used for cryptography. *)

96
  val public_keys : G.t array Lazy.t
97 98
  (** Trustee public keys. *)

99 100 101
  (* TODO: public_keys is not needed during election, remove from
     here, or at least monadify. *)

102
  val params : G.t Serializable_t.params
103 104 105 106
  (** Parameters of the election. *)

  val metadata : Serializable_t.metadata option
  (** Other optional metadata. *)
Stephane Glondu's avatar
Stephane Glondu committed
107 108 109 110 111

  val fingerprint : string
  (** The election fingerprint. *)
end

Stephane Glondu's avatar
Typo  
Stephane Glondu committed
112
(** Cryptographic primitives for an election with homomorphic tally. *)
Stephane Glondu's avatar
Stephane Glondu committed
113
module type ELECTION = sig
Stephane Glondu's avatar
Stephane Glondu committed
114

Stephane Glondu's avatar
Stephane Glondu committed
115 116 117
  type 'a m
  (** The type of monadic values. *)

Stephane Glondu's avatar
Stephane Glondu committed
118 119 120 121 122 123 124
  (** {2 Election parameters} *)

  (** Ballots are encrypted using public-key cryptography secured by
      the discrete logarithm problem. Here, we suppose private keys
      are integers modulo a large prime number. Public keys are
      members of a suitably chosen group. *)

Stephane Glondu's avatar
Stephane Glondu committed
125
  type elt
Stephane Glondu's avatar
Stephane Glondu committed
126
  type private_key = Z.t
Stephane Glondu's avatar
Stephane Glondu committed
127
  type public_key = elt
Stephane Glondu's avatar
Stephane Glondu committed
128

129
  val election_params : elt Serializable_t.params
Stephane Glondu's avatar
Stephane Glondu committed
130 131 132

  (** {2 Ciphertexts} *)

Stephane Glondu's avatar
Stephane Glondu committed
133
  type ciphertext = elt Serializable_t.ciphertext array array
Stephane Glondu's avatar
Stephane Glondu committed
134 135
  (** A ciphertext that can be homomorphically combined. *)

136 137 138
  val neutral_ciphertext : ciphertext
  (** The neutral element for [combine_ciphertext] below. *)

Stephane Glondu's avatar
Stephane Glondu committed
139 140 141 142 143 144 145 146 147 148 149
  val combine_ciphertexts : ciphertext -> ciphertext -> ciphertext
  (** Combine two ciphertexts. The encrypted tally of an election is
      the combination of all ciphertexts of valid cast ballots. *)

  (** {2 Ballots} *)

  type plaintext = int array array
  (** The plaintext equivalent of [ciphertext], i.e. the contents of a
      ballot. When [x] is such a value, [x.(i).(j)] is the weight (0
      or 1) given to answer [j] in question [i]. *)

Stephane Glondu's avatar
Stephane Glondu committed
150
  type ballot = elt Serializable_t.ballot
Stephane Glondu's avatar
Stephane Glondu committed
151 152 153 154 155 156 157
  (** A ballot ready to be transmitted, containing the encrypted
      answers and cryptographic proofs that they satisfy the election
      constraints. *)

  type randomness = Z.t array array
  (** Randomness needed to create a ballot. *)

Stephane Glondu's avatar
Stephane Glondu committed
158
  val make_randomness : unit -> randomness m
159 160 161
  (** Creates randomness for [create_ballot] below. The result can be
      kept for Benaloh-style auditing. *)

Stephane Glondu's avatar
Stephane Glondu committed
162
  val create_ballot : randomness -> plaintext -> ballot m
163
  (** [create_ballot r answers] creates a ballot, or raises
Stephane Glondu's avatar
Stephane Glondu committed
164 165 166 167 168 169 170 171 172 173 174 175
      [Invalid_argument] if [answers] doesn't satisfy the election
      constraints. *)

  val check_ballot : ballot -> bool
  (** [check_ballot b] checks all the cryptographic proofs in [b]. All
      ballots produced by [create_ballot] should pass this check. *)

  val extract_ciphertext : ballot -> ciphertext
  (** Extract the ciphertext from a ballot. *)

  (** {2 Partial decryptions} *)

Stephane Glondu's avatar
Stephane Glondu committed
176
  type factor = elt Serializable_t.partial_decryption
Stephane Glondu's avatar
Stephane Glondu committed
177 178 179 180
  (** A decryption share. It is computed by a trustee from his or her
      private key share and the encrypted tally, and contains a
      cryptographic proof that he or she didn't cheat. *)

Stephane Glondu's avatar
Stephane Glondu committed
181
  val compute_factor : ciphertext -> private_key -> factor m
Stephane Glondu's avatar
Stephane Glondu committed
182 183 184 185 186 187 188 189

  val check_factor : ciphertext -> public_key -> factor -> bool
  (** [check_factor c pk f] checks that [f], supposedly submitted by a
      trustee whose public_key is [pk], is valid with respect to the
      encrypted tally [c]. *)

  (** {2 Result} *)

Stephane Glondu's avatar
Stephane Glondu committed
190
  type result = elt Serializable_t.result
Stephane Glondu's avatar
Stephane Glondu committed
191 192 193 194 195
  (** The election result. It contains the needed data to validate the
      result from the encrypted tally. *)

  val combine_factors : int -> ciphertext -> factor array -> result
  (** Combine the encrypted tally and the factors from all trustees to
Stephane Glondu's avatar
Stephane Glondu committed
196 197
      produce the election result. The first argument is the number of
      tallied ballots. May raise [Invalid_argument]. *)
Stephane Glondu's avatar
Stephane Glondu committed
198

199
  val check_result : result -> bool
Stephane Glondu's avatar
Stephane Glondu committed
200 201 202 203

  val extract_tally : result -> plaintext
  (** Extract the plaintext result of the election. *)
end