Technical Deep-Dive: COTI’s Answer to Quantum Computing

COTI

Published in

COTI

7 min readJul 9, 2024

TLDR

Quantum computing presents a significant threat to classical cryptographic methods used in blockchain security.
COTI is aiming to achieve quantum resistance in early 2025 by doubling symmetric encryption key lengths and using post quantum secure asymmetric encryption schemes.
COTI V2 offers a privacy preserving smart contract solution using Garbled Circuits, enabling any computation between parties without revealing sensitive data, not even the shared state.
This solution enhances blockchain technology with advanced confidential data management and privacy preservation capabilities.
Developers can participate in the COTI V2 Builders program to create quantum-resistant smart contracts and applications.

In the last decades, computers have quadrupled their performance in terms of raw power.

Thanks to advancements in their architecture, and manufacturing processes, CPUs have seen impressive built-in efficiency improvements. From the humble 5MHZ to the Intel 8086 to the current Apple M3 Ultra, the computer has made quantum leaps forward.

Until recently, these improvements followed a concept dubbed Moore’s Law. It is an observation made by Intel’s co-founder, Gordon Moore, who in 1975 predicted that every two years, the number of transistors in integrated circuits would double, and in turn, computation throughput will double.

But as transistors continue to shrink to atomic scales, limitations begin to appear. As researchers and manufacturers push the boundaries of physics, we are reaching a point where downscaling transistors is no longer an option.

To overcome the limitations of traditional transistor-based processors, engineers are exploring alternative technologies, such as quantum computing, where binary 0s and 1s exhibit near-magical characteristics.

In this blog we’re going to dive deep into how COTI V2 is directly addressing the biggest challenge to crypto security — quantum computing.

Strap in, we’re going to get technical!

Quantum computing basics

Traditional computers use bits as their smallest unit of data, which could be either a 0 or a 1.

Quantum computing, on the other hand, uses quantum bits, also known as qubits. This new unit has a fundamentally different way of working, compared to a bit. Qubits can be a 0 and a 1 at the same time, due to a quantum property called superposition.

This so-called mathematical ability enables Quantum Computers to solve complex problems exponentially faster than traditional ones, as they can perform calculations in parallel.

Another key concept in quantum computing is entanglement, where qubits are correlated in a particular way, so the state of one of them is dependent on the other. Notably, quantum computing doesn’t take into account distance, and can allow dependency even if qubits are separated by immense distances.

This offers quantum computers a more efficient way to transfer information.

Jargon-aside, essentially thanks to all these new properties, quantum computers are simply astronomically fast computers. They can make computations at the metaphorical speed of light, rendering your new MacBook Air with a 32GB ram, and M3 chip, looking like a horse and a carriage of the digital age.

The first publicly known demonstration of a quantum algorithm took place in 1998, at Oxford University. A 2-qubit working Quantum Computer was used to solve Deutsch’s problem (today there are 1,000+ qubits Quantum Computers), and later that year a 3-qubit computer was born.

But what really made quantum computing take a quantum leap was Shor’s Algorithm, published by Peter Shor in 1994. Shor’s algorithm allows current cryptographic algorithms–like those widely used in cryptocurrencies–to potentially break.

Quantum computing challenges crypto security

One of the main concerns with Quantum Computing is its potential to render current public-key cryptographic algorithms, such as the RSA algorithm, useless.

The RSA algorithm relies on a mathematical property that states that it’s easy to calculate the product of two large prime numbers, but extremely difficult to factor the product back into its original prime factors.

This property is known as the difficulty of factoring and forms the basis for RSA encryption. Notably, RSA encryption was first published in 1977, and continues to be the cryptographic algorithm most used by mainstream banks today.

ECC (Elliptic Curve Cryptography) is another public-key cryptographic algorithm, which is used by Bitcoin. It offers users the ability to generate a public key. Unlike RSA, which relies on the difficulty of factoring large numbers, ECC relies on the difficulty of finding discrete logarithms on elliptic curves.

A Bitcoin private key is a randomly generated 256-bit number (between 0 and ²²⁵⁶-1).

Finding the private key while knowing the public key is nearly impossible due to how difficult it would be to guess a random 256-bit number. The possible private key combinations are comparable to the number of atoms in the observable universe, multiplied by 77

In other words, and for our still nascent human minds, a number that we can hardly begin to comprehend.

For example, it would take a modern computer 260,000,000,000,000,000,000,000,000,000 years to guess the number. Odds exist, but they are virtually zero.

However, Shor’s Algorithm is a quantum algorithm tailor-made to efficiently find the prime factors of an integer (kind of “bending” traditional math with this new quantum computing technology).

With a Quantum Computer sufficiently powerful, applying the algorithm would not only threaten crypto security, but also online banking, communications, and every transaction we secure under public-key cryptographic algorithms, such as RSA and ECC.

How does the cryptography community addresses quantum computing

Experts are actively developing post-quantum cryptography (PQC) and transitioning systems, establishing new computational standards. These algorithms are designed to be secure against both classical and quantum computing attacks.

There are several promising quantum-resistant algorithms:

Lattice-based cryptography: Cryptographic algorithms that are based on mathematical problems related to lattices. The main lattice-based cryptographic algorithm is NTRU, which is based on the hardness of the shortest vector problem (SVP) in lattices. NTRU is a public-key cryptosystem that can be used for encryption and digital signatures.
Code-based cryptography: Cryptographic algorithms that are based on error correcting codes. The main code-based cryptographic algorithm being developed is the McEliece cryptosystem, which uses the difficulty of decoding linear codes to achieve security.
Isogeny-based cryptography: A class of cryptographic algorithms that are based on the study of isogenies in elliptic curves. The main isogeny-based cryptographic algorithm being developed is the Supersingular Isogeny Diffie-Hellman (SIDH).

Essentially, these 3 categories are part of advanced mathematics being applied in very ingenious ways to achieve goals in terms of engineering security. There are also hybrid approaches that combine classical and quantum-resistant algorithms to ensure a smoother, and more secure transition.

How COTI’s Garbled Circuits-based solution resists quantum computing

In COTI’s garbled circuit-based solution (developed by Soda Labs) there are three components that are adjusted in order to achieve post quantum security:

Key distribution for users
Encryption of user’s inputs
Computation on ciphertexts

Briefly, key distribution is done via a key-encapsulation mechanism (KEM), which can be any post-quantum asymmetric encryption scheme; encryption of inputs can be done using the same symmetric scheme, but with a twice as large secret key, and similarly, computation with garbled circuits can use a PRF with larger secret key.

In more detail, Garbled Circuits allow for computation to be conducted on the private data of multiple parties without leaking the parties’ inputs or any intermediate calculations.

First theorized back in 1982, garbled circuits represent one of the best approaches to solve multi-party computation (MPC), for preserving private information. Although incredibly powerful, they were never considered for use for blockchain application due to their heavy resource requirements and relative slow speed.

But after years of extensive research, a revolutionary breakthrough in Garbled Circuits is now introduced, allowing the technology to be used on the blockchain for the very first time.

By bridging the gap between cutting-edge research and practical application, COTI is pioneering the use of advanced cryptographic techniques in blockchain systems to address the challenges posed by quantum computing.

The garbling scheme at the heart of our protocol relies on applying a pseudo-random function (PRF) like AES to circuit wires’ labels. Additionally, we use a symmetric encryption scheme for on-chain ciphertexts, ensuring data remains encrypted and secure. That symmetric key encryption is again based on applying a PRF like AES on some value.

Since the best known quantum attacks on symmetric key primitives are done through a fast search using Grover’s algorithm, a key of length X typically gives us X/2 bits of security in the post quantum world. This means that to get the same security we had in the classical world, we need to double the key length in the quantum world.

For instance, if we use a 128-bit key in our system, it is required to increase to a 256-bit key in order to be quantum-safe, with the same level of security.

Hence, COTI will be Post Quantum Computing secure and our effort should be completed by 2025.

Other Advantages of COTI V2’s Garbling Circuits

Confidential Data Management: Sensitive data is stored and processed securely on-chain.
Privacy Preservation: Authorized parties can query and analyze encrypted data without compromising confidentiality.
Multi-Party Computation (MPC): Allows multiple parties to jointly compute a function over their inputs while keeping those inputs private.

Our approach enhances security by mitigating risks associated with centralized data storage, defining precise rules for data access, ensuring only authorized personnel can view sensitive information.

On-chain data cannot be altered or deleted once it’s stored, a crucial advantage for legal, medical, defense and regulatory applications.

COTI V2 Garbled Circuits solution is one of the key solutions cryptocurrency systems have to face the challenges posed by quantum computing.

If you have a smart contract idea or application design concept and you want to build on COTI’s Developer Network, you can join the COTI V2 Builders program for an opportunity to get grants.

You can also submit your feedback which the team will be happy to review and respond to. Join our Builder’s program today!