Class: Sharing::Polynomial::Shamir::V1

Inherits:
Object
  • Object
show all
Extended by:
HenselCode::Tools, Tools
Includes:
HenselCode::Tools, Tools
Defined in:
lib/sharing/polynomial/shamir/v1.rb

Overview

first supported version of Shamir secret sharing scheme

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Tools

f, lagrange_basis_polynomial, lagrange_basis_polynomial_inner_loop

Constructor Details

#initialize(params = {}) ⇒ V1

Returns a new instance of V1.



84
85
86
87
88
89
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 84

def initialize(params = {})
  @lambda_ = params[:lambda_]
  @total_shares = params[:total_shares]
  @threshold = params[:threshold]
  generate_prime
end

Instance Attribute Details

#lambda_ ⇒ Object

Returns the value of attribute lambda_.



13
14
15
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 13

def lambda_
  @lambda_
end

#p ⇒ Object

Returns the value of attribute p.



13
14
15
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 13

def p
  @p
end

#threshold ⇒ Object

Returns the value of attribute threshold.



13
14
15
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 13

def threshold
  @threshold
end

#total_shares ⇒ Object

Returns the value of attribute total_shares.



13
14
15
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 13

def total_shares
  @total_shares
end

Class Method Details

.add(shares1, shares2, prime) ⇒ Object 



15
16
17
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 15

def self.add(shares1, shares2, prime)
  shares1.zip(shares2).map { |s| [s[0][0], (s[0][1] + s[1][1]) % prime] }
end

.compute_numerator_denominator(shares1, shares2, r1_, r2_, prime) ⇒ Object 



78
79
80
81
82
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 78

def self.compute_numerator_denominator(shares1, shares2, r1_, r2_, prime)
  cs = shares1.map { |i, share| [i, (share * r1_) % prime] }
  ds = shares2.map { |i, share| [i, (share * r2_) % prime] }
  [cs, ds]
end

.create_shares(secret, total_shares, threshold, lambda_, prime) ⇒ Object 



67
68
69
70
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 67

def self.create_shares(secret, total_shares, threshold, lambda_, prime)
  random_coefficients = generate_random_coefficients(threshold, lambda_)
  (1..total_shares).map.with_index { |x, i| [i + 1, f(x, secret, random_coefficients) % prime] }
end

.encode_reshares(reshares, prime, s_pair) ⇒ Object 



41
42
43
44
45
46
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 41

def self.encode_reshares(reshares, prime, s_pair)
  reshares_encoded = reshares.map do |ss|
    [ss[0], (ss[1].numerator * mod_inverse(ss[1].denominator, prime)) % prime]
  end
  [s_pair[0][0], reshares_encoded]
end

.generate_division_masking(prime) ⇒ Object 



72
73
74
75
76
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 72

def self.generate_division_masking(prime)
  r1, r2 = random_distinct_numbers("integer", 2, prime.bit_length - 1)
  r3 = (r2 * mod_inverse(r1, prime)) % prime
  [r1, r2, r3]
end

.generate_random_coefficients(total_shares, lambda_) ⇒ Object 



63
64
65
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 63

def self.generate_random_coefficients(total_shares, lambda_)
  random_distinct_numbers("integer", total_shares - 1, lambda_ - 1)
end

.mul_first_round(shares, total_shares, threshold, lambda_, prime) ⇒ Object 



31
32
33
34
35
36
37
38
39
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 31

def self.mul_first_round(shares, total_shares, threshold, lambda_, prime)
  shares1, shares2 = shares
  xs = shares1.map(&:first)
  shares1.zip(shares2).map.with_index do |s, i|
    share = prepare_share_for_multiplication(i, xs, prime, s)
    reshares = create_shares(share, total_shares, threshold, lambda_, prime)
    encode_reshares(reshares, prime, s)
  end
end

.mul_second_round(mul_round1) ⇒ Object 



53
54
55
56
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 53

def self.mul_second_round(mul_round1)
  multiplication_shares = mul_round1.map(&:last).map { |m| m.map(&:last) }.transpose.map(&:sum)
  multiplication_shares.map.with_index { |m, i| [i + 1, m] }
end

.prepare_share_for_multiplication(index, xs_, prime, s_pair) ⇒ Object 



48
49
50
51
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 48

def self.prepare_share_for_multiplication(index, xs_, prime, s_pair)
  beta = lagrange_basis_polynomial_inner_loop(index, xs_)
  (s_pair[0][1] * s_pair[1][1] * beta) % prime
end

.sdiv(shares, scalar, prime) ⇒ Object 



27
28
29
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 27

def self.sdiv(shares, scalar, prime)
  shares.map { |s| [s[0], (s[1] * mod_inverse(scalar, prime)) % prime] }
end

.select_mul_shares(total_shares, threshold, shares) ⇒ Object 



58
59
60
61
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 58

def self.select_mul_shares(total_shares, threshold, shares)
  indices = (0..total_shares - 1).to_a.sample((2 * threshold) - 1)
  shares.map { |shares_| shares_.values_at(*indices) }
end

.smul(shares, scalar, prime) ⇒ Object 



23
24
25
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 23

def self.smul(shares, scalar, prime)
  shares.map { |s| [s[0], (s[1] * scalar) % prime] }
end

.sub(shares1, shares2, prime) ⇒ Object 



19
20
21
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 19

def self.sub(shares1, shares2, prime)
  shares1.zip(shares2).map { |s| [s[0][0], (s[0][1] - s[1][1]) % prime] }
end

Instance Method Details

#create_shares(secret) ⇒ Object 



95
96
97
98
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 95

def create_shares(secret)
  random_coefficients = generate_random_coefficients
  (1..total_shares).map { |x| [x, f(x, secret, random_coefficients) % p] }
end

#params ⇒ Object 



91
92
93
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 91

def params
  [lambda_, p, total_shares, threshold]
end

#reconstruct_division(cs_, ds_, r3_) ⇒ Object 



108
109
110
111
112
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 108

def reconstruct_division(cs_, ds_, r3_)
  c, d = [cs_, ds_].map { |shares| reconstruct_secret(shares) }
  c_d_encoded = (c * mod_inverse(d, p) * r3_) % p
  HenselCode::TruncatedFinitePadicExpansion.new(p, 1, c_d_encoded).to_r
end

#reconstruct_secret(points) ⇒ Object 



100
101
102
103
104
105
106
 
# File 'lib/sharing/polynomial/shamir/v1.rb', line 100

def reconstruct_secret(points)
  xs = points.map(&:first)
  ys = points.map(&:last)
  l0s = lagrange_basis_polynomial(xs)
  reconstructed_secret = l0s.zip(ys).map { |l, y| l * y }.sum % p
  encode_to_integer(reconstructed_secret)
end