Redactable blockchains and polynomial equations

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

arXiv:2608.19401v1 [cs.CR] 19 Aug 2026

ALEXANDER DEMIN, ALEXEY OVCHINNIKOV, AND VLADIMIR SHPILRAIN Abstract. We develop new tools for constructing redactable authenticated data structures with post-quantum security. In our construction, inverting the proposed one-way function means solving a polynomial equation (or a system of polynomial equations) in more than one variable. This is presently considered quantum-safe, i.e., there is no known quantum algorithm that could solve this problem efficiently if parameters are chosen wisely.

1. Introduction A crucial part of most artificial intelligence systems is an adaptive network of electronic devices. Perhaps the most popular and quickly proliferating class of such networks is the Internet of Things. The Internet of Things (IoT) represents one of the most significant technologies of this century. It is a natural evolution of the Internet (of computers) to embedded and cyberphysical systems, “things” that, while not obviously computers themselves, nevertheless have computers inside them. IoT is experiencing exponential growth in research and industry, but it still suffers from privacy and security vulnerabilities. Conventional security and privacy approaches tend to be inapplicable for IoT, mainly due to its decentralized topology and the resource-constraints of the majority of its devices. Blockchains have been recently used to provide security and privacy in peer-to-peer networks and artificial intelligence systems such as, for example, smart cars, smart homes, smart cities, etc. A blockchain can be either public or private. A typical example of a public blockchain is bitcoin. In contrast, a private blockchain network is where the participants are known and trusted: for example, an industry group, or a military unit, or in fact any private network, big or small. Originally, blockchains were created to support the bitcoin network, which is public. Immutability for such a network is crucial. More recently, with the ideas of artificial intelligence gaining momentum, private networks have taken the center stage, and this creates new challenges. In particular, it is desirable, while preserving the tampering detection property, to allow someone with higher privileged access like a system administrator or another authority to be able to change the data or erase (“forget”) it. A blockchain that can be changed like this is called redactable. The need for a blockchain (even a public one!) to be redactable is well explained by the following quote from The New York Times [6]: “That permanence has been vital in building trust in the decentralized currencies, which are used by millions of people. But it could severely limit blockchain’s usefulness in other areas of financial services relied on by billions of people. By clashing with new privacy laws like the “right to Research of the second and third authors was partially supported by a CUNY Institutional Research Grant Award. 1

2

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

be forgotten” and by making it nearly impossible to resolve human error and mischief efficiently, the blockchain’s immutability could end up being its own worst enemy.” Eliminating redundancies and deleting outdated records is especially vital for networks (such as IoT, for instance) of computationally limited devices. The present paper proposes a new secure, private, and lightweight architecture for redactable blockchains based on multivariable polynomial equations. Earlier constructions (e.g. [1, 5, 11]) of redactable blockchains were either not practical, or not quantum-safe, or both. While preserving the simplicity and efficiency of the construction in [11], we develop new tools for constructing redactable authenticated data structures with post-quantum security. One possible way to avoid quantum attacks based on solving the hidden subgroup problem (including the attacks in [15]) is not to use one-way functions that utilize, in an essential way, one or another (semi)group structure. In our construction, inverting the proposed one-way function means solving a polynomial equation (or a system of polynomial equations) in more than one variable. This is presently considered quantumsafe, i.e., there is no known quantum algorithm that could solve this problem efficiently if parameters are chosen wisely. 2. Background Our approach in this proposal is focused on private blockchains. It is quite different from [1, 5, 14] and other methods and is transparent and easily implementable. On a high level, our method bears some similarity with the construction in [11] that was based on the computational hardness of the RSA problem and therefore was not quantumsafe, whereas in this paper we aim at quantum-safe constructions. Still, here we first briefly describe the construction from [11] to give a background and put things in perspective. There are several possible structures of a redactable blockchain. Our general method should work with any known structure, but to make the exposition as clear as possible we choose a simple structure as follows. Each block Bi will have 3 parts: a permanent prefix Pi , the actual content Ci , and a redactable suffix Xi . There is also a function (e.g. a hash function) hi = H(Pi , Ci ), where H is a public (hash) function, and a public one-way function F such that F (hi , Xi ) = Pi+1 . To make such a blockchain redactable, a central authority should have a private key that would allow for replacing Ci with an arbitrary Ci′ of his/her choice, so that upon a suitable selection of the new suffix Xi′ , the equality F (h′i , Xi′ ) = Pi+1 would still hold. An RSA-based construction. Now we briefly sketch the construction from [11]. Public information: • a large integer n, which is a product of two large primes • a hash function H, e.g. SHA-512. (We emphasize again that our method can be used with any reasonable hash function, so the reader can replace SHA-512 here with his/her favorite hash function.) Private information: • prime factors of n = pq. These p and q should be safe primes, as in modern implementations of RSA. A safe prime is of the form 2r + 1, where r is another prime [9].

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

3

Block structure. In each block Bi , there is a prefix Pi , the actual content Ci (e.g. a transaction description), and a suffix Xi , which is a nonzero integer modulo n. We also want Xi not to have order 2, i.e., Xi2 ̸= 1 (mod n). This will ensure that Xi does not have a small order since p and q are safe primes, so if the order of an element of the multiplicative group Z∗pq is not 2, then it is large. Thus, whoever builds a block Bi , selects Xi at random on integers between 1 and n − 1 and then checks if Xi2 ̸= 1 (mod n). If Xi2 = 1 (mod n), random selection of Xi is repeated. Once a proper Xi is selected, a public hash function H (e. g. SHA-512) is applied to concatenation of Pi and Ci to produce hi = H(Pi , Ci ), and hi is then converted to an integer di modulo n. The prefix Pi+1 of the next block is then computed as Pi+1 = (Xi )di (mod n). Private redactability. Now suppose the central authority, Alice, who is in possession of the private key, wants to change the content of a block Bi from Ci to Ci′ but does not want to change any other block. Then Alice computes the hash h′i = H(Pi , Ci′ ) and converts it to an integer d′i modulo n. The number d′i should be relatively prime to ϕ(n), the Euler function of n. If it is not, then Alice should use a padding to have d′i relatively prime to ϕ(n). Once e′i (mod n). it is, Alice finds the inverse e′i of d′i modulo ϕ(n). Then she computes Xi′ = Pi+1 The integrity check now gives:  ′ d′i ei ′ d′i (Xi ) = Pi+1 = Pi+1 (mod n) because e′i d′i = 1 (mod ϕ(n)) and (Pi+1 )ϕ(n) = 1 (mod n). Public immutability. As can be seen from the “Block structure” paragraph, a party who would like to change the content of a single block, must essentially solve the RSA problem: recover X from n, X d (mod n), and d, where d is relatively prime to ϕ(n). This is considered computationally infeasible for an appropriate choice of n and a random d, 0 < d < n. 3. Basic construction Now we describe an integrity condition for blockchains that would involve quantum-safe one-way functions with trapdoor. In this section, to illustrate the idea, we first describe a basic version of the construction. The basic version is susceptible to several attacks. Later in the text (Section 5), we propose a construction that is resilient to those attacks. Recall that Pi denotes the prefix of the block Bi . Prefixes are immutable, i.e., they cannot be changed by anybody. We do not go into details here on how this immutability can be arranged; literature on blockchains is awash with that. Then, Ci denotes the content of the block Bi ; this is the crucial part of a block where meaningful information is stored. Finally, Si denotes the suffix of the block Bi ; this is an auxiliary part that makes it possible for a central authority to change the content Ci without violating the integrity condition. Let t be a new variable. We are assuming that all Ci , Si , and Pi are univariate polynomials in t of degree d with coefficients in Zn for a fixed large prime n. We assume that d < n. Needless to say, any content Ci can be encoded this way if n is large enough, say several hundred bits. A crucial part of any blockchain (redactable or not) is the integrity condition. In our case, the integrity condition is of the following form: F (Pi , Ci , Si ) = Pi+1 (mod (t − t0 ) · · · (t − td ))

4

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

where F is a public polynomial and t0 , . . . , td are public distinct integers modulo n. A trapdoor (i.e., a secret known only to a central authority) is a presentation of the polynomial F in the form F (x, y, z) = G(x, H(x, y) − z), where G(x, y) and H(x, y) are private two-variable polynomials. To change the content Ci to Ci′ while preserving the integrity condition, it is sufficient to find a new suffix Si′ such that H(Pi , Ci ) − Si = H(Pi , Ci′ ) − Si′ (mod (t − t0 ) · · · (t − td )). Solving this for Si′ gives Si′ = H(Pi , Ci′ ) − H(Pi , Ci ) + Si (mod (t − t0 ) · · · (t − td )). Thus, whoever knows the function H can change Ci to any other content Ci′ without violating the integrity condition. Note that any Ĝ, Ĥ that satisfy the integrity condition can be used for this purpose (with Ĝ, Ĥ not necessarily the same as the secret G, H, respectively). 4. Possible attacks on the basic construction Now let us look at what an unauthorized party can try to do to modify Ci to some Ci′ . There are several possibilities: Attack 1. Solve the polynomial equation F (Pi , Ci′ , X) = Pi+1 (mod (t − t0 ) · · · (t − td )) for X, where X is a polynomial in t of degree d with unknown coefficients from Zn . Then this X can be a new suffix of the block Bi . This gives rise to a square polynomial system in the coefficients of X. Solving such a system is a hard problem in general, but perhaps for some special polynomials it may turn out to be easy. Attack 2. Recover the secret polynomial H(x, y). The intruder can attempt to present H(x, y) as a sum of monomials (with the degree bounded by the degree of the polynomial F ) with unknown coefficients. Then the equation F (Pi , Ci′ , Si′ ) = Pi+1 (mod (t − t0 ) · · · (t−td )) would translate into a system of polynomial equations in these unknown coefficients. These equations are not linear, so solving them (even over Zp for a prime p) requires Gröbner basis techniques as in [7, 4]. Attack 3. Find a functional decomposition of F (x, y, z). The algorithm by Kozen and Landau [13] is efficient at finding compositions of univariate polynomials over commutative rings. The algorithm can be used in our setting by considering the multivariate polynomial F (x, y, z) as a univariate polynomial in one of the variables x, y, z. An alternative approach [8], which has polynomial complexity in case the degrees are fixed, is to find a multivariate function decomposition of F (x, y, z). In our case, one could construct the secret G(x, y), H(x, y) of arbitrarily large degrees, hence this algorithm would likely be inefficient. Attack 4. If an attacker can observe the same block before and after it was changed, then (s)he can be in possession of the following equation: Si −Si′ = H(Pi , Ci )−H(Pi , Ci′ ) (mod (t− t0 ) · · · (t − td )). Here Si , Si′ , Pi , Ci , Ci′ are all known to the attacker. Then, since the bound on the degree of H(x, y) is known to the public, the above equation translates into a system of linear equations in the coefficients of H(x, y). Upon accumulating sufficiently many equations as above (after observing sufficiently many replacements of Ci and Si by different Ci′ and Si′ , respectively), the attacker can find all the coefficients of H(x, y).

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

5

As the experiments in Section 7 show, the basic construction from Section 3 is susceptible to each of these attacks, although the following modification of the basic construction foils Attack 4. Specifically, the function H(x, y) will appear nonlinearly in the trapdoor presentation of F (x, y, z), as follows: F (x, y, z) = G(x, R(H(x, y), z)), where R(H, z) is a private function nonlinear in the first argument and linear in the second one. We also require that R(H, z) contains a term depending only on H and a term involving both H and z. As a simple example, take R(H, z) = H + H 2 z + z, which yields F (x, y, z) = G(x, H(x, y) + (H(x, y))2 z + z). Then to change the content Ci of a block #i to Ci′ while preserving the integrity condition F (Pi , Ci , Si ) = Pi+1 (mod (t − t0 ) · · · (t − td )), it is sufficient for a legitimate authority to find a new suffix Si′ such that H(Pi , Ci ) − H(Pi , Ci′ ) + (H(Pi , Ci )2 + 1)Si = Si′ (H(Pi , Ci′ )2 + 1) (mod (t − t0 ) · · · (t − td )) Since the legitimate authority knows in this equation everything except Si′ , this equation translates for them into a system of linear equations in the coefficients of Si′ , which has a unique solution whenever H(Pi , Ci′ )2 + 1 and (t − t0 ) · · · (t − td ) are coprime, and is efficiently solvable. (Recall that Si′ is a polynomial of bounded degree.) For this choice of R(H, z), coprimality can be ensured by choosing n so that n = 3 (mod 4), since then −1 is not a square modulo n. At the same time, Attack 4 would yield a system of equations in the coefficients of H(x, y), but this system is no longer linear.

5. Advanced quantum-safe construction We now propose a construction (an integrity condition and a trapdoor) that is not vulnerable to previously mentioned attacks. Let F (x, y, z) be a three-variable polynomial with coefficients given by integers modulo n. Introduce new indeterminates Ā = (A0 , . . . , Ad ), and similarly for B̄, C̄, D̄. Let P̂i (t), Ĉi (t), Ŝi (t), P̂i+1 (t) be univariate polynomials of degree d defined as follows: P̂i (t) = A0 + . . . + td Ad , Ĉi (t) = B0 + . . . + td Bd , Ŝi (t) = C0 + . . . + td Cd , P̂i+1 (t) = D0 + . . . + td Dd . Note that if one specializes Ā, B̄, C̄, D̄ to some particular numbers, then P̂i (t), Ĉi (t), Ŝi (t), and P̂i+1 (t) become concrete prefix, content, and suffix, that is, Pi , Ci , Si , Pi+1 . Therefore, an integrity condition on Pi , Ci , Si , Pi+1 can be formulated as a condition (equation) on Ā, B̄, C̄, D̄.

6

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

The advanced integrity condition is a system of (fully expanded) polynomial equations in Ā, B̄, C̄, D̄: F (P̂i (t0 ), Ĉi (t0 ), Ŝi (t0 )) = P̂i+1 (t0 ), ... F (P̂i (td ), Ĉi (td ), Ŝi (td )) = P̂i+1 (td ), where t0 , . . . , td are private distinct integers modulo n. To verify the condition for some particular choice of Pi , Ci , Si , Pi+1 , one checks if the system obtained by substituting the coefficients in Ā, B̄, C̄, D̄ is consistent. Let us show how the public can find Pi+1 from Pi , Ci , Si . Consider the system of equations that defines the integrity condition; the system depends on Ā, B̄, C̄, D̄. Recall that D̄ are the coefficients of Pi+1 and note that the system is linear in D̄ by construction. Therefore, once Ā, B̄, C̄ are specialized to particular values, the values of D̄ can be obtained by solving a square linear system with d + 1 equations. As in the basic construction, a trapdoor is a presentation of F in the form F (x, y, z) = G(x, R(H(x, y), z)) The procedure for changing the content Ci to Ci′ while preserving the integrity condition also remains the same. The only difference is that the integers t0 , . . . , td are private and known only to the central authority. Then, compared to the basic construction in Section 3, in the construction in this section the polynomial F (x, y, z) is private. This makes direct application of Attack 2 and Attack 3 impossible. Additionally, as we shall see, since F (x, y, z) is private, it is not possible to use shortcuts in the computation of Gröbner bases in Attack 1. Example. For simplicity, in this example we assume that F (x, y, z) = G(x, H(x, y) − z). Calculations in this example are performed modulo n = 11587. Let the private polynomials G(x, y), H(x, y) be G(x, y) = xy + x + y + 3, H(x, y) = xy + 5. Then the private F (x, y, z) is F (x, y, z) = x2 y + xy − xz + 6x − z + 8. Let d = 2. Then Ā = (A0 , A1 , A2 ), B̄ = (B0 , B1 , B2 ), C̄ = (C0 , C1 , C2 ), D̄ = (D0 , D1 , D2 ). We therefore have P̂i (t) = A0 + A1 t + A2 t2 Ĉi (t) = B0 + B1 t + B2 t2 Ŝi (t) = C0 + C1 t + C2 t2 P̂i+1 (t) = D0 + D1 t + D2 t2 Let t0 , t1 , t2 = 1, 2, 3, respectively. To obtain an integrity condition for the advanced construction, we consider the following system of equations: F (P̂i (t0 ), Ĉi (t0 ), Ŝi (t0 )) = P̂i+1 (t0 ), F (P̂i (t1 ), Ĉi (t1 ), Ŝi (t1 )) = P̂i+1 (t1 ), F (P̂i (t2 ), Ĉi (t2 ), Ŝi (t2 )) = P̂i+1 (t2 ).

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

7

By expanding the terms, we obtain equations that depend only on Ā, B̄, C̄, D̄; these equations give us the public integrity condition: 0 = A20 B0 + A20 B1 + A20 B2 + 2A0 A1 B0 + 2A0 A1 B1 + 2A0 A1 B2 + 2A0 A2 B0 + 2A0 A2 B1 + 2A0 A2 B2 + A0 B0 + A0 B1 + A0 B2 − A0 C0 − A0 C1 − A0 C2 + 6A0 + A21 B0 + A21 B1 + A21 B2 + 2A1 A2 B0 + 2A1 A2 B1 + 2A1 A2 B2 + A1 B0 + A1 B1 + A1 B2 − A1 C0 − A1 C1 − A1 C2 + 6A1 + A22 B0 + A22 B1 + A22 B2 + A2 B0 + A2 B1 + A2 B2 − A2 C0 − A2 C1 − A2 C2 + 6A2 − C0 − C1 − C2 − D0 − D1 − D2 + 8 0 = A20 B0 + 2A20 B1 + 4A20 B2 + 4A0 A1 B0 + 8A0 A1 B1 + 16A0 A1 B2 + 8A0 A2 B0 + 16A0 A2 B1 + 32A0 A2 B2 + A0 B0 + 2A0 B1 + 4A0 B2 − A0 C0 − 2A0 C1 − 4A0 C2 + 6A0 + 4A21 B0 + 8A21 B1 + 16A21 B2 + 16A1 A2 B0 + 32A1 A2 B1 + 64A1 A2 B2 + 2A1 B0 + 4A1 B1 + 8A1 B2 − 2A1 C0 − 4A1 C1 − 8A1 C2 + 12A1 + 16A22 B0 + 32A22 B1 + 64A22 B2 + 4A2 B0 + 8A2 B1 + 16A2 B2 − 4A2 C0 − 8A2 C1 − 16A2 C2 + 24A2 − C0 − 2C1 − 4C2 − D0 − 2D1 − 4D2 + 8 0 = A20 B0 + 3A20 B1 + 9A20 B2 + 6A0 A1 B0 + 18A0 A1 B1 + 54A0 A1 B2 + 18A0 A2 B0 + 54A0 A2 B1 + 162A0 A2 B2 + A0 B0 + 3A0 B1 + 9A0 B2 − A0 C0 − 3A0 C1 − 9A0 C2 + 6A0 + 9A21 B0 + 27A21 B1 + 81A21 B2 + 54A1 A2 B0 + 162A1 A2 B1 + 486A1 A2 B2 + 3A1 B0 + 9A1 B1 + 27A1 B2 − 3A1 C0 − 9A1 C1 − 27A1 C2 + 18A1 + 81A22 B0 + 243A22 B1 + 729A22 B2 + 9A2 B0 + 27A2 B1 + 81A2 B2 − 9A2 C0 − 27A2 C1 − 81A2 C2 + 54A2 − C0 − 3C1 − 9C2 − D0 − 3D1 − 9D2 + 8 Now suppose the public would like to check if the integrity condition holds for the following block: Pi (t) = 6533 + 9560t + 2512t2 Ci (t) = 8147 + 6463t + 2498t2 Si (t) = 3507 + 5721t + 3086t2 Pi+1 (t) = 7891 + 7055t + 9071t2 To perform the check, one makes the assignment (A0 , A1 , A2 ) := (6533, 9560, 2512) (B0 , B1 , B2 ) := (8147, 6463, 2498) (C0 , C1 , C2 ) := (3507, 5721, 3086) (D0 , D1 , D2 ) := (7891, 7055, 9071) and checks if the system of equations in the integrity condition is consistent. In this example, all three equations become 0 = 0 modulo n, and one concludes that the integrity condition is satisfied for this block. Using this example, let us show how the public can construct Pi+1 (t) from the knowledge of Pi (t), Ci (t), Si (t). To do this, one makes the assignment (A0 , A1 , A2 ) := (6533, 9560, 2512) (B0 , B1 , B2 ) := (8147, 6463, 2498) (C0 , C1 , C2 ) := (3507, 5721, 3086) and the system of equations in the integrity condition becomes a linear system in D2 , D1 , D0 : 0 = −D0 − D1 − D2 + 843 0 = −D0 − 2D1 − 4D2 + 350 0 = −D0 − 3D1 − 9D2 − 5175. Solving this system modulo n, one obtains (D0 , D1 , D2 ) = (7891, 7055, 9071), as expected.

8

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

6. Suggested parameters and block size Let d1 , d2 , d3 , d4 ∈ N. Let G(x, y) =

d1 X d2 X

ai,j xi y j

and

H(x, y) =

i=0 j=0

d3 X d4 X

bi,j xi y j ,

i=0 j=0

where ai,j are integers modulo n for i = 0, . . . , d1 and j = 0, . . . , d2 , and bi,j are integers modulo n for i = 0, . . . , d3 and j = 0, . . . , d4 . The suggested values of parameters are: n is a prime of size about 20 bits, d1 = d2 = d3 = d4 = 2, d = 20. With these values of d1 , d2 , d3 , d4 , d, performing the proposed attacks seems impossible in practice, as we shall see in the experiments, Section 7. The values of ai,j can be chosen as random nonzero integers modulo n for i = 0, . . . , d1 and j = 0, . . . , d2 , and similarly for bi,j for i = 0, . . . , d3 and j = 0, . . . , d4 . The values of t0 , . . . , td can be chosen as random nonzero integers modulo n. With the suggested parameter values the size of the prefixes, contents, and suffixes, which is roughly equal to (d + 1) log n, is about 400 bits. 7. Experimental results In this section, we show how the attacks on the basic construction may be successful but turn out to be unsuccessful when used against the advanced quantum-safe construction. Experiments in this project were performed on Intel© i9-13900 processor with 50 GB of memory using 24 cores. As the main platforms, we used Maple 2024 [2], and two Julia packages: Groebner.jl 0.8.3 [4] and AlgebraicSolving.jl 0.8.2 [3]. We measured memory consumption using the time command. The code of our experiments is available on GitHub [10]. 7.1. Attack 1. 7.1.1. Attack on the basic construction. Fix a prime n. Let d ∈ N, and let Pi (t), Ci (t), Si (t), and Pi+1 (t) be univariate polynomials of degree d with integer coefficients modulo n. Assume that d < n. Let t0 , . . . , td be distinct integers modulo n. The integrity condition is: F (Pi (tj ), Ci (tj ), Si (tj )) = Pi+1 (tj ), j = 0, . . . , d. To change the content from Ci (t) to Ci′ (t), one needs to find a suffix Si′ (t) that satisfies F (Pi (tj ), Ci′ (tj ), Si′ (tj )) = Pi+1 (tj ), j = 0, . . . , d. One option is to search for a solution in the form of a polynomial with undetermined coeffiP cients, Ŝi′ (t) = di=0 Ai ti (the so-called ansatz polynomial), where Ā = (A0 , . . . , Ad ) are the new indeterminates: F (Pi (tj ), Ci′ (tj ), Ŝi′ (tj )) = Pi+1 (tj ), j = 0, . . . , d. This yields a system of d + 1 polynomial equations in d + 1 unknowns. The computational hardness of solving such a system depends on the choice of secret polynomials. Let d1 , d2 , d3 , d4 ∈ N. Let the secret polynomials be G(x, y) =

d1 X d2 X i=0 j=0

i j

ai,j x y

and

H(x, y) =

d3 X d4 X

bi,j xi y j ,

i=0 j=0

where ai,j are integers modulo n for i = 0, . . . , d1 and j = 0, . . . , d2 , and bi,j are integers modulo n for i = 0, . . . , d3 and j = 0, . . . , d4 .

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

9

d2

Table 1. The memory consumption of a Gröbner basis solver for the square polynomial system for basic construction in Attack 1. OOM stands for out of memory (> 50 GB). d 4 5 6 7 8 9 3 0.7 GB 0.7 GB 0.8 GB 2.0 GB 10.3 GB OOM 4 0.7 GB 1.1 GB 6.4 GB OOM 0.9 GB 5.0 GB OOM 5 6 1.8 GB 28.5 GB 4.6 GB OOM 7 8 12.3 GB 9 33.0 GB 10 OOM -

The degrees d1 , d3 , d4 affect only the size of the coefficients that are taken modulo n, hence d1 , d3 , d4 do not affect the computational hardness of solving the system. We fix d1 = d3 = d4 = 2. The coefficients of G(x, y) and H(x, y) can be selected from a subset of integers modulo n, which typically produces a zero-dimensional system of polynomial equations. It appears that the number of solutions of the system (in an algebraic closure of the ground field) is dd+1 2 , which coincides with the Bézout bound. The bit complexity of Gröbner bases for zero-dimensional systems is (DN )O(1) , where D is the degree of polynomials and N is the number of variables (see [12] and references therein). By the Bézout theorem, this upper bound is essentially sharp. Since the number of solutions equals the bound in the Bézout theorem, we expect that the above complexity is attained for our systems. To assess the computational hardness of solving a system of polynomial equations experimentally, we use Gröbner bases to solve particular instances of our system. We fix n = 11587 and pick the coefficients of G(x, y) and H(x, y) as random integers in the range from 0 to n − 1. In Table 1, we list the memory consumption of Gröbner basis computation for different d2 , d. We do not report the running times since they are qualitatively similar to the memory consumption. We used the groebner command in the Julia package Groebner.jl. We observe that incrementing either d2 or d by 1 roughly doubles the memory consumption. To test a wider selection of algorithms and implementations, we repeated the experiments using two other software packages: Maple (that, as far as we know, uses the F4 algorithm), and AlgebraicSolving.jl, which has a top-of-the-line implementation of a signature-based algorithm. These experiments led to similar conclusions. While experiments suggest that solving the above system is hard, a critical issue of the basic construction is the possibility to produce arbitrarily many more equations by specializing the integrity condition at different points. Let ℓ ∈ N with ℓ < n, such that d < ℓ. Let t0 , . . . , tℓ be distinct integers modulo n. Consider the following (overdetermined) system: F (Pi (tj ), Ci′ (tj ), Ŝi′ (tj )) = Pi+1 (tj ), j = 0, . . . , ℓ. For ℓ = d + 1, in our experiments, such system has a single solution. Taking more equations (ℓ = 2d, 3d, . . .) significantly reduces the running time and memory consumption of the Gröbner basis solver, which is to be expected. Thus, in practice, it is possible to solve the system rather efficiently for the basic construction. 7.1.2. Failure of Attack 1 on the advanced construction. In case of the construction from Section 5, the polynomial F (x, y, z) is not public. Therefore, it is impossible to produce arbitrarily many

10

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

polynomial equations, and one must solve a square system, which is infeasible as we have seen before. The computational hardness of solving such a system is illustrated in Table 1. From this table, we expect the memory consumption to roughly double when incrementing d by 1, and, by extrapolation, solving for d > 30 would require at least 40 petabytes of memory. We note that interpolating F (P̂i (t), Ĉi (t), Ŝi (t)) − P̂i+1 (t) as a polynomial in t of degree d is impossible whenever G(x, y), H(x, y) are not linear. 7.2. Attack 2. 7.2.1. Attack on the basic construction. Fix a prime n. Let d1 , d2 , d3 , d4 ∈ N. Let the secret polynomials be d1 X d2 d3 X d4 X X G(x, y) = ai,j xi y j and H(x, y) = bi,j xi y j , i=0 j=0

i=0 j=0

where ai,j are integers modulo n for i = 0, . . . , d1 and j = 0, . . . , d2 , and bi,j are integers modulo n for i = 0, . . . , d3 and j = 0, . . . , d4 . Introduce new indeterminates Ai,j for i = 0, . . . , d3 and j = 0, . . . , d4 and Bi,j for i = 0, . . . , d1 and j = 0, . . . , d2 . In case d1 , d2 , d3 , d4 are known, the polynomials G(x, y) and H(x, y) can be recovered by constructing the ansatz polynomials Ĝ(x, y) =

d1 X d2 X i=0 j=0

Bi,j xi y j ,

Ĥ(x, y) =

d3 X d4 X

Ai,j xi y j

i=0 j=0

and solving the following system for the undetermined coefficients Ai,j , Bi,j : F (Pi , Ci , Si ) = Ĝ(Pi , Ĥ(Pi , Ci ) − Si ). The dimension of such systems in all experiments we tried is 1. This can be explained by the following symmetry in the equations: if G(x, y) and H(x, y) satisfy the equality F (x, y, z) = G(x, H(x, y) − z), then G(x, y − U ) and H(x, y) + U satisfy it as well for any U . By normalizing one of the secret polynomials (say, H(x, y)) to have the trailing coefficient equal to one, the system becomes zerodimensional in all examples that we have tested. For example, for n = 11587, for d1 = d2 = d3 = d4 = 1, for a particular choice of secret polynomials, one possible instance of the system of equations in the undetermined coefficients is: A0,1 B0,1 + 842 = 0 A1,1 B1,1 + 2023 = 0 11586A1,1 + 5373 = 0 A1,1 B0,0 + A0,1 B1,0 + A1,0 + 6818 = 0 11586A0,1 + 10712 = 0 A0,1 B0,0 + A0,0 + 8216 = 0 A1,1 B1,0 + 289 = 0 A1,1 B0,1 + A0,1 B1,1 + 986 = 0 The system contains trivial linear equations that are readily solved, and substituting the solutions of linear equations into other equations would produce new linear equations, at which point the procedure can be repeated. This example system can be solved by such procedure. An issue with the basic construction is that it seems that this iterative procedure can be applied for any d1 ⩾ 1, d2 ⩾ 1, d3 ⩾ 1, d4 ⩾ 1, which makes it straightforward to solve the resulting systems. 7.2.2. Failure of Attack 2 on the advanced construction. The attack cannot be applied since an unauthorized party has no access to F (x, y, z). 7.3. Attack 3.

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

11

7.3.1. Attack on the basic construction. Direct application of [13, Algorithm 4] to F (x, y, z) considered as a polynomial in Q(x, z)[y] (that is, using y as the main variable) succeeds. The output of the algorithm are G(x, y) and H(x, y), possibly normalized to have trailing coefficients equal to zero. As we have seen, having this output is equivalent to having a trapdoor to the construction. The complexity of the algorithm is polynomial in the degree of F (x, y, z) in y, which makes it efficient at breaking our basic construction. 7.3.2. Failure of Attack 3 on the advanced construction. In this scenario, the polynomial F (x, y, z) is not available publicly. Therefore, direct application of [13, Algorithm 4] is impossible. 7.4. Attack 4. 7.4.1. Attack on the basic construction. If an attacker can observe the same block before and after it was changed, then (s)he can be in possession of the following equation: Si − Si′ = H(Pi , Ci ) − H(Pi , Ci′ ) (mod (t − t0 ) · · · (t − td )). Here Si , Si′ , Pi , Ci , Ci′ are all known to the attacker. Then, if the bound on the degree of H(x, y) is known to the public (as it should be), the above equation translates into a system of linear equations in the coefficients of H(x, y). Upon accumulating sufficiently many equations as above (after sufficiently many replacements of Ci by different Ci′ ), the attacker can find all the coefficients of H(x, y). 7.4.2. Failure of Attack 4 on the advanced construction. In the advanced construction, the attacker no longer sees the actual equality Si − Si′ = H(Pi , Ci ) − H(Pi , Ci′ ) (mod (t − t0 ) · · · (t − td )), but knows only that there exist secret evaluation points t0 , . . . , td at which the corresponding equalities hold. 8. Conclusions We proposed a new quantum-safe and lightweight construction for redactable blockchains based on multivariate polynomial equations. We studied several possible attacks on our scheme using various Gröbner bases computation techniques and determined that none of them is feasible against our construction. Acknowledgements. We are grateful to the referee for pointing out Attack 4. References 1. G. Ateniese, B. Magri, D. Venturi, E. Andrade, Redactable blockchain – or – rewriting history in bitcoin and friends, in: 2017 IEEE European Symposium on Security and Privacy, INSPEC Accession Number: 17011479. (See also https://eprint.iacr.org/2016/757.pdf) 2. L. Bernardin, P. Chin, P. DeMarco, K. O. Geddes, D. E. G. Hare, K. M. Heal, G. Labahn, J. P. May, J. McCarron, M. B. Monagan, D. Ohashi, S. M. Vorkoetter, Maple Programming Guide, Maplesoft, a division of Waterloo Maple Inc., 1996-2023. 3. J. Berthomieu, C. Eder, M. Safey El Din, msolve: A Library for Solving Polynomial Systems, Proceedings of the 46th International Symposium on Symbolic and Algebraic Computation (2021), 51–58. 4. A. Demin, S. Gowda, Groebner.jl: A package for Gröbner bases computations in Julia, preprint (2024), https://arxiv.org/abs/2304.06935. 5. D. Deuber, B. Magri, S. A. K. Thyagarajan, Redactable blockchain in the permissionless setting, in: 2019 IEEE Symposium on Security and Privacy, 124–138. (See also https://arxiv.org/abs/1901.03206) 6. Downside of bitcoin: A ledger that can’t be corrected, The New York Times, 2016. https://tinyurl. com/ydxjlf9e 7. J.-C. Faugére, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139 (1999) 61–88.

12

REDACTABLE BLOCKCHAINS AND POLYNOMIAL EQUATIONS

8. J.-C. Faugére, An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography, J. Symb. Comput. 44 1676–1689 9. J. von zur Gathen, I. E. Shparlinski, Generating safe primes, J. Math. Cryptol. 7 (2013), 333–365. 10. GitHub repository, https://github.com/sumiya11/Redactable_blockchains_and_polynomial_ equations. 11. D. Grigoriev and V. Shpilrain, RSA and redactable blockchains, Int. J. Computer Math.: Computer Systems Theory 6 (2021), 1–6. 12. A. Hashemi and D. Lazard, Sharper Complexity Bounds for Zero-dimensional Gröbner Bases and Polynomial System Solving, International Journal of Algebra and Computation 21 (2011) 703–713. 13. D. Kozen, S. Landau, Polynomial decomposition algorithms, J. Symb. Comput. 7 (1989), 445–456 14. I. Puddu, A. Dmitrienko, S. Capkun, µchain: How to forget without hard forks, preprint, https://eprint.iacr.org/2017/106.pdf 15. P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (1997), 1484–1509. Laboratoire d’informatique de l’École polytechnique, LIX, UMR 7161, CNRS, 1 rue Honoré d’Estienne d’Orves, 91120 Palaiseau, France Email address: alexander.demin@lix.polytechnique.fr Department of Mathematics, Queens College, City University of New York, Queens, NY 11367 Email address: aovchinnikov@qc.cuny.edu Department of Mathematics, The City College of New York, New York, NY 10031 Email address: shpilrain@yahoo.com

Related documents

• Analysis of solutions for a blockchain compliance with GDPR#289137
• An explicit rational lemniscate counterexample with certified separators#1154863
• On the rational solutions of generalized Abel equations#1130548
• Exclusive-or encoded algebraic structure for efficient quantum dynamics#635534
• Exclusive-or encoded algebraic structure for efficient quantum dynamics#633185