A Symmetric PIR scheme $($henceforth SPIR$)$ is a PIR scheme where, at the end, Alice learns nothing more than xi

$.$ We will

allow the databases to share a common random string; however, the length of that string will be one of our parameters.

$($Recall that a is Quadratic Residue modulo m$,$ if z

$2$ a $($modulo m$))$ Hint: User wanting to download item i$,$

downloads n $1$ random quadratic residues modulo m$,$ a$1,$ a$2,...,$ ai$1,$ ai$+1,...,$ an$.$ User also generates one quadratic

non$-$residue bi

$.$ The user then sends a$1,$ a$2,...,$ ai$1,$ bi

$,$ ai$+1,...,$ an$.$ Server then computes R $$ u

X$1$

$1$

$$ u

X$2$

$2$

$...$ u

Xn

n

$.$

Where $($X$1,$ X$2,...,$ Xn$)$ is a one bit database held by the server and ui

$$s are the series of the numbers received by the

server. Of course, recall that server cannot distinguish between a residue and a non$-$residue.

$1.$ Describe the CPIR protocol based on the quadratic residue assumption. Why does the protocol work? $(5$ marks$)$

$2.$ Is the Quadratic Residue based PIR protocol SPIR? Prove it either way