Hey Walter / Tim,
I just wanted to add I had some trouble similar to Tim's when trying to
understand the Wideskies paper. As a person without a background in group
theory/theoretical math trying to get my head around this stuff, it was
very difficult for me to even find with Google what the notations (Z/NZ)
and (Z/N^2 Z)^x (also called (Z/N^2 Z)* in the Wideskies/Paillier papers)
meant. Since these concepts are so central to how the algorithm works, I
think it would be really helpful if we had a footnote the first time those
are introduced defining that notation with links to a more in-depth
explanation, or at least a phrase that can be Googled to reliably find it.
Thanks,
-Ryan Carr
On Mon, Sep 19, 2016 at 1:50 PM Walter Ray-Dulany <raydul...@apache.org>
wrote:
> Correction:
>
> ...bby the binomial theorem, (1+N)**N = 1 + N*N + other terms divisible...
>
> I multiplied by N on the left when I ought to have exponentiated
>
> Walter
>
> On Mon, Sep 19, 2016 at 1:36 PM, Walter Ray-Dulany <raydul...@apache.org>
> wrote:
>
> > Hi Tim,
> >
> > 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'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
> >
> > 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
> >
> > **************************
> >
> > > 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.
> >
> > 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.
> >
> > **************************
> >
> > > 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.
> >
> > **************************
> >
> > 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.
> >
> > **************************
> >
> > 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,
> >
> > Walter
> >
> >
> >
> > 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
> >>
> >
> >
>
