Abstract:

We consider a secure verification problem in which Alice wants to verify whether her signal Xn is compatible with Bob's signal Yn, where Xn and Yn are drawn i.i.d. according to a joint distribution p(x,y). The notion of compatibility is defined as the requirement that p(x,y) belongs to a certain set A of allowable joint distributions. For privacy, Alice jointly encrypts and encodes Xn and transmits the result over a public channel to Bob. Using the information leaked by the encryption algorithm, Bob verifies the compatibility of Xn with Yn. We characterize the minimum information that Alice's encryption and coding algorithm must leak in order to guarantee reliable verification results. Further, we determine the maximum information that Bob can hope to extract about Xn if he is curious. It is shown that a source/channel separation theorem holds for this scenario.