{"id":2059,"date":"2018-04-23T15:31:22","date_gmt":"2018-04-23T14:31:22","guid":{"rendered":"https:\/\/www.quantum-bits.org\/?p=2059"},"modified":"2022-08-12T17:16:21","modified_gmt":"2022-08-12T16:16:21","slug":"on-quantum-computing-and-cryptography","status":"publish","type":"post","link":"https:\/\/www.quantum-bits.org\/?p=2059","title":{"rendered":"On quantum computing and cryptography"},"content":{"rendered":"<p>Cryptography is the cornerstone of <a title=\"Secure communication\" href=\"https:\/\/en.wikipedia.org\/wiki\/Secure_communication\">secure communication<\/a>. Broadly speaking, cryptography deals with creating and studying protocols that prevent third parties (public or <a title=\"Adversary (cryptography)\" href=\"https:\/\/en.wikipedia.org\/wiki\/Adversary_(cryptography)\">adversaries<\/a>) from reading messages. It is strongly tied to information security topics such as confidentiality, data integrity, identification, authentication or non-repudiation \/ proof.<\/p>\n<p>Today&#8217;s cryptography is heavily based on mathematics: cryptographic algorithms are designed from <a title=\"Computational hardness assumption\" href=\"https:\/\/en.wikipedia.org\/wiki\/Computational_hardness_assumption\">computational hardness assumptions<\/a>. These are asymmetrical problems, like integer factorization: multiplying two integers is easy, factoring a 500-digit integer is not. An introduction to complexity was published in a <a href=\"https:\/\/www.quantum-bits.org\/?p=1988\" target=\"_blank\" rel=\"noopener\">previous post<\/a>.&nbsp;<\/p>\n<p>Unconditionally secure schemes (like the he <a title=\"One-time pad\" href=\"https:\/\/en.wikipedia.org\/wiki\/One-time_pad\" target=\"_blank\" rel=\"noopener\">one-time pad<\/a>) do exist. But these schemes are practically more difficult to implement than the best computationally secure ones.<\/p>\n<p>The idea of &#8220;computationally secure scheme&#8221; is the following: although it is theoretically possible to break such a system, it is practicality impossible to do so. The balance is easy to understand: if breaking a system costs more that the value it defends, it is worthless to do so.<\/p>\n<p>Both theoretical and practical advances require computationally secure schemes to be continually evaluated and adapted.<\/p>\n<p>As such, quantum computing poses a threat to encryption schemes based on assumptions about problems that are hard to solve with classical computing (<a href=\"https:\/\/en.wikipedia.org\/wiki\/NP_(complexity)\" target=\"_blank\" rel=\"noopener\">NP complexity class)<\/a> but happen to be efficiently solved by quantum computers (<a href=\"https:\/\/en.wikipedia.org\/wiki\/BQP\" target=\"_blank\" rel=\"noopener\">BQP complexity class<\/a>):<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2033\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits.png\" alt=\"\" width=\"450\" height=\"340\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits.png 1366w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits-300x226.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits-768x580.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits-1024x773.png 1024w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits-285x214.png 285w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/p>\n<p>This is why cryptography enters the quantum realm:<\/p>\n<ul>\n<li>for building (classical) encryption schemes that are considered to be secure against attacks by quantum computers.<\/li>\n<li>for building innovating quantum security schemes (based on quantum properties such as entanglement, no-cloning theorem, &#8230;);<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-1612\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/quantum-physics-formulas-over-blackboard.jpg\" alt=\"\" width=\"850\" height=\"332\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/quantum-physics-formulas-over-blackboard.jpg 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/quantum-physics-formulas-over-blackboard-300x117.jpg 300w\" sizes=\"(max-width: 850px) 100vw, 850px\" \/><\/p>\n<p>First, let&#8217;s define our vocabulary:<\/p>\n<ul>\n<li><strong>plaintext<\/strong>: unencrypted text (also called cleartext). Plaintexts will be denoted by the letter <img src='https:\/\/s0.wp.com\/latex.php?latex=M&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='M' title='M' class='latex' \/> (message);<\/li>\n<li><strong>ciphertext<\/strong>: encrypted text (also called cryptogram). Ciphertexts will be denoted by the letter <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/>;<\/li>\n<li><strong>encryption<\/strong>: process of transforming plaintext into ciphertext, <img src='https:\/\/s0.wp.com\/latex.php?latex=C+%3D+f%28M%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C = f(M)' title='C = f(M)' class='latex' \/> (where <img src='https:\/\/s0.wp.com\/latex.php?latex=f&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='f' title='f' class='latex' \/> is an encryption function);<\/li>\n<li><strong>decryption<\/strong>: process of transforming ciphertext into plaintext, <img src='https:\/\/s0.wp.com\/latex.php?latex=M+%3D+f%5E%7B-1%7D%28C%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='M = f^{-1}(C)' title='M = f^{-1}(C)' class='latex' \/> (where <img src='https:\/\/s0.wp.com\/latex.php?latex=f%5E%7B-1%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='f^{-1}' title='f^{-1}' class='latex' \/> is a decryption function);<\/li>\n<li><strong>cryptographic key<\/strong>: a parameter that determines the output of a cryptographic algorithm. Keys will be denoted by the letter <img src='https:\/\/s0.wp.com\/latex.php?latex=k&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k' title='k' class='latex' \/>. For example, for an encryption algorithm, a key specifies the transformation of plaintext into ciphertext: <img src='https:\/\/s0.wp.com\/latex.php?latex=C+%3D+f%28M%2Ck%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C = f(M,k)' title='C = f(M,k)' class='latex' \/>;<\/li>\n<li><strong>hashing: <\/strong>a mathematical function&nbsp;that can be used to map&nbsp;data&nbsp;of arbitrary size to data of fixed size. It is used to verify data integrity.<\/li>\n<li><strong>cryptosystem<\/strong>: a suite of cryptographic&nbsp;algorithms&nbsp;needed to implement a particular security service. A typical cryptosystem consists of three algorithms: one for&nbsp;key generation, one for encryption, and one for decryption.<\/li>\n<\/ul>\n<p>Now, let&#8217;s define our participants:<\/p>\n<ul>\n<li><strong>Alice<\/strong> and <strong>Bob: <\/strong>Alice and Bob are&nbsp;fictional&nbsp;characters&nbsp;commonly used as&nbsp;placeholder names&nbsp;in&nbsp;cryptology. They ware were invented by&nbsp;<a title=\"Ron Rivest\" href=\"https:\/\/en.wikipedia.org\/wiki\/Ron_Rivest\" target=\"_blank\" rel=\"noopener\">Ron Rivest<\/a>,&nbsp;<a title=\"Adi Shamir\" href=\"https:\/\/en.wikipedia.org\/wiki\/Adi_Shamir\" target=\"_blank\" rel=\"noopener\">Adi Shamir<\/a>, and&nbsp;<a title=\"Leonard Adleman\" href=\"https:\/\/en.wikipedia.org\/wiki\/Leonard_Adleman\" target=\"_blank\" rel=\"noopener\">Leonard Adleman<\/a>&nbsp;in their 1978 seminal paper &#8220;A method for obtaining digital signatures and public-key cryptosystems.&#8221;. These names are used for convenience and to aid comprehension: &#8220;How can Bob send a private message <img src='https:\/\/s0.wp.com\/latex.php?latex=M&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='M' title='M' class='latex' \/> to Alice ?&#8221;.<br \/>\nAdditional characters can be added as generic participants, like <strong>Carol<\/strong>, <strong>Dave<\/strong>, &#8230;<\/li>\n<\/ul>\n<p>And finally, let&#8217;s define our adversaries:<\/p>\n<ul>\n<li><strong>Eve<\/strong>: Eve is an&nbsp;eavesdropper, who is usually a passive attacker: while she can listen in on messages between Alice and Bob, she cannot modify them;<\/li>\n<li><strong>Mallory <\/strong>and <strong>Trudy:&nbsp;<\/strong>Mallory is a malicious attacker, often associated with&nbsp;Trudy, the intruder. Mallory and Trudy are active attackers (often used in <a title=\"Man-in-the-middle attack\" href=\"https:\/\/en.wikipedia.org\/wiki\/Man-in-the-middle_attack\" target=\"_blank\" rel=\"noopener\">man-in-the-middle attacks)<\/a>, who can modify messages, substitute messages, or replay old messages.<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2073\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/abc.png\" alt=\"\" width=\"500\" height=\"220\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/abc.png 1800w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/abc-300x132.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/abc-768x338.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/abc-1024x451.png 1024w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/p>\n<p>There are many other characters: <strong>Wendy <\/strong>(the whistleblower, an insider with privileged access capable of divulging information), <strong>Olivia<\/strong> (the oracle, who, for example, provides external data to smart contracts residing on distributed ledger systems), or <strong>Arthur<\/strong> and <strong>Merlin<\/strong> (usually appearing in interactive proof systems: Merlin &#8211; who has unbounded computational abilities &#8211; claims the truth of a statement, and Arthur questions him to verify the claim), &#8230;<\/p>\n<p>Now that the vocabulary is settled, let&#8217;s explore common classical (<em>i.e.<\/em> non-quantum) cryptography.<\/p>\n<p><strong>Symmetric-key algorithm (classical)<br \/>\n<\/strong><\/p>\n<p>Symmetric-key algorithms use the <strong>same<\/strong> cryptographic <strong>keys<\/strong> for <strong>both<\/strong> encryption of plaintext and decryption of ciphertext:<\/p>\n<ul>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=C+%3D+f%28M%2C%5Cmathbf%7Bk%7D%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C = f(M,\\mathbf{k})' title='C = f(M,\\mathbf{k})' class='latex' \/><\/li>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=M+%3D+f%5E%7B-1%7D%28C%2C%5Cmathbf%7Bk%7D%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='M = f^{-1}(C,\\mathbf{k})' title='M = f^{-1}(C,\\mathbf{k})' class='latex' \/><\/li>\n<\/ul>\n<p>This key, in practice, is a <a title=\"Shared secret\" href=\"https:\/\/en.wikipedia.org\/wiki\/Shared_secret\" target=\"_blank\" rel=\"noopener\">shared secret<\/a> between the parties, used to keep the communication link private.<\/p>\n<p>The first symmetric-key algorithms historically appeared very early (ancient Greece&#8217;s <a href=\"https:\/\/en.wikipedia.org\/wiki\/Scytale\" target=\"_blank\" rel=\"noopener\">Scytale<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Caesar_cipher\" target=\"_blank\" rel=\"noopener\">Caesar shift<\/a>, &#8230;). To encrypt cleartext messages, simple algorithms were used, using <strong>transpositions<\/strong> or mono-alphabetical <strong>substitutions<\/strong>.&nbsp;<\/p>\n<p>In the case of Caesar shift, each letter in the plaintext is <strong>shifted<\/strong>, replaced by a letter some fixed-number of positions down the alphabet:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2076\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/caesar-cipher.png\" alt=\"\" width=\"300\" height=\"184\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/caesar-cipher.png 1024w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/caesar-cipher-300x184.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/caesar-cipher-768x470.png 768w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>In this scheme, the encryption <strong>key<\/strong> is the <strong>shift<\/strong>. It is a secret that has to be shared through a separate secure channel. Knowing the key, one can encrypt and decrypt messages.<\/p>\n<p>Though very simple and ancient, it holds nice properties:<\/p>\n<ul>\n<li>It&#8217;s strength doesn&#8217;t rely on the secrecy of algorithm (which is known), but<strong> relies on the secrecy of the key<\/strong> (which is easier to change than the algorithm)<\/li>\n<li>Since the algorithm is known, it can be studied. Once considered too weak (or broken), it shall be replaced by a more efficient one, which also will be studied, and so on &#8230;<\/li>\n<\/ul>\n<p>These are actually modern qualities, as defined by the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Kerckhoffs%27s_principle\" target=\"_blank\" rel=\"noopener\">Kerckhoffs&#8217;s principle<\/a>: &#8220;<strong>A cryptosystem should be secure even if everything about the system, except the key, is public knowledge<\/strong>&#8220;, or, as formulated by <a href=\"https:\/\/en.wikipedia.org\/wiki\/Claude_E._Shannon\" target=\"_blank\" rel=\"noopener\">Claude Shannon<\/a>: &#8220;One ought to design systems under the assumption that the enemy will immediately gain full familiarity with them&#8221;. Or in even simpler terms: security by obscurity doesn&#8217;t work, never worked and will never work.<\/p>\n<p>Of course, Caesar shift is <strong>easy to break<\/strong>, using simple techniques such as <a title=\"Frequency analysis\" href=\"https:\/\/en.wikipedia.org\/wiki\/Frequency_analysis\" target=\"_blank\" rel=\"noopener\">frequency analysis<\/a>.<\/p>\n<p>Jumping forward in time (around 1590), new algorithms were proposed, using <a title=\"Polyalphabetic cipher\" href=\"https:\/\/en.wikipedia.org\/wiki\/Polyalphabetic_cipher\" target=\"_blank\" rel=\"noopener\">polyalphabetic substitutions<\/a> techniques for example. The famous <a href=\"https:\/\/en.wikipedia.org\/wiki\/Vigen%C3%A8re_cipher\" target=\"_blank\" rel=\"noopener\">Vigen\u00e8re cipher<\/a>&nbsp; is one of them:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2082\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/vigenere-cipher.png\" alt=\"\" width=\"550\" height=\"263\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/vigenere-cipher.png 1600w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/vigenere-cipher-300x143.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/vigenere-cipher-768x367.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/vigenere-cipher-1024x489.png 1024w\" sizes=\"(max-width: 550px) 100vw, 550px\" \/><\/p>\n<p>Here, the encryption key is &#8220;MUSIQUE&#8221; (french for &#8220;music&#8221;) and is used to encrypt &#8220;JADORE ECOUTER&#8230;&#8221; (which is french for &#8220;I like to listen&#8230;&#8221;).<\/p>\n<p>This cipher gained a reputation for being exceptionally strong. It stood its ground until the early 1900&#8217;s, where is was finally <strong>broken<\/strong>.<\/p>\n<p><a title=\"Gilbert Vernam\" href=\"https:\/\/en.wikipedia.org\/wiki\/Gilbert_Vernam\" target=\"_blank\" rel=\"noopener\">Gilbert Vernam<\/a> tried to repair the broken cipher, but, no matter what he did, the cipher was still vulnerable to cryptanalysis. Vernam&#8217;s work, however, eventually led to the <a title=\"One-time pad\" href=\"https:\/\/en.wikipedia.org\/wiki\/One-time_pad\" target=\"_blank\" rel=\"noopener\">one-time pad<\/a>, a theoretically unbreakable cipher !<\/p>\n<p>The one-time pad algorithm it rather simple. It applies <a href=\"https:\/\/en.wikipedia.org\/wiki\/Exclusive_or\" target=\"_blank\" rel=\"noopener\">XOR operations<\/a> on pairs of cleartexts and keys, given the following requirements:<\/p>\n<ul>\n<li>keys are perfectly <strong>random<\/strong>;<\/li>\n<li>the set of keys is <strong>secret<\/strong> (and previously shared through a secure channel);<\/li>\n<li>each key is at least <strong>as long as the current cleartext<\/strong>;<\/li>\n<li>each <strong>key is never reused<\/strong>, in whole or in part (hence the term <strong>one-time<\/strong> pad)<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2084\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/ontimepad.png\" alt=\"\" width=\"500\" height=\"162\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/ontimepad.png 1425w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/ontimepad-300x97.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/ontimepad-768x248.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/ontimepad-1024x331.png 1024w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/p>\n<p>One-time pads are &#8220;<a class=\"mw-redirect\" title=\"Information theoretic security\" href=\"https:\/\/en.wikipedia.org\/wiki\/Information_theoretic_security\">information-theoretically secure<\/a>&#8221; (sometimes also called &#8220;perfect secrecy&#8221;). This is a very strong notion of security, developed by <a title=\"Claude Shannon\" href=\"https:\/\/en.wikipedia.org\/wiki\/Claude_Shannon\" target=\"_blank\" rel=\"noopener\">Claude Shannon<\/a>. He also mathematically <strong>proved<\/strong> that, with the previous requirements, <strong>one-time pads are secure even against adversaries with infinite computational power<\/strong>.<\/p>\n<p>But, alas (!), despite Shannon&#8217;s proof of its security, one-time pad have serious <strong>practical drawbacks<\/strong>&nbsp; :<\/p>\n<ul>\n<li>Truly random (as opposed to <a title=\"Pseudorandomness\" href=\"https:\/\/en.wikipedia.org\/wiki\/Pseudorandomness\" target=\"_blank\" rel=\"noopener\">pseudorandom<\/a>) one-time pad values, which is a highly non-trivial requirement.<\/li>\n<li>Secure generation and exchange of the one-time pad values, which must be at least as long as the message:&nbsp; the security of the one-time pad is only as secure as the security of the one-time pad exchange !<\/li>\n<li>Making sure that keys continues to remain secret, and are disposed of correctly, preventing any reuse in whole or part. See for <a title=\"Data remanence\" href=\"https:\/\/en.wikipedia.org\/wiki\/Data_remanence\">data remanence<\/a> to get an idea of practical difficulties in completely erasing computer media&#8230;<\/li>\n<\/ul>\n<p>Unfortunately, this means that one-time pads solve only few current practical problems: we have to rely on other high quality ciphers, which are widely available, but are not unconditionally secure schemes.<\/p>\n<p>Today&#8217;s golden standard for symmetric-key algorithm is the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Advanced_Encryption_Standard\" target=\"_blank\" rel=\"noopener\">Advanced Encryption Standard<\/a> (<strong>AES<\/strong>, a.k.a Rijndael). It has been adopted by the U.S. government and is now used worldwide (FIPS PUB 197, ISO\/IEC 18033-3). It supersedes the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Data_Encryption_Standard\" target=\"_blank\" rel=\"noopener\">Data Encryption Standard<\/a> (DES) encryption scheme, which is now considered outdated (weak).<\/p>\n<p>AES is based on a substitution\u2013permutation network (<strong>rounds<\/strong> of <strong>substitutions<\/strong> and <strong>permutations<\/strong>):<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2086\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/aes-rounds.png\" alt=\"\" width=\"550\" height=\"577\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/aes-rounds.png 1696w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/aes-rounds-286x300.png 286w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/aes-rounds-768x806.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/aes-rounds-976x1024.png 976w\" sizes=\"(max-width: 550px) 100vw, 550px\" \/><\/p>\n<p>Round keys are derived from the secret key using <a href=\"https:\/\/en.wikipedia.org\/wiki\/Rijndael_key_schedule\" target=\"_blank\" rel=\"noopener\">Rijndael&#8217;s key schedule<\/a>.<\/p>\n<p>At the time of writing, there is <strong>no known practical attack<\/strong> that would allow someone without knowledge of the key to read data encrypted by AES when correctly implemented.<\/p>\n<p>Nevertheless, symmetric-key requirement that both parties have access to the secret key is one of the main <strong>drawbacks<\/strong> of symmetric-key encryption, in comparison to public-key encryption, that we will now discuss.<\/p>\n<p><strong>Asymmetric public-key algorithm (classical)<br \/>\n<\/strong><\/p>\n<p>The idea of an asymmetric<a href=\"https:\/\/en.wikipedia.org\/wiki\/Public-key_encryption\" target=\"_blank\" rel=\"noopener\"> public-private key cryptosystem<\/a> is attributed to <a title=\"Whitfield Diffie\" href=\"https:\/\/en.wikipedia.org\/wiki\/Whitfield_Diffie\" target=\"_blank\" rel=\"noopener\">Whitfield Diffie<\/a> and <a title=\"Martin Hellman\" href=\"https:\/\/en.wikipedia.org\/wiki\/Martin_Hellman\" target=\"_blank\" rel=\"noopener\">Martin Hellman<\/a>. These are cryptographic system that uses <strong>pairs of keys<\/strong>:<\/p>\n<ul>\n<li><strong>public keys<\/strong> which may be distributed publicly;<\/li>\n<li><strong>private keys<\/strong> which are known only to the owner (and thus shall be protected accordingly);<\/li>\n<li>What is encrypted with a public key can only be decrypted by the associated private key;<\/li>\n<li>Conversely, what is encrypted with a private key can only be decrypted by the associated public key.<\/li>\n<\/ul>\n<p>With these requirement, in a public key encryption scheme:<\/p>\n<ul>\n<li>Any person can encrypt a message using the receiver&#8217;s public key and that encrypted message can only be decrypted with the receiver&#8217;s private key;<\/li>\n<li>The strength of a public key cryptography system relies on the computational effort required to find the private key from its associated public key. Effective security only requires keeping the private key private: the public key can be openly distributed without compromising security.<\/li>\n<\/ul>\n<p>The first step towards public-key encryption is thus the creation of pairs of keys with these properties. Each party (Alice and Bob) generates two keys:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2091\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/key-create.png\" alt=\"\" width=\"450\" height=\"146\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/key-create.png 1139w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/key-create-300x97.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/key-create-768x249.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/key-create-1024x333.png 1024w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/p>\n<p>The private keys are to be kept secured ! Usually, they are encrypted using a symmetric-key algorithm, protected by a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Passphrase\" target=\"_blank\" rel=\"noopener\">passphrase<\/a> only known to its owner.<\/p>\n<p>The next step is the exchange of the public keys between parties (Alice and Bob):<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2092\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-exchange.png\" alt=\"\" width=\"550\" height=\"103\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-exchange.png 1417w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-exchange-300x56.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-exchange-768x144.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-exchange-1024x192.png 1024w\" sizes=\"(max-width: 550px) 100vw, 550px\" \/><\/p>\n<p>Please, note that:<\/p>\n<ul>\n<li>public-key algorithms schemes, unlike symmetric-key ones, do not require a secure channel for the initial exchange of one or more secret keys between the parties;<\/li>\n<li>formally associating public keys with the identity of their owners (i.e. key certification, which is not required for encryption) necessitates additional steps, protocols and components (third party authorities, webs of trust, distributed ledgers, &#8230;).<\/li>\n<\/ul>\n<p>Once public keys are distributed, they can be used to encrypt messages. If Alice wants to send a message that can only be read by Bob:<\/p>\n<ul>\n<li><strong>Alice<\/strong> <strong>encrypts<\/strong> his message with <strong>Bob&#8217;s public key<\/strong>: <img src='https:\/\/s0.wp.com\/latex.php?latex=C+%3D+f%5Cbig%28M%2Ck_%7Bpub%7D%28%5Cmathsf%7BBob%7D%29%5Cbig%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C = f\\big(M,k_{pub}(\\mathsf{Bob})\\big)' title='C = f\\big(M,k_{pub}(\\mathsf{Bob})\\big)' class='latex' \/>;<\/li>\n<li><strong>Bob decrypts<\/strong> the message with <strong>his private key<\/strong>: <img src='https:\/\/s0.wp.com\/latex.php?latex=M+%3D+f%5E%7B-1%7D%5Cbig%28C%2Ck_%7Bpriv%7D%28%5Cmathsf%7BBob%7D%29%5Cbig%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='M = f^{-1}\\big(C,k_{priv}(\\mathsf{Bob})\\big)' title='M = f^{-1}\\big(C,k_{priv}(\\mathsf{Bob})\\big)' class='latex' \/>;<\/li>\n<li>Since he is the (only) holder of his private key, <strong>Bob is the only one able to read Alice&#8217;s message<\/strong> (unless Trudy stole Bob&#8217;s private key&#8230;).<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2094\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-encryption.png\" alt=\"\" width=\"600\" height=\"242\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-encryption.png 1689w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-encryption-300x121.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-encryption-768x310.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-encryption-1024x413.png 1024w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>Conversely, public-key schemes can be used for <strong>authentication<\/strong>. Here, the public key is used to verify that a holder of the paired private key sent the message:<\/p>\n<ul>\n<li><strong>Alice encrypts<\/strong> his message with his <strong>private key<\/strong>: <img src='https:\/\/s0.wp.com\/latex.php?latex=C+%3D+f%5Cbig%28M%2Ck_%7Bpriv%7D%28%5Cmathsf%7BAlice%7D%29%5Cbig%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C = f\\big(M,k_{priv}(\\mathsf{Alice})\\big)' title='C = f\\big(M,k_{priv}(\\mathsf{Alice})\\big)' class='latex' \/>;<\/li>\n<li><strong>Anyone<\/strong> can <strong>decrypt<\/strong> Alice&#8217;s message (since Alice&#8217;s public key is available to anybody): <img src='https:\/\/s0.wp.com\/latex.php?latex=M+%3D+f%5E%7B-1%7D%5Cbig%28C%2Ck_%7Bpub%7D%28%5Cmathsf%7BAlice%7D%29%5Cbig%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='M = f^{-1}\\big(C,k_{pub}(\\mathsf{Alice})\\big)' title='M = f^{-1}\\big(C,k_{pub}(\\mathsf{Alice})\\big)' class='latex' \/><\/li>\n<li>Since she is the (only) holder of her private key, <strong>Alice is the only one that could have encrypted the message<\/strong>.<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2103\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-auth.png\" alt=\"\" width=\"600\" height=\"239\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-auth.png 1689w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-auth-300x119.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-auth-768x306.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/pubkey-auth-1024x407.png 1024w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>Please, note that Alice was not actually authenticated: only here (private) key was. Some kind of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Public_key_certificate\" target=\"_blank\" rel=\"noopener\">certification<\/a> would have be required to actually authenticate Alice.<\/p>\n<p>Public key cryptography algorithms are mostly based on hard mathematical problems without (classical) efficient solution : <a title=\"Integer factorization\" href=\"https:\/\/en.wikipedia.org\/wiki\/Integer_factorization\" target=\"_blank\" rel=\"noopener\">integer factorization<\/a>, <a title=\"Discrete logarithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Discrete_logarithm\" target=\"_blank\" rel=\"noopener\">discrete logarithm<\/a>, and <a class=\"mw-redirect\" title=\"Elliptic curve cryptography\" href=\"https:\/\/en.wikipedia.org\/wiki\/Elliptic_curve_cryptography\" target=\"_blank\" rel=\"noopener\">elliptic curve<\/a> relationships, &#8230;<\/p>\n<p>Usually, these problems are thought to be of <a href=\"https:\/\/en.wikipedia.org\/wiki\/NP-intermediate\" target=\"_blank\" rel=\"noopener\">NP-intermediate<\/a> (NPI) class:&nbsp; problems in the&nbsp;complexity class&nbsp;<a title=\"NP (complexity)\" href=\"https:\/\/en.wikipedia.org\/wiki\/NP_(complexity)\" target=\"_blank\" rel=\"noopener\">NP<\/a>&nbsp;but that are neither <a title=\"P (complexity)\" href=\"https:\/\/en.wikipedia.org\/wiki\/P_(complexity)\" target=\"_blank\" rel=\"noopener\">P<\/a>&nbsp;nor&nbsp;<a class=\"mw-redirect\" title=\"NP-complete\" href=\"https:\/\/en.wikipedia.org\/wiki\/NP-complete\" target=\"_blank\" rel=\"noopener\">NP-complete<\/a>. This idea is <strong>crudely<\/strong> (especially the NPI \/ BQP intersection) sketched in the following diagram:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2110\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/npi.png\" alt=\"\" width=\"450\" height=\"249\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/npi.png 2403w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/npi-300x166.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/npi-768x426.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/npi-1024x568.png 1024w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/p>\n<p>Let&#8217;s focus a moment on the <a href=\"https:\/\/en.wikipedia.org\/wiki\/RSA_(cryptosystem)\" target=\"_blank\" rel=\"noopener\">RSA cryptosystem<\/a>, one of the most widely used public-key cryptosystems. RSA is an acronym based on the surnames of <a title=\"Ron Rivest\" href=\"https:\/\/en.wikipedia.org\/wiki\/Ron_Rivest\" target=\"_blank\" rel=\"noopener\">Ron Rivest<\/a>, <a title=\"Adi Shamir\" href=\"https:\/\/en.wikipedia.org\/wiki\/Adi_Shamir\" target=\"_blank\" rel=\"noopener\">Adi Shamir<\/a>, and <a title=\"Leonard Adleman\" href=\"https:\/\/en.wikipedia.org\/wiki\/Leonard_Adleman\" target=\"_blank\" rel=\"noopener\">Leonard Adleman<\/a>.<\/p>\n<p>It is based on the following <a href=\"https:\/\/en.wikipedia.org\/wiki\/Modular_arithmetic\" target=\"_blank\" rel=\"noopener\">modular arithmetic<\/a> observations:<\/p>\n<ul>\n<li>it is <strong>easy<\/strong> to find three very large positive integers <img src='https:\/\/s0.wp.com\/latex.php?latex=e%2C+d&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='e, d' title='e, d' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='n' title='n' class='latex' \/> such that <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cforall+m+%5Cin+%5Cmathsf%7BZ%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\forall m \\in \\mathsf{Z}' title='\\forall m \\in \\mathsf{Z}' class='latex' \/> with <img src='https:\/\/s0.wp.com\/latex.php?latex=0+%5Cleq+m+%3C+n%5C+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='0 \\leq m &lt; n\\ ' title='0 \\leq m &lt; n\\ ' class='latex' \/>: <img src='https:\/\/s0.wp.com\/latex.php?latex=%28m%5Ee%29%5Ed+%5Cequiv+m%5C+%28%5Cmathrm%7Bmod%7D%5C+n%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='(m^e)^d \\equiv m\\ (\\mathrm{mod}\\ n)' title='(m^e)^d \\equiv m\\ (\\mathrm{mod}\\ n)' class='latex' \/>&nbsp; &#8211; or, conversely, that <img src='https:\/\/s0.wp.com\/latex.php?latex=%28m%5Ed%29%5Ee+%5Cequiv+m%5C+%28%5Cmathrm%7Bmod%7D%5C+n%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='(m^d)^e \\equiv m\\ (\\mathrm{mod}\\ n)' title='(m^d)^e \\equiv m\\ (\\mathrm{mod}\\ n)' class='latex' \/>;<\/li>\n<li><span class=\"texhtml mvar\">even knowing <img src='https:\/\/s0.wp.com\/latex.php?latex=e&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='e' title='e' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='n' title='n' class='latex' \/> or even <img src='https:\/\/s0.wp.com\/latex.php?latex=m&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='m' title='m' class='latex' \/> it can be <strong>hard<\/strong> to find <img src='https:\/\/s0.wp.com\/latex.php?latex=d&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='d' title='d' class='latex' \/><\/span>.<\/li>\n<\/ul>\n<p>Proof of these observations can be obtained either via <a href=\"https:\/\/en.wikipedia.org\/wiki\/Fermat%27s_little_theorem\" target=\"_blank\" rel=\"noopener\">Fermat&#8217;s little theorem<\/a> (in RSA&#8217;s original paper) or via <a href=\"https:\/\/en.wikipedia.org\/wiki\/Euler%27s_theorem\" target=\"_blank\" rel=\"noopener\">Euler&#8217;s theorem<\/a> (proof easier to derive).<\/p>\n<p>In this scheme, the public key is represented by <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Be%2Cn%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='{e,n}' title='{e,n}' class='latex' \/>, the private key is represented by <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Bd%2Cn%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='{d,n}' title='{d,n}' class='latex' \/> and the integer <img src='https:\/\/s0.wp.com\/latex.php?latex=m&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='m' title='m' class='latex' \/> represents the message.<\/p>\n<p>RSA keys are generated the following way:<\/p>\n<ol>\n<li>Randomly choose two prime numbers <img src='https:\/\/s0.wp.com\/latex.php?latex=p&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='p' title='p' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=q&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='q' title='q' class='latex' \/>;<\/li>\n<li>Calculate the modulus <img src='https:\/\/s0.wp.com\/latex.php?latex=n+%3D+p+%5Ctimes+q&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='n = p \\times q' title='n = p \\times q' class='latex' \/>;<\/li>\n<li>Calculate <a href=\"https:\/\/en.wikipedia.org\/wiki\/Euler%27s_totient_function\" target=\"_blank\" rel=\"noopener\">Euler&#8217;s totient function<\/a>: <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cvarphi%28n%29+%3D+%28p-1%29+%5Ctimes+%28q-1%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\varphi(n) = (p-1) \\times (q-1)' title='\\varphi(n) = (p-1) \\times (q-1)' class='latex' \/>;<\/li>\n<li>Choose <img src='https:\/\/s0.wp.com\/latex.php?latex=e&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='e' title='e' class='latex' \/> so that <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cmathrm%7Bgcd%7D%28e%2C%5Cvarphi%28n%29%29%3D1+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\mathrm{gcd}(e,\\varphi(n))=1 ' title='\\mathrm{gcd}(e,\\varphi(n))=1 ' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=e+%3E+%5Cvarphi%28n%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='e &gt; \\varphi(n)' title='e &gt; \\varphi(n)' class='latex' \/>;<\/li>\n<li>Calculate <img src='https:\/\/s0.wp.com\/latex.php?latex=d+%5Cequiv+e%5E%7B-1%7D%5C+%28%5Cmathrm%7Bmod%7D%5C+%5Cvarphi%28n%29%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='d \\equiv e^{-1}\\ (\\mathrm{mod}\\ \\varphi(n))' title='d \\equiv e^{-1}\\ (\\mathrm{mod}\\ \\varphi(n))' class='latex' \/>;<\/li>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=k_%7Bpub%7D+%3D+%5C%7Be%2Cn%5C%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k_{pub} = \\{e,n\\}' title='k_{pub} = \\{e,n\\}' class='latex' \/><\/li>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=k_%7Bpriv%7D+%3D+%5C%7Bd%2Cn%5C%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k_{priv} = \\{d,n\\}' title='k_{priv} = \\{d,n\\}' class='latex' \/><\/li>\n<\/ol>\n<p>They are used as follows:<\/p>\n<ul>\n<li><strong>encryption<\/strong>: <img src='https:\/\/s0.wp.com\/latex.php?latex=C+%3D+f%28M%2Ck_%7Bpub%7D%29+%5Cequiv+M%5Ee%5C+%28%5Cmathrm%7Bmod%7D%5C+n%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C = f(M,k_{pub}) \\equiv M^e\\ (\\mathrm{mod}\\ n)' title='C = f(M,k_{pub}) \\equiv M^e\\ (\\mathrm{mod}\\ n)' class='latex' \/><\/li>\n<li><strong>decryption<\/strong>: <img src='https:\/\/s0.wp.com\/latex.php?latex=M+%3D+f%5E%7B-1%7D%28C%2Ck_%7Bpriv%7D%29+%5Cequiv+C%5Ed%5C+%28%5Cmathrm%7Bmod%7D%5C+n%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='M = f^{-1}(C,k_{priv}) \\equiv C^d\\ (\\mathrm{mod}\\ n)' title='M = f^{-1}(C,k_{priv}) \\equiv C^d\\ (\\mathrm{mod}\\ n)' class='latex' \/><\/li>\n<\/ul>\n<p>To calculate <img src='https:\/\/s0.wp.com\/latex.php?latex=k_%7Bpriv%7D%3D%5C%7Be%2Cn%5C%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k_{priv}=\\{e,n\\}' title='k_{priv}=\\{e,n\\}' class='latex' \/> from <img src='https:\/\/s0.wp.com\/latex.php?latex=k_%7Bpriv%7D+%3D+%5C%7Bd%2Cn%5C%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k_{priv} = \\{d,n\\}' title='k_{priv} = \\{d,n\\}' class='latex' \/>, one has to know <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cvarphi%28n%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\varphi(n)' title='\\varphi(n)' class='latex' \/>. Hence, to calculate <img src='https:\/\/s0.wp.com\/latex.php?latex=k_%7Bpriv%7D%3D%5C%7Be%2Cn%5C%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k_{priv}=\\{e,n\\}' title='k_{priv}=\\{e,n\\}' class='latex' \/> from <img src='https:\/\/s0.wp.com\/latex.php?latex=k_%7Bpriv%7D+%3D+%5C%7Bd%2Cn%5C%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k_{priv} = \\{d,n\\}' title='k_{priv} = \\{d,n\\}' class='latex' \/> one has to know <img src='https:\/\/s0.wp.com\/latex.php?latex=p&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='p' title='p' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=q&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='q' title='q' class='latex' \/>:&nbsp; <strong>RSA&#8217;s strength resides in the hardness of prime factoring<\/strong> <img src='https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='n' title='n' class='latex' \/>.<\/p>\n<p>The problem is clearly in class NP, but has not been proved to be or not be&nbsp;NP-complete. <strong>No prime decomposition<\/strong> classical algorithm&nbsp;has been published that can factor all integers <strong>in&nbsp;polynomial time<\/strong>. We will however see that this is a completely different story for quantum algorithms).<\/p>\n<p>Public key algorithms are <strong>fundamental <\/strong>security ingredients :<\/p>\n<ul>\n<li>they underpin various Internet standards, such as <a title=\"Transport Layer Security\" href=\"https:\/\/en.wikipedia.org\/wiki\/Transport_Layer_Security\" target=\"_blank\" rel=\"noopener\">Transport Layer Security (TLS)<\/a> or <a title=\"S\/MIME\" href=\"https:\/\/en.wikipedia.org\/wiki\/S\/MIME\" target=\"_blank\" rel=\"noopener\">S\/MIME<\/a>;<\/li>\n<li>some public key algorithms provide <a title=\"Key distribution\" href=\"https:\/\/en.wikipedia.org\/wiki\/Key_distribution\" target=\"_blank\" rel=\"noopener\">key distribution<\/a> and secrecy (e.g., <a title=\"Diffie\u2013Hellman key exchange\" href=\"https:\/\/en.wikipedia.org\/wiki\/Diffie%E2%80%93Hellman_key_exchange\">Diffie\u2013Hellman key exchange<\/a>).<\/li>\n<\/ul>\n<p>Combined with hashes (that will be discussed in the next paragraph), public key cryptography:<\/p>\n<ul>\n<li>provides <a title=\"Digital signature\" href=\"https:\/\/en.wikipedia.org\/wiki\/Digital_signature\">digital signatures<\/a>;<\/li>\n<li>provides methods for assuring and <a title=\"Non-repudiation\" href=\"https:\/\/en.wikipedia.org\/wiki\/Non-repudiation\" target=\"_blank\" rel=\"noopener\">non-repudiability<\/a>.<\/li>\n<\/ul>\n<p><strong>Cryptographic hash functions (classical)<br \/>\n<\/strong><\/p>\n<p>Cryptographic hash functions are a special class of&nbsp;hash function (see definition at the beginning of this post) that has certain properties &#8211; other than being easy to compute &#8211; which make them suitable for use in&nbsp;cryptography:<\/p>\n<ul>\n<li>They are designed to be a&nbsp;<a title=\"One-way function\" href=\"https:\/\/en.wikipedia.org\/wiki\/One-way_function\" target=\"_blank\" rel=\"noopener\">one-way function<\/a>, that is, a function which is&nbsp;<a title=\"Computational complexity theory\" href=\"https:\/\/en.wikipedia.org\/wiki\/Computational_complexity_theory#Intractability\" target=\"_blank\" rel=\"noopener\">infeasible<\/a>&nbsp;to invert:<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2148\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/onway.png\" alt=\"\" width=\"350\" height=\"91\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/onway.png 987w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/onway-300x78.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/onway-768x200.png 768w\" sizes=\"(max-width: 350px) 100vw, 350px\" \/><\/p>\n<ul>\n<li>They are deterministic: the same message always results in the same hash:<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2151\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-deterministic.png\" alt=\"\" width=\"200\" height=\"129\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-deterministic.png 597w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-deterministic-300x193.png 300w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/p>\n<ul>\n<li>A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value (quick divergence):<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2153\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-divergence.png\" alt=\"\" width=\"250\" height=\"158\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-divergence.png 678w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-divergence-300x190.png 300w\" sizes=\"(max-width: 250px) 100vw, 250px\" \/><\/p>\n<ul>\n<li>It is&nbsp;infeasible&nbsp;to find two different messages with the same hash value (no collisions):<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2152\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-nocollisions.png\" alt=\"\" width=\"250\" height=\"123\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-nocollisions.png 818w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-nocollisions-300x148.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-nocollisions-768x379.png 768w\" sizes=\"(max-width: 250px) 100vw, 250px\" \/><\/p>\n<p>Cryptographic hash functions are widely used as they have many security applications, such as:<\/p>\n<ul>\n<li>fingerprinting (for data deduplication purposes for example);<\/li>\n<li>verifying the integrity of files or messages;<\/li>\n<li>password verification;<\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Proof-of-work_system\" target=\"_blank\" rel=\"noopener\">proof of work<\/a> in <a href=\"https:\/\/en.wikipedia.org\/wiki\/Blockchain\" target=\"_blank\" rel=\"noopener\">blockchain<\/a> technologies;<\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Digital_signature\" target=\"_blank\" rel=\"noopener\">digital signatures<\/a>;<\/li>\n<li><a class=\"mw-redirect\" title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Message_authentication_codes\" target=\"_blank\" rel=\"noopener\">message authentication codes<\/a>&nbsp;(MACs);<\/li>\n<li>file or data identifier;<\/li>\n<li>pseudorandom generation and key derivation;<\/li>\n<li>&#8230;<\/li>\n<\/ul>\n<p>Cryptographic hash functions can be build using the <a title=\"Merkle\u2013Damg\u00e5rd construction\" href=\"https:\/\/en.wikipedia.org\/wiki\/Merkle%E2%80%93Damg%C3%A5rd_construction\" target=\"_blank\" rel=\"noopener\">Merkle\u2013Damg\u00e5rd construction<\/a>:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2157\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/merkle-damgard.png\" alt=\"\" width=\"500\" height=\"301\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/merkle-damgard.png 1656w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/merkle-damgard-300x180.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/merkle-damgard-768x462.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/merkle-damgard-1024x616.png 1024w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/p>\n<ol>\n<li>The input message (here, an extract from a french song &#8220;A la claire fontaine, m&#8217;en allant promener, j&#8217;ai trouv\u00e9 l&#8217;eau si belle que je m&#8217;y suis baign\u00e9&#8221;) is broken into a series of equal-sized blocks to form a prepared message;<\/li>\n<li>A <a href=\"https:\/\/en.wikipedia.org\/wiki\/Initialization_vector\" target=\"_blank\" rel=\"noopener\">initialization vector<\/a> (IV) is introduced;<\/li>\n<li>For each message block, the compression function takes the result so far (using the IV as initial value), combines it with the message block, and produces an intermediate result;<\/li>\n<li>The last block is padded with zeros as needed;<\/li>\n<li>To harden the hash further, the last result is then fed through a&nbsp;finalization function.<\/li>\n<\/ol>\n<p>Common classical hash functions, including&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/SHA-1\" target=\"_blank\" rel=\"noopener\">SHA-1<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/SHA-2\" target=\"_blank\" rel=\"noopener\">SHA-2<\/a> or <a href=\"https:\/\/en.wikipedia.org\/wiki\/MD5\" target=\"_blank\" rel=\"noopener\">MD5<\/a> are based on the Merkle\u2013Damg\u00e5rd construction. Just like any other cryptographic algorithms, hash functions have to be studied, put to the test and have to be discarded when proven to be not enough effective.<\/p>\n<p>Indeed, both SHA-1 and MD5 are severely compromised as they are both vulnerable to <a href=\"https:\/\/en.wikipedia.org\/wiki\/Collision_attack\" target=\"_blank\" rel=\"noopener\">collision attacks<\/a>: <strong>SHA-1 and MD5 shall not be used anymore.<\/strong><\/p>\n<p>Similarly, <strong>SHA-256<\/strong> and <strong>SHA-512 <\/strong>are prone to&nbsp;length extension attacks, rendering them insecure for some applications.<\/p>\n<p>The SHA-3 cryptographic hash function is based on a different scheme, called the <a title=\"Sponge function\" href=\"https:\/\/en.wikipedia.org\/wiki\/Sponge_function\" target=\"_blank\" rel=\"noopener\">sponge construction<\/a>:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2158\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-sponge.png\" alt=\"\" width=\"450\" height=\"208\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-sponge.png 2165w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-sponge-300x139.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-sponge-768x355.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/hash-sponge-1024x473.png 1024w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/p>\n<p>In this construction, data is &#8220;absorbed&#8221; into the sponge, then the result is &#8220;squeezed&#8221; out:<\/p>\n<ul>\n<li>in the absorbing phase, message blocks are&nbsp;XORed&nbsp;into a subset of the state, which is then transformed as a whole using a permutation function.<\/li>\n<li>in the &#8220;squeeze&#8221; phase, output blocks are read from the same subset of the state, alternated with a state transformation function.&nbsp;<\/li>\n<\/ul>\n<p>The purpose of SHA-3 is that it can be directly substituted for SHA-2 in current applications if necessary.<\/p>\n<p><strong>Key distribution (classical)<br \/>\n<\/strong><\/p>\n<p>As we have seen, for symmetric key cryptography, both parties must share a common secret key before using any encryption.<\/p>\n<p>Alas, distribution of secret keys has always been problematic. Traditionally, secure communication between two parties required that they first exchange keys by some secure physical channel:&nbsp;face-to-face meeting, use of a trusted courier &#8230;<\/p>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Diffie%E2%80%93Hellman_key_exchange\" target=\"_blank\" rel=\"noopener\">Diffie\u2013Hellman key exchange<\/a> (DH) is a way of&nbsp;generating&nbsp;a shared secret between two people in such a way that the secret can&#8217;t be seen by observing the communication.<\/p>\n<p>DH is non-authenticated&nbsp;<a title=\"Key-agreement protocol\" href=\"https:\/\/en.wikipedia.org\/wiki\/Key-agreement_protocol\" target=\"_blank\" rel=\"noopener\">key-agreement protocol<\/a> which allows two parties that have <strong>no prior knowledge of each other<\/strong> to <strong>jointly<\/strong> establish a&nbsp;<strong>shared secret&nbsp;key<\/strong> over an&nbsp;<strong>insecure channel<\/strong>. There is an important distinction here: <strong>parties are not&nbsp;sharing information<\/strong>&nbsp;during the key exchange, <strong>parties are creating a key&nbsp;together<\/strong>. This key can then be used to encrypt subsequent communications using a&nbsp;symmetric key&nbsp;cipher.<\/p>\n<p>This is particularly useful because you can use this technique to create an encryption key with someone, and then start encrypting your traffic with that key.<\/p>\n<p>DH essentially breaks down to following steps:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2172\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/dhk.png\" alt=\"\" width=\"350\" height=\"252\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/dhk.png 1448w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/dhk-300x216.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/dhk-768x552.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/dhk-1024x736.png 1024w\" sizes=\"(max-width: 350px) 100vw, 350px\" \/><\/p>\n<ol>\n<li>Each party agrees on a public value <img src='https:\/\/s0.wp.com\/latex.php?latex=g&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='g' title='g' class='latex' \/> and a large prime number <img src='https:\/\/s0.wp.com\/latex.php?latex=p&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='p' title='p' class='latex' \/>;<\/li>\n<li>Next, one party chooses a secret value <img src='https:\/\/s0.wp.com\/latex.php?latex=x&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='x' title='x' class='latex' \/> and the other party chooses a secret value <img src='https:\/\/s0.wp.com\/latex.php?latex=y&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='y' title='y' class='latex' \/>;<\/li>\n<li>Both parties use their secret values to derive public values: <img src='https:\/\/s0.wp.com\/latex.php?latex=g%5Ex+%28%5Cmathrm%7Bmod%7D%5C+p%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='g^x (\\mathrm{mod}\\ p)' title='g^x (\\mathrm{mod}\\ p)' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=g%5Ey+%28%5Cmathrm%7Bmod%7D%5C+p%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='g^y (\\mathrm{mod}\\ p)' title='g^y (\\mathrm{mod}\\ p)' class='latex' \/>;<\/li>\n<li>Alice and Bob exchange these public values. Each party then uses the other party&#8217;s public value to calculate the shared secret key that is used by both parties for confidential communication;<\/li>\n<li>Alice uses the value <img src='https:\/\/s0.wp.com\/latex.php?latex=g%5E%7Bxy%7D+%28%5Cmathrm%7Bmod%7D%5C+p%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='g^{xy} (\\mathrm{mod}\\ p)' title='g^{xy} (\\mathrm{mod}\\ p)' class='latex' \/> as her secret key for confidential communications with Bob;<\/li>\n<li>Conversely Bob uses the value <img src='https:\/\/s0.wp.com\/latex.php?latex=g%5E%7Byx%7D+%28%5Cmathrm%7Bmod%7D%5C+p%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='g^{yx} (\\mathrm{mod}\\ p)' title='g^{yx} (\\mathrm{mod}\\ p)' class='latex' \/> as his secret key.<\/li>\n<\/ol>\n<p>Because <img src='https:\/\/s0.wp.com\/latex.php?latex=g%5E%7Bxy%7D+%28%5Cmathrm%7Bmod%7D%5C+p%29+%3D+g%5E%7Byx%7D+%28%5Cmathrm%7Bmod%7D%5C+p%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='g^{xy} (\\mathrm{mod}\\ p) = g^{yx} (\\mathrm{mod}\\ p)' title='g^{xy} (\\mathrm{mod}\\ p) = g^{yx} (\\mathrm{mod}\\ p)' class='latex' \/>, Alice and Bob can use their secret keys with a symmetric key algorithm to conduct confidential online communications. The use of the modulo function ensures that both parties can calculate the same secret key value, but an eavesdropper cannot.<\/p>\n<p>Variations of the described DH scheme exist. For example, the <a class=\"mw-redirect\" title=\"Elliptic curve Diffie\u2013Hellman\" href=\"https:\/\/en.wikipedia.org\/wiki\/Elliptic_curve_Diffie%E2%80%93Hellman\" target=\"_blank\" rel=\"noopener\">Elliptic curve Diffie\u2013Hellman<\/a> (ECDH) protocol is variant that uses<strong> elliptic curves<\/strong> instead of the multiplicative group of integers modulo <img src='https:\/\/s0.wp.com\/latex.php?latex=p&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='p' title='p' class='latex' \/>.<\/p>\n<p>Even if the traffic is recorded and later analyzed, there&#8217;s no way to figure out what the key was, even though the exchanges that created it may have been visible (see <a href=\"http:\/\/en.wikipedia.org\/wiki\/Perfect_forward_secrecy\" target=\"_blank\" rel=\"noopener noreferrer\">perfect forward secrecy<\/a>) because the<strong> secret key is known only to each party and was never visible on the network<\/strong>.<\/p>\n<p>If Eve (the eavesdropper) intercepts the values of <img src='https:\/\/s0.wp.com\/latex.php?latex=g&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='g' title='g' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=p&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='p' title='p' class='latex' \/>, because of the hard mathematical problem created by the use of a large prime number in <img src='https:\/\/s0.wp.com\/latex.php?latex=%28%5Cmathrm%7Bmod%7D%5C+p%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='(\\mathrm{mod}\\ p)' title='(\\mathrm{mod}\\ p)' class='latex' \/>, she would not be able to feasibly calculate either secret value <img src='https:\/\/s0.wp.com\/latex.php?latex=x&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='x' title='x' class='latex' \/> or secret value <img src='https:\/\/s0.wp.com\/latex.php?latex=y&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='y' title='y' class='latex' \/>: for Eve to resolve the DH (or ECDH) problem, she would have to solve a <a class=\"mw-redirect\" title=\"Discrete logarithm problem\" href=\"https:\/\/en.wikipedia.org\/wiki\/Discrete_logarithm_problem\" target=\"_blank\" rel=\"noopener\">discrete logarithm problem<\/a>, which is of <a href=\"https:\/\/en.wikipedia.org\/wiki\/NP-intermediate\" target=\"_blank\" rel=\"noopener\">NPI complexity<\/a> and is <strong>not solvable for classical computers in polynomial time<\/strong>.<\/p>\n<p><strong>How secure is classical cryptography against quantum computing?<\/strong><\/p>\n<p>In cryptography, <strong>security level<\/strong> is a measure of the strength that a cryptographic primitive (cipher, hash function, &#8230;). They are usually expressed in bits, where n-bit security means that the attacker would have to perform <img src='https:\/\/s0.wp.com\/latex.php?latex=2%5En&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='2^n' title='2^n' class='latex' \/> operations to break it. Though not perfect, it allows convenient comparison between algorithms. For example, AES-128 (key size 128 bits) is designed to offer a 128-bit security level, which is considered roughly equivalent to 3072-bit RSA.<\/p>\n<p>Let&#8217;s start with <strong>symmetric-key algorithms<\/strong>. They usually have a strictly defined security claim, typically <strong>equal to the key size of the cipher<\/strong> (equivalent to the complexity of a brute-force attack).<\/p>\n<p>Symmetric encryption algorithms are affected by quantum computing: <a href=\"https:\/\/en.wikipedia.org\/wiki\/Grover%27s_algorithm\" target=\"_blank\" rel=\"noopener\"><strong>Grover\u2019s Algorithm<\/strong><\/a> does provide a significant <strong>speed-up by<\/strong> finding the solution in the <strong>square-root of the time of a classical computer<\/strong>:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2037\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-grover.png\" alt=\"\" width=\"500\" height=\"122\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-grover.png 1374w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-grover-300x73.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-grover-768x187.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-grover-1024x250.png 1024w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/p>\n<p>For example, AES-256 has up to 2<sup>256 <\/sup>keys. A quantum computer could make that same search as if there were only 2<sup>128<\/sup> keys. On the one hand, that\u2019s a lot faster. On the other hand, it\u2019s still an awful lot of searching to do&#8230;<\/p>\n<table width=\"450\" cellspacing=\"0\" cellpadding=\"0\" border=\"1\">\n<tbody>\n<tr style=\"border-top: none !important;\">\n<td style=\"text-align: center; border-top: none !important;\">Algorithm<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Key length<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Security Level (classical)<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Security Level (quantum)<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">AES-128<\/td>\n<td style=\"text-align: left;\">128 bits<\/td>\n<td style=\"text-align: left;\">128 bits<\/td>\n<td style=\"text-align: left;\">64 bits<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">AES-256<\/td>\n<td style=\"text-align: left;\">256 bits<\/td>\n<td style=\"text-align: left;\">256 bits<\/td>\n<td style=\"text-align: left;\">128 bits<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Therefore, <strong>to counteract this quadratic speedup, larger key sizes must be used<\/strong>. <strong>AES-like<\/strong> ciphers are usually <strong>considered quantum-safe <\/strong>as long as the key length is <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cgeq&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\geq' title='\\geq' class='latex' \/> 256 bits, which is no big deal.<\/p>\n<p>However, it is <strong>a completely different story for public-key algorithm<\/strong>.&nbsp;Indeed, we have seen in a previous post that <strong>Shor&#8217;s algorithm<\/strong> is able to <strong>solve prime factoring problems in polynomial time<\/strong> :&nbsp; it takes only <img src='https:\/\/s0.wp.com\/latex.php?latex=O%28b%5E3%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='O(b^3)' title='O(b^3)' class='latex' \/> time and <img src='https:\/\/s0.wp.com\/latex.php?latex=O%28b%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='O(b)' title='O(b)' class='latex' \/> space on&nbsp;b-bit number inputs:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-1971\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-circuit-shor.png\" alt=\"\" width=\"500\" height=\"274\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-circuit-shor.png 1437w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-circuit-shor-300x164.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-circuit-shor-768x421.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qec-circuit-shor-1024x561.png 1024w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/p>\n<p>It means that, this time, quantum computers are predicted to get <strong>exponential speed-up<\/strong>. Therefore, <strong>RSA-like and ECC-like (Elliptic Curve) ciphers are not considered quantum safe<\/strong> because they are not able to adapt by increasing their key sizes to outpace the rate of development of quantum computing.&nbsp;<\/p>\n<table width=\"450\" cellspacing=\"0\" cellpadding=\"0\" border=\"1\">\n<tbody>\n<tr style=\"border-top: none !important;\">\n<td style=\"text-align: center; border-top: none !important;\">Algorithm<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Key length<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Security Level (classical)<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Security Level (quantum)<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">RSA-1024<\/td>\n<td style=\"text-align: left;\">1024 bits<\/td>\n<td style=\"text-align: left;\">80 bits<\/td>\n<td style=\"text-align: left;\">0 bits<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">RSA-2048<\/td>\n<td style=\"text-align: left;\">2048 bits<\/td>\n<td style=\"text-align: left;\">112 bits<\/td>\n<td style=\"text-align: left;\">0 bits<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">ECC-256<\/td>\n<td style=\"text-align: left;\">256 bits<\/td>\n<td style=\"text-align: left;\">128 bits<\/td>\n<td style=\"text-align: left;\">0 bits<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">ECC-384<\/td>\n<td style=\"text-align: left;\">384 bits<\/td>\n<td style=\"text-align: left;\">256 bits<\/td>\n<td style=\"text-align: left;\">0 bits<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Concerning <strong>cryptographic hash function<\/strong>, quantum computers seem to provide some <strong>non-trivial quadratic speedup<\/strong> (via the use of the Grover algorithm).<\/p>\n<p>Moreover, for <strong>collision resistance<\/strong>, quantum computers provide an <strong>even less impressive speed-up<\/strong>: the classical <a href=\"https:\/\/en.wikipedia.org\/wiki\/Birthday_attack\" target=\"_blank\" rel=\"noopener\">birthday attack<\/a> gives a <img src='https:\/\/s0.wp.com\/latex.php?latex=O%28%5Csqrt%7Bn%7D%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='O(\\sqrt{n})' title='O(\\sqrt{n})' class='latex' \/> attack, and it&#8217;s quantum version seems only to make this attack <img src='https:\/\/s0.wp.com\/latex.php?latex=O%28n%5E%7B1%2F3%7D%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='O(n^{1\/3})' title='O(n^{1\/3})' class='latex' \/>. It has been proven for example that the <strong>Merkle\u2013Damg\u00e5rd construction<\/strong> (as used by SHA-2), <strong>is quantum collision-resistant<\/strong>. The <strong>sponge construction<\/strong> (as used by SHA-3) is quantum collision-resistant, but only in certain conditions, which make it <strong>a little less effective against such attacks<\/strong>.<\/p>\n<p>It is nevertheless believed that a hash function with 256 bits of classical security would still have 128 bits of quantum security:<\/p>\n<table width=\"450\" cellspacing=\"0\" cellpadding=\"0\" border=\"1\">\n<tbody>\n<tr style=\"border-top: none !important;\">\n<td style=\"text-align: center; border-top: none !important;\">Algorithm<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Key length<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Security Level (classical)<\/td>\n<td style=\"text-align: left; border-top: none !important;\">Security Level (quantum)<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">SHA-256<\/td>\n<td style=\"text-align: left;\">256 bits<\/td>\n<td style=\"text-align: left;\">256 bits<\/td>\n<td style=\"text-align: left;\">128 bits<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Good <strong><span class=\"highlight selected\">hash <\/span>functions (SHA-2, SHA-3, &#8230;) are believed to be resistant to quantum adversaries<\/strong>.<\/p>\n<p>Finally, as we have already seen,<strong> Shor&#8217;s algorithm<\/strong> allows a quantum circuit to <strong>solve discrete logarithm problems <\/strong>in <strong>polynomial time<\/strong>, which opens the door to <strong>attacks on DH and ECDH with large enough quantum computer, <\/strong>in the same way at they do with RSA or ECC<strong>.<br \/>\n<\/strong><\/p>\n<p><strong>Post-quantum cryptography<\/strong><\/p>\n<p>Quantum computing is still in its infancy. Experiments have been carried out in which operations are executed on a very small number of quantum bits. In 2001, a 7-qubit quantum computer became the first to run Shor&#8217;s algorithm and factored &#8230; the number 15.<\/p>\n<p>Since then, a lot has progress has been made, especially in the field of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Topological_quantum_computer\" target=\"_blank\" rel=\"noopener\">topological quantum computing<\/a>.&nbsp;Google\u2019s Bristlecone 72 qubits processor holds the record as of 2018. Practical and theoretical research are carried on, in effort to develop quantum computers for civilian, business, trade, environmental and security purposes, such as cryptanalysis.<\/p>\n<p>As seen in the previous paragraph, not all security protocols and cryptographic algorithms are born equals: some are believed to be resistant from quantum attacks, while some are already known to be vulnerable.<\/p>\n<p>For example, a recent study has been carried out on quantum attacks on the Bitcoin blockchain (<a href=\"https:\/\/arxiv.org\/abs\/1710.10377\" target=\"_blank\" rel=\"noopener\">arXiv:1710.10377v1<\/a>). The study found:<\/p>\n<ul>\n<li>that the hash-based proof-of-work currently used is relatively resistant to substantial quantum speedup;<\/li>\n<li>that the ECC signature scheme used by Bitcoin is much more at risk and could be completely broken by a quantum computer in a early future (less than 10 years by their most optimistic estimate).<\/li>\n<\/ul>\n<p>Security controls that are known to be highly vulnerable to quantum attack, and can be easily broken by a quantum computer, include:<\/p>\n<ol>\n<li>Cryptosystem that is built on top of mathematical problem such as integer factoring or discrete logarithms. This includes <strong>RSA<\/strong>, <strong>DSA<\/strong>, <strong>DH<\/strong>, <strong>ECDH<\/strong>, <strong>ECDSA<\/strong> (and other variants of these ciphers). .<\/li>\n<li>Any security protocols that derive security from the above public key ciphers.<\/li>\n<li>Any products or security systems that derive security from the above protocols.<\/li>\n<\/ol>\n<p>It is important to point out that <strong>almost all public key cryptography and protocols<\/strong> today use these types of ciphers.<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2182\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/etsi.png\" alt=\"\" width=\"300\" height=\"321\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/etsi.png 964w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/etsi-280x300.png 280w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/etsi-768x822.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/etsi-957x1024.png 957w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>Some cryptographers are looking at ways to \u201cfight quantum with quantum\u201d, but there are another options. Research is also carried on what is called post-quantum cryptography (although a more precise name might be quantum-resistant cryptography): post-quantum cryptography usually refers to the effort to build classical cryptographic algorithms that are secure against attacks via quantum computing.<\/p>\n<p>Focus is usually made on cryptography based on mathematical problems such as solving systems of multivariable polynomials, finding the shortest distance from a point to an n-dimensional skewed grid of other points, and finding the closest bit string to a set of other bit strings.<\/p>\n<p>One of the front-runners for post-quantum is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Lattice-based_cryptography\" target=\"_blank\" rel=\"noopener\">lattice-based cryptography<\/a>.<b> Lattice problems <\/b>are a class of optimization problems on <a title=\"Lattice (group)\" href=\"https:\/\/en.wikipedia.org\/wiki\/Lattice_(group)\" target=\"_blank\" rel=\"noopener\">lattices<\/a>. <b><br \/>\n<\/b><\/p>\n<p>As&nbsp;Joshua Holden explains [http:\/\/nautil.us] &#8220;<em>If Alice wants to send Bob a message, she could identify it with a point in Bob\u2019s&nbsp;n-dimensional grid and then add some \u201cnoise\u201d to it by moving it off the grid a small amount. If&nbsp;n&nbsp;is very large and the angles in the grid are skewed\u2014very far from right angles\u2014it seems difficult for Eve the Eavesdropper to figure out Alice\u2019s original point, and a quantum computer doesn\u2019t seem to help much. But if Bob (and only Bob) has a different set of lines drawn through the same points, but with angles closer to 90 degrees, then he has a \u201ctrap door\u201d which allows him to recover the point and the message.<\/em> &#8221;<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2185\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/lattice.png\" alt=\"\" width=\"450\" height=\"764\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/lattice.png 1609w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/lattice-177x300.png 177w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/lattice-768x1305.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/lattice-603x1024.png 603w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/p>\n<p>Many lattice-based cryptographic schemes are known to be secure assuming the <a title=\"Worst-case complexity\" href=\"https:\/\/en.wikipedia.org\/wiki\/Worst-case_complexity\" target=\"_blank\" rel=\"noopener\">worst-case<\/a> hardness of certain lattice problems.<\/p>\n<p>Among them, <b>NTRU<\/b> is an open source public-key cryptosystem that uses lattice-based cryptography. NTRU (and its variants) have been entered into the <a title=\"Post-Quantum Cryptography Standardization\" href=\"https:\/\/en.wikipedia.org\/wiki\/Post-Quantum_Cryptography_Standardization\" target=\"_blank\" rel=\"noopener\">Post-Quantum Cryptography Standardization<\/a> <a class=\"mw-redirect\" title=\"NIST\" href=\"https:\/\/en.wikipedia.org\/wiki\/NIST\" target=\"_blank\" rel=\"noopener\">NIST<\/a> effort to standardize post-quantum cryptography. The Post Quantum Cryptography Study Group of the European Commission is also considering standardization of the provably secure Stehle-Steinfeld version of NTRU.<\/p>\n<p>The security of the NTRU encryption is related to the <a title=\"Lattice problem\" href=\"https:\/\/en.wikipedia.org\/wiki\/Lattice_problem#Closest_vector_problem_.28CVP.29\" target=\"_blank\" rel=\"noopener\">Closest Vector Problem (CVP)<\/a> in a Lattice, which is known to be <a class=\"mw-redirect\" title=\"NP-hard\" href=\"https:\/\/en.wikipedia.org\/wiki\/NP-hard\" target=\"_blank\" rel=\"noopener\">NP-hard<\/a>.<\/p>\n<p>As a bonus, some NTRU-based cryptosystem are <a href=\"https:\/\/en.wikipedia.org\/wiki\/Homomorphic_encryption\" target=\"_blank\" rel=\"noopener\">homomorphic<\/a> (a form of encryption that allows operations on ciphertexts, which, when decrypted, matches the result of the operations as if they had been performed on the plaintext), making them particularly suitable for cloud-computing.<\/p>\n<p><strong>Quantum Key distribution<\/strong><\/p>\n<p>Let&#8217;s finish this (long) post with a few information on <strong>quantum cryptography.<\/strong> Its purpose is to exploit quantum mechanical properties (entanglement, superposition, measurement and wave function collapse, teleportation, <a href=\"https:\/\/en.wikipedia.org\/wiki\/No-cloning_theorem\" target=\"_blank\" rel=\"noopener\">no-cloning theorem<\/a>, &#8230;) to perform cryptographic tasks.<\/p>\n<p>The best known example of quantum cryptography is<strong> <a title=\"Quantum key distribution\" href=\"https:\/\/en.wikipedia.org\/wiki\/Quantum_key_distribution\" target=\"_blank\" rel=\"noopener\">quantum key distribution<\/a><\/strong> which offers, like DH, an information-theoretically secure solution to the key exchange problem.<\/p>\n<p>Indeed, even with the one-time pad (forgetting its practical drawbacks), the secrecy problem is only shifted to the problem of distributing the key in a safe way to the receiver. In principle, a spy can get hold of the share key, copy it and send it on to the receiver.<\/p>\n<p>This is the point where quantum physics enters the stage: if the key distribution makes use of quantum states the spy cannot measure them without disturbing them. <strong>Thus principles of quantum mechanics can help to make the key distribution safe<\/strong>. The unique property of quantum key distribution is the <strong>ability of the two communicating users to detect the presence of any third party trying to gain knowledge of the key: <\/strong><\/p>\n<ul>\n<li>A third party trying to eavesdrop on the key must in some way measure it, thus introducing detectable anomalies;<\/li>\n<li>By using quantum superpositions or quantum entanglement and transmitting information in quantum states, a communication system can be implemented that detects eavesdropping.<\/li>\n<\/ul>\n<p>Just like DH, quantum key distribution is only used to produce and distribute a key, not to transmit any message data. The algorithm most commonly associated with QKD is the one-time pad.<\/p>\n<p>Here is a list of common quantum mechanics properties used to build secure key distribution protocols:<\/p>\n<ul>\n<li><strong>P1 &#8211; no-cloning theorem<\/strong>: we introduced this quantum properties in <a href=\"https:\/\/www.quantum-bits.org\/?p=1930\" target=\"_blank\" rel=\"noopener\">a previous post<\/a>. It is impossible to create perfect copies of an unknown quantum state. <strong>Thus a spy is not able to produce perfect copies of a quantum state in transit in order to measure it, while sending on the original<\/strong>.<\/li>\n<li><strong>P2 &#8211; entanglement<\/strong>: as seen in our <a href=\"https:\/\/www.quantum-bits.org\/?p=1785\" target=\"_blank\" rel=\"noopener\">posts on Bell states<\/a> and on <a href=\"https:\/\/www.quantum-bits.org\/?p=1857\" target=\"_blank\" rel=\"noopener\">quantum teleportation<\/a>, two or more quantum systems can be correlated or entangled. If measurement are being performed on the two entangled subsystems, <strong>there will always be a correlation between the outcomes<\/strong>;<\/li>\n<li><strong>P3 &#8211; non-orthogonal states cannot be reliably distinguished<\/strong>:&nbsp; Generally speaking, a qubit can be written as <img src='https:\/\/s0.wp.com\/latex.php?latex=%7C%5Cpsi_i%5Crangle+%3D+%5Calpha_i+%7C0%5Crangle+%2B+%5Cbeta_i+%7C1%5Crangle&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|\\psi_i\\rangle = \\alpha_i |0\\rangle + \\beta_i |1\\rangle' title='|\\psi_i\\rangle = \\alpha_i |0\\rangle + \\beta_i |1\\rangle' class='latex' \/> where <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Calpha_i&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\alpha_i' title='\\alpha_i' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cbeta_i&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\beta_i' title='\\beta_i' class='latex' \/> are complex coefficients satisfying <img src='https:\/\/s0.wp.com\/latex.php?latex=%7C%5Calpha_i%7C%5E2+%2B+%7C%5Cbeta_i+%7C%5E2%3D+1&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|\\alpha_i|^2 + |\\beta_i |^2= 1' title='|\\alpha_i|^2 + |\\beta_i |^2= 1' class='latex' \/>. It is impossible to distinguish reliably between two states <img src='https:\/\/s0.wp.com\/latex.php?latex=%7C%5Cpsi_1%7C%5Crangle&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|\\psi_1|\\rangle' title='|\\psi_1|\\rangle' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=%7C%5Cpsi_2%5Crangle&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|\\psi_2\\rangle' title='|\\psi_2\\rangle' class='latex' \/> unless <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Clangle%5Cpsi_1%7C%5Cpsi_2%5Crangle%3D1&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\langle\\psi_1|\\psi_2\\rangle=1' title='\\langle\\psi_1|\\psi_2\\rangle=1' class='latex' \/> (i.e the states are orthogonal);<\/li>\n<\/ul>\n<p>Causality, though not an ingredient of (non-relativistic) quantum mechanics, is also an important ingredient. Together with the superposition principle, causality can be used for secure key distribution: <strong>if the<\/strong> <strong>two terms of which a superposition consists are sent with a time delay relative to each other, such that they are not causally connected, the eavesdropper cannot spy on them<\/strong>.<\/p>\n<div>In a typical QKD protocol, Alice and Bob obtain some quantum states and measure them (quantum channel). They then communicate (via a classical communication channel) to determine which of their measurement results could lead to secret key bits:<\/div>\n<div>&nbsp;<\/div>\n<div><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2187\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qkd.png\" alt=\"\" width=\"450\" height=\"203\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qkd.png 1308w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qkd-300x136.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qkd-768x347.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/qkd-1024x463.png 1024w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/div>\n<div>&nbsp;<\/div>\n<div>Note: neither of these two channels need to be secure: the protocol is designed with the assumption that Eve can interfere in any way with both.<\/div>\n<p>&nbsp;<\/p>\n<p>The BB84 scheme was the first proposed quantum key distribution protocol&nbsp;(1984, <a title=\"Charles H. Bennett (computer scientist)\" href=\"https:\/\/en.wikipedia.org\/wiki\/Charles_H._Bennett_(computer_scientist)\" target=\"_blank\" rel=\"noopener\">Charles Bennett<\/a> and <a title=\"Gilles Brassard\" href=\"https:\/\/en.wikipedia.org\/wiki\/Gilles_Brassard\" target=\"_blank\" rel=\"noopener\">Gilles Brassard<\/a>). This protocol is <a title=\"Provable security\" href=\"https:\/\/en.wikipedia.org\/wiki\/Provable_security\" target=\"_blank\" rel=\"noopener\">provably secure<\/a>, relying on the <strong>property P3<\/strong> seen before: information gain is only possible at the expense of disturbing the signal if the two states one is trying to distinguish are not orthogonal.<\/p>\n<p>For this, one has to <strong>encode information in non-orthogonal states<\/strong>. Alice chooses two n-bits long strings <img src='https:\/\/s0.wp.com\/latex.php?latex=a&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='a' title='a' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=b&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b' title='b' class='latex' \/> (<img src='https:\/\/s0.wp.com\/latex.php?latex=a_i&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='a_i' title='a_i' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=b_i&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b_i' title='b_i' class='latex' \/> being the i-th bit of <img src='https:\/\/s0.wp.com\/latex.php?latex=a&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='a' title='a' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=b&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b' title='b' class='latex' \/>).<\/p>\n<p>She encodes this information into the quantum state <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cdisplaystyle+%7C%5Cpsi%5Crangle+%3D+%5Cbigotimes_%7Bi%3D1%7D%5E%7Bn%7D+%7C%5Cpsi_%7Ba_i+b_i%7D%5Crangle&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\displaystyle |\\psi\\rangle = \\bigotimes_{i=1}^{n} |\\psi_{a_i b_i}\\rangle' title='\\displaystyle |\\psi\\rangle = \\bigotimes_{i=1}^{n} |\\psi_{a_i b_i}\\rangle' class='latex' \/>, where:<\/p>\n<ul>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cdisplaystyle+%7C%5Cpsi_%7B00%7D%5Crangle+%3D+%7C0%5Crangle&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\displaystyle |\\psi_{00}\\rangle = |0\\rangle' title='\\displaystyle |\\psi_{00}\\rangle = |0\\rangle' class='latex' \/>;<\/li>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cdisplaystyle+%7C%5Cpsi_%7B10%7D%5Crangle+%3D+%7C1%5Crangle&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\displaystyle |\\psi_{10}\\rangle = |1\\rangle' title='\\displaystyle |\\psi_{10}\\rangle = |1\\rangle' class='latex' \/>;<\/li>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cdisplaystyle+%7C%5Cpsi_%7B01%7D%5Crangle+%3D+%5Cfrac%7B1%7D%7B%5Csqrt%7B2%7D%7D+%7C0%5Crangle+%2B+%5Cfrac%7B1%7D%7B%5Csqrt%7B2%7D%7D+%7C1%5Crangle+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\displaystyle |\\psi_{01}\\rangle = \\frac{1}{\\sqrt{2}} |0\\rangle + \\frac{1}{\\sqrt{2}} |1\\rangle ' title='\\displaystyle |\\psi_{01}\\rangle = \\frac{1}{\\sqrt{2}} |0\\rangle + \\frac{1}{\\sqrt{2}} |1\\rangle ' class='latex' \/>;<\/li>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cdisplaystyle+%7C%5Cpsi_%7B11%7D%5Crangle+%3D+%5Cfrac%7B1%7D%7B%5Csqrt%7B2%7D%7D+%7C0%5Crangle+-+%5Cfrac%7B1%7D%7B%5Csqrt%7B2%7D%7D+%7C1%5Crangle+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\displaystyle |\\psi_{11}\\rangle = \\frac{1}{\\sqrt{2}} |0\\rangle - \\frac{1}{\\sqrt{2}} |1\\rangle ' title='\\displaystyle |\\psi_{11}\\rangle = \\frac{1}{\\sqrt{2}} |0\\rangle - \\frac{1}{\\sqrt{2}} |1\\rangle ' class='latex' \/>.<\/li>\n<\/ul>\n<p>The bit <img src='https:\/\/s0.wp.com\/latex.php?latex=b_i&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b_i' title='b_i' class='latex' \/> (only known by Alice) is what decides which basis <img src='https:\/\/s0.wp.com\/latex.php?latex=a_i&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='a_i' title='a_i' class='latex' \/> is encoded in (either in the computational basis or in the Hadamard basis). The qubits are now in states that are not mutually orthogonal, and thus it is impossible to distinguish all of them with certainty without knowing <img src='https:\/\/s0.wp.com\/latex.php?latex=b&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b' title='b' class='latex' \/>.<\/p>\n<p>Practically speaking, photons are shot between parties, and information is encoded along either a rectilinear or diagonal axis.<\/p>\n<p>The BB84 protocol goes like this:<\/p>\n<ol>\n<li>Alice sends <img src='https:\/\/s0.wp.com\/latex.php?latex=%7C%5Cpsi%5Crangle&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|\\psi\\rangle' title='|\\psi\\rangle' class='latex' \/> to Bob over a public quantum channel;<\/li>\n<li>Bob receives a state affected by errors (effect of noise in the channel or of Eve&#8217;s eavesdropping);<\/li>\n<li>We know that Eve cannot be in possession of a copy of the qubits sent to Bob, by the no-cloning theorem (property <strong>P1<\/strong>), unless she has made measurements. Her measurements, however, risk disturbing a particular qubit with probability 1\/2 if she guesses the wrong basis;<\/li>\n<li>As Bob does not know the basis the information was encoded in, all he can do is to select a basis to measure in, either rectilinear or diagonal. Bob chooses <img src='https:\/\/s0.wp.com\/latex.php?latex=b%27_i&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b&#039;_i' title='b&#039;_i' class='latex' \/> axes and measures the received state along these axes (and gets <img src='https:\/\/s0.wp.com\/latex.php?latex=a%27&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='a&#039;' title='a&#039;' class='latex' \/>);<\/li>\n<li>Bob announces on the classical public channel that he has received Alice&#8217;s transmission;<\/li>\n<li>Bob communicates with Alice (over the same public classical channel) to determine which <img src='https:\/\/s0.wp.com\/latex.php?latex=b_i+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b_i ' title='b_i ' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=b%27_i&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b&#039;_i' title='b&#039;_i' class='latex' \/> are not equal;<\/li>\n<li>Both Alice and Bob drop the qubits in <img src='https:\/\/s0.wp.com\/latex.php?latex=a&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='a' title='a' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=a%27&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='a&#039;' title='a&#039;' class='latex' \/> where <img src='https:\/\/s0.wp.com\/latex.php?latex=b&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b' title='b' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=b%27&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='b&#039;' title='b&#039;' class='latex' \/> don&#8217;t match;<\/li>\n<li>From the remaining <img src='https:\/\/s0.wp.com\/latex.php?latex=k&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k' title='k' class='latex' \/> bits where both Alice and Bob measured in the same basis, Alice randomly chooses <img src='https:\/\/s0.wp.com\/latex.php?latex=k+%2F+2&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='k \/ 2' title='k \/ 2' class='latex' \/> bits and discloses her choices over the public channel;<\/li>\n<li>To check for the presence of an eavesdropper, Alice and Bob compare the subset of bits. If Eve has gained any information about the photons&#8217; polarization, this introduces errors in Bob&#8217;s measurements. Other environmental conditions can cause errors in a similar fashion. If more than <img src='https:\/\/s0.wp.com\/latex.php?latex=p&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='p' title='p' class='latex' \/> bits differ they abort the key and try again. <img src='https:\/\/s0.wp.com\/latex.php?latex=p&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='p' title='p' class='latex' \/> is chosen so that if the number of bits known to Eve is less than this, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Quantum_key_distribution#Information_reconciliation_and_privacy_amplification\" target=\"_blank\" rel=\"noopener\">privacy amplification<\/a> can be used to reduce Eve&#8217;s knowledge of the key to an arbitrarily small amount at the cost of reducing the length of the key.<\/li>\n<\/ol>\n<p>There are many other QKD protocols, such as <strong>E91<\/strong>, which relies on properties <strong>P1<\/strong> and <strong>P2<\/strong>. An Industry Specification Group (ISG) of the European Telecommunications Standards Institute (ETSI) has been set up to address standardization issues in quantum cryptography.<\/p>\n<p>Many experiments have been carried out over the last 10 years, and companies are starting offering commercial quantum key distribution systems (in Switzerland, France, Australia and USA). The 2016 QUESS space mission created an international QKD channel between China and the Institute for Quantum Optics and Quantum Information in Austria. By October 2017, a 2,000-km fiber line was operational between Beijing, Jinan, Hefei and Shanghai. Together they constitute the world\u2019s first space-ground quantum network. It is expected that a European\u2013Asian quantum-encrypted network will by ran by 2020, and a global network by 2030.<\/p>\n<p><span style=\"font-size: 8pt;\">Note: A few paragraphs and illustrations of this post are based on wikipedia&#8217;s entries on quantum cryptography, ETSI White Paper No. 8 and Nautilus blog (nautil.us\/blog).<br \/>\n<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Cryptography is the cornerstone of secure communication. Broadly speaking, cryptography deals with creating and studying protocols that prevent third parties (public or adversaries) from reading messages. It is strongly tied &#8230;<\/p>\n","protected":false},"author":1,"featured_media":3846,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0},"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/posts\/2059"}],"collection":[{"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2059"}],"version-history":[{"count":0,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/posts\/2059\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/media\/3846"}],"wp:attachment":[{"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}