Re: Math deck (was: Re: [GitHub] incubator-pirk pull request #92: [Pirk 67] - Add Slide Deck to the Website D...)
One explicit vote, one implicit vote for updating/clarifying the slides.
I've created PIRK-69 to improve slide clarity.
Unless this doesn't make sense (tell me) I'll mark PRs on this as WIPs
until I've got some agreement from the community that the slides are clear
enough.
On Mon, Sep 19, 2016 at 3:31 PM, Ryan Carr wrote:
> 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
> 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 >
> > 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
Re: Math deck (was: Re: [GitHub] incubator-pirk pull request #92: [Pirk 67] - Add Slide Deck to the Website D...)
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
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
> 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,
Re: Math deck (was: Re: [GitHub] incubator-pirk pull request #92: [Pirk 67] - Add Slide Deck to the Website D...)
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
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 h
Re: Math deck (was: Re: [GitHub] incubator-pirk pull request #92: [Pirk 67] - Add Slide Deck to the Website D...)
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 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 th
Math deck (was: Re: [GitHub] incubator-pirk pull request #92: [Pirk 67] - Add Slide Deck to the Website D...)
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
[GitHub] incubator-pirk pull request #92: [Pirk 67] - Add Slide Deck to the Website D...
Github user asfgit closed the pull request at: https://github.com/apache/incubator-pirk/pull/92 --- If your project is set up for it, you can reply to this email and have your reply appear on GitHub as well. If your project does not have this feature enabled and wishes so, or if the feature is enabled but not working, please contact infrastructure at infrastruct...@apache.org or file a JIRA ticket with INFRA. ---
[GitHub] incubator-pirk pull request #92: [Pirk 67] - Add Slide Deck to the Website D...
GitHub user wraydulany opened a pull request: https://github.com/apache/incubator-pirk/pull/92 [Pirk 67] - Add Slide Deck to the Website Documentation Explaining the Mathematics of Pirk This PR does the following: * Adds a slide deck (please read it, make comments, assert errors, indicate where it's too confusing, and so on) * Updates the website to point to the paper, and makes a few other minor changes to pages that mention papers. * Eliminates an orphaned page. You can merge this pull request into a Git repository by running: $ git pull https://github.com/wraydulany/incubator-pirk PIRK-67 Alternatively you can review and apply these changes as the patch at: https://github.com/apache/incubator-pirk/pull/92.patch To close this pull request, make a commit to your master/trunk branch with (at least) the following in the commit message: This closes #92 commit c701bb0761fcaf8a96631c3c4c5fc8bf0fd7faf2 Author: Walter Ray-Dulany Date: 2016-09-17T04:14:14Z Add math deck, make link on papers page. commit 29e7941b010c99bdc8c09a4e0bf08995dbca6731 Author: Walter Ray-Dulany Date: 2016-09-17T04:55:16Z Updated nav bar to say 'Papers & Presentations' commit 7e79013b80052a1cdacf4dfacdce2d1a01809b6f Author: Walter Ray-Dulany Date: 2016-09-17T04:55:30Z Removed pirk_papers.md, an orphaned page with no links to it. commit c804e7f0cf5c39ea313c6553eedd4f7f1dc8ae05 Author: Walter Ray-Dulany Date: 2016-09-17T05:00:36Z Noticed that for_users had a pretend link to the wideskies paper. fixed. commit e21588e8ddce5a3fc0a12235f3cb288ab5d6e262 Author: Walter Ray-Dulany Date: 2016-09-17T05:03:36Z Maybe now the for_users link will work? commit f42bbadcd55b7d1bb2659c7e4d1b1a7f515511b3 Author: Walter Ray-Dulany Date: 2016-09-17T05:19:55Z Added short descriptions to each of the paper/slide links in Papers and Presentations. commit 850014f4bd39d135aaf692c466569da2fff23a8d Author: Walter Ray-Dulany Date: 2016-09-17T05:39:24Z Noticed a missing 'with' in the math deck. --- If your project is set up for it, you can reply to this email and have your reply appear on GitHub as well. If your project does not have this feature enabled and wishes so, or if the feature is enabled but not working, please contact infrastructure at infrastruct...@apache.org or file a JIRA ticket with INFRA. ---
