Redactable blockchains and polynomial equations

In the digital age, our world is increasingly woven together by networks of smart devices, from the cars we drive to the thermostats in our homes. These systems, often called the Internet of Things, rely on a shared record of events to function securely. For years, the gold standard for keeping such records safe has been a technology called a blockchain. Think of a blockchain as a digital ledger that is copied across thousands of computers, where every new entry is locked into place by the one before it. Once a record is written, the design of this system makes it nearly impossible to alter or delete, ensuring that no one can tamper with history. This permanence is a strength, but it has become a weakness in a world where privacy laws now demand that people have the right to be forgotten, or where simple human errors need to be corrected without destroying the entire chain.

The challenge for scientists has been to create a system that keeps the security of an unchangeable record while allowing a trusted authority to edit or erase specific entries when necessary. This is the problem of creating a "redactable" blockchain. Previous attempts to solve this have relied on mathematical puzzles that are easy to solve with today's computers but could be cracked instantly by future quantum computers, which are expected to arrive within the next decade. A team of researchers has now proposed a new solution that avoids these vulnerable puzzles entirely. Instead, they have built their system on a different kind of mathematical difficulty: solving complex equations with many variables, a task that current quantum computers are not known to be able to solve efficiently.

The researchers, Alexander Demin, Alexey Ovchinnikov, and Vladimir Shpilrain, developed a method where the security of the blockchain depends on the difficulty of finding the solution to a specific type of polynomial equation. In their system, the data in each block is treated as a mathematical expression involving a variable, much like a formula with an unknown number. The integrity of the chain is maintained by a public rule that links one block to the next. However, a central authority holds a secret key, which is essentially a specific way of arranging these formulas. With this secret, the authority can change the content of a block and calculate a new ending piece that still satisfies the public rule, effectively editing the record without breaking the chain. For anyone without the secret key, trying to forge such a change is equivalent to solving a massive system of equations with dozens of unknowns, a task that is computationally overwhelming.

To ensure their new system is truly secure, the team first built a basic version and then subjected it to a battery of simulated attacks to see where it might fail. They tested four different ways an attacker might try to break the code. One approach involved trying to solve the equations directly to find a new ending piece; another involved trying to reverse-engineer the secret formula from the public data; a third looked for patterns in how the formulas were built; and the fourth relied on watching the system change over time to deduce the secret. In their initial, simpler version, the researchers found that the system was vulnerable to all four of these attacks. An attacker with enough computing power could eventually solve the equations or deduce the secret formula, especially if they could observe the system being edited multiple times.

Recognizing these weaknesses, the team refined their design into an advanced version that closes these loopholes. In this improved construction, the public rule that links the blocks is no longer a single, known formula. Instead, the rule is a hidden system of equations that is only partially revealed. The secret key now includes the specific points where these equations are evaluated, which are kept private. This change means that an attacker cannot simply look at the public data and try to solve for the secret, because the full equation they need to solve is never shown. When the researchers tested this advanced version against the same four attacks, the results were dramatically different. The attempts to solve the equations failed because the system was too complex and the necessary information was missing. The attempts to deduce the secret formula failed because the attacker could not see the full picture of how the data was being transformed.

The team ran these tests on powerful computers using specialized software designed to solve complex mathematical problems. They simulated attacks with varying levels of difficulty, increasing the size of the equations to see how much computing power would be required to break the system. Their experiments showed that as they increased the complexity of the equations, the amount of memory needed to solve them grew exponentially. For the parameters they recommended, which involve equations with a degree of twenty and coefficients based on a prime number of about twenty bits, the memory required to break the system would exceed the capacity of any existing computer, reaching into the realm of petabytes. This suggests that while the basic version of their idea was flawed, the advanced version provides a robust defense against both current and future quantum threats.

The significance of this work lies in its balance between flexibility and security. It offers a way to maintain the trustworthiness of a digital record while respecting the need for privacy and correction. By moving away from the mathematical structures that quantum computers are expected to exploit, and toward the complexity of multivariable polynomial equations, the researchers have provided a blueprint for a blockchain that can evolve. Their findings indicate that with the right choice of parameters, such a system can remain secure even as computing technology advances, offering a potential path forward for the secure management of data in an increasingly connected and regulated world.