header-langage
简体中文
English
Tiếng Việt
Scan to Download the APP
Partnered With:

How a New Award-Winning Paper That's Shaking Up the Cryptography World Is Changing the Foundations of Blockchain Cryptography

Read this article in 4 Minutes
The mathematical structure of "one-way functions" can prove whether methods such as zero-knowledge proofs in L2 blockchains are cryptographically secure
Original title: "The Paper that can Change the Foundations of all Blockchain Cryptography"
Original author: Jesus Rodriguez
Original compilation: Cicada Chan talks about Zen


Cryptography is at the heart of many blockchain protocols. From traditional proof-of-work (PoW) to L2 modern methods such as ZK-rollups, many advanced cryptographic methods provide the foundation for blockchain runtimes and protocols. Hence, there is an omnipresent question about the security robustness of any blockchain architecture. Naively, we assume that blockchain cryptographic implementations that survive sophisticated attacks are inherently secure, but this is far from empirically proven. Is there a better way to verify the robustness of security algorithms. The answer appears to be in a new paper that just won the National Security Agency's (NSA) "Best Cybersecurity Research Paper Competition," which has caused quite a stir in the cryptography research community.  


This article is titled "One-Way Functions and Kolmogorov Complexity" 's paper provides an answer to a 500-year-old question in cryptography. The question at hand has to do with the existence of mathematical structures called "one-way functions" that can prove whether methods like zero-knowledge proofs in L2 blockchains are cryptographically secure.  


The very nature of modern cryptography relies on creating passwords on data in the hope that they remain secure. But how do we ensure they are safe? The theoretical answer to this question came in the 1970s, when cryptographers came up with the concept of one-way functions, mathematical functions that are easy to compute but difficult to reverse. To illustrate how one-way functions work, imagine if you were asked to multiply two large prime numbers, such as 485144 and 999983. Getting the number 485,135,752,552 as an answer might be a bit of work, but we have a way to do it. Now let's answer the inverse problem, starting with a number and trying to determine its prime factors. This is an extremely difficult task. This is the nature of one-way functions.


Image source: Codeprg


< /p>

The cryptography used in L1 and L2 blockchains is based on the premise of the existence of one-way functions. If a one-way function exists for a given problem, then its cryptographic protection, if not, it may be vulnerable to different attacks. However, until now, it has been nearly impossible to prove the existence of one-way functions. In their paper, the Cornell researchers found an answer that parallels an obscure field of computer science.


Enter Kolmogorov Complexity 


Answer proposed in Cornell University research paper Basically shows that the existence of one-way functions is related to another fundamental problem in computer science, namely Kolmogorov complexity (KC). KC theory is concerned with the complexity of strings of numbers. If you see two large numbers 66666666666666666666 and 123948109102912, you can't quite prove which is "more random" than the other, but intuitively you think the second number is more complicated to generate. This was the idea that Soviet mathematician Andrey Kolmogorov used to start a new theory of computational complexity. Essentially, KC theory defines the complexity of a string of numbers as the length of the shortest program that produces that string as output.  


Going back to our example, KC theory is much more complicated, but hopefully you get the core idea. KC theory has been fundamental to many areas of computer science for decades, but not so much in cryptography. Until the Cornell research group pulled a rabbit out of the hat and proved the existence of a one-way function related to KC for a given problem. In simple terms, if a problem is KC complex, a one-way function exists, and if it doesn't, it probably doesn't.  


This simple statement may become one of the most revolutionary discoveries in modern cryptography.


Image source: Quanta Magazine


What does this mean for the blockchain world?


The Cornell paper provides an empirical approach to assess The robustness of the cryptographic techniques used. This is especially important given the advent of L2 runtimes based on cryptography such as secure multi-party computation or zero-knowledge proofs. Determining whether an algorithm is KC complex is fundamentally simpler than determining the existence of a one-way function. Admittedly, this question is beyond the scope of the blockchain ecosystem, but if we are talking about building rails for a new financial system, then cryptographic robustness is a foundational capability.


Note: For the explanation of the paper, see "one-way Functions and Kolmogorov Complexity》


Original link


Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia

Choose Library
Add Library
Cancel
Finish
Add Library
Visible to myself only
Public
Save
Correction/Report
Submit