Invented by KIM; Seongkwang, LEE; Byeonghak, SON; Mincheol, SAMSUNG SDS CO., LTD.

Zero-knowledge proof is a way to prove you know something without giving away what you know. It is a powerful tool for online safety, especially as computers become faster and smarter. Today, we look closely at a new patent application for a method that uses binary trees for zero-knowledge proof. We break it down in simple terms, so everyone can understand how it works, why it matters, and how it stands apart from earlier ideas.

Background and Market Context

The need to keep secrets safe online has never been more important. Every day, people use the internet to send money, sign documents, and talk to each other. They want to know that their private information will not be stolen or misused. For a long time, we used cryptography based on math problems that are hard for computers to solve, like the RSA or elliptic curve methods.

But things are changing. Quantum computers are coming, and they might be able to break these old cryptographic methods. This is a big worry for governments, banks, and anyone who cares about privacy and security. That’s why experts are searching for new ways to protect secrets, even from quantum computers. This area is called post-quantum cryptography.

One promising approach is zero-knowledge proof, or ZKP for short. ZKP lets someone prove they know a secret without showing the secret itself. This is useful for situations like signing a document, logging into a website, or even making a cryptocurrency transaction. If you can prove you know your password or your secret key, but don’t reveal it, hackers can’t steal it.

The United States government, through NIST (National Institute of Standards and Technology), has been working to find new digital signature methods that are safe from quantum computers. Some of the main candidates use ZKP. For example, the Picnic signature and the FAEST signature both use zero-knowledge proof techniques.

However, these methods have their own problems. They can be slow and the signatures they create can be very large. This is a problem for real-world use, especially on devices with limited memory or slow processors. There is a strong demand for ZKP methods that are both fast and produce small signatures. This is where the new invention comes in. It aims to solve these problems by using a binary tree structure for zero-knowledge proof.

So, why does this matter in the market? Faster and smaller digital signatures mean easier, safer online banking, shopping, government services, and more. It means that even tiny devices, like smart cards or mobile phones, can use strong security without slowing down. It also helps companies reduce costs by using less computing power and storage.

The demand for safe, fast, and efficient zero-knowledge proof systems is huge. As more people and businesses move online, and as quantum computers get closer to being real, the need for post-quantum safety is only going to grow. This invention is tapping into a market that is both urgent and growing fast.

Scientific Rationale and Prior Art

To understand what makes this invention new, let’s look at how zero-knowledge proofs have been done before, and the science behind them.

A zero-knowledge proof is like a secret handshake. You want to prove you know the handshake, but you don’t want to show it to anyone. In the digital world, this is done using math. The challenge is to make sure that the proof is hard to fake, but does not reveal any secrets.

Some earlier systems use something called MPC-in-the-Head. In this model, you imagine several parties in your head, each holding a piece of your secret. You simulate a conversation between these parties and reveal just enough for another person to be convinced that you know the secret, but not enough for them to steal it. FAEST and Picnic use these ideas. Another technique is called VOLE-in-the-Head, which is similar but uses different math tools.

A common way to build these proofs is to use a block cipher. A block cipher is a way to scramble information with a secret key. In the proof, you show that you can use the block cipher correctly, without revealing the secret key. You might also use hash functions, which turn any data into a short, unique string of numbers.

One of the big problems with these older systems is size. To make the proof safe, you need to reveal many pieces of information. Each piece is like a puzzle piece, and the more pieces you reveal, the bigger the proof becomes. If the proof is too big, it takes up a lot of storage and is slow to check.

Another problem is speed. Every time you create a proof, you have to do many calculations. If you have to do the same calculation over and over, it slows things down. In small devices, this can be a major problem.

To make things more efficient, previous work looked at using binary trees. A binary tree is a way to organize information so that each piece is connected to two child pieces, like a family tree. One famous type of binary tree is the GGM tree, named after Goldreich, Goldwasser, and Micali. This tree is used to create many random values from a single secret, which is useful for zero-knowledge proofs.

In earlier systems, each node in the tree is created by applying a hash function or block cipher to its parent. But this means you have to do a lot of separate calculations. To make things faster, some systems tried to cut down on the number of calculations, but this often made the proofs less safe or still too large.

One more challenge is the need for “compensation values.” In some systems, when you break the secret into parts for the tree, you need to add extra values to make sure everything adds up correctly. These extra values make the proof bigger.

So, the prior art gives us a few main ideas:
– Use block ciphers or hash functions to break up secrets.
– Use binary trees to organize the information.
– Use multiple pieces of information to build a secure proof.
– Face problems with large proof size, slow speed, and extra compensation values.

This invention builds on all of this, but makes key improvements. It aims to keep things safe, but also much faster and smaller.

Invention Description and Key Innovations

Now, let’s dig into what this invention actually does, and why it is special. We will keep it simple and clear.

The heart of this invention is a method for zero-knowledge proof that uses a binary tree, but in a smarter way. The process starts by putting the secret key into the very top node of the tree, called the root. From there, the tree is built downwards, with each branch and leaf being created using either hash functions or block ciphers, but with fewer calculations than before.

Here is the clever part: instead of doing the same work twice to create two child nodes from a parent, the invention only computes the first child node using a hash function (or block cipher) and a random salt value. The second child node is then made by simply taking the XOR (exclusive or) of the parent and the first child node. XOR is a simple and fast operation for computers, so this saves a lot of time.

For example, if you have a parent node P, you create the first child C1 by running a hash function on P with a salt. Then, you get the second child C2 by doing C2 = C1 XOR P. You don’t have to run the hash function twice, which saves resources.

This process is repeated down the tree, building more nodes at each level. At the bottom, the tree has leaf nodes. Each leaf node represents a share of the secret, just like in earlier MPC-in-the-Head systems.

When you want to prove you know the secret, you don’t send all the leaf nodes. Instead, you leave one or more out and send the rest, along with just enough information so that the verifier can reconstruct the missing nodes. This is possible because of the way the tree was built: knowing the parent and one child, the verifier can work out the other child using XOR.

This method gives you two big benefits. First, you reduce the number of calculations, because you only need to run the hash or cipher once per parent node, not twice. This makes the proof much faster to create and check. Second, you don’t need to include extra compensation values, because the secret key was injected at the root and the shares add up properly. This means the proof is smaller.

The method works with both hash functions and block ciphers. In the block cipher case, there are extra steps to make sure the system is safe. It uses something called an orthomorphism function, which is a special kind of function that keeps the output unpredictable. This adds an extra layer of security, making it hard for attackers to guess the secret key.

The system is flexible. It can use different types of hash functions or block ciphers, and the size of the tree can be adjusted depending on how many shares are needed or how much security is required. For example, you can use SHAKE as the hash function or AES as the block cipher. The tree can be as deep as needed, depending on the number of parties or the strength of the proof.

The proof works with different zero-knowledge frameworks, including MPC-in-the-Head and VOLE-in-the-Head. This means it can be used in a wide range of applications, from digital signatures to safe online transactions, to private smart contracts in blockchain systems.

The invention is not just a method. It also describes how to make a device or a computer program that carries out the process. The device has a processor and memory, and runs the steps as described. The patent also covers a computer-readable storage medium with the instructions needed to run the method on any computer or device.

So, what are the key innovations?

1. Injecting the secret key at the root of the binary tree, making the tree structure simpler and removing the need for extra compensation values.

2. Creating only one child node per parent with a hash function or block cipher, and using XOR to create the other child. This halves the number of heavy computations.

3. Making the proof smaller by only sending some of the leaf nodes and the minimum extra information needed for the verifier to check the missing pieces.

4. Supporting both hash function and block cipher approaches, and adding the use of orthomorphism functions for extra safety.

5. Making the system more flexible, so it can be used in many different applications and adjusted for different levels of security and speed.

The result is a zero-knowledge proof system that is faster, uses less memory, and creates much smaller signatures, all while keeping secrets safe from both regular and quantum computers. This is a major step forward in making zero-knowledge proofs practical for real-world use.

Conclusion

As the world moves closer to the era of quantum computers, the need for new ways to keep secrets safe is greater than ever. Zero-knowledge proofs are a key technology for this future, but until now, they have been held back by slow speeds and large signature sizes. This invention changes the game by using a smart binary tree structure, clever use of XOR, and flexible cryptographic tools to make zero-knowledge proofs that are fast, small, and safe.

By bringing together the best ideas from prior systems and adding its own key improvements, this method stands out as a strong candidate for the next generation of secure online transactions. It is simple enough to understand, yet powerful enough to protect even the most valuable secrets. As more businesses and people demand better online safety, inventions like this will shape the future of digital trust.

Click here https://ppubs.uspto.gov/pubwebapp/ and search 20250337585.