On Tue, Sep 20, 2016 at 12:10 PM, Tim Ellison <t.p.elli...@gmail.com> wrote:

> On 20/09/16 15:20, Walter Ray-Dulany wrote:
> >> Is this the same as I've seen this written elsewhere as double stroked Z
> >> subscript N?
> >
> > Most definitely. I write it the way that I do to for historical reasons
> > (mathematical and personal).
>
> Ok, works well in ascii comments too.
>
> >> I assume that, practically, it is better to work with smaller factors
> to make
> >> the math operations faster (but not too small to compromise security)
> and
> >> chunk the message accordingly, rather than working with large messages.
> >
> > This is precisely what Pirk does.
>
> I guess my question is, does Pirk change the message chunk size
> depending upon the bit length of N?  Seems that there is going to be
> some correlation there - if the message length is too small you are
> doing more calculations than necessary.
>
> Is this chunking the DataPartitioner's job?  In which case I see the
> built-in partitioners are all going to 8-bit partitions.
>

No - just to be clear - the message size is independent of the modulus size
(N). The message is broken up into 'chunks' (currently 8 bits in length)
and then 'striped' across the rows of the matrix in order to perform the
encrypted query. This data 'chunking' is the responsibility of the
DataPartitioner in Pirk. There are other dependencies with N in the
parameter selection, but the message size is not one of them.



> >> Whoa, why is g = 1 + N the standard Wideskies g?
> >
> > (1) It works (as I showed above), and (2) it turns out that all such g
> are
> > powers of (1+N). I'm not going to prove that, but it's true.
> >
> > Paillier's paper goes into detail about how the security of the system is
> > independent of the g one chooses. Since g is public, and since the
> security
> > of the system does not suffer for just choosing the same g every time,
> > Wideskies just says "screw it, we're going with 1+N".
>
> I'm curious, but I'll draw the line there and trust :-)
>
> >> How do you want to receive proposed changes to the PDF, if at all?  I'm
> rephrasing
> >> your version a bit as I go, and quite happy to keep it separate so
> there is
> >> a simple version for those that don't "speak algebra".
> >
> > I've created another issue, PIRK-70, to add the LaTeX beamer doc from
> which
> > I generated the pdf, along with the relevant Pirk images. These docs will
> > live in the main branch (not the web branch) under contrib. This is in
> > addition to the changes I've made to the PDF to clarify the math
> language.
> > With the TeX there, anyone can edit the doc, if they so choose. Tim, you
> > could do that, or roll your own in whatever format you like.
>
> Cool, thanks.  I'll keep working my way through it as I get a few mins.
>
> Please can you clarify, the doc for Wideskies algorithm (slide 16) says
> that zeta is chosen to be in (Z/N^2 Z)* -- but the code we have in
> Paillier.java[1] appears to be selecting for (Z/NZ)*
>
> [1]
> https://github.com/apache/incubator-pirk/blob/master/
> src/main/java/org/apache/pirk/encryption/Paillier.java#L257
>
> Regards,
> Tim
>
> > What do you think?
> >
> > Walter
> >
> > On Tue, Sep 20, 2016 at 8:33 AM, Tim Ellison <t.p.elli...@gmail.com>
> wrote:
> >
> >> On 19/09/16 18:36, Walter Ray-Dulany wrote:
> >>> Apologies! It's disorienting at first, and most of all when one
> actually
> >>> tries to sit down and do a real example. The version on the slides was
> >> not
> >>> written in one go, I assure you.
> >>>
> >>> Let's go through, and see what's not working.
> >>
> >> I appreciate your patience Walter.  I'm sure this "just makes sense" to
> >> you, but my brain is hurting trying to keep up :-)
> >>
> >>> **************************
> >>>
> >>>> I'm trying a very simple example.  I'm going to choose, p = 3, q = 5
> and
> >>> a message m = 42
> >>>
> >>> Already we're in trouble. p and q are fine; but remember that the
> >> plaintext
> >>> space (let's call it P(N)) is the set of all integers in Z/NZ; that is,
> >> it
> >>> is all numbers m
> >>>
> >>> 0 <=  m < N
> >>
> >> Ah, so understanding the notation was confusing me, which is not going
> >> to help!  Is this the same as I've seen this written elsewhere as double
> >> stroked Z subscript N?
> >>
> >>> You can see already that the m you chose is not in the plaintext space.
> >>>
> >>> Let's pick a new m to continue with; in this case, let's choose your m,
> >> but
> >>> mod 15 so that it lies in P(N). Thus, our new m going forward shall be
> >>>
> >>> m = 12
> >>
> >> Interesting.  That means that the size of message I can encode directly
> >> using this scheme is related to the bit length of my RSA factors.
> >>
> >> I assume that, practically, it is better to work with smaller factors to
> >> make the math operations faster (but not too small to compromise
> >> security) and chunk the message accordingly, rather than working with
> >> large messages.
> >>
> >>> **************************
> >>>
> >>>> I'm going to pick g = 240.  I think it needs to be a multiple of N
> that
> >>> is greater than N*N, correct?
> >>>
> >>> No, and this is important. g has to be an element of (Z/(N squared )Z)*
> >> of
> >>> order a nonzero multiple of N. That sentence is meaningless unless
> you're
> >>> already embedded in the mathematics, so let's go through what it means,
> >> bit
> >>> by bit.
> >>>
> >>> g must be:
> >>> 1. *an element of (Z/(N squared)Z)**: everything but the outer * on the
> >>> right just means that 0 <= g < N*N; in this case that means 0 <= g <
> 225.
> >>> The outer * on the right indicates that we only want to take a certain
> >>> special kind of g: one that is what we call a *unit* mod N*N; that is,
> it
> >>> means that we require that there exist another element 0<= h < N*N such
> >>> that g*h = 1 mod N*N. In our current situation, N = p*q is a product of
> >>> primes, and so N*N = p**2 * q**2, and we can easily characterize G =
> >> (Z/(N
> >>> squared)Z)*: G = { 0<= g < N*N such that neither p nor q divide g}. So
> as
> >>> long as we pick a g that does not have p or q as a factor, we're good
> for
> >>> this condition (this also includes 0, so really all of my "0 <=" in
> this
> >>> paragraph could have been "0 < "). Another way to characterize G is to
> >> say
> >>> that it is the set of integers less than N*N that are relatively prime
> to
> >>> N*N.
> >>
> >> Ok, got that.
> >>
> >>> 2. *of order a nonzero multiple of N*: this is a little trickier.  The
> >>> *order* of an element g of a finite group (which G is) is the least
> >> integer
> >>> k such that g^k = 1 in G. I'm not going to prove it here, but it turns
> >> out
> >>> that every element of G has finite order (that is, if g is in G, then
> >> there
> >>> exists a finite non-zero k such that g^k = 1), and that it is less than
> >> or
> >>> equal to the Carmichael number lambda(N*N). That takes care of what
> >> 'order'
> >>> means, and, like I said, order is defined for all g in G. But! We
> >> require a
> >>> special order. Specifically, we only want g in G such that the order
> of g
> >>> is a non-zero multiple of N. We might ask whether we know that such
> >> always
> >>> exists (a good question, since we require it), and we do! Here's a
> quick
> >>> proof of existence, one tied closely to Wideskies:
> >>>
> >>> * Take g = 1 + N (I'm going to prove, all at once, that 1+N is in G and
> >>> that it has an order that fits the bill).
> >>> * Consider g**N: by the binomial theorem, (1+N)*N = 1 + N*N + other
> terms
> >>> divisible by N*N. This number is equivalent to 1 mod N*N. QED
> >>>
> >>> Ok, great, such g exist, and so we can require that we use one of them.
> >> But
> >>> you must be careful: you can't just choose any g in G off the street
> and
> >>> expect it will satisfy our requirements. You chose g = 240, which (1)
> >>> bigger than N*N, which isn't what we want, and (2) is divisible by N,
> and
> >>> so even if we take 240 mod N*N, we still aren't in G, much less of the
> >>> 'right order' (turns out 240, being not relatively prime to N, can
> never
> >> be
> >>> exponentiated to 1 mod N*N). For now, let's just take the standard
> >>> Wideskies g, g = 1 + N = 16. If you want to go through this with a
> >>> different g, give it a shot, but make sure it's got the right kind of
> >> order.
> >>
> >> Whoa, why is g = 1 + N the standard Wideskies g?
> >>
> >> I was following what you said, and thinking, ok I've got to pick a value
> >> for g that
> >>  (i)   does not have p or q as a factor,
> >>  (ii)  0 <= g < N*N, and
> >>  (iii) has multiplicative order that's a non-zero multiple of N
> >>
> >> this is going to take some finding ... then you simply say N + 1 ?!
> >>
> >> I would go through with a different g, but it may take me a while to
> >> sift through and find one without knowing the trick :-)
> >>
> >>> **************************
> >>>
> >>>> I'll pick zeta = 21.  I think it needs to be greater than N.
> >>>
> >>> As in point 2, no. We require zeta to be in (Z/NZ)*, which, similar to
> >> the
> >>> above, means a number
> >>>
> >>> 0 < zeta < N such that zeta is a unit.
> >>>
> >>> You picked 21; if we take 21 mod N we get zeta = 6, which is not a unit
> >> (in
> >>> particular it is not relatively prime to p=3). Let's pick the next
> number
> >>> greater than 6 which is in (Z/NZ)*, which is
> >>>
> >>> zeta = 7.
> >>
> >> So apart from the fact that I picked all the numbers incorrectly I was
> >> on the right lines :-)  D'oh.
> >>
> >>
> >>> **************************
> >>>
> >>> 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'll get to decryption in a moment.  I want to have this encrypt sorted
> >> first.
> >>
> >>> **************************
> >>>
> >>> Ok, that's all so far. If the above is still not computing (literally
> or
> >>> metaphorically), I am available to converse one-on-one either over the
> >>> phone or some other medium (face time or what have you) and only too
> >> happy
> >>> to go over this more.
> >>>
> >>> Let me know,
> >>
> >> Thanks for the offer.  I'm happy to demonstrate my ignorance on the
> >> list, and work towards a description that hopefully is useful to anyone
> >> else coming from the same direction.
> >>
> >> How do you want to receive proposed changes to the PDF, if at all?  I'm
> >> rephrasing your version a bit as I go, and quite happy to keep it
> >> separate so there is a simple version for those that don't "speak
> algebra".
> >>
> >> Regards,
> >> Tim
> >>
> >>
> >>> On Mon, Sep 19, 2016 at 12:13 PM, Tim Ellison <t.p.elli...@gmail.com>
> >> wrote:
> >>>
> >>>> On 17/09/16 06:42, wraydulany wrote:
> >>>>>     [Pirk 67] - Add Slide Deck to the Website Documentation
> Explaining
> >>>> the Mathematics of Pirk
> >>>>
> >>>> Argh! Walter you are driving me mad! :-)
> >>>>
> >>>> Thank you for putting up the slides, and I really want to grok this,
> but
> >>>> I'm struggling to work through even the simplest of examples.
> >>>> I need the kindergarten version :-(
> >>>>
> >>>> What am I doing wrong?  I'm trying a very simple example.  I'm going
> to
> >>>> choose,
> >>>> p = 3, q = 5 and a message m = 42
> >>>>
> >>>> Looking at page 11 on the math_deck.pdf line by line
> >>>>
> >>>> line 2:
> >>>>   N = 15.
> >>>>   I'm going to pick g = 240.  I think it needs to be a multiple of N
> >>>> that is greater than N*N, correct?
> >>>>
> >>>> line 3:
> >>>>   I'll pick zeta = 21.  I think it needs to be greater than N.
> >>>>
> >>>> Line 4:
> >>>>   (240^42 x 21^15) mod 225 = 0
> >>>>
> >>>> That's suspicious.
> >>>> ...and if I play with my free choices of m, g and zeta I always get
> >> zero.
> >>>>
> >>>> Help!
> >>>>
> >>>> I get the gist of the flow through the deck, but I want to work
> through
> >>>> my own examples from top to bottom.
> >>>>
> >>>> Regards,
> >>>> Tim
> >>>>
> >>>
> >>
> >
>

Reply via email to