Contact Elucyda to upgrade your cybersecurity strategy by systematically analyzing your cryptographic inventory to ensure crypto-agility and interoperability in practical implementations of cryptographic algorithms, including Transport Layer Security (TLS), the Secure Shell Protocol (SSH Protocol), X.509 certificates and S/MIME (Secure/Multipurpose Internet Mail Extensions). The aim is to achieve your security goals by implementing evidence-based changes informed by a risk assessment specific to your long-term security requirements.
Quantum-safe/quantum-resistant/post-quantum cryptography (PQC) mitigates risks from quantum cryptanalysis performed with a cryptographically relevant quantum computer (CRQC) capable of running polynomial-time algorithms for order-finding and discrete logarithms. CRQCs enable retrospective decryption of confidential data (harvest now, decrypt later) and threaten digital signatures. Public-key/asymmetric cryptographic algorithms based on factoring (e.g. RSA with minimum 3072-bit modulus) or the generalized discrete logarithm problem (e.g. DH with minimum 3072-bit modulus, ECDH & ECDSA with curve P-384) are vulnerable to quantum cryptanalysis. Symmetric block ciphers (e.g. AES-256 in GCM mode) and cryptographic hash algorithms (e.g. SHA-384, SHA-512) are at low risk from quantum cryptanalysis.
Post-quantum migration targets high risk asymmetric algorithms responsible for key establishment and digital signatures. High risk asymmetric algorithms can either be replaced with low risk PQC alternatives or combined with PQC to produce hybrid PQC algorithms. Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM) and Module-Lattice-Based Digital Signature Standard (ML-DSA) are examples of PQC algorithms based on lattice problems. Implementations using ML-KEM-1024 & ML-DSA-87 are intended to meet long-term security requirements. ML-KEM-768 & ML-DSA-65 are suitable for applications where improved performance is required. Stateful hash-based signature schemes (e.g. LMS & XMSS) are appropriate for digitally signing software and firmware.
Contact Konstantin for enquiries. Visit the Elucyda YouTube Channel for educational video series that elucidate mathematics & physics. Download Elucyda Educational Resources to view diagrams in PDF format. Explore the explanations below which elucidate quantum algorithms and provide context for the transition to post-quantum cryptography.
A uniform superpostion of all computational basis states in a \(\beta\)-qubit register is defined as \begin{align*} \ket{+}^\beta =H^{\otimes \beta}\ket{0}^\beta =\frac{1}{\sqrt{2^\beta}}\sum\limits_{v \in\mathbb{Z}_{2^\beta}} \ket{v}^\beta =\underbrace{\sqrt{\frac{|T|}{2^\beta}}}_{\sin \frac{\theta}{2}}\overbrace{\frac{1}{\sqrt{|T|}}\sum\limits_{t \in T} \ket{t}^\beta}^{\ket{T}^\beta} +\underbrace{\sqrt{1-\frac{|T|}{2^\beta}}}_{\cos \frac{\theta}{2}}\overbrace{\frac{1}{\sqrt{2^\beta -|T|}}\sum\limits_{u \notin T} \ket{u}^\beta}^{\ket{\perp}^\beta}, \end{align*} where \(|T|=C\) is the total number of targets in the set \(T\), \(\ket{T}^\beta\) is the target superposition and \(\ket{\perp}^\beta\) is the non-target superposition. For quantum search and counting, it is useful to consider the relationship, $$ \frac{|T|}{2^{\beta}}=\sin^2\left(\pi\frac{\theta}{2\pi}\right)=\sin^2\left(\pi\left(1-\frac{\theta}{2\pi}\right)\right) \approx\sin^2\left(\pi 2^{-\alpha}\left[\pm\frac{\theta}{2\pi}\right]\right).$$ \(\beta\) must be chosen such that \(|T|<2^{\beta -1}\) and \(\alpha\) determines the number of bits in the approximations \(\left[\pm\frac{\theta}{2\pi}\right]\). The search iteration operator is defined as \begin{align*} U_\theta=H^{\otimes\beta}\left(2\ket{0}^\beta\bra{0}-I_{2^\beta}\right)H^{\otimes\beta}\left(I_{2^\beta} - 2\sum\limits_{t\in T}\ket{t}^\beta\bra{t}\right) =H^{\otimes\beta}\left(2\ket{0}^\beta\bra{0} - \sum\limits_{v\in \mathbb{Z}_{2^\beta}}\ket{v}^\beta\bra{v}\right)H^{\otimes\beta}\left(\sum\limits_{u\notin T}\ket{u}^\beta\bra{u} - \sum\limits_{t\in T}\ket{t}^\beta\bra{t}\right), \end{align*} with the eigenstates \(\ket{\pm i}^\beta=\frac{1}{\sqrt{2}}\left(\ket{\perp}^\beta\pm i\ket{T}^\beta\right)\) satisfying \(U_\theta\ket{\pm i}^\beta=e^{\mp i \theta}\ket{\pm i}^\beta\). The search iteration can be thought of as the composition of 2 reflections, defined as $$R=H^{\otimes\beta}\left(2\ket{0}^\beta\bra{0}-I_{2^\beta}\right)H^{\otimes\beta}, \quad \Omega=I_{2^\beta} - 2\sum\limits_{t\in T}\ket{t}^\beta\bra{t},$$ where \(\Omega\) is the oracle that marks the target states with a phase factor, so that \(\Omega\ket{T}^\beta=-\ket{T}^\beta\) and \(\Omega\ket{\perp}^\beta=\ket{\perp}^\beta\). The oracle can be expressed with a function that outputs 1 for targets and 0 for non-targets, so that \(\forall t\in T, f(t)=1, \Omega\ket{t}^\beta=-\ket{t}^\beta\) and \(\forall u\notin T, f(u)=0, \Omega\ket{u}^\beta=\ket{u}^\beta\). Both cases can be expressed as \(\forall v\in \mathbb{Z}_{2^\beta}, \Omega\ket{v}^\beta=(-1)^{f(v)}\ket{v}^\beta\). To perform the quantum search algorithm, amplify the target state amplitudes by repeatedly applying the search iteration operator to produce the state, \begin{align*} U_\theta^q\ket{+}^\beta &=\cos\left(\theta\left(\frac{1}{2}+q\right)\right)\ket{\perp}^\beta +\sin\left(\theta\left(\frac{1}{2}+q\right)\right)\ket{T}^\beta \\ &=\frac{1}{\sqrt{2}}\left(e^{-i \theta\left(\frac{1}{2}+q\right)}\ket{+i}^\beta+e^{+i \theta\left(\frac{1}{2}+q\right)}\ket{-i}^\beta\right) =\frac{1}{\sqrt{2}}\sum\limits_{\zeta \in\{-1,+1\}}e^{\zeta i \theta\left(\frac{1}{2}+q\right)}\ket{-\zeta i}^\beta, \end{align*} where the number of iterations that maximizes target amplitudes is $$ q=\left\lfloor \frac{\pi}{2\theta} \right\rfloor=\left\lfloor \frac{\pi}{4\arcsin\left(\sqrt{|T|2^{-\beta}}\right)} \right\rfloor \leq \left\lceil \frac{\pi}{4}\sqrt{\frac{2^{\beta}}{|T|}} \right\rceil ,$$ then measure the state after amplitude amplification. Repeat amplitude amplification and measurement until all targets have been identified.
To estimate the number of targets (counting), repeatedly prepare then measure the state, \begin{align*} &\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}} F^\dagger_{2^\alpha} \ket{z}^\alpha U_\theta^z \ket{+}^\beta \\ &=\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\frac{1}{\sqrt{2^\alpha}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} e^{-2\pi i zx 2^{-\alpha}} \ket{x}^\alpha \frac{1}{\sqrt{2}}\sum\limits_{\zeta \in\{-1,+1\}} e^{\zeta i\theta \left(\frac{1}{2}+z\right)}\ket{-\zeta i}^\beta \\ &=\frac{1}{\sqrt{2}}\sum\limits_{\zeta \in\{-1,+1\}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} 2^{-\alpha}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(\zeta \frac{\theta}{2\pi}-\left(x+\left[\zeta \frac{\theta}{2\pi}\right]\right)2^{-\alpha}\right)}\right)^z e^{\zeta i\frac{\theta}{2}} \ket{x+\left[\zeta \frac{\theta}{2\pi}\right]}^\alpha \ket{-\zeta i}^\beta \\ &\approx\frac{1}{\sqrt{2}}\sum\limits_{\zeta \in\{-1,+1\}} e^{\zeta i\frac{\theta}{2}} \ket{\left[\zeta \frac{\theta}{2\pi}\right]}^\alpha \ket{-\zeta i}^\beta =\frac{1}{\sqrt{2}}\left(e^{-i\frac{\theta}{2}} \ket{\left[-\frac{\theta}{2\pi}\right]}^\alpha \ket{+i}^\beta +e^{+i\frac{\theta}{2}} \ket{\left[+\frac{\theta}{2\pi}\right]}^\alpha \ket{-i}^\beta\right), \end{align*} to obtain the \(\alpha\)-bit approximations which can be used to compute \(C=|T|\approx 2^{\beta}\sin^2\left(\pi 2^{-\alpha}\left[\pm\frac{\theta}{2\pi}\right]\right)\), where \(\left[+\frac{\theta}{2\pi}\right]\) and \(\left[-\frac{\theta}{2\pi}\right]\) are \(\alpha\)-bit approximations of \(2^{\alpha}\frac{\theta}{2\pi}\) and \(2^{\alpha}\left(1-\frac{\theta}{2\pi}\right)\), respectively.
Order-finding: Given \(N,a,r\in \mathbb{N}\) such that \(1 < a < N\) and \(gcd(a,N)=1\), find the order \(r=|a|\) which is the smallest positive integer such that \(a^r=1 \, mod\, N\). Powers of \(a\) are computed \(mod \, N\).
If \(2|r\wedge a^{\frac{r}{2}}\neq -1\) compute \(gcd\left(a^{\frac{r}{2}}\pm 1, N\right)\) to find factors of \(N\). This works because \(\left(a^{\frac{r}{2}}-1\right)\left(a^{\frac{r}{2}}+1\right)=a^r-1=0\). Repeat with other choices of \(a\) until all prime factors of \(N\) have been identified.
Discrete logarithm: The discrete logarithm can be expressed as \(s=\log_a p \, mod \, N\), where \(s\in\mathbb{Z}_r\) satisfies \(1 < s < r\). The aim is to find \(s\) such that \(a^s=p\).
For \(z,k\in\mathbb{Z}\), the order-finding function is defined as \[f_1(z)=a^z=a^z\times (a^r)^k=a^{z+kr}=f_1(z+kr).\] For \((z,h)\in\mathbb{Z}_r\times\mathbb{Z}_r\) and \(l\in\mathbb{Z}_r\), the discrete logarithm function is defined as \[f_2(z,h)=a^{z+sh}=a^{(z-ls)+s(h+l)}=f_2(z-ls,h+l)=f_2(z+sh,0)=f_1(z+sh)=a^z\times(a^s)^h=a^z\times p^h.\] Both functions exhibit periodicity. They output 1 for the inputs, \[f_2(-ls,l)=f_2(0,0)=f_1(0)=f_1(kr)=a^r=1,\] and they output \(p\) for the inputs, \[f_2(0,1)=f_2(s,0)=f_1(s)=a^s=p.\] Order-finding and discrete logarithms can both be described as hidden subgroup problems.
Hidden subgroup problem: Find a generating set for the hidden subgroup \(H\leq G\) given the function \(f:G\longrightarrow X\) for which \(\forall g_1,g_2\in G, f(g_1)=f(g_2)\longleftrightarrow g_1 H=g_2 H\).
The \(a\)-multiplier \(U_a\) and \(p\)-multiplier \(U_p\) are operators with the properties, $$ U_a\ket{\underbrace{f_1(z)}_{a^z}}^\beta = \ket{\underbrace{f_1(z+1)}_{a^z\times a=a^{z+1}}}^\beta, \quad U_p\ket{\underbrace{f_1(z)}_{a^z}}^\beta = \ket{\underbrace{f_1(z+s)}_{a^z\times p=a^{z+s}}}^\beta, \quad U_a^s=U_p,$$ with the eigenstates, $$ U_a\ket{\lambda(\zeta)}^\beta = e^{2\pi i \zeta r^{-1}}\ket{\lambda(\zeta)}^\beta, $$ which can be combined in the superposition of \(a\)-multiplier eigenstates, \begin{align*} U_a^z\ket{f_1(0)}^\beta=\ket{f_1(z)}^\beta&= \frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} e^{2\pi i z\zeta r^{-1}}\ket{\lambda(\zeta)}^\beta. \end{align*} \(z\) iterations of the \(a\)-multiplier and \(h\) iterations of the \(p\)-multiplier can produce the state, \begin{align*} U_p^h U_a^z\ket{1}^\beta=\ket{a^z p^h}^\beta=\ket{f_2(z,h)}^\beta=\ket{f_1(z+sh)}^\beta =\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} e^{2\pi i (z+sh)\zeta r^{-1}}\ket{\lambda(\zeta)}^\beta. \end{align*} To perform the quantum order-finding algorithm, repeatedly prepare and measure the quantum state, \begin{align*} &\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}} F^\dagger_{2^\alpha} \ket{z}^\alpha \ket{f_1(z)}^\beta \\ &=\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\frac{1}{\sqrt{2^\alpha}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} e^{-2\pi i zx 2^{-\alpha}} \ket{x}^\alpha \frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} e^{2\pi i z\zeta r^{-1}}\ket{\lambda(\zeta)}^\beta \\ &=\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} 2^{-\alpha}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(\zeta r^{-1}-\left(x+\left[\zeta r^{-1}\right]\right)2^{-\alpha}\right)}\right)^z \ket{x+\left[\zeta r^{-1}\right]}^\alpha \ket{\lambda(\zeta)}^\beta \\ &\approx\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} \ket{\left[\zeta r^{-1}\right]}^\alpha \ket{\lambda(\zeta)}^\beta. \end{align*} To perform the quantum discrete logarithm algorithm, repeatedly prepare and measure the quantum state, \begin{align*} &\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}} F^\dagger_{2^\alpha} \ket{z}^\alpha \frac{1}{\sqrt{2^\alpha}}\sum\limits_{h \in\mathbb{Z}_{2^\alpha}} F^\dagger_{2^\alpha} \ket{h}^\alpha \ket{f_2(z,h)}^\beta \\ &=\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\frac{1}{\sqrt{2^\alpha}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} e^{-2\pi i zx 2^{-\alpha}} \ket{x}^\alpha \frac{1}{\sqrt{2^\alpha}}\sum\limits_{h \in\mathbb{Z}_{2^\alpha}}\frac{1}{\sqrt{2^\alpha}}\sum\limits_{y \in\mathbb{Z}_{2^\alpha}} e^{-2\pi i hy 2^{-\alpha}} \ket{y}^\alpha \frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} e^{2\pi i (z+sh)\zeta r^{-1}}\ket{\lambda(\zeta)}^\beta \\ &=\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} \sum\limits_{x \in\mathbb{Z}_{2^\alpha}} 2^{-\alpha}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(\zeta r^{-1}-\left(x+\left[\zeta r^{-1}\right]\right)2^{-\alpha}\right)}\right)^z \ket{x+\left[\zeta r^{-1}\right]}^\alpha \\ &\quad\sum\limits_{y \in\mathbb{Z}_{2^\alpha}} 2^{-\alpha}\sum\limits_{h \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(s\zeta r^{-1}-\left(y+\left[s\zeta r^{-1}\right]\right)2^{-\alpha}\right)}\right)^h \ket{y+\left[s\zeta r^{-1}\right]}^\alpha \ket{\lambda(\zeta)}^\beta \\ &\approx\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} \ket{\left[\zeta r^{-1}\right]}^\alpha \ket{\left[s\zeta r^{-1}\right]}^\alpha \ket{\lambda(\zeta)}^\beta. \end{align*} The order \(r\) and the discrete logarithm \(s\) can be determined after repeated measurement of the \(\alpha\)-qubit registers, since \(\left[\zeta r^{-1}\right]\) and \(\left[s\zeta r^{-1}\right]\) are \(\alpha\)-bit approximations of \(2^{\alpha}\zeta r^{-1}\) and \(2^{\alpha}s\zeta r^{-1}\), respectively. In the quantum algorithms for counting targets, order-finding and discrete logarithms, the amplitudes are described by an expression of the form, \[2^{-\alpha}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)}\right)^z =2^{-\alpha}\frac{1-e^{2\pi i\left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)2^{\alpha}}}{1-e^{2\pi i\left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)}}\] where \(\omega=\pm\frac{\theta}{2\pi},\zeta r^{-1},s\zeta r^{-1}\) in these 3 examples. The absolute square of this expression is \[2^{-2\alpha}\frac{\left|\sin{\left(\pi \left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)2^{\alpha}\right)}\right|^2}{\left|\sin{\left(\pi \left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)\right)}\right|^2},\] which peaks when \(x=0\) for sufficient choice of \(\alpha\), leaving non-zero \(x\) values with negligible probabilities.
Explore a geometric visualization of the quantum search algorithm:
How does the quantum search algorithm work when the number of non-targets is 3 times the number of targets? Only a single iterative rotation is required to ensure a target state is measured. This is successful amplitude amplification. Explore a geometric visualization of this ideal example for quantum search:
Does the quantum search algorithm still work with an equal number of targets and non-targets? Iterative rotations preserve the original 1/2 probability for measuring a target state. Instead of amplitude amplification, there is amplitude preservation. This is why \(\beta\) must be chosen such that \(|T|<2^{\beta -1}\). Explore a geometric visualization of this limiting case for quantum search:
Explore this side-by-side comparison of quantum teleportation and superdense coding:
