Beta Binomial Encryption

Question

For the sake of example, suppose we have a list of advertisements $\{A_i\}_{i=1}^n$, each of which have parameters $I_i$: the number of impressions, and $C_i$ the number of clicks. Then $C_i/I_i$ denotes the click-thru rate of advertisement $i$.

I'm writing an MAB Thompson sampler, whose job is to sample from advertisements $\{A_i\}$. This works by sampling a random values according to:

$$\theta_i\approx \mbox{Beta}(\alpha+C_i-1,\beta+I_i-C_i-1),$$

after which we choose advertisement $A_s$, where $s=\mbox{argmax}_i(\{\theta\}_{i=1}^n)$.

Due to security reasons, I can't explicitly show $I_i,C_i$ anywhere in the code (this is happening client-side). So I was thinking that instead of delivering $I_i,C_i$, I could deliver transformed versions $\tilde{I}_i,\tilde{C}_i$ of these, and exploit some of the equivalence properties of beta distributions. My worry is that this isn't enough: if you know the true values must be integers, then maybe there's a way to recover the original values. Suggestions?

Answer 1

The problem with using any symmetries is that they are symmetric, so you can easily reverse them, so this sounds rather like a security through obscurity strategy. It would be enough for your adversary to learn what kind of symmetries did you use, to decode your data.

The simple obfuscation that can be used in here is to add noise to the values of $I_i, C_i$, where the amount of noise is proportional to the altered values. If reasonable amount of noise is added, then this should not have a great impact on the results. You possibly would need to check (e.g. by simulation) how much noise is "acceptable" and if it adds enough secrecy. On another hand, this would still give your adversary an occasion to learn about approximate values of $I_i, C_i$.

In the comments you worry that the $I_i/C_i$ ratio tends to be very small and this could lead to problems. First of all, if you alter the values proportionally to their initial values, this should not have much impact. Second, if your aim is to sample probabilities, so to randomly allocate advertisements, then if the "noisy" probabilities would be slightly larger then the true value, this would lead displaying the adds more often then it is needed. In multi-armed bandit scenario this would lead to adding additional layer of randomization to allocating the adds and this does not have to be bad. If they would be smaller, this should not have impact as well since you probably won't choose those adds as well. It is a accuracy vs privacy trade-off, that you are going to face.

The idea of adding noise to the data is related to differential-privacy, so you could read more about the theory behind it.