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.

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

Reply via email to