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
> > >>>>
> > >>>
> > >>
> > >
> >
>
