Polymorphic Computing

Introduction

Traditional polymorphic computing [1] achieves adaptability by dynamically modifying the computing architecture in time and space to meet varying workload requirements. The current work introduces an inverse paradigm: preserving a constant architecture while substituting isomorphic operations at the implementation layer to induce continuous variation in the physical realization. This new framework is applied to cryptography, where maintaining architectural invariance ensures that formal security guarantees hold across every transformed execution instance.

This article introduces a computational implementation that allows functions to transform while adhering to stringent architectural requirements. The central claim is simple: computer arithmetic contains hidden assumptions that unnecessarily constrain computational design. Once these assumptions are removed, entire families of alternative computational structures become available.

The concepts of computational polymorphism are hidden by the limitations of binary and n-state switches, of practical desires and of interpreting computational operations in the context of mathematical meaning.

The article uses binary and n-state multi-element carry ripple addition as examples of how to apply polymorphic computational transformations while preserving an operational architecture.

Is it useful? For years, cybersecurity experts were warned that quantum computers would eventually threaten today's cryptographic infrastructure. It now seems the QC threat is in the future and recently, attention has shifted toward AI-driven attacks, autonomous agents capable of reverse engineering software, discovering vulnerabilities, using dispersed attack methods, sharing and combining information and adapting faster than human defenders [8].

Although these threats of AI and QC appear very different, they share a common assumption: both attack a computational target whose internal structure is fixed.

Architecture and Implementation

Part of the theoretical basis finds its roots in the Architecture / Implementation / Realization framework developed by Prof. Dr. Gerrit “Gerry” Blaauw, one of the three architects of the IBM System/360.

Dr. Blaauw differentiates in computer machine design 1) the architecture, what the system designer sees as functionality; 2) the implementation, which is in fact the logic design of gates that enables the architecture and 3) the realization that discloses the actual physical circuits. In modern computer design, almost no one (except the silicon engineers) is involved with the physics. The implementation is mostly designed in software (Blaauw uses APL). But the underlying idea is that when an APL program runs, it is a complete computer machine.

Blaauw shows in his book Computer System Design, for instance, up to 10 different implementations of adders that compute a sum. The result of these different implementations are all the same sum under the same architecture [2].

Polymorphic computing applies the Blaauw framework with a twist: using a same architecture (or dataflow), each implementation is designed to create a different output.

Is it a trick? At first sight computational transformations may look like some obscure trick. They are not. This article uses simple binary and non-binary examples to arrive at deterministic polymorphic transformations and their application to cyber security, specifically to cryptography.

The Hidden Rigidity of Modern Computing

Current machine computing is binary and assumes fixed computational primitives. While computers and especially Artificial Intelligence (AI) like Large Language Models (LLMs) are popularly characterized as thinking or performing almost human tasks, they are in essence binary switching machines. And the underlying computational structures remain largely invariant. Attackers benefit from that stability.

A fundamental part of a computer or computing machine is a 2-operand binary function, usually called a gate or switching gate or logic gate. The gate may be illustrated by a block having two (binary) inputs a and b and a (binary) output c as in figure 1.

There are several ways to represent the above switch in notation, Herein the notation: c → sc(a,b) is used.

The function characteristics are defined by ‘sc.’ All elements a, b and c are binary and represented as drawn from {0,1}.

The performance of ‘sc’ is commonly represented as a binary (2 by 2) switching table. Because the switching table has 4 positions, each position able to be 0 or 1, there are maximum of 16 binary different 2-operand switching table. These tables are well known and have their own name. For instance, XOR, AND and NAND are well known.

The following figure provides the switching table for the binary XOR function. The indicators a and b show that a determines a row index and b the column index. A particular aspect of switching algebra is that indices of the tables are the same as the input value. So, a can be 0 or 1, and thus XOR(0,0)=0, XOR(0,1)=1, XOR(1,0)=1 and XOR(1,1)=0.

One is reminded that the above is a matter of notation. But one can already notice some important properties of the function XOR. The function is outcome balanced and for all possible inputs a and b the outputs are equally 0 and 1 (appearing twice). Furthermore, the XOR is commutative or XOR(a,b)=XOR(b,a). And another important property that is not directly apparent from the table, is that XOR is associative or that the order of inputs using two XOR functions doesn’t matter to the output. Finally, the XOR function is an involution, or self inverting. When one has c=XOR(a,b) then a=XOR(c,b) and b=XOR(a,c).

An important property of the XOR gate in its switching model, is its similarity to the modulo-2 addition. The XOR gate doesn’t process numbers. It processes signals, like voltages, which may be referred to as Low (close to 0 Volt output in CMOS) and High (around 4.9 Volt output in CMOS). By detecting output voltages and representing it as a 0 or 1 on a display, it seems like the device is processing numbers.

A machine adder uses two functions for 2 numbers radix-2: a residue and a carry. It looks a bit in its basic form how addition is learned in school. It is provided un diagram below in Figure 3.

The addition above is created by 2 words of 4 elements in radix-n or in this case binary (modulo-2) format. The addition consists of a first word of 4 bits, called the augend [a1 a2 a3 a4] with added to it an addend, also of 4 bits [b1 b2 b3 b4]. Because the word consists of 4 bits, it may look like [0 1 0 1] representing the decimal value 5, for instance.

The above diagram represents what is generally called a carry ripple adder. It consists of several, identical steps, of determining a residue word and a carry word.

The residue operation is the XOR: it executes for instance residue r14=XOR(a4,b4). It is known that the XOR switching table is similar to a modulo-2 operation.

The carry gate in the adder needs to meet the carry requirement in addition of binary elements. Clear 0+0 provides no carry (or carry 0) and neither do 0+1 and 1+0. However, 1 + 1 = 0 in mod-2 and generates a carry 1 to the next position. This is exemplified by the AND gate, of which the switching table is provided below.

For completing a radix-2 addition of words of multiple bits, as shown in Figure 3, one continues until no further carry is generator. The sum is the set of residues [r41 r32 r23 r14]. If so desired one may also provide a carry-out.

The Reversing of the Addition

In computer arithmetic, the reverse of the radix-n addition is the radix-n subtraction. For radix-2 that means a radix-2 subtraction. This is of course equivalent to the XOR table. Instead of a carry a borrow digit (0 or 1) is required. The transitional digit 0 or 1 is borrowed from the higher position. It happens differently from the carry function. The following subtractions do not require a borrow: 0-0, 1-0 and 1-1. But, 0-1 requires borrowing a 1 from the higher position. The binary borrowing function is provided in the following table.

Because, a indicates the row index and b the column index, one may call this the ‘a<b’ gate. By using XOR and ‘a<b’ in the process illustrated by Figure 3, and use the previous sum as new augend and the same addend, one recovers the original augend by the operation.

Traditionally, the true subtraction as proved above, is seldom used. One prefers the complement-2 approach for subtraction, as this applies the same implementation, preceded by an inversion.

The basic radix-2 addition/subtraction as explained above, allows for further investigation. One question one can ask is: are there other transitional/carry binary functions that in combination with the XOR residue function, creates in the structure of Figure 3 a sum that may be reversed.

Figure 6 shows two transition/carry functions (the b’ or inverse of b and NAND function) that can each replace the classical AND as carry function.

There are actually 8 different transition functions that fit the architecture of Figure 3 with XOR as residue function. The borrow function is the transposition of the rows of the corresponding carry function.

As a result, one can create a reversible radix-2 addition-like operation that has different outcomes in what one would call a sum and a difference.

The Residue Function and Polymorphic Computing

One may also change the residue function. In a radix-2 system, the one of 16 binary 2-operand function that will work is the EQUAL function, of which the switching table is provided in Figure 7.

There are several (actually 8) different carry-type functions that may be used in the structure of Figure 3 and have a corresponding borrow-like function that make the operation reversible. Figure 8 shows 3 functions that enable the reversible structure of Figure 3 in combination with the EQUAL function.

The name designation and polymorphic computing: The above example with the EQUAL function, directly illustrates the problem of naming. The XOR function in combination with the AND generates what is generally called a sum. But there are different logic functions or implementations that, when used in the ripple transition structure of Figure 3, create a result that may also be called a sum.

In fact, the above illustrates a simple polymorphic computational implementation, wherein the architecture is preserved, including the reversibility. However, most implementations provide different outcomes or sums. Nothing mysterious or theoretically invalid takes place here.

Moving from Binary (2-State) to n-State (n>2)

The actual polymorphic computation space for binary implementations is fairly small. This changes dramatically when one considers n-state implementations [3].

For illustrative purposes, the n=4 state will be considered. The matter explained herein, is not limited to n=4 and may be applied to any useful size of n. That is for n=256 in AES-GCM and ChaCha20 or 512 or 2048 bit numbers in RSA and Diffie-Hellman, and 32 bit or 64 bit words in ECC.

Staying with radix-n addition, the following provides the switching tables for standard radix-4 addition, being the residue function, which is the modulo-4 addition and the carry function, sum>=4. One is reminded that a carry function, sum>=4, is defined by traditional number theory, and not by computational restraints. Figure 9 shows the classical 4-state residue and carry tables.

One may apply the above 4-state function in the ripple carry structure of Figure 3 and realize a reversible radix-4 addition. The radix-4 addition has a corresponding subtraction, with the mod-4 subtraction and a corresponding borrow function as the reversing operation. The relevant 4-state tables are provided in Figure 10.

This radix-4 addition operation has a set of 32 different carry functions in combination with the modulo-4 addition that provides a reversible 4-state radix-4 addition in accordance with the structure of Figure 3. There is 1 trivial solution for the carry being all 0. One example of a different 4-state carry function that in combination with mod-4 addition provides a reversible radix-4 addition is shown in Figure 11.

Surprisingly, in the radix-n addition, one is not limited to using transitional elements 0 and 1, but one may use any of the n-state elements, as long the initial structure is preserved. An example of a transformed transitional (=carry) element is provided in Figure 12.

This significantly expands the transform space of the carry or transitional function. One can intuitively see that for n=256 or greater, this unlocks a significant transformation space.

Addition over GF(n=2^k) with Carry

Other transformations are available that enable polymorphic computation. An example of that is addition over GF(2^k) with carry. Addition over GF(2^k) is extensively used in cryptography. The base computational function herein is the XOR. This makes the addition over GF(2^k) a self reversing function or an involution. It also is an addition that is carry-less. Using n=4 as example, one can change this carry-less addition into a carry propagating or transitional element propagating operation.

The focus herein is to show that polymorphic computation is possible and available. For details one is referred to the references below.

Figure 13 shows the 4-state tables for the addition sc4 over GF(4) and a transition 4-state function car4gf that applied in the ripple carry structure of Figure 3 creates a reversible operation. Also, here are different 4-state transition operations within the architecture of Figure 3.

Other Transformations and The Finite Lab Transform (FLT)

Other transformations of computational operations have been created. The above ripple carry structure has been used to illustrate that within a defined architecture as defined by Figure 3, one can find different computational implementations that fit the architecture, but will create entire different outcomes. This of course Is the basis for polymorphic computation.

One may observe several issues in the above in cryptographic application:

• The relatively small base variations in the context of cryptography. For n=256 these variations may run in the millions. For cryptographic attacks these are not very large numbers;
• Even though there may be millions of variations, finding these variations may take significant processing time, especially for n greater than 16 (n>16), the searching becomes prohibitively slow;
• Current Public Key Infrastructure (PKI) allows 2 parties (computers) which don’t know each other, to create a secure common keyword; and
• Repeat use of a variation in function is a risk for security, as it starts to have the same static nature of the unchanged base function.

The Finite Lab Transform or FLT, applies n-state reversible inverters to transform a computational function. It preserves the meta-properties or the architecture of the computation process [4].

1. The FLT solution space is determined by the size of the n-state reversible inverter. There are factorial of n (n!) different n-state inverters, including identity. In certain cases the FLT with different n-state provides identical transformations. Still for n=256, the FLT can generate over 10⁴⁰⁰ different additions over GF(256), which renders the chance for duplicates or same results insignificant;
2. The FLT is a deterministic operation. The base operation in combination with a specific n-state inverter provides a guaranteed deterministic outcome;
3. A novel procedure applies a secure PKI keyword, like a 256-bit Kyber keyword, into a reversible n-state inverter. Exchange of inverters is thus reduced to exchange of secure keywords; and
4. A generated secure reversible n-state inverter generates it own child inverter and does so in repeat steps, wherein each step generates a new n-state inverter. This creates a dynamic and agile polymorphic process, wherein one or more functions are updated based on pre-agreed conditions. For instance, one may transform an addition over GF(256), as used in AddRoundKey() in AES, per round, per block, per message, per session, per packet, per location, per user, per time, per device, etc.

Conclusion

The above shows that polymorphic computation, as a transformation of logic functions, is demonstrated and enabled [6].

It is entirely in line with Dr. Blaauw’s framework [7]. Dr. Blaauw developed his framework to get compatibility and complex design under control. Different implementations fitted in a well defined architecture will in that framework create the same output in machines designed under a common architecture as demonstrated by the history of the IBM System/360 of which Dr. Blaauw was one of three co-architects.

The twist being that above it has been shown that a different outcome may be forced for each different implementation. And the implementation is not static, but a dynamic operation that may be changed in real-time.

One prominent effort that similarly relies on runtime modifications was DARPA’s Moving Target Defense (MTD) [9], which dynamically alters system configurations—such as memory layouts and execution environments—to prevent attackers from relying on static reconnaissance, with current MTD-based cybersecurity products surveyed by Gartner [10].

Unlike conventional MTD techniques that modify external system parameters or require specialized hardware wrappers, the Blaauw-framework-based approach confines these modifications strictly to the software implementation via functionally equivalent logic substitutions, leaving the provably secure architecture completely untouched.

Function or Switch or Logic-Gate?

A gate or logic gate is an elementary physical device or circuit in digital microelectronics that performs a logical operation on one or more binary inputs (as high/low voltages, or represented as 1 and 0) to produce a single binary output.

The physical device is the actual circuit that inputs and outputs voltages. One may call this also a switch, which switches between states. A function describes as a model how the device reacts in output to inputs.

In computer technology one can program an n-state switch in a program and execute the program. When the physical performance matches the n-state model, an actual n-state switch has been realized. This is a direct consequence of the Blaauw framework. The logic implementation is instantiated in a physical realization.

Patents

The application of polymorphic computation has been disclosed in a portfolio of US patents. The patents predominantly address specific cryptographic applications of the underlying concepts, rather than polymorphic computation as a general computational principle.

The patents are in force in the United States. Operational use of inventions falling within the scope of their claims requires authorization from the Assignee. This includes, where covered by the respective claims, encryption, data authentication, keyword generation, and the transmission or storage of data.

The Assignee expressly permits the use of the claimed aspects of these inventions for non-operational trials, evaluation, testing, education and research, only installed on a single machine. No multi-machine networked implementations are permitted without express written permission [5].

The Assignee provides express permission to apply the claimed aspects for non-operational trials, testing, education and research on a single computing device.

The IP Portfolio includes: US Patent No. US 12,476,789; US 12,143,468; US 11,093,213; 12,056,549; US 11,336,425; US 12,665,744; US 12,609,809; US 12,425,189 and pending cases.