Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to implement an interactive (secure) protocol which operates only on integers. Here's what I have:

$$ f(x) = \sum_i{a_i K_i} + b $$

$$ K_i = \dfrac{1}{1 + \gamma \|x - s_i\|^2}$$

where $ 0 < i \le M $ and $$ \|x - s_i \|^2 = \sum_{j=1}^{N}{(x_j - s_{ij})^2}.$$

Because the server has to work only with encrypted values, it needs to engage in an interactive protocol with the client in order to perform the division. So, basically, the server computes every $ 1 + \gamma \|x - s\|^2 $ value, blinds each of them multiplicatively with a random factor $ r_i $ ($ 0 < r_i < 2^{100} $) and sends the value vector to the client to perform the division. After the client divides 1 by each blinded value, it sends the results back to the server, which multiplies each received value by $ r_i $, to remove the blinding, and then it computes $ f(x) $.

Now, the above protocol works nice, if the numbers are floating point, but, unfortunately, the server can only work with encrypted integers (it performs homomorphic additions on them). In order to overcome this issue, I need to scale all the values accordingly:

$$ K_{ri} = \dfrac{s_{\gamma} s_f^2 s_k s_r}{r_i (s_{\gamma} s_f^2 + \gamma s_{\gamma} \|x s_f - s_i s_f\|^2)}$$

where:

  • $ s_{\gamma} $ is the scaling applied to $ \gamma $
  • $ s_f $ is the scaling applied to $ x $ and $ s_i $
  • $ s_r $ is the scaling needed to compensate for the blinding factor $ r_i $
  • $ s_k $ specifies how many decimals should be preserved after the division, because the value of $ K $ itself also needs to be scaled

After the client sends back the $ K_{ri} $ values, the server computes $ f(x) $:

$$ f(x_i) = \sum_i{a_i s_a K_{ri} r_i} + b s_b $$

where:

  • $ s_a $ is the scaling applied to $ a_i $
  • $ s_b $ is the scaling which needs to be applied to $ b $

Since $ b $ is usually large enough, it's sufficient to scale it with the scaling that is implied from the other factors.

Now, my problem is that I am having a really hard time figuring out how to construct $ s_b $ in order to compensate for $ s_r $. I think it should be a trivial thing, but I've been staring at the formulas for many hours and I can't figure it out. For starters, it needs to contain $ s_a s_k s_{\gamma} s_f^2 $, but what do I do about $ s_r $, given that $ 0 < r_i < 2^{100} $? There is no way to communicate the size of each $ r_i $ to the client, and the multiplication $ K_{ri} r_i $ seems to mess everything up...

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

To avoid confusion, let me use the superscript $\,^*$ to denote the scaled variables. So the unscaled return value $$K_{ri} = K_i / r = \frac{1}{r_i(1 + \gamma\|x - s_i\|^2)}$$ corresponds to the scaled return value $$K^*_{ri} = \frac{s_{\gamma} s_f^2 s_k s_r}{r_i (s_{\gamma} s_f^2 + \gamma s_{\gamma} \|x s_f - s_i s_f\|^2)} = \frac{s_{\gamma} s_f^2 s_k s_r}{s_{\gamma} s_f^2 r_i (1 + \gamma \|x - s_i\|^2)} = s_k s_r K_{ri}.$$

Now, you want to calculate the scaled version of $$f(x) = \sum_i{a_i K_i} + b =\sum_i{a_i K_{ri} r_i} + b,$$ namely $$f^*(x) = \sum_i{a_i s_a K^*_{ri} r_i} + b s_b = \sum_i{a_i s_a s_k s_r K_{ri} r_i} + b s_b.$$

If $b = 0$, we have $f^*(x) = s_a s_k s_r f(x)$. To make this equation apply even when $b \ne 0$, we need to choose $$s_b = s_a s_k s_r.$$

share|improve this answer
    
Thanks for correcting my sloppy latex and thanks for helping me see the obvious. I mixed some stuff up in my implementation and the formulas stopped making sense. –  Mihai Todor Jul 8 '12 at 21:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.