Makes sense, thanks Ellison Anne and Walter. While I think I grok enough of the encryption/decryption for now, I'm still plodding through the PIR mechanism.

## Advertising

There will be more questions ;-) Thank you for your tolerance. Regards, Tim On 22/09/16 14:45, Walter Ray-Dulany wrote: > I would like to emphasize this, because it is of the utmost importance. > > As just one example of how extremely bad it would be if we didn't pick > random zeta for every encryption, let's talk about zero. Zero is far and > away the most frequently encrypted number in Wideskies (see page 32 in the > slides). If zero always encrypts to a specific number, let's call it f, > then the responder, when it receives a query, is going to see that most (a > more appropriate phrase might be "the overwhelming majority") of the 2^{el} > E_i (I'm using 'el' instead of 'script-lower-case-L', for readability) all > have the same value f, and it can immediately assume that f is an > encryption of zero. Now in the course of forming its response, it notes > which of its terms hash to an index that is an encryption of zero, knowing > that those terms cannot be search terms. At the stopping-point of the > algorithm, the responder knows that none of those terms were search terms, > and this partial information shrinks the possible plaintext space, to the > detriment of the secrecy of the search terms. > > The special sauce of Paillier is, in fact, that you can choose this random > zeta, and use it to make a single number m encrypt to a *ton* of different > numbers all of which decrypt, without knowledge of zeta (but with knowledge > of the private key), to m. > > On Thu, Sep 22, 2016 at 5:23 AM, Ellison Anne Williams < > eawilli...@apache.org> wrote: > >> No - you would lose the semantic security. In other words, two encryptions >> of the same plaintext would be the same two ciphertexts. With a random >> zeta, I can encrypt two equal plaintexts and get two different ciphertexts. >> This is particularly important in Wideskies when encrypting the E_i values. >> >> On Thu, Sep 22, 2016 at 5:02 AM, Tim Ellison <t.p.elli...@gmail.com> >> wrote: >> >>> On 21/09/16 20:10, Walter Ray-Dulany wrote: >>>> Let me see if I understand you, but, if I do, then I would respond: >>> "Yes." >>>> >>>>> can I simply think of this as a way that one of the encryption values >> is >>>>> 'selected' during the encrypt process? >>>> >>>> When encrypting, because of our friendly random zeta, we can get many >>>> different ciphertexts from the same message. As you point out, when >>> taking >>>> E(5)*E(7) we can (and in your case, do) get another valid-but-distinct >>>> ciphertext corresponding to the message m=12. Additionally, there is >> some >>>> choice of zeta that would make E(12) encrypt to 19 instead of 208. >>> >>> Yep, that's what I meant. >>> >>> So why does Pirk provoke a different secure random number for each >>> encryption via Pailler#encrypt(BigInteger)? I don't see that it >>> enhances the security, since whatever random value we choose the >>> decryption is based solely upon knowing our p and q. >>> >>> Would it be ok to pick some zeta value when Paillier is initialized, and >>> stick with it? >>> >>> Regards, >>> Tim >>> >>>> On Wed, Sep 21, 2016 at 12:14 PM, Tim Ellison <t.p.elli...@gmail.com> >>> wrote: >>>> >>>>> With apologies for the lazy language...since there can be multiple >>>>> numbers in the encryption space that map back to the same plain text >>>>> number, can I simply think of this as a way that one of the encryption >>>>> values is 'selected' during the encrypt process? >>>>> >>>>> Taking my simple example, if I encrypt E() and decrypt D() the >> following >>>>> to test the homomorphic properties: >>>>> >>>>> E(5 + 7) mod N = 208 >>>>> D(E(5) * E(7) mod N^2) = D(19) >>>>> >>>>> hmm, but D(19) = D(208) = 12 so we are all good. >>>>> >>>>> Regards, >>>>> Tim (hoping to get to some PIR soon!) >>>>> >>>>> On 21/09/16 13:25, Ellison Anne Williams wrote: >>>>>> Ah, the math-magic of semantic encryption... :) (re: random zeta) >>>>>> >>>>>> We can certainly walk through the proof of the semantic encryption >> (the >>>>>> random zeta) as it is quite mathematically beautiful, but it will >> take >>> us >>>>>> even further down the algebraic path. >>>>>> >>>>>> On Wed, Sep 21, 2016 at 8:19 AM, Tim Ellison <t.p.elli...@gmail.com> >>>>> wrote: >>>>>> >>>>>>> On 19/09/16 18:36, Walter Ray-Dulany wrote: >>>>>>> <snip/> >>>>>>>> Let's see what we've got. >>>>>>>> >>>>>>>> ( (16**12)*(7**15) ) mod 225 = 208. >>>>>>>> >>>>>>>> I will leave it as an exercise to check that the decryption of 208 >> is >>>>> in >>>>>>>> fact 12. >>>>>>> >>>>>>> I like a challenge :-) >>>>>>> >>>>>>> So we got to p=3, q=5, and my encrypted value c=208. >>>>>>> >>>>>>> Following the Wideskies Pallier decryption algorithm, >>>>>>> Step (2): >>>>>>> N = p * q >>>>>>> = 15 >>>>>>> >>>>>>> lambda(N) = lcm(p-1,q-1) >>>>>>> = 4 >>>>>>> >>>>>>> Step (3): >>>>>>> mu = lambda(N) modinverse N >>>>>>> = 4 >>>>>>> >>>>>>> Step (4): >>>>>>> c' = c^lambda(N) mod N^2 >>>>>>> = 208^4 mod 225 >>>>>>> = 46 >>>>>>> >>>>>>> Step(5): >>>>>>> m' = L(c') >>>>>>> = ((c' - 1) / N) mod N >>>>>>> = (45 / 15) mod 15 >>>>>>> = 3 >>>>>>> >>>>>>> Step(6): >>>>>>> m = (m' * mu) mod N >>>>>>> = 12 >>>>>>> >>>>>>> yay! >>>>>>> >>>>>>> The fog is slowly clearing, though I'm totally baffled about how I >> can >>>>>>> pick a random zeta during encryption, and it plays no part in the >>>>>>> decryption. >>>>>>> >>>>>>> Regards, >>>>>>> Tim >>>>>>> >>>>>> >>>>> >>>> >>> >> >