{"id":1983,"date":"2024-06-01T00:01:39","date_gmt":"2024-06-01T04:01:39","guid":{"rendered":"https:\/\/mathvoices.ams.org\/featurecolumn\/?p=1983"},"modified":"2024-07-15T11:58:33","modified_gmt":"2024-07-15T15:58:33","slug":"lattices-plane-and-not-so-plane","status":"publish","type":"post","link":"https:\/\/mathvoices.ams.org\/featurecolumn\/2024\/06\/01\/lattices-plane-and-not-so-plane\/","title":{"rendered":"Lattices, Plane and Not-So-Plane"},"content":{"rendered":"

Suppose this blog\u2019s editor Ursula and I want to create a shared secret to use as a password to access this blog post…<\/em> <\/span><\/p>\n

Lattices, Plane and Not-So-Plane<\/h1>\n

Courtney Gibbons<\/strong>
\nHamilton College<\/strong><\/p>\n

In January 2023, Bill Casselman wrote a great column<\/a> introducing readers to lattices that imagined them as vectors in the plane and described some cryptographic applications. This got me thinking about a lovely little paper I read from the 1950s that summarized some of the then-new developments in semigroup theory involving a completely different algebraic object named \u2013 you guessed it! \u2013 a lattice. [1]<\/a> And, to bring us full circle, the reason I was reading about lattice ordered semigroups was because they offer some interesting possibilities for cryptology, some of which I\u2019ll sketch at the end.<\/p>\n

For me, a lattice is a partially ordered set satisfying some extra conditions. For example, in the sketch below, some pairs of vegetables are related by “higher than” or “lower than”, while others can’t be compared. That’s a partial order!<\/p>\n

\"Four
A little lettuce-ordered math joke.<\/figcaption><\/figure>\n

What about semigroups? I want to start with a little example to keep us company. (If you’re more comfortable with formal definitions, you’ll find one in the appendix<\/a>.) Let $B = \\{0,1\\}$ and equip it with operations $+$ and $\\cdot$ as below:<\/p>\n

\"Logical
Logical “or” and logical “and” give rise to these operation tables.<\/figcaption><\/figure>\n

These operations may seem familiar if you have seen the truth tables for the logical “or” and the logical \u201cand\u201d \u2013 indeed, if you think of $0$ as false and $1$ as true, addition is “or” and multiplication is “and.”<\/p>\n

Put on your algebra hat for a moment and consider the following questions:<\/p>\n

    \n
  1. Are these operations closed? That is, if you add two things in $B$, do you land back in $B$? Same question for multiplication!<\/li>\n
  2. Are these operations associative? I.e., does it matter where you put parentheses when adding three or more things? Same question for multiplication!<\/li>\n
  3. Are these operations commutative? I.e., does order matter?<\/li>\n
  4. Is there an additive identity? I.e., is there an element $z$ for which $z + a = a + z= a$ for all $a \\in B$?<\/li>\n
  5. Is there a multiplicative identity? I.e., is there an element $e$ for which $e \\cdot a = a \\cdot e = a$ for all $a \\in B$?<\/li>\n<\/ol>\n

    The answers to all of these questions are “yes” and in particular, the additive identity is $0$ and the multiplicative identity is $1$. Here are two questions for which the answer is “no”:<\/p>\n

      \n
    1. Since $1$ is not the additive identity, we can ask if $1$ has an additive inverse: is there an element $a \\in B$ for which $a + 1 = 1 + a = 0$?<\/li>\n
    2. Since $0$ is not the multiplicative identity, we might hope that it has a multiplicative inverse. Is there an element $a \\in B$ for which $a \\cdot 0 = 0 \\cdot a = 1$?<\/li>\n<\/ol>\n

      Examining the addition table, you\u2019ll see the answer is that $1$ does not have an additive inverse. And $0$ doesn\u2019t have a multiplicative inverse.<\/p>\n

      Now that we\u2019ve collected these properties, we can call $(B,+)$ what it is: an abelian semigroup with identity (or an abelian monoid). That is, $+$ is an associative, commutative binary operation on $B$ and $0$ is the identity. (Similarly, $(B,\\cdot)$ is an abelian semigroup with identity.)<\/p>\n

      But that\u2019s not the main attraction. Let\u2019s consider matrices with entries from $B$ where matrix operations are defined with $+$ and $\\cdot$ as above. For instance, matrix addition is a little different:<\/p>\n

      $$\\begin{bmatrix} 1 \\\\ 1 \\\\ 0 \\end{bmatrix} + \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix} 1+1 \\\\ 1+0 \\\\ 0+ 0 \\end{bmatrix} = \\begin{bmatrix} 1 \\\\ 1 \\\\ 0 \\end{bmatrix}$$<\/p>\n

      and the dot product looks a little different:<\/p>\n

      $$\\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix} \\cdot \\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix} = 1\\cdot 1 + 1 \\cdot 1 = 1 + 1 = 1$$<\/p>\n

      and similarly, matrix multiplication looks different! When we get down to the entries of the resulting matrix, our operations are happening in $B$ so multiplication by $1$ and $0$ act as expected, and so does adding $0$. But whenever we try to add $1$ and $1$, we get $1$ again.<\/p>\n

      Now, the set $X$ of $n \\times n$ matrices with entries from $B$ is also a semigroup with identity, but it\u2019s no longer abelian (here’s some homework: come up with an example to show that matrix multiplication need not commute).<\/p>\n

      And in [2]<\/a>, Luce collects some other matrix operations that we can do with these matrices, which he attributes to Birkhoff: intersection, union, complementation, and inclusion. For the purposes of this column, we\u2019re interested in inclusion because it makes $X$ something called a lattice-ordered semigroup. <\/p>\n

      \"an
      Examples of the matrix operations collected by Luce in [2].<\/figcaption><\/figure>If you assert that $0 < 1$, then you can do entry-by-entry comparisons for two $n \\times n$ matrices. We can say $A$ is included in $B$ and write $A \\leq B$ provided that $A_{i,j} \\leq B_{i,j}$ for every entry. (If we know the matrices are not equal, we\u2019ll use $<$; otherwise we\u2019ll hedge our bets with $\\leq$.)<\/p>\n

      We see, for example,
      \n$ \\begin{bmatrix} 0 & 0 \\\\ 0 & 0 \\end{bmatrix} < \\begin{bmatrix} 1 & 0 \\\\ 0 & 0 \\end{bmatrix} < \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} < \\begin{bmatrix} 1 & 1 \\\\ 0 & 1 \\end{bmatrix} < \\begin{bmatrix} 1 & 1 \\\\ 1 & 1 \\end{bmatrix}$.<\/p>\n

      But not every matrix is directly comparable: neither $\\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix}$ nor $ \\begin{bmatrix} 1 & 0 \\\\ 1 & 0 \\end{bmatrix}$ can be related to the other by $<$.<\/p>\n

      If you draw a picture of the scenario for $2 \\times 2$ matrices, you get something like this:<\/p>\n

      \"The
      a lattice of the elements of the semigroup; an element $A$ with a line drawn upwards to another element $B$ captures the relationship $A \\lneq B$<\/figcaption><\/figure>\n\n

      There are books aplenty about lattice-ordered (semi)groups, but one of the reasons I looked at them initially is because one of my research students showed me a paper [3]<\/a> in which the authors suggest reimagining the Diffie-Hellman key exchange protocol using semigroup actions.<\/p>\n

      Example 1.<\/em><\/strong>
      \nTraditional Diffie-Hellman key exchange works like this: Suppose this blog\u2019s editor       Ursula<\/a> and I want to create a shared secret (or “key”) to use as a password to access this blog post. We can do this using a combination of public and private information.<\/p>\n

      First, we agree on a positive integer that will serve as a base for exponentiation later. Let\u2019s call the base $x$.<\/p>\n

      In private, Ursula picks a positive integer, $a$ and computes $u = x^a$. Meanwhile, and also in private, I pick a positive integer, $b$. Ursula sends me $u$ and I calculate $u^b$.<\/p>\n

      You may have already guessed that I send $c = x^b$ to Ursula ($c$ for Courtney!).<\/p>\n

      Now, our shared secret is $s = u^b = (x^a)^b = x^{ab} = x^{ba} = (x^b)^a = c^a$ thanks to the commutativity of exponentiation. And if $x$, $a$, and $b$ are biggish, it\u2019s really hard to figure out what $h$ is because it requires solving something called the discrete logarithm problem (DLP): What is $\\log_x u$? If you weren\u2019t privy to Ursula\u2019s thought process, you have to crank this out using whatever algorithms are available to you for computing logarithms.<\/p>\n

      Example 1.5.<\/em><\/strong>
      \nUrsula and Courtney agree that $g = 7$. You observe $u = 117649$ and $c = 5764801$. One (very slow!) algorithm you might use is repeated division by $7$ and discover, after a few long divisions by hand, that $a = 6$.<\/p>\n

      Now you have the same information Ursula does, so you can work out that $h = 5764801^6$. This turns out to be quite large, with 40ish digits. [4]<\/a><\/p>\n

      Anyway, you can imagine that this algorithm does not scale well. Neither do the other traditional computing algorithms (although there are weaknesses in the implementation of Diffie-Hellman key exchange!) [5]<\/a> In fact, to tie back to Bill Casselman’s column<\/a>, experts at agencies like NIST recommend using elliptic curves instead of \u201cmod-p\u201d Diffie-Hellman.<\/p>\n

      But there\u2019s another possible implementation that you can do with semigroups. The revised key exchange protocol with semigroups looks something like this:<\/p>\n

      Example 2.<\/em><\/strong>
      \nUrsula and Courtney agree ahead of time on an element $x$ in a finite set $S$ (think column vectors) and a semigroup $(X,*)$ (think square matrices) that acts on $S$ (think matrix multiplication). The semigroup $X$ should be special: it should have an identity and it shouldn\u2019t be a group \u2013 in fact, it shouldn\u2019t even be able to be embedded in a group (meaning, you can\u2019t easily \u201cfix\u201d the problem of inverses by inventing them if they don\u2019t exist).<\/p>\n

      In this situation, Ursula picks an element $a$ that commutes with every other element of $X$, and calculates $u = ax$. Ursula sends this new element to Courtney who has chosen her own element $b$ that commutes with everything in $X$. Their shared secret is $b (a x) = (b *a) x = (a*b) x = a (b x)$ (which gives you an idea of how Ursula computes their shared secret). Notice you need to pick elements that commute with every other element (i.e., pick elements in the center of $G$) to ensure that $b*a = a*b$, or else you\u2019ll only end up with a shared secret if you accidentally pick elements that commute with each other.<\/p>\n

      The security of this implementation depends on the difficulty of calculating orbits of elements under the semigroup action. To my knowledge, this hasn\u2019t been studied too much \u2013 and that\u2019s how I got interested in these Boolean matrices as examples of lattice-ordered semigroups!<\/p>\n

      \n

      Appendix<\/strong><\/h2>\n<\/p>\n

      For the reader who finds definitions comforting, here are the definitions of a semigroup and a semigroup action:<\/p>\n

      A semigroup<\/strong> $(G,*)$ is a set $G$ with a binary, associative operation $*$. It may have an identity element for the operation $*$, in which case you can call it a monoid<\/strong>. If you have a monoid and every element also has $*$-inverses, you have a group<\/strong>. If every element in your semigroup\/monoid\/group commutes, you can tack on the adjective abelian. [Mandatory bad joke: what\u2019s purple and commutes? An abelian grape! Even worse joke: What\u2019s purple, commutes, and is worshipped by 11 people? A finitely venerated abelian grape!]<\/p>\n

      The center<\/strong> of a semigroup\/monoid\/group is the set of all elements that commute with all other elements (that is, it\u2019s the set $Z(G) = \\{z \\in G \\, : \\, z * a = a*z \\, \\forall \\, a \\in G\\}$.).<\/p>\n

      A semigroup action<\/strong> of $(G,*)$ on a set $S$ is a map $\\odot: G \\times S \\to S$ where $g \\odot (h \\odot s) = (g*h) \\odot s$ (and if $G$ has an identity element, $e$, we insist $e \\odot s= s$).<\/p>\n

      References and End Notes<\/strong><\/h2>\n
        \n
      1. With apologies to David A. Singer, who has one of the best punny titles<\/a> you could hope for in a textbook.<\/li>\n
      2. Duncan R. Luce, A Note on Boolean Matrix Theory<\/em>, Proceedings of the American Mathematical Society, 3, 1952, pp. 382-388. This is a nice accessible and short paper if you\u2019re looking for something fun to read and have an introduction to linear algebra under your belt.<\/li>\n
      3. Maze, Monico, and Rosenthal, Public Key Cryptography Based on Semigroup Actions<\/em>, Advances in Mathematics of Communications Vol. 1, No. 4, 2007<\/li>\n
      4. Indeed, $h = 36703368217294127796651824617432373264384$. If you have a kiddo in your life who likes to know how to \u201csay\u201d large numbers, you can impress them with this one: \u201c36 duodecillion 703 undecillion 368 decillion 217 nonillion 294 octillion 127 septillion 796 sextillion 651 quintillion 824 quadrillion 617 trillion 432 billion 373 million 264 thousand 384\u201d \u2013 and then use your new clout to convince them that place value is what matters, not names!<\/li>\n
      5. David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thom\u00e9, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-B\u00e9guelin, and Paul Zimmermann, Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice<\/em>, 22nd ACM Conference on Computer and Communications Security (CCS \u201915), Denver, CO, October 2015. Even if you aren\u2019t an expert, this is an accessible read!<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

        Suppose this blog\u2019s editor Ursula and I want to create a shared secret to use as a password to access this blog post… Lattices, Plane and Not-So-Plane Courtney Gibbons Hamilton College In January 2023, Bill Casselman wrote a great column introducing readers to lattices that imagined them as vectors inRead More →<\/a><\/span><\/p>\n","protected":false},"author":5,"featured_media":2037,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":true,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[147,6,10],"tags":[107,163,164,162],"class_list":["entry","author-cgibbons","post-1983","post","type-post","status-publish","format-standard","has-post-thumbnail","category-147","category-algebra-and-number-theory","category-courtney-gibbons","tag-cryptography","tag-lattices-posets","tag-posets","tag-semigroups"],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/cropped-FC1380x500x2.png?fit=1380%2C288&ssl=1","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/1983","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/comments?post=1983"}],"version-history":[{"count":11,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/1983\/revisions"}],"predecessor-version":[{"id":2009,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/1983\/revisions\/2009"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/media\/2037"}],"wp:attachment":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/media?parent=1983"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/categories?post=1983"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/tags?post=1983"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}