You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@pirk.apache.org by wraydulany <gi...@git.apache.org> on 2016/09/17 05:42:13 UTC
[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 <ra...@gmail.com>
Date: 2016-09-17T04:14:14Z
Add math deck, make link on papers page.
commit 29e7941b010c99bdc8c09a4e0bf08995dbca6731
Author: Walter Ray-Dulany <ra...@gmail.com>
Date: 2016-09-17T04:55:16Z
Updated nav bar to say 'Papers & Presentations'
commit 7e79013b80052a1cdacf4dfacdce2d1a01809b6f
Author: Walter Ray-Dulany <ra...@gmail.com>
Date: 2016-09-17T04:55:30Z
Removed pirk_papers.md, an orphaned page with no links to it.
commit c804e7f0cf5c39ea313c6553eedd4f7f1dc8ae05
Author: Walter Ray-Dulany <ra...@gmail.com>
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 <ra...@gmail.com>
Date: 2016-09-17T05:03:36Z
Maybe now the for_users link will work?
commit f42bbadcd55b7d1bb2659c7e4d1b1a7f515511b3
Author: Walter Ray-Dulany <ra...@gmail.com>
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 <ra...@gmail.com>
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-pirk issue #92: [Pirk 67] - Add Slide Deck to the Website Document...
Posted by ellisonanne <gi...@git.apache.org>.
Github user ellisonanne commented on the issue:
https://github.com/apache/incubator-pirk/pull/92
+1 merging now
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
Re: Math deck (was: Re: [GitHub] incubator-pirk pull request #92:
[Pirk 67] - Add Slide Deck to the Website D...)
Posted by Walter Ray-Dulany <ra...@gmail.com>.
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 <jr...@gmail.com> 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 <ra...@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 <raydulany@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....@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
> > >>
> > >
> > >
> >
>
Re: Math deck (was: Re: [GitHub] incubator-pirk pull request #92:
[Pirk 67] - Add Slide Deck to the Website D...)
Posted by Ryan Carr <jr...@gmail.com>.
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 <ra...@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 <ra...@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....@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
> >>
> >
> >
>
Re: Math deck (was: Re: [GitHub] incubator-pirk pull request #92:
[Pirk 67] - Add Slide Deck to the Website D...)
Posted by Walter Ray-Dulany <ra...@apache.org>.
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 <ra...@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....@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
>>
>
>
Re: Math deck
Posted by Tim Ellison <t....@gmail.com>.
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.
I'd love to follow you down that path, but I fear I don't have the right
footwear. I'll admire the beautiful view from here. :-)
Regards,
Tim
Re: Math deck
Posted by Tim Ellison <t....@gmail.com>.
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 <
> eawilliams@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....@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....@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....@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
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
Re: Math deck
Posted by Walter Ray-Dulany <ra...@gmail.com>.
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 <
eawilliams@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....@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....@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....@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
> > >>>>
> > >>>
> > >>
> > >
> >
>
Re: Math deck
Posted by Ellison Anne Williams <ea...@apache.org>.
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....@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....@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....@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
> >>>>
> >>>
> >>
> >
>
Re: Math deck
Posted by Tim Ellison <t....@gmail.com>.
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....@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....@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
>>>>
>>>
>>
>
Re: Math deck
Posted by Walter Ray-Dulany <ra...@apache.org>.
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.
On Wed, Sep 21, 2016 at 12:14 PM, Tim Ellison <t....@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....@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
> >>
> >
>
Re: Math deck
Posted by Tim Ellison <t....@gmail.com>.
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....@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
>>
>
Re: Math deck
Posted by Ellison Anne Williams <ea...@apache.org>.
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....@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
>
Re: Math deck
Posted by Tim Ellison <t....@gmail.com>.
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
Re: Math deck
Posted by Walter Ray-Dulany <ra...@apache.org>.
> 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 <
eawilliamspirk@gmail.com> wrote:
> On Tue, Sep 20, 2016 at 12:10 PM, Tim Ellison <t....@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....@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.ellison@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
> > >>>>
> > >>>
> > >>
> > >
> >
>
Re: Math deck
Posted by Ellison Anne Williams <ea...@gmail.com>.
On Tue, Sep 20, 2016 at 12:10 PM, Tim Ellison <t....@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....@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....@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
> >>>>
> >>>
> >>
> >
>
Re: Math deck
Posted by Tim Ellison <t....@gmail.com>.
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.
>> 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....@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....@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
>>>>
>>>
>>
>
Re: Math deck
Posted by Walter Ray-Dulany <ra...@apache.org>.
> 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).
> 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.
> 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".
> 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.
What do you think?
Walter
On Tue, Sep 20, 2016 at 8:33 AM, Tim Ellison <t....@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....@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
> >>
> >
>
Re: Math deck
Posted by Tim Ellison <t....@gmail.com>.
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....@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
>>
>
Re: Math deck (was: Re: [GitHub] incubator-pirk pull request #92:
[Pirk 67] - Add Slide Deck to the Website D...)
Posted by Walter Ray-Dulany <ra...@apache.org>.
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....@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
>
Math deck (was: Re: [GitHub] incubator-pirk pull request #92: [Pirk
67] - Add Slide Deck to the Website D...)
Posted by Tim Ellison <t....@gmail.com>.
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...
Posted by asfgit <gi...@git.apache.org>.
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---