'''
Contains all the auxillary functions to do linear secret sharing (LSS) over an access structure. Mainly, we represent the
access structure as a binary tree. This could also support matrices for representing access structures.
'''
from charm.core.math.pairing import ZR
from charm.toolbox.policytree import *
[docs]class SecretUtil:
def __init__(self, groupObj, verbose=True):
self.group = groupObj
# self.parser = PolicyParser()
[docs] def P(self, coeff, x):
share = 0
# evaluate polynomial
for i in range(0, len(coeff)):
share += (coeff[i] * (x ** i))
return share
[docs] def genShares(self, secret, k, n):
if(k <= n):
rand = self.group.random
a = [] # will hold polynomial coefficients
for i in range(0, k):
if (i == 0): a.append(secret) # a[0]
else: a.append(rand(ZR))
Pfunc = self.P
shares = [Pfunc(a, i) for i in range(0, n+1)]
return shares
# shares is a dictionary
[docs] def recoverCoefficients(self, list):
"""recovers the coefficients over a binary tree."""
coeff = {}
list2 = [self.group.init(ZR, i) for i in list]
for i in list2:
result = 1
for j in list2:
if not (i == j):
# lagrange basis poly
result *= (0 - j) / (i - j)
# print("coeff '%d' => '%s'" % (i, result))
coeff[int(i)] = result
return coeff
[docs] def recoverSecret(self, shares):
"""take shares and attempt to recover secret by taking sum of coeff * share for all shares.
if user indeed has at least k of n shares, then secret will be recovered."""
list = shares.keys()
if self.verbose: print(list)
coeff = self.recoverCoefficients(list)
secret = 0
for i in list:
secret += (coeff[i] * shares[i])
return secret
[docs] def getCoefficients(self, tree):
coeffs = {}
self._getCoefficientsDict(tree, coeffs)
return coeffs
def _getCoefficientsDict(self, tree, coeff_list, coeff=1):
"""recover coefficient over a binary tree where possible node types are OR = (1 of 2)
and AND = (2 of 2) secret sharing. The leaf nodes are attributes and the coefficients are
recorded in a coeff-list dictionary."""
if tree:
node = tree.getNodeType()
if(node == OpType.AND):
this_coeff = self.recoverCoefficients([1,2])
# left child => coeff[1], right child => coeff[2]
self._getCoefficientsDict(tree.getLeft(), coeff_list, coeff * this_coeff[1])
self._getCoefficientsDict(tree.getRight(), coeff_list, coeff * this_coeff[2])
elif(node == OpType.OR):
this_coeff = self.recoverCoefficients([1])
self._getCoefficientsDict(tree.getLeft(), coeff_list, coeff * this_coeff[1])
self._getCoefficientsDict(tree.getRight(), coeff_list, coeff * this_coeff[1])
elif(node == OpType.ATTR):
attr = tree.getAttributeAndIndex()
coeff_list[ attr ] = coeff
else:
return None
def _calculateShares(self, secret, tree, _type=dict):
"""performs secret sharing over a policy tree. could be adapted for LSSS matrices."""
attr_list = []
self._compute_shares(secret, tree, attr_list)
if _type == list:
return attr_list
else: # assume dict
share = {}
for i in range(0, len(attr_list)):
key = attr_list[i][0].getAttributeAndIndex()
if not key in share.keys():
share[ key ] = attr_list[i][1]
return share
[docs] def calculateSharesList(self, secret, tree):
"""calculate shares from given secret and returns a list of shares."""
return self._calculateShares(secret, tree, list)
[docs] def calculateSharesDict(self, secret, tree):
"""calculate shares from given secret and returns a dict as {attribute:shares} pairs"""
return self._calculateShares(secret, tree, dict)
def _compute_shares(self, secret, subtree, List):
"""computes recursive secret sharing over the binary tree. Start by splitting 1-of-2 (OR) or 2-of-2 (AND nodes).
Continues recursively down the tree doing a round of secret sharing at each boolean node type."""
k = 0
if(subtree == None):
return None
type = subtree.getNodeType()
if(type == OpType.ATTR):
# visiting a leaf node
# t = (subtree.getAttribute(), secret)
t = (subtree, secret)
List.append(t)
return None
elif(type == OpType.OR or type == OpType.AND):
k = subtree.threshold # 1-of-2 or 2-of-2
# elif(type == OpType.AND):
# k = 2 # 2-of-2
else:
return None
# generate shares for k and n
shares = self.genShares(secret, k, n=2)
# recursively generate shares for children nodes
self._compute_shares(shares[1], subtree.getLeft(), List)
self._compute_shares(shares[2], subtree.getRight(), List)
[docs] def strip_index(self, node_str):
if node_str.find('_') != -1: return node_str.split('_')[0]
return node_str
[docs] def createPolicy(self, policy_string):
assert type(policy_string) == str, "invalid type for policy_string"
parser = PolicyParser()
policy_obj = parser.parse(policy_string)
_dictCount, _dictLabel = {}, {}
parser.findDuplicates(policy_obj, _dictCount)
for i in _dictCount.keys():
if _dictCount[ i ] > 1: _dictLabel[ i ] = 0
parser.labelDuplicates(policy_obj, _dictLabel)
return policy_obj
[docs] def prune(self, policy, attributes):
"""determine whether a given set of attributes satisfies the policy"""
parser = PolicyParser()
return parser.prune(policy, attributes)
[docs] def getAttributeList(self, Node):
aList = []
self._getAttributeList(Node, aList)
return aList
def _getAttributeList(self, Node, List):
"""retrieve the attributes that occur in a policy tree in order (left to right)"""
if(Node == None):
return None
# V, L, R
if(Node.getNodeType() == OpType.ATTR):
List.append(Node.getAttributeAndIndex()) # .getAttribute()
else:
self._getAttributeList(Node.getLeft(), List)
self._getAttributeList(Node.getRight(), List)
return None
# TODO: add test cases here for SecretUtil
if __name__ == "__main__":
pass