Prio3: Private, Robust, and Scalable Computation of Aggregate Statistics and SNIPs

Prio3: Private, Robust, and Scalable Computation of Aggregate Statistics and SNIPs

Verifiable Distributed Aggregation Functions (VDAFs)

The collection of aggregated data is one of the most profitable industries in computing, but how can we efficiently harvest data without breaching user privacy? Well, a Multi-party Distributed Aggregation Protocol (DAP) is one answer, and the PRIO3 method is one of the best around for this.

While security has been applied to data while at rest and over the air, we often still do our computations on plaintext data. This opens up many problems, especially that the processor can determine PII (Personally Identifiable Information) and things like secret encryption keys. One approach is to use MPC (Multi-party Computation), and where we can split our computation up into smaller blocks, and give each of the parties a share of the computation. One of the best applications of this is to collect statistics in a privacy-aware manner.

For example, a mobile phone manufacturer may want to determine gender balance for the owners of their phones, but not actually reveal any specific person. For this, each client device creates an SNIP (secret-shared non-interactive proof) for their gender. Within PRIO3, this is a fast and efficient zero-knowledge proof. Then servers can receive these SNIPs, and check them for their validity. Once checked, they can then update their local accumulators for the current aggregation of statistics. Then, when we want ot reveal the gender balance from the client devices, they can then publish their aggregation totals:

Overall, none of the servers can determine whether the client is male or female, as a zero-knowledge proof of their gender is created; however, we can still compute the total. With PRIO3, none of the servers ever gets to see plaintext data, and is based on a classic paper [here][1]:

The PRIO3 implementation can be seen as generally part of a Multi-party Distributed Aggregation Protocol (DAP) for privacy measurement, and which is now progressing for standardisation with the IETF [here]:

We will use PRIO3 to create a number of shares for Boolean values (count), and then aggregate the data back. The core analysis is a basic count on whether something is True or False, and the data set is {true, false, true, true} and will count the number of true values [here]:

package main

import (
 "fmt"
 "crypto/rand"
 "os"
 "io"
 "strconv"
 "github.com/cloudflare/circl/vdaf/prio3/count"


)

func fromReader[T any](r io.Reader) (z T) {

 switch zz := any(&z).(type) {
 case *count.Nonce:
  _, _ = r.Read(zz[:])
 case *count.VerifyKey:
  _, _ = r.Read(zz[:])

 }

 return
}

var Context = []byte("Test")

func main() {
 NumShares := uint8(2)


 input := []bool{true,false,true, true}


 argCount := len(os.Args[1:])

 if argCount > 0 {
  a,_ := strconv.Atoi(os.Args[1])
  NumShares=uint8(a)
 }


 c, _ := count.New(NumShares, Context)

 params := c.Params()
 shares := params.Shares()

 aggShares := make([]count.AggShare, shares)
 for i := range aggShares {
  aggShares[i] = c.AggregateInit()
 }



 for _, mi := range input {
  nonce := fromReader[count.Nonce](rand.Reader)
  verifyKey := fromReader[count.VerifyKey](rand.Reader)

  randb := make([]byte, params.RandSize())
  _, _ = io.ReadFull(rand.Reader, randb)


  var pubShare count.PublicShare
  var inputShares []count.InputShare
  pubShare, inputShares, _ = c.Shard(mi, &nonce , randb)


  var prepStates []*count.PrepState
  var outboundPrepShares []count.PrepShare
  for i := range shares {
   state, share, _ := c.PrepInit(&verifyKey, &nonce, i, pubShare, inputShares[i])


   prepStates = append(prepStates, state)
   outboundPrepShares = append(outboundPrepShares, *share)
  }

  var prepMsg *count.PrepMessage
  prepMsg, _ = c.PrepSharesToPrep(outboundPrepShares)

  var outShare *count.OutShare
  for i := range shares {
   outShare,_ = c.PrepNext(prepStates[i], prepMsg)
   c.AggregateUpdate(&aggShares[i], outShare)

  }


 }

 numMeas := uint(len(input))
 aggResult, _ := c.Unshard(aggShares, numMeas)


 fmt.Printf("Inputs: %v\n\n", input)

 fmt.Printf("Number of inputs: %d\n\n", numMeas)
 fmt.Printf("Number of shares: %d\n\n", NumShares)
 fmt.Printf("Aggregated Count %d\n\n", *aggResult)


 for i := range shares {
  fmt.Printf("Share %v\n", aggShares[i])

 }
}

And a sample run [here]:

Inputs: [true false true true]

Number of inputs: 4

Number of shares: 4

Aggregated Count 3

Share {[[7227276485192055052]]}
Share {[[673113590378828220]]}
Share {[[14679250781088487564]]}
Share {[[14313847295054699691]]}

An example of summation is here:

PRIO3 for Verifiable Distributed Aggregation Functions for Summation with Go
The collection of aggregated data is one of the most profitable industries in computing, but how can we efficiently…asecuritysite.com

And for a histogram:

PRIO3 for Verifiable Distributed Aggregation Functions for Histograms with Go
The collection of aggregated data is one of the most profitable industries in computing, but how can we efficiently…asecuritysite.com

References

[1] Corrigan-Gibbs, H., & Boneh, D. (2017). Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX symposium on networked systems design and implementation (NSDI 17) (pp. 259–282).