Cryptographic algorithms as interactive and non-interactive proofs
This article aims to reach a conclusion and spread awareness about the interactive cryptographic systems and non-interactive cryptographic systems and the common difference that differentiate the two. The algorithms to be discussed in this article are Diffie Hellman (DH), Rivest Shamir Adleman (RSA), Schnorr Signature Scheme, Schnorr Identification Scheme, Digital Signature Algorithm (DSA), and FIAT Shamir.
Introduction
The debate remains whether the interactive cryptosystem or non-interactive cryptosystem is better. In this article, we will minimize the discussion by stating some facts and clarity based on these two systems. Let’s first go through some of the basic overviews:
In the symmetric cryptographic system, the sender and receiver use one key, or it is better to say they exchange one secret key to encrypt and decrypt at both sides. In an asymmetric cryptographic system, the sender and receiver use two separate keys at both ends. The sender uses the receiver’s public key to encrypt the message, and only the receiver can decrypt it using their private key. Let’s further read how these systems differentiate and what is more to the cryptographic system than just message passing.
Trusted system
A trusted system is a communication channel through which information is sent from source to destination but without opening it to the channel. In a cryptographic system, a trusted system has a broad meaning, but the root cause is the protection and security of keys from theft.
Interactive proof system
It is an abstract system with two parties; a prover and a verifier. The communication between these two parties is in terms of computation, known as an interactive system. In the interactive proof system communication, it is deduced that the prover has unlimited resources but cannot be trusted, whereas the verifier has fewer resources but is always honest. Therefore, an interactive proof system is based on trust and honesty.
Messages are exchanged between the verifier and prover, and the way it works is when the prover states something, the verifier verifies it until has itself convinced that the statement is correct and the prover is telling the truth.
Most of the interactive proof systems depend upon the verifier’s random choices ability. The verifier sends an unexpected challenge, and the prover utilizing the random set has to create proof. The verifier then verifies. The verifier can inquire repeatedly. It is the reason that this system is called an interactive proof system.
The interactive proof system has two main properties:
- Completeness: Completeness means that the prover can prove anything that is right.
2. Soundness: Soundness is when the prover cannot prove anything that is wrong.
Non-interactive proof system
To make the communication one-way and deterministic, non-interactive proof systems emerged. The non-interactive systems have no direct interaction between the prover and verifier. It is done to make a trust-less system.
Unlike the interactive proof system, The verifier does not send a random set, but the system relies on an oracle model as a way to prove and verify. This Random Oracle Model (ROM) is called a theoretical black box that responds to a query with a random response. Both the prover and the verifier look up the model for their reference strings. In this case, the verifier does not inquire the same message repeatedly from the prover. This approach of a non-interactive proof system is called deterministic.
The interactive proof system has two main properties:
- Completeness: Completeness means that the verifier, without a doubt, will be convinced of the fact.
2. Soundness: Soundness is that the prover without cheating can convince the verifier that the statement is true.
Why do we need proof systems:
When people use services or products, they require proof that the working behind it or the product made is authentic, its documents, and the process has been validated or not. These queries are best tackled using proof systems. Proofs and verifications are made without sharing any additional or personal information to satisfy such questions. They are stated over interactive and non-interactive proof systems.
Algorithms implementation based on the difference between the two systems
We will start looking at the algorithms based on the differences based on the interactive and non-interactive approaches.
Diffie Hellman:
Diffie Hellman is a secure key-exchanging protocol. This method is based on Non-Interactive Key Exchange (NIKE). NIKE is a cryptographic procedure that allows the two parties who know each others’ public keys to settle on a shared symmetric variable that does not require any interaction and is available to both. Its properties are listed below:
- The algorithm does not share any random number to any side of the communicators.
- No challenges are presented to be validated.
- It does not authenticate any side of the party.
- It provides Encryption.
- It includes the identification of the two parties.
- There is a key generation process involved in DH.
- No signatures are created or validated based on the DH algorithm.
Rivest Shamir Adleman:
The RSA algorithm is the all-rounder algorithm that can be used for data encryption, key exchange, and signature. It is an asymmetric algorithm it uses a pair of keys. RSA algorithm is widely used for a non-interactive approach for cryptography.
The public key is shared publicly while the private key is not shared, and know that the public key available to the verifier and used for Encryption does not yield a private key. Below are the properties discussed of RSA:
- The algorithm does not share any random number to any side of the communicators.
- No challenges are presented to be validated.
- It authenticates the two parties associated with the communication.
- It provides Encryption.
- It includes the identification of the two parties.
- It also includes signature generation.
- There is a key generation process involved in RSA.
Digital Signature Algorithm:
Digital Signature Algorithm (DSA) has two operations; Signature generation and signature verification. It is an asymmetric signature generation algorithm. It is a non-interactive system. The signer takes a random value for each signature, and the verifier verifies it using multi-exponentiation. The verifier uses the signed message, signer’s public key, and signature to verify. But no challenge is given to the prover by the verifier.
- It does not perform Encryption
- It can identify the two parties communicating.
- It can authenticate the prover and verifier.
- It is used for signature generation and verification.
- It does a key exchange between the prover and verifier.
Schnorr Signature Scheme:
Schnorr signature scheme is the most efficient and secure scheme, more than RSA and DSA. It has non-interactive proof of the system. The challenge in the Schnorr Identification scheme is replaced by randomness. The random integer is added in the signature while generating a signature for each message. This scheme is more or less a version of FIAT Shamir. Schnorr signature scheme is also used for multiple signatures generation and verification. Some properties of the Schnorr Signature Scheme are listed as:
- It can be used for Encryption
- It can be used for the identification of two parties
- It can help authenticate.
- It is used for signature generation and verification.
Schnorr Identification Scheme:
Schnorr identification scheme is a type of exchange protocol with a prover and a verifier. The prover has the public and secret keys. In comparison, the verifier keeps the prover’s public key copy. This scheme works in an interactive system where the verifier challenges the prover. The prover sends back the response, and the verifier verifies.
It has the same properties as the Schnorr Signature Scheme. However, it is being modified, and there might be an upgrade added to Schnorr that ECDSA (Elliptic Curve Digital Signature Algorithm) lacks.
FIAT Shamir
FIAT Shamir is a type of non-interactive schnorr signature scheme. Both methods provide the solution to identification problems. However, in FIAT Shamir, the significant computation is done by the prover, whereas in the Schnorr signature scheme, the main calculation is done by both the prover and the verifier.
A few of the FIAT Shamir properties are listed below:
- It is not used for Encryption.
- It is used for signature generation and verification.
- It is used for identification problem-solving.
- It can not be used for authentication.
- It does not generate keys or exchanges in the protocol.
Analysis
Conclusion
To quickly overview all algorithms, use some Parameters, Public keys, Private keys as inputs, some exchange the keys for Encryption, some algorithms exchange the keys for proving and verification of the data. All the algorithms do not differ much, except for using the direct channel of communication or indirect.
The interactive and non-interactive systems can be distinguished using a single entity in between. The distinction strictly depends on whoever generates the critical number, making it interactive and non-interactive.
In the interactive trusted systems, the prover commits a statement, and the verifier sends the challenge to inquire if the prover has integrated a reasonable solution in response to that commitment. The prover using that challenge sends a reply (Result) to the verifier. The verifier verifies if the prover has sent the correct solution and has used the given challenge or not.
In the non-interactive trusted system, the verifier and the prover do not interact directly. Instead, an entity like a storage box is used in the middle, which has the resources available required by both the prover and verifier. This middle entity is known as Random Oracle Model (ROM). You can read more about ROM here.
Also check out this article related to Mina Blockchain: https://xord.solutions/mina-lightest-blockchain/
References
- Trusted System (2022), Wikipedia https://en.wikipedia.org/wiki/Trusted_system
- What Are the Security Considerations When Choosing A Root of Trust Solution?,(2020),Prof. Yehuda Lindell https://www.unboundsecurity.com/blog/the-basic-root-of-trust-in-cryptographic-infrastructure/
- Interactive proof system, (2022), Wikipedia https://en.wikipedia.org/wiki/Interactive_proof_system
- What is the difference between Completeness and Soundness in first-order logic?, (2012), Mathexchange.com https://math.stackexchange.com/questions/105575/what-is-the-difference-between-completeness-and-soundness-in-first-order-logic
- Interactive and Non-Interactive Proofs of Knowledge, (2012), Olivier Blazy https://tel.archives-ouvertes.fr/tel-00768787/file/thesis.pdf
- Comparison: Fiat-Shamir, GQ, and Schnorr https://ebrary.net/134584/computer_science/comparison_fiat_shamir_schnorr
