BACKGROUND

The present invention relates to quantum resistant public key encryption, and more specifically, a new trapdoor design for a multivariate encryption scheme in which the trapdoor has degree 4 and utilizes a new split-and-switch composition mechanism.

SUMMARY

According to an embodiment of the present invention, a new method and system for Quantum Resistant Public Key Encryption is described. A key feature of this method, referred to herein as “Split-and-Switch Composition”, describes a method in which the trapdoor in Multivariate Public Key Cryptography (MPKC) has degree greater than 2 and which provides a public key for encrypting an input plaintext into a ciphertext having two components each of degree 4 (the split), with one component having a composition with a map that has been switched from a map used in the other component (the switch).

The new trapdoor includes the definition of the algorithm underlying the split and switch, so that the private key associated with the encrypted plaintext permits the reconstruction of the original plaintext from the two components of the encrypted ciphertext. This new method of public key encryption additionally advantageously provides much smaller key size than conventional MPKC methods as well as providing potentially a strong and scalable security O(qⁿ).

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 exemplarily shows in diagrammatic format the problem being addressed by the present invention;

FIG. 2 exemplarily shows a generic format generic MPKC mechanism 200;

FIG. 3 shows an exemplary embodiment of a new trapdoor design 300 of the present invention, as used in multivariate encryption schemes using the split-and-switch composition mechanism;

FIG. 4 shows the starting point of the split-and-switch composition, namely an invertible multivariate polynomial map F of degree 4;

FIG. 5 exemplarily shows the concept of the “split” aspect of the present invention;

FIG. 6 exemplarily shows the concept of the “switch” aspect of the present invention;

FIG. 7 demonstrates encryption using split-and-switch composition;

FIG. 8 shows the first stage of decryption using split-and-switch composition;

FIG. 9 shows the second stage of decryption using split-and-switch composition;

FIG. 10 shows the system design for encryption using a public key (e.g., public polynomial 1004);

FIG. 11 shows the system design for decryption using private key 1102 and the trapdoor 1000;

FIG. 12 exemplarily shows a comparison of key size using split-and-switch composition;

FIG. 13 depicts a cloud computing environment according to an embodiment of the present invention; and

FIG. 14 depicts abstraction model layers according to an embodiment of the present invention.

DETAILED DESCRIPTION

With reference now to FIG. 1, the present invention is directed to an improvement in cryptographic systems which play a fundamental role in applications such as high security business standards, such as RSA 104 or ECC 106, used universally on Internet transactions. ECC (Elliptic-Curve Cryptography) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. RSA (Rivest-Shamir-Adleman) is an acronym formed of the initials of the surnames of the three individuals who first publicly described this algorithm in 1978.

RSA is one of the first public-key cryptosystems and is still widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret (private), thereby being an example of an asymmetric cryptography system as referring to any cryptographic system that uses pairs of keys: public keys which may be disseminated widely, and private keys which are known only to the owner.

The asymmetry of RSA is based on the practical difficulty of the factorization of the product of two large prime numbers. A user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, and if the public key is large enough, only someone with knowledge of the prime numbers can decode the message feasibly.

As further demonstrated in FIG. 1, the present invention is directed to the problem recognized in cryptography that Shor's algorithm 100, which provides a quantum algorithm (an algorithm that runs on a quantum computer) for factorization, could be used to break public-key cryptography schemes such as the RSA scheme. On a quantum computer 102, to factor an integer N, Shor's algorithm would run in polynomial time, meaning the time taken is polynomial in log N, which is the size of the input. Thus, using fast multiplication with a number of quantum gates of order O((log N)²(log log N)(log log log N)), the integer factorization problem can be efficiently solved on a quantum computer substantially faster than the most efficient known classical factoring algorithms. Such awareness of the potential of Shor's algorithm has facilitated research on new cryptosystems that are secure from quantum computers, often collectively called post-quantum cryptography. The cryptography community has been actively searching for such algorithms since the early 1990s, and the National Institute of Standards and Technology (NIST) in the United States called for quantum-secure cryptographic algorithms in 2017.

FIG. 2 shows a generic MPKC mechanism 200. When MPKC is used for encryption, n<=m and the polynomial map F is an injective function, any two distinct points are mapped to different images. Most existing designs use degree 2 polynomials. Advantages of the MPKC mechanism include very short input, high efficiency, and a security foundation that is backed by an NP-hard problem. However, all designs of MPKC for encryption have failed to date, except designs proposed only in recent several years which require extensive security analysis in the future and have disadvantages including large or even huge key sizes with moderate practical security, weak scalability, and lack of theoretical proof of security.

For purpose of clarity in describing the present invention and as well understood in the art of cryptography, the term “trapdoor” is related to the term “trapdoor function” and is distinguished from the term “backdoor”, as follows. A backdoor is a mechanism added to a cryptographic algorithm such as a key pair generation algorithm or digital signing algorithm or to an operation system. A backdoor permits one or more unauthorized parties to somehow bypass or subvert the security of the system.

In contrast, a trapdoor function is a function that is easy to compute in one direction but difficult to compute in the opposite direction without special information, typically referred to as the “trapdoor”. Trapdoor functions are widely used in cryptography. Thus, a trapdoor function can be described as a function ƒ: D→R, such that, given x in D, ƒ(x) in R is easy to compute, but the inverse ƒ(x)⁻¹is difficult to compute without knowing the associated trapdoor.

Also, for purpose of this discussion, the term “degree” as used herein refers to the degree of a polynomial function and is the highest degree of its monomials (individual terms) with non-zero coefficients. The degree of a term is the sum of the exponents of the variables that appear in it, and thus is a non-negative integer. For example, the polynomial 4x²y³+5x−8, which can also be expressed as 4x²y²+5x−8x⁰y⁰has three terms. The first term has a degree of 5 (the sum of the powers 2 and 3), the second term has a degree of 1, and the last term has a degree of 0. Therefore, the polynomial has a degree of 5, which is the highest degree of any term.

The term “composition”, often symbolized with “s”, is understood in the art as referring to a mechanism that combines simple functions to build a more complicated function. Similar to the composition concept in mathematics, when implemented on a computer, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole composition.

Thus, for example, the functions ƒ: X→Y and g: Y→Z can be composed to yield a function which maps x in X to g(ƒ(x)) in Z. The resulting composite function is denoted g∘ƒ: X→Z, defined by (g∘ƒ)(x)=g(ƒ(x)), for all x in X Relative to the present invention, a composition g∘ƒ involving multivariate polynomial maps g, will have degree 4, when g, ƒ each has degree 2.

Trapdoor designs of Multivariate Public Key Cryptography (MPKC) are still mainly of degree 2, with a few of degree 3. As recognized by the present inventor and as would be understood in the art, this is due to three main reasons: 1) the key size normally becomes huge when the degree is higher than 2, 2) any higher degree polynomial can be reduced to degree 2 polynomials, and 3) the obvious composition F1∘F2 has been tried in some designs but found to be insecure and there lacks nontrivial approach for such composition. However, degree 2 remains a considerable restriction on the freedom of trapdoor designs, and thus restricts potential in this direction for encryption. The present inventor has recognized that a future direction would be to consider higher degrees, but still small, such as degrees 3 or 4.

As exemplarily shown in FIG. 3, the present invention provides a new trapdoor design 300 for multivariate encryption schemes which is of degree 4 and which embeds a novel trapdoor in the composition, called split-and-switch composition. With this trapdoor, the public polynomial is P: [Image Omitted] _qⁿ→_q²ⁿ

P


(
x
)

=

T
∘

[

F
-

G
2

∘

G
1

,

H
∘

G
1

]

∘

S


(
x
)

=

T


[

F


(

S


(
x
)

)

-

G
2



(

G
1



(

S


(
x
)

)

)

,

H


(

G
1



(

S


(
x
)

)

)

]

Here [Image Omitted] _qis the finite field of q elements, F: _qⁿ→_qⁿis an invertible polynomial of degree 4, G₁, G₂: F_qⁿ→_qⁿare random polynomials with degree 2, H: _qⁿ→_qⁿis an invertible polynomial with degree 2, S: _qⁿ→_qⁿand T: _q²ⁿ→_q²ⁿare two invertible linear transformation. There are a few classes of degree 4 invertible polynomials known in the art for F to choose, or F can be constructed by composing any two invertible polynomial maps of degree 2. There are a few well known, big enough, classes of invertible multivariate polynomial maps which are of degree 2 and can be inverted efficiently. Any two of them can form a degree 4 map by composition. It is noted that, because of the composition of two polynomial maps of degree 2, the public key will have degree 4.

This trapdoor design 300 has the following three special properties:

- It is expected that the central degree 4 polynomial map cannot be decomposed as the composite of two quadratic polynomial maps in general;
- Because G1, G2 are random, the two inner branches (F−G₂∘G₁, and H∘G₁) 302 are (mostly) random as well; and
- G1 is hidden by two quadratic maps G2 and H which have no relationship with each other, so the two branches have no linear relationship.

FIG. 4-6 show in detail the concepts underlying the split-and-switch composition utilized in the present invention.

Specifically, FIG. 4 exemplarily shows the starting point of the split-and-switch composition, namely an invertible multivariate polynomial map F of degree 4 which may be constructed as described above.

FIG. 5 shows the concept of the “split” aspect of the present invention. The polynomial F is split into two branches, F−G2(G1) as one branch and the composition G1∘G2 (e.g., G2(G1)) as the other branch. Here G1, G2 are random multivariate polynomial maps, degree 2, so that the composite G1∘G2 has degree 4.

FIG. 6 shows the concept of the “switch” aspect of the invention. Here, H is an invertible multivariate polynomial map of degree 2. Note that G2 in FIG. 5 is switched to H in FIG. 6. Also note that F−G2(G1), previously processed in FIG. 5 participates as part of this switch by reason that it retains the information used in the previous composition G1° G2. Thus, both F−G2(G1) and H ∘G1 in FIG. 6 are of degree 4.

FIG. 7 demonstrates encryption using split-and-switch composition by showing how a plaintext (x₁, . . . , x_n) 802 is provided as an input into the split-and-switch composition to generate a ciphertext 704 having two components y=(y₁, . . . , y_n), z=(z₁, . . . , z_n). Here, x_i, y_i, z_iare in [Image Omitted] _q. The two transfer functions of the two ciphertext components are:

y=F(x)−G2(G1(x)); and

z=H(G1(x)).

FIG. 8 and FIG. 9 demonstrate how decryption of the two ciphertext components can be achieved in the trapdoor, since H is invertible (i.e., H⁻¹) and:

G2(G1(x))=G2(H⁻¹(z));

F(x)=G2(H⁻¹(z))+y; and

x=F⁻¹(G2(H⁻¹(z))+y).

FIG. 10 accordingly shows encryption of a system using a trapdoor 1000 of the present invention with public key P 1004. Input plaintext (x1, . . . xn) 1002 is provided as input into public key P 1004 to provide encryption ciphertext 1006 (y1, . . . yn, z1, . . . , zn)=P(x1, . . . , xn). Here, components of the public key P are the coefficients of the polynomial P(x)=T(F(S(x))−G2(G1(S(x))), H(G1(S(x)))), having degree 4. The components of the private key are: the coefficients of F, G1, G2, H; and the invertible linear matrices S, T.

A small key size can result in the present invention by using a big field and small dimensions. For example, with q=2³², n=4, public key size is 4.4 KB.

FIG. 11 shows the decryption of the encrypted ciphertext 1006 of FIG. 10, using private key 1102 and the trapdoor 1000. Here components of the private key 1102 are: the coefficients of F, G1, G2, H; and the invertible linear matrices S, T. Here, the decryption processing is:

(y′,z′)=T⁻¹(y,z);

x′=F⁻¹(G2(H⁻¹(z′))+y′); and

x=S⁻¹(x′).

Further, as demonstrated in FIG. 12, the trapdoor mechanism of exemplary embodiments 1200 of the present invention, which provide exemplary encryption mechanisms using an original split-and-switch composition mechanism, is expected to provide a practical algorithm of degree>2 for MPKC. That is, as shown in FIG. 12, the present invention provides a degree−4 encryption/decryption mechanism in which the public key size 1202 is much smaller than conventional methods. The split-and-switch composition mechanism also provides stronger security 1204, stronger scalability 1206, and no decryption failure 1208.

It would also to be understood by one of ordinary skill that although this disclosure includes a detailed description on cloud computing, as follows, implementation of the teachings recited herein are not limited to a cloud computing environment. Rather, embodiments of the present invention are capable of being implemented in conjunction with any other type of computing environment now known or later developed.

Cloud computing is a model of service delivery for enabling convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, network bandwidth, servers, processing, memory, storage, applications, virtual machines, and services) that can be rapidly provisioned and released with minimal management effort or interaction with a provider of the service. This cloud model may include at least five characteristics, at least three service models, and at least four deployment models.

Characteristics are as follows:

On-demand self-service: a cloud consumer can unilaterally provision computing capabilities, such as server time and network storage, as needed automatically without requiring human interaction with the service's provider.

Broad network access: capabilities are available over a network and accessed through standard mechanisms that promote use by heterogeneous thin or thick client platforms (e.g., mobile phones, laptops, and PDAs).

Resource pooling: the provider's computing resources are pooled to serve multiple consumers using a multi-tenant model, with different physical and virtual resources dynamically assigned and reassigned according to demand. There is a sense of location independence in that the consumer generally has no control or knowledge over the exact location of the provided resources but may be able to specify location at a higher level of abstraction (e.g., country, state, or datacenter).

Rapid elasticity: capabilities can be rapidly and elastically provisioned, in some cases automatically, to quickly scale out and rapidly released to quickly scale in. To the consumer, the capabilities available for provisioning often appear to be unlimited and can be purchased in any quantity at any time.

Measured service: cloud systems automatically control and optimize resource use by leveraging a metering capability at some level of abstraction appropriate to the type of service (e.g., storage, processing, bandwidth, and active user accounts). Resource usage can be monitored, controlled, and reported, providing transparency for both the provider and consumer of the utilized service.

Service Models are as follows:

Software as a Service (SaaS): the capability provided to the consumer is to use the provider's applications running on a cloud infrastructure. The applications are accessible from various client devices through a thin client interface such as a web browser (e.g., web-based e-mail). The consumer does not manage or control the underlying cloud infrastructure including network, servers, operating systems, storage, or even individual application capabilities, with the possible exception of limited user-specific application configuration settings.

Platform as a Service (PaaS): the capability provided to the consumer is to deploy onto the cloud infrastructure consumer-created or acquired applications created using programming languages and tools supported by the provider. The consumer does not manage or control the underlying cloud infrastructure including networks, servers, operating systems, or storage, but has control over the deployed applications and possibly application hosting environment configurations.

Infrastructure as a Service (IaaS): the capability provided to the consumer is to provision processing, storage, networks, and other fundamental computing resources where the consumer is able to deploy and run arbitrary software, which can include operating systems and applications. The consumer does not manage or control the underlying cloud infrastructure but has control over operating systems, storage, deployed applications, and possibly limited control of select networking components (e.g., host firewalls).

Deployment Models are as follows:

Private cloud: the cloud infrastructure is operated solely for an organization. It may be managed by the organization or a third party and may exist on-premises or off-premises.

Community cloud: the cloud infrastructure is shared by several organizations and supports a specific community that has shared concerns (e.g., mission, security requirements, policy, and compliance considerations). It may be managed by the organizations or a third party and may exist on-premises or off-premises.

Public cloud: the cloud infrastructure is made available to the general public or a large industry group and is owned by an organization selling cloud services.

Hybrid cloud: the cloud infrastructure is a composition of two or more clouds (private, community, or public) that remain unique entities but are bound together by standardized or proprietary technology that enables data and application portability (e.g., cloud bursting for load-balancing between clouds).

A cloud computing environment is service oriented with a focus on statelessness, low coupling, modularity, and semantic interoperability. At the heart of cloud computing is an infrastructure that includes a network of interconnected nodes.

Referring now to FIG. 13, illustrative cloud computing environment 50 is depicted. As shown, cloud computing environment 50 includes one or more cloud computing nodes 10 with which local computing devices used by cloud consumers, such as, for example, personal digital assistant (PDA) or cellular telephone 54A, desktop computer 54B, laptop computer 54C, and/or automobile computer system 54N may communicate. Nodes 10 may communicate with one another. They may be grouped (not shown) physically or virtually, in one or more networks, such as Private, Community, Public, or Hybrid clouds as described hereinabove, or a combination thereof. This allows cloud computing environment 50 to offer infrastructure, platforms and/or software as services for which a cloud consumer does not need to maintain resources on a local computing device. It is understood that the types of computing devices 54A-N shown in FIG. 13 are intended to be illustrative only and that computing nodes 10 and cloud computing environment 50 can communicate with any type of computerized device over any type of network and/or network addressable connection (e.g., using a web browser).

Referring now to FIG. 14, a set of functional abstraction layers provided by cloud computing environment 50 (FIG. 13) is shown. It should be understood in advance that the components, layers, and functions shown in FIG. 14 are intended to be illustrative only and embodiments of the invention are not limited thereto. As depicted, the following layers and corresponding functions are provided:

Hardware and software layer 60 includes hardware and software components. Examples of hardware components include: mainframes 61; RISC (Reduced Instruction Set Computer) architecture based servers 62; servers 63; blade servers 64; storage devices 65; and networks and networking components 66. In some embodiments, software components include network application server software 67 and database software 68.

Virtualization layer 70 provides an abstraction layer from which the following examples of virtual entities may be provided: virtual servers 71; virtual storage 72; virtual networks 73, including virtual private networks; virtual applications and operating systems 74; and virtual clients 75.

In one example, management layer 80 may provide the functions described below. Resource provisioning 81 provides dynamic procurement of computing resources and other resources that are utilized to perform tasks within the cloud computing environment. Metering and Pricing 82 provide cost tracking as resources are utilized within the cloud computing environment, and billing or invoicing for consumption of these resources. In one example, these resources may include application software licenses. Security provides identity verification for cloud consumers and tasks, as well as protection for data and other resources. User portal 83 provides access to the cloud computing environment for consumers and system administrators. Service level management 84 provides cloud computing resource allocation and management such that required service levels are met. Service Level Agreement (SLA) planning and fulfillment 85 provide pre-arrangement for, and procurement of, cloud computing resources for which a future requirement is anticipated in accordance with an SLA.

Workloads layer 90 provides examples of functionality for which the cloud computing environment may be utilized. Examples of workloads and functions which may be provided from this layer include: mapping and navigation 91; software development and lifecycle management 92; virtual classroom education delivery 93; data analytics processing 94; transaction processing 95; and trapdoor 96 of the present invention, including associated functions to implement the trapdoor as described herein.

However, it should be clear to one of ordinary skill in the art that the concepts of the present invention can be implemented without using a cloud service. For example, the trapdoor and associated mechanisms of the present invention, as described herein, could be stored on a server located on the Internet such that users would access the server to receive a public key and/or transmit a plaintext message to the server for encryption, possibly using a first secure channel. The server would then encrypt the plaintext message and transmit it to a second user designated by the first user. The server would then also transmit, using a third secure channel, a private key to the second user who has received the encrypted plaintext message that was encrypted using the public key. The server would then use a third secure channel to receive from the second user the private key and the received encrypted plaintext message and would then decrypt the received encrypted plaintext message, using the private key, and then send the decrypted version of the plaintext to the second user, using a fourth secure channel.

The present invention provides enhanced security for asymmetrical cryptography even in view of potential attacks from upcoming quantum computing capabilities, as follows.

First, there are two key points in the design of the public polynomial

P(x)=T[F(S(x))−G₂(G₁(S(x))),H(G₁(S(x)))].

A first key point is that, because both G₁, G₂are random, each of the two inner branches F-G₂(G₁) and H(G₁), also referred herein as components, is random as well. A second key point is that, G₁is hidden by two quadratic maps G₂and H, which have no relationship with each other. So these two branches have no linear relationship, and thus no linear transformation can remove any part of them.

Second, the design of the present invention has several layers of protection that are interrelated, as follows.

- A first layer of protection is that the secret T (which, it is noted, is a component of the private key) hides the composition structure of the two branches (F(S(x))−G₂(G₁(S(x))), H(G₁(S(x)))).
- A second layer of protection is that the two secret quadratic maps H, G₁are hidden in the composite H(G₁).
- A third layer of protection is that the secret random quadratic map G₂and the secret degree−4 map F are hidden in F-G₂(G₁).
- A fourth layer of protection is that the secret S further hides the structure of the two inner branches (F-G₂(G₁), H(G₁)).

Existing conventional attacking methods are not applicable against the present invention, as follows:

- Direct attacks (especially Groebner-based attacks) are not applicable because, due to the two key points identified above, solving P(x)=y directly is the same as solving a random polynomial equation system of degree at least 2, which is NP-hard.
- Linearization attacks are not applicable against the present invention since there is no linear relationship between x and y because G₁, G₂are random quadratic maps.
- Rank attacks are not applicable because the notion of rank is only applicable to quadratic maps, but in the present invention P is of degree 4 and there is not such rank.
- Differential attacks are also not applicable because the differential of a quadratic map is a linear map and may have some differential invariants in some cases, but such invariants can be easily destroyed by adding enough randomness. However, because P(x) is of degree 4 and its differential is of degree 3, which cannot be reduced further by applying the differential again, such differential attacks do not apply against the present invention. In addition, the two random quadratic maps G1, G2 would destroy possible differential invariants, if any.

Accordingly, in view of these security enhancements, again, the present invention notes that existing designs of MPKC for encryption focus on degree two only, thereby restricting their potential in resisting decryption failure by quantum computing. As previously explained, the crypto community has been actively searching since the early 1990's for quantum-secure cryptographic algorithms, and the present invention provides a solution for this ongoing problem in cryptography.

Therefore, although the present invention is arguably based on one or more abstract concepts, the description herein clearly describes that these underlying concepts define a combination of elements that provide a solution to a technical problem in security for encryption/decryption, thereby providing a specific solution to a real-world problem. By defining a specific method for an asymmetric cryptographic system based on degree 4, the claims below clearly describe more than a generic implementation of the abstract idea of an asymmetric cryptographic system on a generic computer. By providing a new method for asymmetrical encryption based on the specific method of split-and-switch composition, the present invention utilizes these underlying concepts as defining at least one inventive concept that distinguishes from the abstract idea of asymmetrical cryptography. To the present inventor's knowledge, this split-and-switch composition concept has never been used in any application, let alone in an asymmetrical cryptographic system.

The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.