Module: RSA::ACC::PoE

Extended by:
Functions
Includes:
Functions
Included in:
RSA::Accumulator
Defined in:
lib/rsa/acc/poe.rb

Overview

Non-Interactive Proof of Exponentiation

Constant Summary

Constants included from Functions

Functions::CHALLENGE_DST, Functions::ELEMENT_DST, Functions::HASH_DST

Class Method Summary collapse

Methods included from Functions

blake2_hash, compute_challenge, egcd, elements_to_prime, hash_to_prime, normalize, shamir_trick, valid_elements?

Class Method Details

.prove(base, exp, result, modulus) ⇒ Object

Computes a proof base ^ H(+exp+) was performed to derive result.

Parameters:

  • base (Integer) —

    The known base.

  • exp (Integer) —

    The exponentiation.

  • result (Integer) —

    such as result = base^exp.

  • modulus (Integer) —

    modulus using computation.



19
20
21
22
23
24
25
 
# File 'lib/rsa/acc/poe.rb', line 19

def prove(base, exp, result, modulus)
  base = normalize(base, modulus)
  result = normalize(result, modulus)
  l = compute_challenge(base, exp, result)
  q = exp / l
  normalize(base.pow(q, modulus), modulus)
end

.verify(base, exp, result, proof, modulus) ⇒ Object

Verifies that base^exp = result using the given proof to avoid computation.

Parameters:

  • base (Integer) —

    The known base.

  • exp (Integer) —

    The exponentiation.

  • result (Integer) —

    such as result = base^exp.

  • proof (Integer) —

    an proof.

  • modulus (Integer) —

    modulus using computation.



33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/rsa/acc/poe.rb', line 33

def verify(base, exp, result, proof, modulus)
  # A proof comes from an untrusted prover, so a malformed one is a false result and
  # not an exception.
  return false unless [base, exp, result, proof, modulus].all? { |v| v.is_a?(Integer) }
  return false unless exp.positive? && modulus > 1
  base = normalize(base, modulus)
  result = normalize(result, modulus)
  proof = normalize(proof, modulus)
  l = compute_challenge(base, exp, result)
  r = exp % l
  w = normalize(proof.pow(l, modulus) * base.pow(r, modulus), modulus)
  w == result
end