Parallelizing fully homomorphic encryption for a cloud environment

1. Introduction

• Gentry scheme を対象

3. Gentry scheme and cloud compiting

Gentryのスキームでは、2つの8ビット整数に対して加算、減算、比較演算を実行するのに数秒かかることが示されています。また、2つの8ビット整数の乗算には数分、2つの8ビット整数の除算には数時間かかることが示された。

4. Algorithm

• 要求からデータ依存関係のグラフを作成
• 実行する部分回路を決めて評価
• 評価するのがなくなったら計算完了

4.1 Crating data dependency grpah

回路からデータ依存グラフを作成するアルゴリズム

class Node:
	inputs: List[int]
	outputs: List[int]
 
E: List[Node]
D = []
P = [Set() for _ in range(len(E))]
C = [Set() for _ in range(len(E))]
for e, i in enumerate(E):
	for input in e.inputs:
		if D[input] == null:
			D[input] = 0
		P[i].add(d)
		C[d].add(i)
	for output in e.outputs:
		if D[output] == null:
			D[output] = 0;
		owner = D[output]
		if not owner.is_root():
			for dep in C[d].dependants():
				P[index].add(dep)
				C[dep].add(index)
		D[output] = index

4.2 Finding sub-circuit

c = [e for e in C[0] if e.state != 'pending']
E = [c]
cands = C[c]
while len(cands) > 0:
	c = cands.pop()
	add = True
	for c_par in P[c]:
		if c_par not in E:
			add = False
	if add and c.state != 'pending':
		E.add(c)
		c.state = 'pending'
		for ce of C[c]:
			if ce not in cands:
				cands.append(ce)

• 愚直な回路分割ぽい