Into the True vision of TrueID

Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs) have been hailed as a technological marvel in cryptography, enabling applications in blockchain technology, secure multi-party computation, and beyond. These cryptographic proofs enable one party to prove to another that a statement is true without revealing anything else about the information contained in the statement. Typically, zkSNARKs have been founded on mathematical problems like bilinear pairings or the discrete logarithm problem. However, the arrival of quantum computing technology threatens to undermine the security of these systems. One algorithm at the heart of this threat is Shor's Algorithm, which can efficiently factor large numbers and compute discrete logarithms.

zkSNARKs: Bilinear Pairings and the Discrete Log Problem

1. Bilinear Pairings: Bilinear pairings are mathematical functions that take as input two points on an elliptic curve and produce an output in another group. The pairings are designed to be computationally hard to reverse, thereby providing a strong basis for cryptographic systems.

2. Discrete Log Problem: The discrete logarithm problem is another mathematical problem that serves as the foundation for various cryptographic protocols, including some zk-SNARKs. The problem can be defined as finding an integer $x$ such that $$g^x mod(p) = y$$

   Given that where $g$ is a generator of a finite group of order $p$. Like bilinear pairings, the discrete logarithm problem is considered difficult to solve efficiently using classical algorithms, thereby providing a secure foundation.

Shor's Algorithm and it's Potential in Quantum Computing

Shor's Algorithm is a quantum algorithm that can efficiently factor large composite numbers into their prime factors and solve the discrete logarithm problem, both in polynomial time. If a sufficiently powerful quantum computer were built, it would be capable of running Shor's Algorithm efficiently, thereby rendering the cryptographic systems based on these mathematical problems insecure.

Dealing with the NP Problem Misconception

It's crucial to clarify a common misunderstanding: factoring and the discrete logarithm problem are not NP-complete problems. Shor's Algorithm solves them in polynomial time on a quantum computer, but these problems are not classified under the NP-complete set. Solving these problems efficiently does not imply that all problems in NP can be solved efficiently.

Threats on zkSNARKs

1. Security Breach: If a powerful enough quantum computer is developed, the zk-SNARKs schemes based on bilinear pairings or the discrete logarithm problem would become insecure. This could have vast implications for blockchain technology, secure data sharing, and more.
2. Shift to Quantum-Resistant Algorithms: Cryptographers are already researching post-quantum cryptographic algorithms that are believed to be secure against the capabilities of a quantum computer. Systems like lattice-based cryptography are being considered as potential replacements for current zkSNARK systems.

Enter Lattice Crypto

Lattice-based cryptography is founded upon the hardness of problems in lattice theory, a branch of mathematics. A lattice is a set of all integer linear combinations of basis vectors. The security of lattice-based cryptography is based on the difficulty of problems like the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). In contrast to traditional cryptography, which often relies on the hardness of factoring large numbers or solving discrete logarithms, lattice-based cryptography is believed to be resistant to quantum attacks.

CRYSTALS: A Game-Changing Framework

CRYSTALS (Cryptographic Suite for Algebraic Lattices) is a framework that includes both key encapsulation mechanisms (KEMs) and digital signatures, aiming to provide a comprehensive suite of tools that are secure against quantum attacks. Developed by researchers in the field, it is one of the cryptographic systems being considered for standardization by NIST. CRYSTALS offers both encryption schemes like Kyber and digital signature algorithms like Dilithium.

TrueID on Dilithium : A Standardized Digital Signature Algorithm

In order to make TrueID's privacy-preserving feature true to every sense of it's word, we are currently pushing applied crypto research to harness the power of Dilithium to give the world, the most secure Proof-Of-Identity ever developed.

Dilithium is the digital signature component of the CRYSTALS suite and is one of the candidates for post-quantum cryptographic standardization.