hide and seek

Abstract

Hide and Seek is a method using bulletproofs bunz2018bulletproofs to prove your presence in a given time and area while keeping confidentiality of the actual location data (and timestamp).

Bulletproofs

A method developed to conduct confidential transactions in cryptocurrency. Most cryptocurrency has limited or no confidentiality. Similar to this term, there is anonymity, which is the measure of identity obscurity. Confidentiality is however, a term for concealing the amount of each transaction. Both are important.

Bulletproofs provides cryptographic proof that a secret number is in a given range. This is also called zero knowledge range proofs.

Example: A bank is asking a customer’s income. The customer does not want to report the exact amount. The bank asks for a range instead, the customer provides a proof. The bank does not know the actual amount but can verify.

Geo fences

A defined geolocation area is commonly called geofences, and a time range information is added to know the duration of that event. Hide and Seek can use different geometrical shapes.

Figure 1: bulletproofs can handle different shapes

Figure 1: bulletproofs can handle different shapes

Tablegeofence-type-table shows the different ranges and required ranges to express that shape.

Table 1: mapping of shapes and required ranges
shapedescription of rangesnumber of range
circledistance from the center1
rectanglewidth and height2
(poly) line w/ thicknessdistance from closest point and parameter2
polygonnumber of intersection of ray1number of intersections (1 for concave)
multiplenumber of intersection of raynumber of intersections

will this work? On Tracking Apps, Private Kit

System Architecture

API

API’s needed for the hide and seek platform

Node: I’ve decided to leave the loclock feature for the initial skateboard version

1. Core module

DONE a. Hide (l []Location, f Fence) Proof

generates a proof for a specific Fence. Fence contains a range of three values, Timestamp, Latitude, Longitude.

DONE b. Seek (f Fence, p Proof) bool

verifies the proof with the fence.

2. Back end

assuming this provides a HTTP REST API

DONE a. [GET] api/fence/{fid}

returns a json Fence object

DONE b. [GET] api/fences

returns a list of fence ids(fid)

DONE c. [POST] api/fence

client posts and saves a fence that should the request hold in the body. Response will contain a fence (fid)

DONE d. [POST] api/seek/{fid}

client posts a proof that should verified with the fence id. Initially it should just aggregate the bool values.

DONE (later) e. [POST] api/loclock

client posts a LocLock to the server. This is a hash of chained locations to keep integrity of the location list the client holds.

DONE (later) f. [GET] api/locklock/check

client checks if a locklock is valid by sending two hashes. The previous loclock, and Hash(Location). returns a bool if the combination exists in the database.

3. Mobile App (ios)

a. update_loclock(l LocLock) (later)

posts the latest loclock

b. fetchFenceIds() []fid

fetches the list of fence ids

c. fetchFence(fid) Fence

fetches one fence

d. hide(f Fence, locs []Location) Proof

generates the proof if the list of locations passed through that fence

e. postProof(p Proof)

posts a Proof

f. postFense(f Fence)

posts a new Fence

Range proof overview

This section is a mathmatical guide to understand the basic workings of range proofs.

representation of int numbers and the vector

Computers intrepet numbers as 0’s and 1’s. for example a the number 3 in normal terms (base 10) is represented as ‘11’ internally.

\[3 = 1 \cdot 2^1 + 1 \cdot 2^0\]

we can save the 1s and 0s in a vector like this

\[a = [1, 1]\]

so we can express a number in the following term.

\begin{equation} \label{eq} v = \langle a, 2^n \rangle \quad \unicode{x1f600} \end{equation}

we need a way to express element wise products. We use \(x\circ y\) for this. Since we’re just dealing with only 0s and 1s, the following should hold.

\[a \circ (a-1) = 0\]

it’s useful to handle \(a\) and \(a-1\) as separate things for the upcomming operations so we rename them \(a_L\) and \(a_R\).

\begin{eqnarray} a_L &=& a\\\
a_R &=& a-1\\\
a_L \circ a_R &=& 0 \quad \unicode{x1f600} \\\
(a_L - 1) - a_R &=& 0 \quad \unicode{x1f600} \\\
\end{eqnarray}

We want to consolidate the \(\unicode{x1f600}\)s into one statement. \(v\) is representing our secret number in a vector notation, where the others are relationships between thoes vectors. We introduce a new number, with a vector \(b\) which the verifier can choose the value of the base. This number will be always 0 if the elements of b is all 0.

\[\langle b, y^n \rangle = 0\]

this skeleton can be used to integrate the relations presented above.

\[ \langle a_L, a_R \circ y^n \rangle = 0 \\\
\langle (a_L-1)-a_R, y^n\rangle = 0 \]

now we can combine the it to make a single statement with a variable \(z\).

\[z^2v = z^2\langle a_L,2^n\rangle + z\langle a_L - 1 - a_R, y^n\rangle + \langle a_L, a_R \circ y^n\rangle\]

This relation should hold true in an arbitrary combination of y and z. We then want to convert this to a more useful form meeting the following criteria.

  1. A single inner product
  2. \(a_L\) and \(a_R\) appear separate in each side. \(\langle a_L, a_R\rangle\)
  3. factor out the non secret terms

we shuffle the last statement in the form of this,

TODO elaborate this

\[z^2v + z\langle 1, y^n\rangle = \langle a_L, z^22^n+zy^n+a_R \circ y^n\rangle + \langle -z, a_R \circ y^n\rangle\]

we add \(\langle -z, z^22^n+zy^n\rangle\) to both sides. Note that this does not contain any secret (\(a_R\) nor \(a_L\)). For the left side, we consolidate \(z\langle1,y^n\rangle + \langle -z, z^22^n+zy^n\rangle\) to \(\delta(z,y)\).

TODO elaborate this

\[z^2v + \delta(y,z) = \langle a_L-z, y^n \circ (a_R + z) z^22^n\rangle \quad \unicode{x1f61c}\]

now we can handle the inner product separately. To review, \(v\) and \(a_L\) and \(a_R\) represent the secret number, so we want to somehow hide it, while have this equation hold true.

Blinding \(a_L\) and \(a_R\)

we add a blinding factor \(s\) for each \(a\) vectors.

\[s_L, s_R \quad \underleftarrow{rand.} \quad \mathbb{Z}^n_p\]

and make a function for each side.

\[ l(x) = (a_L + s_Lx) - z \\\
r(x) = y^n \circ (a_R + s_Rx + z) z^22^n \]

\(x=0\) will be the same as the left side of eq \(\unicode{x1f61c}\)

TODO finish this

Commitment schemes

Commitment Schemes are used in range proofs. A commitment is a value that shows one holds a secret without exposing the actual secret. It is analogous to a cealed letter that later could be exposed that the sender had that secret. There are different types of commitment schemes, and for bulletproofs we are using Pedersen Commitments pedersen1991non. Pedersen commitments have four numbers involed, the secret number \(v\), a random number \(r\), and two prime numbers which holds a logarithmic relation.

ref: What is a Pedersen Commitment?

phd

Bibliography

[bunz2018bulletproofs] B"unz, Bootle, Boneh, Poelstra, Wuille & Maxwell, Bulletproofs: Short proofs for confidential transactions and more, 315-334, in in: 2018 IEEE Symposium on Security and Privacy (SP), edited by (2018)

[pedersen1991non] Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, 129-140, in in: Annual international cryptology conference, edited by (1991)


  1. The ray’s length could be calculated by the shapes longest diagonal length ↩︎