<story><title>iMessage with PQ3 Cryptographic Protocol</title><url>https://security.apple.com/blog/imessage-pq3/</url></story><parent_chain><item><author>andy_xor_andrew</author><text>I&amp;#x27;m way out of my depth in terms of the math here.&lt;p&gt;But my &amp;#x27;software engineer brain&amp;#x27; likes the ideal of using the prime factoring problem, because it&amp;#x27;s so simple to understand, and feels like some kind of universal primitive. &amp;quot;It&amp;#x27;s easy to multiply but hard to factor.&amp;quot; It just seems so intuitive.&lt;p&gt;But I&amp;#x27;m reading the &amp;#x27;learning with errors&amp;#x27; wiki page and it&amp;#x27;s beyond my comprehension.&lt;p&gt;There&amp;#x27;s a weird fear in my mind that all these &amp;quot;post quantum algorithms&amp;quot; are so complicated, with such a large surface area, that they may hide flaws. While prime factoring, or even the elliptic key stuff, is so simple to comprehend.&lt;p&gt;that said, obviously the experts know what they&amp;#x27;re doing, and I&amp;#x27;ll use what they suggest. just saying that this thought has crossed my mind.</text></item><item><author>sandyarmstrong</author><text>This is pretty fascinating. For easier reading, the Signal blog post [0] they link to is great.&lt;p&gt;Both Signal and Apple went with CRYSTALS-Kyber [1] as their post-quantum algorithm. If you&amp;#x27;re interested in the math, and maybe learned at some point about how classic public key cryptography is built on the idea that it&amp;#x27;s easy to multiply two primes, but hard to factor them, and how this (or other math problems) can be used as a one-way function to make encryption hard to break, the hard math problem that backs Kyber is the &amp;quot;learning-with-errors&amp;quot; [2] problem.&lt;p&gt;[0] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;signal.org&amp;#x2F;blog&amp;#x2F;pqxdh&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;signal.org&amp;#x2F;blog&amp;#x2F;pqxdh&amp;#x2F;&lt;/a&gt;&lt;p&gt;[1] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;pq-crystals.org&amp;#x2F;kyber&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;pq-crystals.org&amp;#x2F;kyber&amp;#x2F;&lt;/a&gt;&lt;p&gt;[2] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Learning_with_errors&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Learning_with_errors&lt;/a&gt;</text></item></parent_chain><comment><author>hannob</author><text>I know that thinking, but learning more about RSA, I came to realize that there&amp;#x27;s a flipside of this.&lt;p&gt;People think &amp;quot;RSA is easy&amp;quot;, because someone gave them a lecture of a simplified&amp;#x2F;wrong&amp;#x2F;insecure version of RSA. Pretty much all &amp;quot;simple introductions to RSA&amp;quot; you can find out there are wrong.&lt;p&gt;The truth is: RSA isn&amp;#x27;t that simple. If you want to have RSA, and want to have it secure, there&amp;#x27;s a whole bunch of things to consider. But RSA looks simple.&lt;p&gt;So lots of people go ahead and implement their RSA. And then you end up with, hey, I can break almost a third of the top 100 webpage&amp;#x27;s RSA implementations. (I&amp;#x27;m not kidding, I did that -&amp;gt; &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;robotattack.org&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;robotattack.org&amp;#x2F;&lt;/a&gt; .)&lt;p&gt;I think the fact that crystals-kyber is obviously not that simple may actually protect us. Because hopefully most peopple will end up using some hopefully well audited optimized free implementation, because they won&amp;#x27;t even have the idea that they could do this on their own.</text></comment>
<story><title>iMessage with PQ3 Cryptographic Protocol</title><url>https://security.apple.com/blog/imessage-pq3/</url></story><parent_chain><item><author>andy_xor_andrew</author><text>I&amp;#x27;m way out of my depth in terms of the math here.&lt;p&gt;But my &amp;#x27;software engineer brain&amp;#x27; likes the ideal of using the prime factoring problem, because it&amp;#x27;s so simple to understand, and feels like some kind of universal primitive. &amp;quot;It&amp;#x27;s easy to multiply but hard to factor.&amp;quot; It just seems so intuitive.&lt;p&gt;But I&amp;#x27;m reading the &amp;#x27;learning with errors&amp;#x27; wiki page and it&amp;#x27;s beyond my comprehension.&lt;p&gt;There&amp;#x27;s a weird fear in my mind that all these &amp;quot;post quantum algorithms&amp;quot; are so complicated, with such a large surface area, that they may hide flaws. While prime factoring, or even the elliptic key stuff, is so simple to comprehend.&lt;p&gt;that said, obviously the experts know what they&amp;#x27;re doing, and I&amp;#x27;ll use what they suggest. just saying that this thought has crossed my mind.</text></item><item><author>sandyarmstrong</author><text>This is pretty fascinating. For easier reading, the Signal blog post [0] they link to is great.&lt;p&gt;Both Signal and Apple went with CRYSTALS-Kyber [1] as their post-quantum algorithm. If you&amp;#x27;re interested in the math, and maybe learned at some point about how classic public key cryptography is built on the idea that it&amp;#x27;s easy to multiply two primes, but hard to factor them, and how this (or other math problems) can be used as a one-way function to make encryption hard to break, the hard math problem that backs Kyber is the &amp;quot;learning-with-errors&amp;quot; [2] problem.&lt;p&gt;[0] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;signal.org&amp;#x2F;blog&amp;#x2F;pqxdh&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;signal.org&amp;#x2F;blog&amp;#x2F;pqxdh&amp;#x2F;&lt;/a&gt;&lt;p&gt;[1] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;pq-crystals.org&amp;#x2F;kyber&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;pq-crystals.org&amp;#x2F;kyber&amp;#x2F;&lt;/a&gt;&lt;p&gt;[2] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Learning_with_errors&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Learning_with_errors&lt;/a&gt;</text></item></parent_chain><comment><author>pbsd</author><text>The LWE problem is one level of abstraction away from the fundamental lattice problems it reduces to. It is somewhat analogous to the Diffie-Hellman problem that many constructions reduce to, which itself is related to the lower-level discrete logarithm problem.&lt;p&gt;The lattice equivalent of integer factorization is the shortest vector problem: you&amp;#x27;re given n vectors of length m, and you have to find the sum of integer multiples of those vectors that comes closest to (or a small factor away from the closest) the zero vector. Say you have the 4 vectors&lt;p&gt;&lt;pre&gt;&lt;code&gt;    [ 3 92  4  2]
    [54  0 92 41]
    [19 91 61 48]
    [39 59 40 14].
&lt;/code&gt;&lt;/pre&gt;
The shortest vector that you can obtain from adding integer multiples of these vectors is [19  -8 -15   2], which you can obtain by 3*[39 59 40 14] + [19 91 61 48] - 2*[54  0 92 41] - 3*[ 3 92  4  2].&lt;p&gt;With only 4 vectors it is easy to find the solution here. But the hardness grows exponentially with the dimension, and the dimensions in cryptographically relevant lattices are in the hundreds to thousands.</text></comment>