Samee Zahur [email protected]

David Evans [email protected]

University of Virginia

These slides available at MightBeEvil.org/circuits

We are actually going to revisit a rather old problem today —
converting programs to boolean circuits... switch slides

Secure

Computation

Computation

Verifiable

Computation

Computation

Static Analysis

of Programs

of Programs

Non-interactive

Zero-knowledge

Widely studied applications need this,
their efficiency depends on the efficiency of this conversion process
So we will show you:
why existing practice is not good enough
new techniques that is designed for such circuits
implementation results
Zero-knowledge

Example: computing histogram frequencies

for (i=0; i<n; i++) a[i]++;

We designed data structures that can help in cases between these two extremes …
For example, locality of access (switch slide)
Finish by 5 min

if (x!=0) { if (y>0) i++; a[i] = 5; }

stk.condPush (x!=0 && y>0, NULL); stk.condChTop (x!=0, 5);

3

9

9 3 2

7 5

Finish by 12 min

&

Evaluation

Finish by 15 min

~ Θ(*n*)

~ Θ(log *n*)

~ Θ(*n*)

~ Θ(log^{2} *n*)

for (i=0; i<n; i++) C[A[i] + B[i]]++;

arr1 = <Array size n> arr2 = <Array size n> j = k = 0; for (i=0; i<2*n; i++) if (arr1[j] < arr2[k]) res[i] = arr1[j++]; else res[i] = arr2[k++];

Finish by 19 min

Finish by 20 min

www.MightBeEvil.org

Samee Zahur <[email protected]>

David Evans <[email protected]>