Using conversion schemes in public key cryptosystems

In a general aspect, a conversion scheme is used in a public key cryptosystem. In some aspects, a plaintext value is generated based on a message value, a constant value, and a random value. An error vector derivation function is applied to the plaintext value to produce an error vector. The plaintext value and the error vector are used in an encryption function to produce a ciphertext component, and the ciphertext component is provided for transmission in a communication network.

BACKGROUND

The following description relates to conversion schemes for public key cryptosystems.

Cryptography systems (“cryptosystems”) are used to communicate securely over public channels. For example, cryptosystems may provide confidentiality by encrypting messages sent over the public channels. Public key encryption algorithms may utilize public and private cryptographic keys to encrypt and decrypt messages. Some public key cryptosystems may be vulnerable to attacks by an adversary, such as an adversary with access to quantum computational resources.

DETAILED DESCRIPTION

In aspects of what is described here, a conversion scheme is incorporated into a public key cryptosystem to encrypt communications. For instance, in some examples, a conversion scheme is used with a public key cryptosystem to encrypt electronic mail communications, such as, for example messages formatted according to the Secure/Multipurpose Internet Mail Extensions (S/MIME) standard, in one pass. The public key cryptosystem may be one based on error correction codes, such as, for example, the McEliece cryptosystem implemented using a Quasi-Cyclic Medium Density Parity Check (QC-MDPC) code, a Niderreiter cryptosystem, or another type of public key cryptosystem. By incorporating a conversion scheme into public key cryptosystems, the communications may be secure against certain types of attacks, such as the Adaptive Chosen Ciphertext Attack (CCA2) and the key recovery attack.

In some aspects, a sender of a message msg may generate a random value s and combine (e.g., concatenate) the message and random value. An error vector derivation function may then be applied to the combination of the message msg and the random value s to produce an error vector e. The error vector derivation function may include, in some instances, the application of a one-way pseudorandom function and a Fisher-Yates shuffle to produce the error vector e. A pseudorandom function may then be applied to the error vector e, and an exclusive-or (XOR) function may be applied to the output of the pseudorandom function and the combination of the message and random value to produce a masked stringy. At least a portion of the masked stringy may then be used as an input to an encryption function (e.g., a McEliece encryption function) along with the error vector e, and the encryption function may produce a first ciphertext component C1, which is sent to a recipient. In some implementations, a portion of the stringy may be used as a second ciphertext component C2, which is also sent to the recipient.

After receipt of the first ciphertext component C1, the recipient may apply a decryption function (e.g., a McEliece decryption function) to the first ciphertext component to produce a first and second decryption function outputs, x and e. A pseudorandom function is applied to the second decryption function output e, and an exclusive-or (XOR) function is applied to the pseudorandom function output and the first decryption function output x. Where a second ciphertext component C2is used, the first decryption function output x and second ciphertext component C2are combined (e.g., concatenated) and the combination is used as an input to the exclusive-or (XOR) function instead of just the first decryption function output x. An error vector derivation function is then applied to the output of the exclusive-or function to produce an error vector check value e′. If the error vector check value e′ matches the error vector e, then a message is derived from the output of the exclusive-or function and provided to the recipient. In some instances, the output of the exclusive-or function includes the message value (e.g., the message is the k most significant bits of the exclusive-or function output). If the error vector check value e′ does not match the error vector e, then a failure is returned.

In some aspects, a sender of a message msg may combine (e.g., concatenate) the message and a constant value const. The sender may also generate a random value s and apply a pseudorandom function to the random value. An exclusive-or (XOR) function can then be applied to the combined message/constant value and the output of the pseudorandom function to produce a first string. A cryptographic hash function may be applied to the first string y1, and an exclusive-or (XOR) function may be applied to the output of the cryptographic hash function and the random value s to produce a second string y2. The first and second strings may be combined (e.g., concatenated), with a plaintext value x being generated therefrom. An error vector derivation function may be applied to the plaintext value x to produce an error vector e. The error vector derivation function may include, in some instances, the application of a one-way pseudorandom function and a Fisher-Yates shuffle to produce the error vector e. The plaintext value x and the error vector e may then be used as inputs to an encryption function (e.g., a McEliece encryption function), and the encryption function may produce a first ciphertext component C1, which is sent to a recipient. In some implementations, a portion of the combined first and second strings may be used as a second ciphertext component C2, which is also sent to the recipient.

After receipt of the first ciphertext component C1, the recipient may apply a decryption function (e.g., a McEliece decryption function) to the first ciphertext component to produce first and second decryption function outputs, x and e. Where a second ciphertext component C2is used, the first decryption function output x and second ciphertext component C2are combined (e.g., concatenated) and the combination is used to generate the first and second strings, y1 and y2. A cryptographic hash function may be applied to the first string y1, and an exclusive-or (XOR) function may be applied to the output of the cryptographic hash function and the second string y2 to produce the random value s. A pseudorandom function may be applied to the random value s, and an exclusive-or (XOR) function may be applied to the output of the pseudorandom function and the first string y1 to produce a value containing the message msg and a constant check value const′. An error vector derivation function may be applied to the first decryption function output x to produce an error vector check value e′. If the error vector check value e′ matches the error vector e, and the constant check value const′ matches the constant value const used to generate the first ciphertext component C1, then the message msg is provided to the recipient. If the error vector check value e′ does not match the error vector e or the constant check value const′ doesn't match the constant value const, then a failure is returned.

Aspects of the present disclosure may provide one or more advantages in some instances. For example, some aspects may provide communications (e.g., electronic mail communications formatted according to the Secure/Multipurpose Internet Mail Extensions (S/MIME) standard) over a public channel that are secure against adversaries equipped with classical or quantum computational resources. The communications may be secured, in some aspects, using a one pass protocol using a static key pair. In some instances, the public key used to secure the communications may be small compared to other public key cryptosystem implementations (e.g., the McEliece cryptosystem implemented using a Goppa code). For instance, in some implementations, the public key may be approximately 4 kilobytes (kB) whereas the public key in a McBits implementation may be approximately 1 Megabytes (MB). In addition, in some aspects, a key pair for the public key cryptosystem may be used repeatedly without jeopardizing security. Some aspects may provide secure communications that are resistant to key recovery attacks, the Adaptive Chosen Ciphertext Attack (CCA2), or both.

Further, some aspects may perform a CCA2 conversion technique that is more computationally efficient than other CCA2 conversion techniques, such as, for example, the Kobara-Imai CCA2 conversion. The communications may thus be encrypted, in some cases, using less computational resources than typical public key cryptosystem implementations (e.g., the McEliece cryptosystem implemented with a Kobara-Imai CCA2 conversion, which can take up to approximately 80% of the overall time needed for encrypting messages). For example, in some instances, the error vector derivation function is faster than the error-vector-to-integer function used in the Kobara-Imai CCA2 conversion. Further, the use of a one-way error vector derivation function as described herein may also allow for verification that the error vector is generated in a pseudorandom manner. In some instances, some aspects may allow for the implementations of side channel attack mitigation schemes more easily than other CCA2 conversion techniques. Aspects of the present disclosure may provide other advantages as well.

FIG. 1is a block diagram showing aspects of an example communication system100. The example communication system100shown inFIG. 1includes two nodes102,104. The nodes use a cryptographic scheme to communicate with each other over a channel106. In the example shown, a quantum-enabled adversary108has access to the channel106, information exchanged on the channel106, or both. In some instances, the quantum-enabled adversary108can transmit or modify information on the channel106. The communication system100may include additional or different features, and the components in a communication system may be configured to operate as shown inFIG. 1or in another manner.

In some implementations, nodes in the communication system100may have a server-client relationship. For example, the node102can be a server and the node104can be its client, or vice-versa. In some implementations, nodes in the communication system100may have a peer-to-peer relationship. For example, the nodes102,104can be peers in a served network, in a peer-to-peer network or another type of network. Nodes may have another type of relationship in the communication system100.

In the example shown inFIG. 1, the example nodes102,104each have computational resources (e.g., hardware, software, firmware) that are used to communicate with other nodes. In some implementations, nodes in the communication system100can be implemented in various systems, such as, for example, laptops, desktops, workstations, smartphones, tablets, personal digital assistants, servers, server clusters, mainframes, and other types of computer systems. As shown inFIG. 1, the example node102includes a memory110, a processor112, and an interface114. Each of the nodes102,104may include the same, additional or different components. The nodes102,104may be configured to operate as shown and described with respect toFIG. 1or in another manner.

The example memory110can include, for example, random access memory (RAM), a storage device (e.g., a writable read-only memory (ROM) or others), a hard disk, or another type of storage medium. The example memory110can store instructions (e.g., computer code, a computer program, etc.) associated with an operating system, computer applications and other resources. The memory110can also store application data and data objects that can be interpreted by one or more applications or virtual machines running on the node102. The node102can be preprogrammed, or it can be programmed (and reprogrammed), by loading a program from another source (e.g., from a DVD-ROM, from a removable memory device, from a remote server, from a data network or in another manner). In some cases, the memory110stores computer-readable instructions for software applications, scripts, programs, functions, executables or other modules that are interpreted or executed by the processor112. For example, the computer-readable instructions can be configured to perform one or more of the operations shown in one or both ofFIGS. 2-7.

Instructions (e.g., computer code, a computer program, etc.) associated with an operating system, computer applications, or other resources may be stored in the memory110. In addition, the memory110can also store application data and data objects that can be interpreted by one or more applications or virtual machines running on the node102. The node102can be preprogrammed, or it can be programmed (and reprogrammed), by loading a program from another source (e.g., from a removable memory device, from a remote server, from a data network, or in another manner). In some cases, the memory110stores computer-readable instructions for software applications, scripts, programs, functions, executables or other modules that are interpreted or executed by the processor112. For example, the computer-readable instructions can be configured to perform one or more of the operations shown inFIGS. 2-7, as described further below.

In the example node102shown inFIG. 1, the processor112is a data processing apparatus that can execute instructions, for example, to generate output data based on data inputs. For example, the processor112can run computer programs by executing or interpreting the software, scripts, programs, functions, executables, or other modules stored in the memory110. In some instances, the processor112may perform one or more of the operations shown inFIGS. 2-7, as described further below.

The example processor112shown inFIG. 1can include one or more chips or chipsets that include analog circuitry, digital circuitry or a combination thereof. In some cases, the processor112includes multiple processor devices such as, for example, one or more main processors and one or more co-processors. For instance, the processor112may include a main processor that can delegate certain computational tasks to a cryptographic co-processor, which may be configured to perform the computational tasks more efficiently than the main processor or in parallel with other computational tasks performed by other processor devices. In some instances, the processor112coordinates or controls operation of other components of the node102, such as, for example, user interfaces, communication interfaces, peripheral devices and possibly other components.

In the example node102shown inFIG. 1, the interface114provides communication with other nodes (e.g., via channel106). In some cases, the interface114includes a wireless communication interface that provides wireless communication using various wireless protocols or standards. For example, the interface114may provide wireless communication via Bluetooth, Wi-Fi, Near Field Communication (NFC), CDMA, TDMA, PDC, WCDMA, CDMA2000, GPRS, GSM, or other forms of wireless communication. Such communication may occur, for example, through a radio-frequency transceiver or another type of component. In some cases, the interface114includes a wired communication interface (e.g., USB, Ethernet) that can be connected to one or more input/output devices, such as, for example, a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, for example, through a network adapter.

The example channel106can include all or part of a connector, a data communication network or another type of communication link. For example, the channel106can include one or more wired or wireless connections, one or more wired or wireless networks or other communication channels. The channel106may have any spatial distribution. The channel106may be public, private, or include aspects that are public and private. For instance, in some examples, the channel106includes one or more of a Local Area Network (LAN), a Wide Area Network (WAN), a Virtual Private Network (VPN), the Internet, a peer-to-peer network, a cellular network, a Wi-Fi network, a Personal Area Network (PAN) (e.g., a Bluetooth low energy (BTLE) network, a ZigBee network, etc.) or other short-range network involving machine-to-machine (M2M) communication, or another type of data communication network.

In the example shown, the quantum-enabled adversary108is a node in the communication system100that has access to quantum computational resources. For example, the quantum-enabled adversary108can be, include, or have access to a quantum computer, a quantum information processor, a quantum memory, a quantum communication interface or a combination of these and possibly other quantum technologies. In some implementations, the quantum-enabled adversary108can include a hybrid computing system, for instance, that includes a quantum processor driven by a classical front end processor, or another type of hybrid computing system.

In some examples, the quantum-enabled adversary108can store and process information in a quantum system. For instance, the quantum-enabled adversary108may encode information as quantum bits (“qubits”) and process the information by manipulating the qubits. The information may be encoded in physical qubits, logical qubits, or a combination of these and other types of qubits encodings. In some implementations, the quantum-enabled adversary108can operate in a fault-tolerant regime, or the quantum-enabled adversary may operate below the fault-tolerant regime.

Many public-key cryptosystems are known to be insecure against an attacker armed with a scalable quantum computer. The threat of quantum computers to public key cryptography can be mitigated by switching to other public key cryptosystems that are believed to be invulnerable to quantum attack. For example, certain code-based signature schemes (e.g., the McEliece and Niederreiter cryptosystems) have been proposed as quantum-resistant replacements for certain RSA-based or ECC-based cryptosystems that are believed to be quantum-vulnerable.

In some implementations, the example quantum-enabled adversary108can perform quantum computing algorithms, execute quantum computing circuits or quantum communication protocols, or perform other types of quantum information processing tasks. In the example shown, the quantum-enabled adversary108can perform Shor's algorithm, which allows the quantum-enabled adversary to efficiently solve problems that are believed to be hard on a classical computer. For example, the quantum-enabled adversary108may use Shor's algorithm to factor large integers, find discrete logarithms or possibly to solve other problems in a computationally-efficient manner. Accordingly, the example quantum-enabled adversary108can compromise the security of certain quantum-vulnerable cryptosystems (e.g., by computing a private key of a certificate authority or other entity based on public information).

The example quantum-enabled adversary108shown inFIG. 1can access information exchanged on the channel106. For example, the quantum-enabled adversary108may access some or all of the information exchanged between the nodes102,104. In some instances, the quantum-enabled adversary108can directly observe correspondence on the channel106; in some instances, the quantum-enabled adversary108indirectly obtains such correspondence, for example, by receiving information observed on the channel106by another entity or system.

In some implementations, the quantum-enabled adversary108can factor integers, compute discrete logarithms, or perform other classically-hard computational tasks fast enough to compromise the security of certain cryptosystems. For example, the quantum-enabled adversary108may be capable of computing prime factors fast enough to compromise certain RSA-based cryptosystems or computing discrete logarithms fast enough to compromise certain ECC-based cryptosystems.

In the example shown inFIG. 1, the nodes102,104may use a quantum-resistant cryptosystem that cannot be compromised by the example quantum-enabled adversary108. For instance, the nodes102,104may communicate using a cryptosystem that is secure against a quantum computer that can efficiently execute Shor's algorithm or other types of algorithms that are known to compromise the security of certain conventional cryptography standards. In some implementations, for example, the nodes102,104communicate using a McEliece cryptosystem implemented using a Quasi-Cyclic Medium Density Parity Check (QC-MDPC) code, a Niederreiter cryptosystem, or another type of public key cryptosystem. The nodes102,104may implement a CCA2 conversion technique to provide additional security against certain known attacks by adversaries. For example, in some implementations, a CCA2 conversion technique as described herein can be used with the McEliece cryptosystem implemented using a QC-MDPC code to provide security against key recovery attacks and the Adaptive Chosen Ciphertext Attack (CCA2). In some implementations, the nodes102,104execute secure communication over the channel106using the example techniques provided inFIGS. 2-7or using other techniques.

FIG. 2is a block diagram showing aspects of an example conversion scheme. In the example shown, a communication system200includes nodes202and204communicating over a channel206. The nodes202,204may be implemented similar to the nodes102,104ofFIG. 1. For instance, the nodes202,204may each have computational resources (e.g., hardware, software, firmware) that are used to communicate with other nodes in the communication system200, and may include a memory, processor, and interface as described above with respect to node102ofFIG. 1. The nodes202,204can be implemented in various systems, such as, for example, laptops, desktops, workstations, smartphones, tablets, personal digital assistants, servers, server clusters, mainframes, and other types of computer systems.

In the example shown inFIG. 2, the nodes202,204exchange encrypted communications over the channel206. The encrypted communications may be secure, in some instances, against both classical- and quantum-enabled adversaries (e.g., the quantum adversary108ofFIG. 1). For instance, in some implementations, the node202uses a conversion scheme in a McEliece cryptosystem implemented using a Quasi-Cyclic Medium Density Parity Check (QC-MDPC) codeof (n, k, t), where n is the size of a code word, k is the size of a QC-MDPC plaintext, and t is the Hamming weight of an error vector. By using a conversion scheme, such as the one shown inFIG. 2, the communications exchanged over the channel206may be secure against the known key recovery attack as well as the Adaptive Chosen Ciphertext Attack (CCA2) more efficiently than other CCA2 conversion techniques (e.g., the Kobara-Imai CCA2 conversion technique).

In the example shown inFIG. 2, the node202obtains a message208(msg) and a random value210(s). The message208may be generated by the node202(e.g., by a user of the node202using a messaging application), may be obtained from another node in the communication system200, or may be obtained in another manner. The random value210may be generated using a random number generator, or in another manner. In the example shown, the random value210has a length of h-bits and the message208has a length of l-bits (with l≥k−h, where k denotes the length of a plaintext value (described below)). The node202then applies an error vector derivation function214(v(⋅)) to a string212(msg∥s) formed by the concatenation of the message208and the random value210to produce an error vector216(e). In the example shown, the error vector derivation function214is a one-way (non-invertible) function that generates the error vector216in a pseudorandom manner. The error vector216has a length of n-bits. In some instances, the error vector derivation function214may apply a pseudorandom function (e.g., a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), or a stream cipher (e.g., a Salsa20 or ChaCha function)) to the random value and apply a filter (e.g., a Fisher-Yates shuffle) to the pseudorandom function output to produce a set of t integers (a1, a2, . . . , an), where each integer is in the range 1≤ai≤n for ai≠ajfor i≠j. The set of t integers can then be used to generate the error vector. For example, the error vector may have a Hamming weight equal to t, where the a1-th element of the error vector is set to one (1) and the other elements of the error vector are set to zero (0).

The node202then applies a pseudorandom function218to the error vector216(e). The pseudorandom function218may include a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), a stream cipher (e.g., a Salsa20 or ChaCha function), or another type of pseudorandom function. The node202then applies an exclusive-or (XOR) function220to the output of the pseudorandom function218and the string212to produce a masked string222(y). In the example shown, the masked string222(y) has a length of (l+h) bits, and includes a k-bit plaintext value224(x) and an h-bit second ciphertext component226(C2). In the example shown, the plaintext value224(x) is the k most significant bits of the masked string222(y), and the second ciphertext component226(C2) is the remaining portion of the masked string222(y). In some instances (e.g., where the message208is of length k), the masked string222(y) does not include a second ciphertext component226(C2).

The plaintext value224(x) is then used as an input to an encryption function228along with the error vector216(e) to produce a first ciphertext component230(C1). In the example shown, the first ciphertext component230has a length of n-bits. In some implementations, the encryption function228is a McEliece encryption function implemented according to a McEliece cryptosystem using the QC-MDPC code. For instance, the QC-MDPC code may generate a public key G and private key H, where G is a k×n code generator matrix and H is a (n×k)×n parity check matrix for G. In some implementations, the private key matrix H may be computed first, and the public key matrix G may be derived from H. The encryption function228may use the public key matrix G to generate the first ciphertext component230, for example, according to the equation C1=xG+e, where C1is the first ciphertext component230, x is the plaintext224, G is the public key matrix for the McEliece cryptosystem, and e is the error vector216. The node202then transmits the first ciphertext component230and the second ciphertext component226to the node204over the channel206.

In the example shown inFIG. 2, after receiving the first ciphertext component230and the second ciphertext component226, the node204applies a decryption function232to the first ciphertext component230. The decryption function232may be the inverse of the encryption function228. In some implementations, the decryption function232is a McEliece decryption function implemented according to a McEliece cryptosystem using the QC-MDPC code. For instance, the private key matrix H discussed above may be used to decrypt the first ciphertext component230, for example, by applying a QC-MDPC decoding algorithm equipped with knowledge of H. The decryption function232produces a first decryption function output234(x) with a length of k-bits and a second decryption function output236(e) with a length of n-bits. The node204then applies a pseudorandom function240to the second decryption function output236, and applies an exclusive-or (XOR) function242to the output of the pseudorandom function240and a string238formed by the concatenation of the first decryption function output234and the second ciphertext component226. The exclusive-or function242produces a check string244(msg∥s) with a length of (k+h)-bits. The pseudorandom function240may include a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), a stream cipher (e.g., a Salsa20 or ChaCha function), or another type of pseudorandom function.

The node204then applies an error vector derivation function246(v(⋅)) to the check string244of the exclusive-or function242to produce an error vector check value248(e′). In the example shown, the error vector derivation function236is the same as error vector derivation function214. The node204compares the error vector check value248with the second decryption function output236. If the error vector check value248is equal to the second decryption function output236(if e=e′), the node204outputs the message250(msg). In the example shown, the message250is the k most significant bits of the exclusive-or function check string244. If, however, the error vector check value248is not equal to the second decryption function output236(if e≠e′), the node204returns a failure. In some implementations, returning a failure includes delivering an error message, a return code, a flag, or another type of indicator. The indicator may be sent back to the node202, or to another node in a communication system. In some implementations, however, no indicator is sent and the indicator is kept only with the node204.

FIG. 3is a flow diagram showing an example ciphertext generation process300. The example process300can be performed, for example, by computer systems that can exchange information over a communication channel. For instance, operations in the process300may be performed by the nodes102,104in the example communication system100shown inFIG. 1, the nodes202,204in the example communication system200shown inFIG. 2or in another type of system. The example process300may include additional or different operations, and the operations may be performed in the order shown or in another order. In some cases, one or more of the operations shown inFIG. 3are implemented as processes that include multiple operations, sub-processes or other types of routines. In some cases, operations can be combined, performed in parallel, iterated or otherwise repeated or performed in another manner. In some examples, the process300is secure against quantum-enabled adversaries such as, for example, the quantum-enabled adversary108shown inFIG. 1. The example process300may also provide security against classically-enabled adversaries who do not have access to quantum computers or other quantum resources.

At302, an error vector derivation function is applied to a message value msg and a random value s to produce an error vector e. In some implementations, the error vector derivation function is applied to a combination of the message value msg and the random value s. For example, the error vector derivation function may be applied to a concatenation of the message value msg and the random values as in the example shown inFIG. 2. As another example, the error vector derivation function may be applied to the output of a hash function (e.g., a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), or a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function)) applied to the message value msg and the random value s (e.g., applied to a combination of the message value msg and the random value s). The random value s may be obtained from a random number generator, retrieved from memory, or obtained in another manner. The error vector derivation function v(⋅) may be a one-way function that generates an n-bit error vector e (an n-dimensional vector of bits) using a pseudorandom function and a filter. In some implementations, for instance, the error vector derivation function applies a pseudorandom function (e.g., a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), or a stream cipher (e.g., a Salsa20 or ChaCha function)) to a combination of the message value and the random value, and applies a filter (e.g., a Fisher-Yates shuffle) to the output of the pseudorandom function to produce a set of t integers (a1, a2, . . . , an), where each integer is in the range 1≤ai≤n for ai≠ajfor i≠j. The set of t integers can then be used to generate the error vector e. For example, the error vector e may have a Hamming weight equal to t, where the ai-th element of the error vector e is set to one (1) and the other elements of the error vector e are set to zero (0). The error vector derivation function may be implemented in another manner.

At304, a plaintext value x is generated based on the message value msg, the random value s, and the error vector e. In some implementations, the plaintext value x is generated from the output of an exclusive-or (XOR) function. For example, an exclusive-or function may be applied to a string formed by the combination (e.g., concatenation) of the message value msg and the random value s and the output of a pseudorandom function applied to the error vector e, as in the example shown inFIG. 2. The pseudorandom function applied to the error vector e may be a cryptographic hash function (a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function)), or a stream cipher (e.g., a Salsa20 or ChaCha function). In some instances, the output of the exclusive-or function includes a stringy that includes the plaintext value x and a second ciphertext component C2, as described above with respect toFIG. 2. The plaintext value x may be generated in another manner.

At306, the plaintext value x and the error vector e are used in an encryption function to produce a first ciphertext component C1. The encryption function may use a public key to produce the first ciphertext component C1based on the plaintext value x and the error vector e. In some implementations, the encryption function is a McEliece encryption function, and the plaintext value x is encrypted according to a McEliece cryptosystem using the error vector e and a public key G. For example, the encryption function may be implemented according to a McEliece cryptosystem using a QC-MDPC code, and the first ciphertext component C1may be generated by adding the error vector e to the product of the plaintext value x and a public key matrix G (C1=xG+e), as discussed above with respect toFIG. 2. The public key may be based on a private key known to a recipient node in some instances. For example, referring to the example shown inFIG. 2, the public key used in the encryption function228may be a public key matrix G based on a private key matrix H known to the node204. The encryption function may be based on another cryptosystem, in some instances. For example, the encryption function may be based on a Niederreiter cryptosystem.

At308, the first ciphertext component C is provided for transmission in a communication system. For example, the first ciphertext component C1are provided to an interface of the node or nodes performing the process300such that the node(s) may transmit the information to another node in the communication system. For instance, referring to the example shown inFIG. 2, the first ciphertext component230may be provided to a network interface of the node202for transmission to the node204over the channel206. In some implementations, the second ciphertext component C2may also be provided for transmission in the communication system. The second ciphertext component C2may be provided for transmission in the same or separate transmission as the first ciphertext component C1.

FIG. 4is a flow diagram showing an example ciphertext decryption process400. The example process400can be performed, for example, by computer systems that can exchange information over a communication channel. For instance, operations in the process400may be performed by the nodes102,104in the example communication system100shown inFIG. 1, the nodes202,204in the example communication system200shown inFIG. 2or in another type of system. The example process400may include additional or different operations, and the operations may be performed in the order shown or in another order. In some cases, one or more of the operations shown inFIG. 4are implemented as processes that include multiple operations, sub-processes or other types of routines. In some cases, operations can be combined, performed in parallel, iterated or otherwise repeated or performed in another manner. In some examples, the process400is secure against quantum-enabled adversaries such as, for example, the quantum-enabled adversary108shown inFIG. 1. The example process400may also provide security against classically-enabled adversaries who do not have access to quantum computers or other quantum resources.

At402, a first ciphertext component C1is obtained. The first ciphertext component may be a ciphertext transmitted between nodes in a communication system. For instance, referring to the example shown inFIG. 2, the first ciphertext component230is transmitted from node202to node204over the channel206. The first ciphertext component may be obtained by receiving the first ciphertext component from an interface (e.g., network interface) after receipt of the first ciphertext component from another node, by retrieving the first ciphertext component stored in memory, or in another manner.

At404, a decryption function is applied to the first ciphertext component C1, and produces a first decryption function output x and a second decryption function output e. The decryption function may be the inverse of an encryption function used by another node in the communication network to generate the first ciphertext component C1. Thus, the first and second decryption function outputs may include the plaintext value x and the error vector e, respectively, that are used in the encryption function to generate the first ciphertext component C1. In some implementations, the decryption function is a McEliece decryption function, and the first ciphertext component C1is decrypted using a private key. For example, the decryption function may be implemented according to a McEliece cryptosystem using a QC-MDPC code, and the first ciphertext component C1may be decrypted using a private key matrix H, as discussed above with respect toFIG. 2. The decryption function may be based on another cryptosystem, in some instances. For example, the decryption function may be based on a Niederreiter cryptosystem.

At406, a check string is generated based on the first and second decryption function outputs. In some implementations, the check string is generated by applying a pseudorandom function to the second decryption function output e, and applying an exclusive-or function to the output of the pseudorandom function and a value that includes the first decryption function output x. In some instances (e.g., where a second ciphertext component is transmitted with the first ciphertext component, as described above), the value includes the first decryption function output x and a second ciphertext component C2. The pseudorandom function may be a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), a stream cipher (e.g., a Salsa20 or ChaCha function), or another type of pseudorandom function.

At408, an error vector derivation function is applied to the check string to produce an error vector check value e′. The error vector derivation function may be a one-way function that generates an error vector check value e′ of n-bits using a pseudorandom function and a filter. In some implementations, the error vector derivation function applies a pseudorandom function (e.g., a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), or a stream cipher (e.g., a Salsa20 or ChaCha function)) to the check string, and then applies a filter (e.g., a Fisher-Yates shuffle) to the output of the pseudorandom function to produce a set of t integers (a1, a2, . . . , an), where each integer is in the range 1≤ai≤n for ai≠ajfor i≠j. The set oft integers can then be used to generate the error vector check value e′. For example, the error vector check value e′ may have a Hamming weight equal to t, where the ai-th element of the error vector check value e′ is set to one (1) and the other elements of the error vector check value e′ are set to zero (0).

At410, the error vector check value e′ and the second decryption function output e are compared. If the error vector check value e′ is equal to the second decryption function output e, a message value is generated at412based on the check string. In some implementations, the message value is a portion of the check string. For example, the message may be the k most significant bits of the check string. The message value may be generated in another manner. If the error vector check value e′ does not equal to the second decryption function output e, a failure is returned at414. In some implementations, returning a failure includes delivering an error message, a return code, a flag, or another type of indicator. The indicator may be sent back to the node that transmitted the ciphertext, or to another node in a communication system. In some implementations, however, no indicator is sent and the indicator is kept only with the node performing the process400.

FIG. 5is a block diagram showing aspects of another example conversion scheme for a public key cryptosystem. In the example shown, a communication system500includes nodes502and504communicating over a channel506. The nodes502,504may be implemented similar to the nodes102,104ofFIG. 1. For instance, the nodes502,504may each have computational resources (e.g., hardware, software, firmware) that are used to communicate with other nodes in the communication system500, and may include a memory, processor, and interface as described above with respect to node102ofFIG. 1. The nodes502,504can be implemented in various systems, such as, for example, laptops, desktops, workstations, smartphones, tablets, personal digital assistants, servers, server clusters, mainframes, and other types of computer systems.

In the example shown inFIG. 5, the nodes502,504exchange encrypted communications over the channel506. The encrypted communications may be secure, in some instances, against both classical- and quantum-enabled adversaries (e.g., the quantum adversary108ofFIG. 1). For instance, in some implementations, the node502uses a conversion scheme in a McEliece cryptosystem implemented using a Quasi-Cyclic Medium Density Parity Check (QC-MDPC) codeof (n, k, t), where n is the size of a code word, k is the size of a QC-MDPC plaintext, and t is the Hamming weight of an error vector. By using a conversion scheme, such as the one shown inFIG. 5, the communications exchanged over the channel506may be secure against the known key recovery attack as well as the Adaptive Chosen Ciphertext Attack (CCA2) more efficiently than other CCA2 conversion techniques (e.g., the Kobara-Imai CCA2 conversion technique).

In the example shown inFIG. 5, the node502obtains a message508(msg) and a constant value510(const). The message508may be generated by the node502(e.g., by a user of the node502using a messaging application), may be obtained from another node in the communication system500, or may be obtained in another manner. The constant value510may be any constant value that is known to both nodes502,504. In some instances, for example, the constant value may be a known parameter of the conversion scheme. In the example shown, the constant value510has a length of h bits. The node502also obtains a random value514(s). The random value514may be generated using a random number generator or in another manner. In the example shown, the random value514has a length of h-bits and the message508has a length of l-bits (with l≥k−h, where k denotes the length of a plaintext value (described below)).

The node502concatenates the message508and the constant value510to produce the concatenated string512, and also applies a pseudorandom function516to the random value514. The pseudorandom function516may include a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), a stream cipher (e.g., a Salsa20 or ChaCha function), or another type of pseudorandom function. The node502then applies an exclusive-or (XOR) function518to the string512and the output of the pseudorandom function516to produce a first string520(y1). A cryptographic hash function522is applied to the first string520, and an exclusive-or (XOR) function524is applied to the output of the hash function522and the random value514to produce a second string516(y2). The cryptographic hash function522may include a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function) or another type of cryptographic hash function.

The first string520and second string526are concatenated to produce the concatenated string528(y1∥y2), which includes a k-bit plaintext value530(x) and an h-bit second ciphertext component532(C2). In the example shown, the plaintext value530(x) is the k most significant bits of the concatenated string528, and the second ciphertext component532is the remaining portion of the concatenated string528. In some instances (e.g., where the message508is of length k), the concatenated string528does not include the second ciphertext component532.

The node502then applies an error vector derivation function534(v(⋅)) to the plaintext value530to produce an error vector536(e). In the example shown, the error vector derivation function534is a one-way (non-invertible) function that generates the error vector536in a pseudorandom manner. The error vector536has a length of n-bits. In some instances, the error vector derivation function534may apply a pseudorandom function (e.g., a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), or a stream cipher (e.g., a Salsa20 or ChaCha function)) to the plaintext value530and apply a filter (e.g., a Fisher-Yates shuffle) to the pseudorandom function output to produce a set of t integers (a1, a2, . . . , an), where each integer is in the range 1≤ai≤n for ai≠ajfor i≠j. The set of t integers can then be used to generate the error vector536. For example, the error vector536may have a Hamming weight equal to t, where the ai-th element of the error vector is set to one (1) and the other elements of the error vector are set to zero (0).

The plaintext value530and error vector536are then used as inputs to an encryption function538, which produces a first ciphertext component540(C1). In the example shown, the first ciphertext component540has a length of n-bits. In some implementations, the encryption function538is a McEliece encryption function implemented according to a McEliece cryptosystem using the QC-MDPC code. For instance, the QC-MDPC code may generate a public key G and private key H, where G is a k×n code generator matrix and H is a (n−k)×n parity check matrix for G. In some implementations, the private key matrix H may be computed first, and the public key matrix G may be derived from H. The encryption function538may use the public key matrix G to generate the first ciphertext component540, for example, according to the equation C1=xG+e, where C1is the first ciphertext component540, x is the plaintext530, G is the public key matrix for the McEliece cryptosystem, and e is the error vector536. The node502then transmits the first ciphertext component540and the second ciphertext component532to the node504over the channel506.

In the example shown inFIG. 5, after receiving the first ciphertext component540and the second ciphertext component532, the node504applies a decryption function542to the first ciphertext component540. The decryption function542may be the inverse of the encryption function538. In some implementations, the decryption function542is a McEliece decryption function implemented according to a McEliece cryptosystem using the QC-MDPC code. For instance, the private key matrix H discussed above may be used to decrypt the first ciphertext component540, for example, by applying a QC-MDPC decoding algorithm equipped with knowledge of H. The decryption function542produces a first decryption function output546(x) with a length of k-bits and a second decryption function output544(e) with a length of n-bits. The node504then concatenates the first decryption function output546and the second ciphertext component532to produce the concatenated string548, which includes the values550,552. In the example shown, the second value552is the k least significant bits of the concatenated string548and the first value550is the remaining most significant bits of the concatenated string548.

The node504applies a cryptographic hash function554to the first value550, and applies an exclusive-or (XOR) function556to the output of the cryptographic hash function554and the second value552to produce a third value558(s). The cryptographic hash function554may include a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function) or another type of cryptographic hash function. The node504then applies a pseudorandom function560to the third value558, and applies an exclusive-or (XOR) function562to the output of the pseudorandom function560and the first value550to produce a check string564(msg∥const′) having a length of (l+h) bits. The pseudorandom function560may include a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), a stream cipher (e.g., a Salsa20 or ChaCha function), or another type of pseudorandom function.

The node504also applies an error vector derivation function570(v(⋅)) to the first decryption function output546to produce an error vector check value572(e′). In the example shown, the error vector derivation function570is the same as error vector derivation function534. The node504compares the error vector check value572with the second decryption function output544. If the error vector check value572is equal to the second decryption function output544(if e=e′) and the constant check value568is equal to the constant value510(if const=const′), the node504generates the message566(msg) from the check string564and outputs the message566(e.g., for display to a user of the node504). In the example shown, the message566is the k most significant bits of the check string564, the constant check value568is the h least significant bits of the check string564. If, however, the error vector check value572is not equal to the second decryption function output544(if e≠e′) or the constant check value568is not equal to the constant value510(if const≠const′), the node504returns a failure. In some implementations, returning a failure includes delivering an error message, a return code, a flag, or another type of indicator. The indicator may be sent back to the node502, or to another node in a communication system. In some implementations, however, no indicator is sent and the indicator is kept only with the node504.

FIG. 6is a flow diagram showing another example ciphertext generation process600. The example process600can be performed, for example, by computer systems that can exchange information over a communication channel. For instance, operations in the process600may be performed by the nodes102,104in the example communication system100shown inFIG. 1, the nodes502,504in the example communication system500shown inFIG. 5or in another type of system. The example process600may include additional or different operations, and the operations may be performed in the order shown or in another order. In some cases, one or more of the operations shown inFIG. 6are implemented as processes that include multiple operations, sub-processes or other types of routines. In some cases, operations can be combined, performed in parallel, iterated or otherwise repeated or performed in another manner. In some examples, the process600is secure against quantum-enabled adversaries such as, for example, the quantum-enabled adversary108shown inFIG. 1. The example process600may also provide security against classically-enabled adversaries who do not have access to quantum computers or other quantum resources.

At602, a plaintext value x is generated based on a message value msg, a constant value const, and a random value s. In some implementations, the plaintext value is generated by applying a pseudorandom function to the random value, and applying a first exclusive-or (XOR) function to an output of the pseudorandom function and a combination (e.g., concatenation) of the message value and the constant value. A cryptographic hash function may be applied to the output of the first exclusive-or function, and a second exclusive-or (XOR) function may be applied to the random value and an output of the cryptographic hash function. The outputs of the first and second exclusive-or (XOR) functions (y1 and y2, respectively) may then be combined (e.g., concatenated), and the plaintext value may be generated based on the combination. For example, the plaintext value x may be the k most significant bits of the combination. In some instances, a second ciphertext component C2may also be generated from the combination. For example, the second ciphertext component C2may be the h least significant bits of the combination. The plaintext value x may be generated in another manner.

At604, an error vector derivation function is applied to the plaintext value x to produce an error vector e. The error vector derivation function v(⋅) may be a one-way function that generates an n-bit error vector e (an n-dimensional vector of bits) using a pseudorandom function and a filter. In some implementations, for instance, the error vector derivation function applies a pseudorandom function (e.g., a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), or a stream cipher (e.g., a Salsa20 or ChaCha function)) to the plaintext value x, and applies a filter (e.g., a Fisher-Yates shuffle) to the output of the pseudorandom function to produce a set oft integers (a1, a2, . . . , an), where each integer is in the range 1≤ai≤n for ai≠ajfor i≠j. The set of t integers can then be used to generate the error vector e. For example, the error vector e may have a Hamming weight equal to t, where the ai-th element of the error vector e is set to one (1) and the other elements of the error vector e are set to zero (0). The error vector derivation function may be implemented in another manner.

At606, the plaintext value x and the error vector e are used in an encryption function to produce a first ciphertext component C1. The encryption function may use a public key to produce the first ciphertext component C1based on the plaintext value x and the error vector e. In some implementations, the encryption function is a McEliece encryption function, and the plaintext value x is encrypted according to a McEliece cryptosystem using the error vector e and a public key G. For example, the encryption function may be implemented according to a McEliece cryptosystem using a QC-MDPC code, and the first ciphertext component C1may be generated by adding the error vector e to the product of the plaintext value x and a public key matrix G (C1=xG+e), as discussed above with respect toFIG. 5. The public key may be based on a private key known to a recipient node in some instances. For example, referring to the example shown inFIG. 5, the public key used in the encryption function538may be a public key matrix G based on a private key matrix H known to the node504. The encryption function may be based on another cryptosystem, in some instances. For example, the encryption function may be based on a Niederreiter cryptosystem.

At608, the first ciphertext component C1is provided for transmission in a communication system. For example, the first ciphertext component C1may be provided to an interface of the node or nodes performing the process600such that the node(s) may transmit the first ciphertext component C1to another node in the communication system. For instance, referring to the example shown inFIG. 5, the first ciphertext component540may be provided to a network interface of the node502for transmission to the node504over the channel506. In some implementations, the second ciphertext component C2may also be provided for transmission in the communication system. A second ciphertext component C2may be provided for transmission in the same or separate transmission as the first ciphertext component C1.

FIG. 7is a flow diagram showing another example ciphertext decryption process700. The example process700can be performed, for example, by computer systems that can exchange information over a communication channel. For instance, operations in the process700may be performed by the nodes102,104in the example communication system100shown inFIG. 1, the nodes502,504in the example communication system500shown inFIG. 5or in another type of system. The example process700may include additional or different operations, and the operations may be performed in the order shown or in another order. In some cases, one or more of the operations shown inFIG. 7are implemented as processes that include multiple operations, sub-processes or other types of routines. In some cases, operations can be combined, performed in parallel, iterated or otherwise repeated or performed in another manner. In some examples, the process700is secure against quantum-enabled adversaries such as, for example, the quantum-enabled adversary108shown inFIG. 1. The example process700may also provide security against classically-enabled adversaries who do not have access to quantum computers or other quantum resources.

At702, a first ciphertext component C1is obtained. The first ciphertext component may be a first ciphertext component transmitted between nodes in a communication system. For instance, referring to the example shown inFIG. 5, the first ciphertext component540is transmitted from node502to node504over the channel506. The first ciphertext component may be obtained by receiving the first ciphertext component from an interface (e.g., network interface) after receipt of the first ciphertext component from another node, by retrieving the first ciphertext component stored in memory, or in another manner. In some implementations, the constant value const used to generate the first ciphertext component C1is also obtained. In some cases, the constant value is a value known to all nodes participating in cryptographic communications according to the processes600,700. The constant value may be obtained in another manner. In some implementations, a second ciphertext component C2is also obtained. In some instance, the second ciphertext component is obtained in the same transmission as the first ciphertext component C1. The second ciphertext component may be obtained in another manner.

At704, a decryption function is applied to the first ciphertext component C1to produce a first decryption function output x and a second decryption function output e. The decryption function may be the inverse of an encryption function used by another node in the communication network to generate the first ciphertext component C1. Thus, the first and second decryption function outputs may include the plaintext value x and the error vector e, respectively, that are used in the encryption function to generate the first ciphertext component C1. In some implementations, the decryption function is a McEliece decryption function, and the first ciphertext component C1is decrypted using a private key. For example, the decryption function may be implemented according to a McEliece cryptosystem using a QC-MDPC code, and the first ciphertext component C1may be decrypted using a private key matrix H, as discussed above with respect toFIG. 5. The decryption function may be based on another cryptosystem, in some instances. For example, the decryption function may be based on a Niederreiter cryptosystem.

At706, a check string is generated based on the first decryption function output x. In some implementations, the check string is generated by generating a first value y1 and a second value y2 based on the plaintext value x, generating a third values based on the first and second values, and applying a first exclusive-or function to the first value (y1) and an output of a pseudorandom function applied to the third value to produce the check string. The pseudorandom function may be a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), a stream cipher (e.g., a Salsa20 or ChaCha function), or another type of pseudorandom function. The third value s may be generated by applying a cryptographic hash function to the first value y1 and applying a second exclusive-or function to the second value y2 and an output of the cryptographic hash function. The cryptographic hash function may be a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function) or another type of cryptographic hash function. Where a second ciphertext component C2is obtained at702, the second ciphertext component may be combined (e.g., concatenated) with the plaintext value x, with the first and second values y1 and y2 being generated by parsing the combination.

At708, an error vector derivation function is applied to the first decryption function output x to produce an error vector check value e′. The error vector derivation function may be a one-way function that generates an error vector check value e′ of n-bits using a pseudorandom function and a filter. In some implementations, the error vector derivation function applies a pseudorandom function (e.g., a National Institute of Standards and Technology key derivation function (NIST KDF), a keyed-hash message authentication code (HMAC) based key derivation function (HKDF), a hash function of the primitive family Keccak (e.g., a SHA3 or SHAKE function), or a stream cipher (e.g., a Salsa20 or ChaCha function)) to the first decryption function output x, and then applies a filter (e.g., a Fisher-Yates shuffle) to the output of the pseudorandom function to produce a set oft integers (a1, a2, . . . , an), where each integer is in the range 1≤ai≤n for ai≠ajfor i≠j. The set of t integers can then be used to generate the error vector check value e′. For example, the error vector check value e′ may have a Hamming weight equal to t, where the ai-th element of the error vector check value e′ is set to one (1) and the other elements of the error vector check value e′ are set to zero (0).

At710, the error vector check value e′ and the second decryption function output e are compared. If the error vector check value e′ is equal to the second decryption function output e, a message value msg is generated at712based on the check string. In some implementations, the message value is a portion of the check string. For example, the message value msg may be the k most significant bits of the check string. The message value may be generated in another manner. If the error vector check value e′ does not equal to the second decryption function output e, a failure is returned at714. In some implementations, returning a failure includes delivering an error message, a return code, a flag, or another type of indicator. The indicator may be sent back to the node that transmitted the first ciphertext component, or to another node in a communication system. In some implementations, however, no indicator is sent and the indicator is kept only with the node performing the process700.

In some implementations, where the constant value const used to generate the first ciphertext component C1is also obtained at702, the constant value const may be compared, at710, with a constant check value const′ that is generated based on the check string. In some cases, for example, the constant check value const′ is the h least significant bits of the check string. If the error vector check value e′ is equal to the second decryption function output e and the constant check value const′ is equal to the constant value const, then the message is generated based on the check string at712. Otherwise, a failure is returned at714.

Some of the operations described in this specification can be implemented as operations performed by data processing apparatus on data stored in memory (e.g., on one or more computer-readable storage devices) or received from other sources. The term “data processing apparatus” encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, a system on a chip, or multiple ones, or combinations, of the foregoing. The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, a cross-platform runtime environment, a virtual machine, or a combination of one or more of them. In some instances, the data processing apparatus includes a set of processors. The set of processors may be co-located (e.g., multiple processors in the same computing device) or located in different location from one another (e.g., multiple processors in distributed computing devices). The memory storing the data executed by the data processing apparatus may be co-located with the data processing apparatus (e.g., a computing device executing instructions stored in memory of the same computing device), or located in a different location from the data processing apparatus (e.g., a client device executing instructions stored on a server device).

Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random-access memory or both. Elements of a computer can include a processor that performs actions in accordance with instructions, and one or more memory devices that store the instructions and data. A computer may also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., non-magnetic drives (e.g., a solid-state drive), magnetic disks, magneto optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a phone, a tablet computer, an electronic appliance, a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, an Internet-of-Things (IoT) device, a machine-to-machine (M2M) sensor or actuator, or a portable storage device (e.g., a universal serial bus (USB) flash drive). Devices suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices (e.g., EPROM, EEPROM, flash memory devices, and others), magnetic disks (e.g., internal hard disks, removable disks, and others), magneto optical disks, and CD ROM and DVD-ROM disks. In some cases, the processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

In a general aspect of the examples described here, a conversion scheme is used in a public key cryptosystem.

In a first example, an error vector derivation function (v(⋅)) is applied to a random value (s) and a message value (msg) to produce an error vector (e). A plaintext value (x) is generated based on the random value (s), the message value (msg), and the error vector (e). The error vector (e) and the plaintext value (x) are used, by operation of one or more processors, in an encryption function to produce a first ciphertext component (C1), and the first ciphertext component (C1) is provided for transmission in a communication system.

Implementations of the first example may include one or more of the following features. Applying the error vector derivation function (v(⋅)) to the random value (s) and the message value (msg) may include applying the error vector derivation function to a concatenation of the random value and the message value (msg∥s). Applying the error vector derivation function (v(⋅)) to the random value (s) and the message value (msg) may include applying the error vector derivation function to an output of a hash function applied to the random value and the message value. Applying the error vector derivation function (v(⋅)) to the random value (s) and the message value (msg) may include applying a pseudorandom function to the random value (s) and the message value (msg) to produce a pseudorandom function output, applying a filter to the pseudorandom function output the produce a filtered pseudorandom function output (a1, a2, . . . , an), and generating the error vector (e) based on the filtered pseudorandom function output, the error vector (e) having a Hamming weight equal to t. The filtered pseudorandom function output may include t integers, and respective positions of the nonzero elements of the error vector (e) may be indicated by the filtered pseudorandom function output.

Implementations of the first example may include one or more of the following features. Generating the plaintext value (x) may include applying a pseudorandom function to the error vector (e) to produce a pseudorandom function output, and applying an exclusive-or (XOR) function to the pseudorandom function output and a combination of the random value and the message value (msg∥s). The pseudorandom function may include a cryptographic hash function or a stream cipher. Generating the plaintext value (x) may include generating a string (y) that includes the plaintext value (x) and a second ciphertext component (C2). The second ciphertext component may be provided for transmission in the communication system.

Implementations of the first example may include one or more of the following features. The encryption function may include a McEliece encryption function. Using the error vector and the plaintext value in the encryption function may include adding the error vector to the product of the plaintext value and a public key matrix (c=xG+e).

In a second example, a first ciphertext component (C1) transmitted between nodes in a communication system is obtained. A decryption function is applied, by operation of one or more processors, to the first ciphertext component (C1) to produce a first decryption function output (x) and a second decryption function output (e). A check string (msg∥s) is generated based on the first decryption function output (x) and the second decryption function output (e), and an error vector derivation function (v(⋅)) is applied to the check string (msg∥s) to produce an error vector check value (e′). The second decryption function output (e) is compared with the error vector check value (e′), and a message value (msg) is generated based on the check string in response to a determination that the second decryption function output (e) is equal to the error vector check value (e′).

Implementations of the second example may include one or more of the following features. The decryption function may include a McEliece decryption function. Generating the check string (msg∥s) may include applying a pseudorandom function to the second decryption function output (e) to produce a pseudorandom function output, and applying an exclusive-or (XOR) function to the pseudorandom function output and a value that includes the first decryption function output (x). Applying the error vector derivation function (v(⋅)) to the check string (msg∥s) may include applying a pseudorandom function to the check string (msg∥s) to produce a pseudorandom function output, applying a filter to the pseudorandom function output the produce a filtered pseudorandom function output (a1, a2, . . . , an), and generating an error vector check value (e′) based on the filtered pseudorandom function output, the error vector check value (e′) having a Hamming weight equal to t. The filtered pseudorandom function output may include t integers; and respective positions of the nonzero elements of the error vector check value (e′) may be indicated by the filtered pseudorandom function output.

In a third example, a plaintext value (x) is generated based on a message value (msg), a constant value (const), and a random value (s). An error vector derivation function (v(⋅)) is applied to the plaintext value (x) to produce an error vector (e). The plaintext value (x) and the error vector (e) used, by operation of one or more processors, in an encryption function to produce a first ciphertext component (C1), and the first ciphertext component (C1) is provided for transmission in a communication network.

Implementations of the third example may include one or more of the following features. Generating the plaintext value may include applying a pseudorandom function to the random value, applying an exclusive-or function to an output of the pseudorandom function and a combination of the message value and the constant value, and generating the plaintext value based on an output of the exclusive-or function (y1). The exclusive-or function may be a first exclusive-or function, a cryptographic hash function may be applied to the output of the first exclusive-or function (y1), a second exclusive-or function may be applied to the random value and an output of the cryptographic hash function, and the plaintext value may be based on the output of the first exclusive-or function (y1) and the output of the second exclusive-or function (y2). Generating the plaintext value may include generating a string comprising the plaintext value and a second ciphertext component (C2), and the second ciphertext component may be provided for transmission in the communication system. Applying the error vector derivation function (v(⋅)) to the plaintext value may include applying a pseudorandom function to the plaintext value to produce a pseudorandom function output, applying a filter to the pseudorandom function output the produce a filtered pseudorandom function output (a1, a2, . . . , an), the filtered pseudorandom function output comprising t integers; and generating the error vector (e) based on the filtered pseudorandom function output. The error vector (e) may have a Hamming weight equal to t, wherein respective positions of the nonzero elements of the error vector (e) are indicated by the filtered pseudorandom function output. The encryption function may include a McEliece encryption function, and applying the encryption function to the error vector and the plaintext value may include adding the error vector to the product of the plaintext value and a public key matrix (c=xG+e).

In a fourth example, a first ciphertext component (C1) transmitted between nodes in a communication system is obtained. A decryption function is applied to the first ciphertext component (C1) to produce a first decryption function output (x) and a second decryption function output (e). A check string (msg∥const′) is generated based on the first decryption function output (x), and an error vector derivation function (v(⋅)) is applied to the first decryption function output (x) to produce an error vector check value (e′). The second decryption function output (e) is compared with the error vector check value (e′), and a message value (msg) is generated based on the check string in response to a determination that the second decryption function output (e) is equal to the error vector check value (e′).

Implementations of the fourth example may include one or more of the following features. A constant value (const) used in generating the first ciphertext component may be obtained, a portion of the check string (const′) may be compared with the constant value, and the message value may be generated in response to a determination that the constant value is equal to the portion of the check string. Generating the check string based on the first decryption function output may include generating a first value (y1) and a second value (y2) based on the plaintext value (x), generating a third value (s) based on the first and second values, and generating the check string by applying an exclusive-or function to the first value (y1) and an output of a pseudorandom function applied to the third value. The exclusive-or function may be a first exclusive-or function, and generating the third value based on the first and second values may include applying a cryptographic hash function to the first value (y1) and applying a second exclusive-or function to the second value (y2) and an output of the cryptographic hash function. A second ciphertext component (C2) transmitted between the nodes in the communication system may be obtained, and generating the first value (y1) and the second value (y2) based on the plaintext value (x) may include parsing a combination of the plaintext value (x) and the second ciphertext component (C2). The decryption function may include a McEliece decryption function, and applying the decryption function may include using a private key to decrypt the first ciphertext component according to a McEliece cryptosystem. Applying the error vector derivation function (v(⋅)) to the first decryption function output (x) may include applying a pseudorandom function to the first decryption function output (x) to produce a pseudorandom function output, applying a filter to the pseudorandom function output the produce a filtered pseudorandom function output (a1, a2, . . . , an), where the filtered pseudorandom function output includes t integers, and generating the error vector check value (e′) based on the filtered pseudorandom function output. The error vector check value (e′) may have a Hamming weight equal to t, and respective positions of the nonzero elements of the error vector check value (e′) may be indicated by the filtered pseudorandom function output.

In some implementations, a computing system includes data processing apparatus and memory storing instructions that are operable when executed by the data processing apparatus to perform one or more operations of the first, second, third, or fourth example. In some implementations, a computer-readable medium stores instructions that are operable when executed by data processing apparatus to perform one or more operations of the first, second, third, or fourth example.

While this specification contains many details, these should not be understood as limitations on the scope of what may be claimed, but rather as descriptions of features specific to particular examples. Certain features that are described in this specification or shown in the drawings in the context of separate implementations can also be combined. Conversely, various features that are described or shown in the context of a single implementation can also be implemented in multiple embodiments separately or in any suitable subcombination.