Matchings are perfect

💦 One of my favorite object in graph theory are Matchings, especially Perfect Matchings (PMs). Let me restate the definition of a PM briefly:

Definition (Perfect Matching). Given a graph $\mathcal{G} = (E,V)$, then a Perfect Matching $M$ is a set of pair-wise non-adjacent edges from $E$, such that every vertex in $V$ is touched by one edge in $M$.

Here is a little example for a two PMs in a graph:

Figure 1 - Top: The original graph $\mathcal{G}$; Below: The red lines indicate two example perfect matchings in $\mathcal{G}$

This post list some of the properties of PMs regarding finding and counting them in different graphs types. During writing this posts, i found that a similar listing can also be red in [6].

Dlogs and Factoring with polynomial number of arithmetic steps

❚ This post is related to a paper of mine, that will get published around the end of October this year in the Journal of Groups, Complexity and Cryptography (GCC). Some people may think, when they read the headline of this post, this must be a post about Shor's quantum factoring/dlog algorithm, because it is well known that dlogs and factoring can not be solved in polynomial number of arithmetic steps otherwise.

 But this is not true.

This sounds very unintuitive, because in cryptography we nearly always work with finite fields, where the bit length is restricted by the size of the modulus and the complexity of an algorithm is hence often measured as the number of arithmetic steps.

But of course you can do this, if you increase the available space. It is not obvious how to do it, but Adi Shamir [1] already showed in 1979 how this could be done, it you allow integers in memory/registers that are of exponential size.

A New Hope

There is new hope, new hope for a feasible algorithm that survives Quantum Computer attacks and will give us secure cryptographic key agreements in the future. It is based on Ring-LWE, where LWE is the abbreviation for Learning With Errors and Ring simply means, that you are working over some ring structure. Roughly you can put LWE in the corner of lattice based cryptography, which is one of the contestants for post-quantum cryptography. The other contestants are multivariate equations and coding based cryptography (i.e. McEliece and Niederreiter). In the meantime, one major application of LWE is also fully homomorphic encryption [4].

The underlying scheme for the $\text{NewHope}$ algorithm was proposed by Jintai Ding, Xiang Xie and Xiaodong Lin [1] in 2012, then got improved by Peikert in 2014 [2]. Joppe W. Bos, Craig Costello, Michael Naehrig and Douglas Stebila [3] presented an implementation in 2015. The next major improvement by Erdem Alkim, Léo Ducas, Thomas Pöppelmann and Peter Schwabe [4] finally led to the $\text{NewHope}$ algorithm.


Let me first describe Ring-LWE in a short, rather informal manner. Assume you have a system of equations, with unknowns $s_0,s_1,\ldots,s_{n-1}$.
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & = b_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & = b_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & = b_{m-1} \\
\end{align*} where usually $m > n$. Given this system of equations, pick $n$ equations and solve for $s_i$, which could be done using the folklore Gaussian elimination algorithm. For LWE, this system of equation is slightly changed. Instead of given a system of equations as above, you have:
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & \approx b_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & \approx b_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & \approx b_{m-1} \\
\end{align*} You only know the approximate value of each equation. To be a little bit more precise, we can write:
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & = b_0 + e_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & = b_1 + e_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & = b_{m-1} + e_{m-1} \\
\end{align*} where the $e_i$ are the small error terms that are sampled from a certain distribution. Solving this system of equations (of course with unknown $e_i$) is roughly speaking the Learning with Error problem. If you work over a ring, e.g. $\mathbb{Z}_q[x]/(f(x))$ you get Ring-LWE (some details are missing here, but this should illustrate the concept). The believe in its hardness stems from the fact Regev [6] proved that the LWE problem is as hard as to solve several worst-case lattice problems, which again are known to resist quantum computer attacks.

The question is: How can this be turned into key exchange protocol?

Using the ABC-Conjecture in Cryptography

The ABC-Conjecture is a very famous conjecture in Number Theory which is perhaps not a conjecture anymore if it the proof of Shinichi Mochizuki will turn out to be correct. I can not say anything useful about proving this conjecture, but i thought about its application for a while. Let me state the stronger version of the conjecture due to Baker [1];

ABC-Conjecture (strong, explicit version)

Given co-prime integers $a,b,c$ with $a + b = c$ then $$ c < (\text{rad}(abc))^{1.75}$$

The operator $\text{rad}$ (=radical) means the product of the distinct prime numbers dividing $n$. The version was derived from the (following) explicit ABC-Conjecture, also due to Baker:

ABC-Conjecture (explicit version)

Given co-prime integers $a,b,c$ with $a + b = c$ and let $\omega(n)$ be the number of distinct prime factors of $n$ then $$c < \frac{6}{5}\text{rad}(abc)\frac{(\log(\text{rad}(abc)))^{\omega(abc)}}{\omega(abc)!}$$

Assume you have co-prime integers $a,b,c$, wlog $a < b < c$, with $\text{rad}(a) < a^{1/6}$,  $\text{rad}(b) < b^{1/6}$ and $\text{rad}(c) < c^{1/6}$, then it is
\begin{align*}
 c &\leq \text{rad}(abc)^{1.75} = (\text{rad}(a)\text{rad}(b)\text{rad}(c))^{1.75}\\
 &< (a^{1/6}b^{1/6}c^{1/6})^{1.75} < (c^{1/2})^{1.75} = c^{15/16}\\
& < c
\end{align*} which is a contradiction and hence such integers can not exists. That's also the reason, why the even more famous Fermat Last Theorem follows from the ABC-Conjecture, which shows how deep the ABC-Conjecture is.

Observe the following simple Heuristic:

Homomorphic encryption using Ring Fixpoints

❚ In the previous post, i gave a short introduction about homomorphic encryption and presented the DGHV scheme [5] as an example. The scheme was published in 2010 and got several important updates from Coron et al. in the following papers:

[1], 2011 : The first improvement enhances the original system by reducing the size of the public key from $\mathcal{\tilde{O}}(\lambda^{10})$ to $\mathcal{\tilde{O}}(\lambda^{7})$. The idea is, to publish fewer elements that can be combined on-the-fly to reach a larger public key if necessary. To achieve this, they need the already discussed optimization to set $x_0 = pq_0$, hence they settle the system on the stronger partial approximate common divisor problem.

[2], 2012 : In this paper, they further reduce the size of the public key down to $\mathcal{\tilde{O}}(\lambda^5)$. Instead of storing the large numbers $r_i+pq_i$, they only store a public seed $\text{se}$ and a set of small $\delta_i$ values that are of size $~p$. To recover the original public key, the seed $\text{se}$ is fed into the PRNG and it is $x_i = \text{PRNG}_i(\text{se}) - \delta_i$. The published $\delta_i$ are chosen that way that $$x_i = \text{PRNG}_i(\text{se}) - \delta_i \equiv r_i\pmod{q}, r_i\;\text{small}$$ The $\delta_i$ are now of the same bitsize as $p$ which is much smaller than the $x_i$ values, that were stored previously. Additionally, the apply the concept of modulus switching to the DGHV scheme. Modulus switching is a technique to reduce the noise level of a ciphertext. It does not allow infinitely many homomorphic operations, but reduces the noise grow rate from exponentially to linear (i.e. a leveled scheme), which is huge.

[3], 2013 : In this paper, the authors enhance the performance of the DGHV scheme, by converting it to a batch scheme, i.e., a scheme which allows to simultaneously process a vector of plaintexts bits. Just view this technique as some kind of parallel execution. In a simplified form, their idea is not to use a single prime $p$ as their secret key, but to use several such primes $p_0,p_1,...,p_{l-1}$. Hence their public key consists not of integers $x_i = r_i+q_ip$ but $x_i = r_i+q_i\prod^{l-1}_{j=0} p_j$. Each $p_j$ is responsible for another plaintext bit, and the ciphertext is then $$c= \text{CRT}_{p_0,...,p_{l-1}}(2r_0+m_0,...,2r_{l-1}+m_{r-1}) + q\prod^{l-1}_{j=0} p_j$$ (CRT = Chinese Remainder Theorem). Each bit can be recovered individually by computing $c$ mod $p_j$.

[4], 2014 : In this paper, the authors apply the scale-invariant property to the DGHV scheme. This technique allows get linear noise grow rate but without modulus switching. The key trick is, given a ciphertext $c$, that the message is not anymore encoded in the least significant bit of $c\;\text{mod}\;p$ but in the most significant bit of $c\;\text{mod}\;p$. A ciphertext $c$ has the form $$\text{TYPE-1:}\;\;c = r + (m+2r')\frac{p-1}{2}+qp^2$$ After multiplication of two ciphertexts $c_1$ and $c_2$ one gets a ciphertext of the form $$\text{TYPE-2:}\;\;2c_1c_2 = r'' + m_1m_2\frac{p^2-1}{2}+q'p^2$$. Then they show how publicly convert a TYPE-2 ciphertext back to TYPE-1.

Below the fold, i show how to use fixpoints of a RSA modul for homomorphic encryption.