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

Yes! Slide 22 (formerly slide 16) is wrong; zeta is in (Z/NZ)*. I, or
someone else, can update the slides.

Good catch.

On Tue, Sep 20, 2016 at 4:10 PM, Ellison Anne Williams <
eawilliamsp...@gmail.com> wrote:

> 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