I have a set S={1,2,...,N-1}. N=pq (where p and q are RSA prime numbers). Scenario is that User need to retrieve the Database blocks without revealing his block index to the Server i.e, Private Information Retrieval(PIR). Here numbers are used to retrieve the blocks with some pre=defined operations. Previous schems were using a number theoretic assumption Quadratic Residuosity Assumption( means two queries sent from the user to access a block are computationally indistinguishable. Means quadratic residue number for interested blocks and quadratic non-residue numbers for other not-interested blocks). Hence there exists a non-negligiable probability to know user interested blocks. That is, QR ($quadratic~residue$ set) $\cup$ QNR ($quadratic~nonresidue$ set) = $\mathbb{Z}_{N}^{+1}$. To retrieve interested blocks, numbers from QNR were being used and to retrieve not interested blocks, numbers from QR were being used.
But in our modified scheme, we use the entire sample space $\mathbb{Z}^{+1}_{n}$ irrespective of its domain element property (like Quadratic residue or Quadratic Non-residue) for both interested and not interested blocks. Means any element $x~\in~\mathbb{Z}_{N}^{+1}$ can be used to any block. Now how should i prove that number theoretic property (Quadratic residue or Quadratic Non-residue) is not directly useful (to leak user privacy . Here user privacy means his interested blocks) in order to know user interested block ?
Suppose, assume there are 4 blocks on the database server with some size. User has a set S={1,2,3,4,.....,N-1} and he needs to access $3^{rd}$ block without revealing that he is interested in $3^{rd}$ block (i.e, through PIR concept). Assume {1,2} are Quadratic Residue numbers and others are Quadratic Non-residue numbers. User need to send 4 numbers for 4 blocks and hence he selects randomly three numbers with a property Quadratic Residue and one with the property Quadratic Non-residue from the set $S$. After recieving the 4 numbers from the user, server applies some pre-defined operations on each block using respective numbers sent from the user and generates the output (4 output numbers for each block) and sends the output back to the user. On recieving the output, user does the reverse operation (reverse operation is done only for the interested block) carried out by the server in order to retrieve his interested block (i.e,$3^{rd}$ block). Server has some non-negligiable probability to know user interest based on the numbers (upon recognizing the number property (QR or QNR), user interest will be revealed) sent from the user.
Now if, instead of sending a number with the specific property to the interested blocks, we extended to use the entire set $S$ irrespective of the number property. So, how should we prove that the privacy is not dependent on the property of a number in an $Information-theoretic$ manner ?