Class: RSA::Accumulator

Inherits:
Object
  • Object
show all
Includes:
RSA::ACC::Functions, RSA::ACC::PoE
Defined in:
lib/rsa/accumulator.rb

Constant Summary collapse

RSA2048_MODULUS =

RSA-2048 modulus(https://en.wikipedia.org/wiki/RSA_numbers#RSA-2048).

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
RSA2048_UNKNOWN_ELEM = 
2

Constants included from RSA::ACC::Functions

RSA::ACC::Functions::CHALLENGE_DST, RSA::ACC::Functions::ELEMENT_DST, RSA::ACC::Functions::HASH_DST

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from RSA::ACC::PoE

prove, verify

Methods included from RSA::ACC::Functions

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

Constructor Details

#initialize(n, value, initial_acc, hold_elements, products = 1) ⇒ RSA::Accumulator

Initialize accumulator

Parameters:

  • n (Integer) —

    modulus

  • value (Integer) —

    a value of acc.

  • initial_acc (Integer) —

    a value of initial acc.

  • hold_elements (Boolean)
  • products (Integer) (defaults to: 1) —

    product of all elements in acc, this param is enable only hold_elements set true.



71
72
73
74
75
76
77
 
# File 'lib/rsa/accumulator.rb', line 71

def initialize(n, value, initial_acc, hold_elements, products = 1)
  @n = n
  self.value = value
  @g = normalize(initial_acc, n)
  @hold_elements = hold_elements
  @products = products if hold_elements
end

Instance Attribute Details

#g ⇒ Object (readonly)

Initial value



19
20
21
 
# File 'lib/rsa/accumulator.rb', line 19

def g
  @g
end

#hold_elements ⇒ Object (readonly)

tha flag which indicate hold product of all elements.



20
21
22
 
# File 'lib/rsa/accumulator.rb', line 20

def hold_elements
  @hold_elements
end

#n ⇒ Object (readonly)

Returns the value of attribute n.



17
18
19
 
# File 'lib/rsa/accumulator.rb', line 17

def n
  @n
end

#products ⇒ Object

(Optional) product of all elements in Accumulator



21
22
23
 
# File 'lib/rsa/accumulator.rb', line 21

def products
  @products
end

#value ⇒ Object

Returns the value of attribute value.



18
19
20
 
# File 'lib/rsa/accumulator.rb', line 18

def value
  @value
end

Class Method Details

.generate_random(bit_length = 3072, hold_elements: false) ⇒ RSA::Accumulator

Generate accumulator with random modulus.

WARNING: this is a TRUSTED SETUP. The modulus comes from a freshly generated RSA key, so the caller learns its factorization. Anyone who knows p and q can compute an x-th root of any value and therefore forge a membership proof for an element that was never added, and forge a non-membership proof for an element that was. The factorization is not retained by this method, but it existed in this process, so the resulting accumulator is only sound for verifiers who trust the caller. Use generate_rsa2048 or generate_with_modulus when that trust does not hold.

Parameters:

  • bit_length (Integer) (defaults to: 3072) —

    bit length of accumulator. Default: 3072 bits.

Returns:



54
55
56
57
58
59
60
61
62
 
# File 'lib/rsa/accumulator.rb', line 54

def self.generate_random(bit_length = 3072, hold_elements: false)
  n = OpenSSL::PKey::RSA.generate(bit_length).n.to_i
  initial_value = SecureRandom.random_number(n)
  # Reject the degenerate elements 0, 1 and n - 1, and anything sharing a factor with n.
  until initial_value > 1 && initial_value < n - 1 && initial_value.gcd(n) == 1
    initial_value = SecureRandom.random_number(n)
  end
  new(n, initial_value, initial_value, hold_elements)
end

.generate_rsa2048(hold_elements: false) ⇒ RSA::Accumulator

Generate accumulator using the RSA-2048 challenge modulus. Nobody is known to hold its factorization, so this requires no trusted setup and is the right choice whenever the party running the accumulator is not trusted by the party verifying its proofs.

Returns:



28
29
30
 
# File 'lib/rsa/accumulator.rb', line 28

def self.generate_rsa2048(hold_elements: false)
  new(RSA2048_MODULUS, RSA2048_UNKNOWN_ELEM, RSA2048_UNKNOWN_ELEM, hold_elements)
end

.generate_with_modulus(n, hold_elements: false) ⇒ RSA::Accumulator

Generate accumulator with an externally supplied modulus n of unknown factorization. Use this with a modulus produced by a trusted setup ceremony(e.g. a multi-party computation) when the RSA-2048 modulus is not desired.

Parameters:

  • n (Integer) —

    modulus whose factorization is unknown to every participant.

Returns:

Raises:

  • (ArgumentError) 


37
38
39
40
 
# File 'lib/rsa/accumulator.rb', line 37

def self.generate_with_modulus(n, hold_elements: false)
  raise ArgumentError, 'modulus must be an odd integer greater than 4.' unless n.is_a?(Integer) && n > 4 && n.odd?
  new(n, RSA2048_UNKNOWN_ELEM, RSA2048_UNKNOWN_ELEM, hold_elements)
end

Instance Method Details

#==(other) ⇒ Boolean

Check whether other is same accumulator.

Parameters:

  • other (RSA::ACC:Accumulator) —

    other accumulator.

Returns:

  • (Boolean) —

    if same acc return true, otherwise return false.



101
102
103
104
 
# File 'lib/rsa/accumulator.rb', line 101

def ==(other)
  return false unless other.is_a?(Accumulator)
  self.n == other.n && self.value == other.value
end

#add(*elements) ⇒ RSA::ACC::MembershipProof

Add element to accumulator and get inclusion proof.

Parameters:

  • elements (Array[String]) —

    a list of elements to be added.

Returns:



90
91
92
93
94
95
96
 
# File 'lib/rsa/accumulator.rb', line 90

def add(*elements)
  current_acc = value
  p = elements_to_prime(elements)
  self.value = value.pow(p, n)
  self.products *= p if hold_elements
  RSA::ACC::MembershipProof.new(elements, current_acc, value, RSA::ACC::PoE.prove(current_acc, p, value, n))
end

#delete(*proofs) ⇒ RSA::ACC::MembershipProof

Remove the elements in proofs from the accumulator.

Parameters:

Returns:



172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/rsa/accumulator.rb', line 172

def delete(*proofs)
  return RSA::ACC::MembershipProof.new(proofs.map(&:element).flatten, value, value, RSA::ACC::PoE.prove(value, 1, value, n)) if proofs.empty?

  witnesses = proofs.map do |proof|
    raise RSA::ACC::Error, 'Invalid proof.' unless proof.is_a?(RSA::ACC::MembershipProof)
    p = proof.element_prime
    raise RSA::ACC::Error, 'Invalid element.' if p.nil?
    raise RSA::ACC::Error, 'Bad witness.' unless proof.witness.is_a?(Integer)
    raise RSA::ACC::Error, 'Bad witness.' unless normalize(proof.witness.pow(p, n), n) == value
    [p, normalize(proof.witness, n)]
  end

  current_value = value
  proof_product = witnesses.first[0]
  new_value = witnesses.first[1]
  if witnesses.size > 1
    witnesses[1..-1].each do |w|
      new_value = shamir_trick(new_value, w[1], proof_product, w[0], n)
      proof_product *= w[0]
    end
  end
  self.products = self.products / proof_product if hold_elements
  self.value = new_value
  RSA::ACC::MembershipProof.new(proofs.map{|p|p.element}.flatten, value, current_value, RSA::ACC::PoE.prove(value, proof_product, current_value, n))
end

#member?(proof) ⇒ Boolean

Check whether +proof+#element include in accumulator.

Parameters:

Returns:

  • (Boolean) —

    If element exist in acc return true, otherwise false.



109
110
111
112
113
114
 
# File 'lib/rsa/accumulator.rb', line 109

def member?(proof)
  return false unless proof.is_a?(RSA::ACC::MembershipProof)
  x = proof.element_prime
  return false if x.nil?
  RSA::ACC::PoE.verify(proof.witness, x, value, proof.proof, n)
end

#non_member?(elements, proof) ⇒ Boolean

Verifies a non-membership proof against the current accumulator and elements whose non-inclusion is being proven.

Parameters:

Returns:

  • (Boolean) 


120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/rsa/accumulator.rb', line 120

def non_member?(elements, proof)
  return false unless proof.is_a?(RSA::ACC::NonMembershipProof)
  return false unless valid_elements?(elements)
  x = elements_to_prime(elements)
  return false unless valid_group_elem?(proof.v)
  return false unless valid_group_elem?(proof.d)
  v = normalize(proof.v, n)
  d = normalize(proof.d, n)
  # g * v^{-1} must be derived by the verifier. If proof#gv_inv were used as-is,
  # a prover could pick an arbitrary d and claim gv_inv = d^x, which passes for any x.
  gv_inv = normalize(g * v.pow(-1, n), n)
  RSA::ACC::PoKE2.verify(value, v, proof.poke2_proof, n) &&
      RSA::ACC::PoE.verify(d, x, gv_inv, proof.poe_proof, n)
end

#prove_membership(*elements) ⇒ RSA::ACC::MembershipProof

Generate membership proof for elements. This method is only available if hold_elements is set to true when the accumulator is initialized.

Parameters:

  • elements (Array[String]) —

    The elements for which you want to generate an membership proof.

Returns:

Raises:

  • RSA::ACC::Error.new This exception is raised when hold_elements is set to false.



140
141
142
143
144
145
146
 
# File 'lib/rsa/accumulator.rb', line 140

def prove_membership(*elements)
  raise RSA::ACC::Error.new 'This accumulator does not hold the product of the elements.' unless hold_elements
  x = elements_to_prime(elements)
  return nil unless products.modulo(x) == 0
  witness = normalize(g.pow(products / x, n), n)
  RSA::ACC::MembershipProof.new(elements, witness, value, RSA::ACC::PoE.prove(witness, x, value, n))
end

#prove_non_membership(members, non_members) ⇒ RSA::ACC::NonMembershipProof

Generate non-membership proof using set of elements in current acc and non membership elements.

Parameters:

  • members (Array[String]) —

    The entire set of elements contained within this accumulator.

  • non_members (Array[String]) —

    Elements not included in this accumulator that you want to prove non-membership.

Returns:

Raises:

  • (ArgumentError) 


152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/rsa/accumulator.rb', line 152

def prove_non_membership(members, non_members)
  s = elements_to_prime(members)
  x = elements_to_prime(non_members)

  a, b = egcd(s, x)
  raise ArgumentError, "Inputs not co-prime." unless a * s + b * x == 1

  v = normalize(value.pow(a, n), n)
  d = normalize(g.pow(b, n), n)
  gv_inv = normalize(g * v.pow(-1, n), n)

  poke2_proof = RSA::ACC::PoKE2.prove(value, a, v, n)
  poe_proof = RSA::ACC::PoE.prove(d, x, gv_inv, n)

  RSA::ACC::NonMembershipProof.new(d, v, gv_inv, poke2_proof, poe_proof)
end

#root_factor(*f) ⇒ Array{Integer}

Computes an xi-th root of y for all i = 1, ..., n in total time O(n log(n)).

Parameters:

  • f (Array[Integer]) —

    factorizations of the exponent x = x1, ..., xn.

Returns:

  • (Array{Integer}) —

    array of xi-th root

Raises:

  • (ArgumentError) 


201
202
203
204
205
206
207
208
209
210
 
# File 'lib/rsa/accumulator.rb', line 201

def root_factor(*f)
  raise ArgumentError, 'factorization must not be empty.' if f.empty?
  return [value] if f.size == 1
  half_n = f.size / 2
  g_l = RSA::Accumulator.new(n, value.pow(f[0...half_n].map.inject(:*), n), g, false)
  g_r = RSA::Accumulator.new(n, value.pow(f[half_n..-1].map.inject(:*), n), g, false)
  l = g_r.root_factor(*f[0...half_n])
  r = g_l.root_factor(*f[half_n..-1])
  [l, r].flatten
end