Circuit Structures for Improving Efficiency of Security and Privacy Tools

Samee Zahur
David Evans
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

Introduction

Secure
Computation
Verifiable
Computation
Static Analysis
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

The Problem

Example: computing histogram frequencies

An Easy Case

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)

Access Patterns

In our paper we describe … but in the interest of time
Finish by 5 min

Exploiting Locality: Stacks

if (x!=0) {
  if (y>0) i++;
  a[i] = 5;
}
stk.condPush (x!=0 && y>0, NULL);
stk.condChTop (x!=0, 5);
      

Naïve Stack

Efficient Stack

3
9
9  3  2
7  5
Finish by 12 min

Efficient Queue

Locality in General

Non-local Batched Access

Implementation
&
Evaluation

Implementation

Finish by 15 min

Runtime: Secure Computation

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

Runtime: Static Analysis

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

Conclusion

Finish by 20 min

Thank you

www.MightBeEvil.org

Samee Zahur <[email protected]>
David Evans <[email protected]>