1.3.1. Variables

s = [1, 3, 35, 9, 27, 30]

1.3.2. R1CS Matrices

1.3.3. Combined Matrices

[0 1 0 0 0 0]
[0 0 0 1 0 0]
[0 1 0 0 1 0]
[5 0 0 0 0 1]

[0 1 0 0 0 0]
[0 1 0 0 0 0]
[1 0 0 0 0 0]
[1 0 0 0 0 0]

[0 0 0 1 0 0]
[0 0 0 0 1 0]
[0 0 0 0 0 1]
[0 0 1 0 0 0]

1.4.1. Interpolation of Each Column

1.4.2. Final Polynomials

A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

2.2.1. Generate Public & Private Keys:

2.2.2. Encrypt & Decrypt:

1. Encryption
   

   When we encrypt a message m, we compute: \( c = m^e \pmod{n} \)

2. Decryption
   

   To decrypt, we compute: \( D(c) = c^d \pmod{n} \)

2.2.3. Mathematical Backbone:

1. i. Euler's Theroem
   

   Euler's Theorem ensures that the encryption and decryption process is correct. It gives us a rigorous proof that decrypting after encrypting returns the original message without leaking the private key. Euler's Theorem says that if \( gcd(m, n) = 1 \) (m and n are co-prime) then: \( m^phi(n) == 1 (\pmod{n}) \). The \( \phi(n) \) here, which is called Euler's totient of n, counts how many integers from 1 up to n-1 are coprime to n. (The breakability of number n) Since here n can be factorized into \( p \times q \), the number of integers coprime to n ends up being \( (p-1)(q-1) \).

   The math of Euler's Theorem ensures that no matter what message m you start with, encrypting with e, n and then decrypting with d returns m. By choosing d and e so that: \[ d \times e \equiv 1 \pmod{\phi(n)} \]

   we have: \[ m^{e d} = m^{1 + k \phi(n)} = m \times m^{k \phi(n)} \equiv m \times 1 = m \pmod{n} \]

   This ensures that: Encrypting \(m^e \mod{n} \) and then decrypting \(c^d \mod{n}\) returns the original message m.

2. ii. Large Number Cannot be Factorized Efficiently (Trapdoor Function)
   

   The trapdoor function ensures that even though every one knows n and e, they cannot comopute d (the "key" to decrypt) without factoring n. The difficulty in factoring large numbers makes RSA safe to use in practice.

2.2.4. Multiplicative Homomorphic Property of RSA

1. Homomorphic Encryption Basics
   
   • Homomorphic Operations: Two operations are homomorphic if applying them in either order yields the same result.
   • Homomorphic Encryption: Enables computations on ciphertexts that correspond to meaningful operations on the plaintexts.
2. Multiplicative Homomorphism in RSA
   

   For RSA, the homomorphic property specifically pertains to multiplication. Formally, this can be expressed as:

   \[ E(x) \times E(y) \equiv E(x \times y) \pmod{n} \]

   Where:

   • \( E(m) = m^e \mod n \) is the RSA encryption function.
   • \( x \) and \( y \) are plaintext messages.
   • \( n \) is the RSA modulus.
3. Step-by-Step Explanation
   
   1. Encryption of Two Messages:
      • Encrypt message \( x \): \[ E(x) = x^e \mod n \]
      • Encrypt message \( y \): \[ E(y) = y^e \mod n \]
   2. Multiplying the Ciphertexts: \[ E(x) \times E(y) = (x^e \mod n) \times (y^e \mod n) \mod n \] Since multiplication is distributive over modular arithmetic: \[ E(x) \times E(y) \equiv x^e \times y^e \mod n \] \[ E(x) \times E(y) \equiv (x \times y)^e \mod n \]
   3. Encryption of the Product:
      • Encrypt the product \( x \times y \): \[ E(x \times y) = (x \times y)^e \mod n \]
   4. Equivalence: \[ E(x) \times E(y) \equiv E(x \times y) \mod n \] This shows that multiplying the ciphertexts \( E(x) \) and \( E(y) \) results in the ciphertext of the product \( E(x \times y) \).
4. Implications for Zero-Knowledge Proofs
   

   This homomorphic property allows for zero-knowledge proofs of multiplication. Here's how it works:

   1. Prover's Knowledge:
      • The prover knows secret values \( x \) and \( y \).
      • The prover computes their product \( x \times y \).
   2. Prover Sends Encrypted Values:
      • \( a = E(x) \)
      • \( b = E(y) \)
      • \( c = E(x \times y) \)
   3. Verifier's Check:
      • The verifier checks if: \[ (a \times b) \mod n \equiv c \mod n \]
      • If the equality holds, the verifier is convinced that \( c \) is indeed the encryption of \( x \times y \).
   4. Privacy Preserved:
      • The verifier learns only the encrypted product \( c \).
      • The actual values of \( x \), \( y \), and \( x \times y \) remain hidden.

   To ensure robustness, the prover must also prove - without revealing \( x \) that \(a\) really is the encryption of some valid plaintext \(x \) and so on. To ensure that each ciphertext really corresponds to a well-defined plaintext Here is an example of a Zero-Knowledge Proof:

   Example for Robustness: Prover try to convinces Verifier that "I know a \( x \) for which \( a = x^e \mod{n} \)." without revealing \( x \).

   1. 1. Setting
      
      • RSA modulus: \( n \) (unknown factorization).
      • Public exponent: \( e \).
      • Ciphertext: \( a \equiv x^e \pmod{n} \).
      • Prover knows \( x \), wants to prove \( a = x^e \pmod{n} \) without revealing \( x \).
      • Verifier knows \(n \), \( e \), and \( a \).
   2. 2. Protocol Outline
      
      1. Prover picks a random \( r \) in \([1, n-1] \) and computes: \( T := r^e \mod{n} \), After that prover sends \( T \) to Verifier.
      2. Verifier chooses a random challenge \( c \) and sends it to Prover.
      3. Prover computes: \( z := r * (x^c) \mod{n} \), And then Prover sends \( z \) to Verifier.
      4. Verifier checks: \( z^e = T * a^c \pmod{n} \)
   3. 3. Why It Works
      
      • Expand the left side: \( z^e = (r * x^c)^e = r^e * x^{c e} \).
      • Expand the right side: \( T * a^c = (r^e) * (x^e)^c = r^e * x^{e c} \).
      • Since both expansions are \( r^e * x^{c e} \), equality holds exactly if \( a \equiv x^e \mod{n} \).
   4. 4. Zero-Knowledge Aspect
      
      • Prover never reveals \( x \); only sends random \( T \) and the response \( z \).
      • The random \( r \) hides \( x \) from the Verifier.
      • If Prover did not know \( x \), producing correct \( z \) for a random \( c \) would be infeasible.
      • Verifier gains no information about \( x \) itself - only the certainty that Prover knows it.
5. Connection to zk-SNARKs and Elliptic Curves
   
   • Zero-Knowledge Proofs: The ability to prove computations on encrypted data without revealing the data itself is foundational for zero-knowledge proofs.
   • Elliptic Curves in zk-SNARKs: While RSA uses multiplicative groups, zk-SNARKs often leverage the algebraic structure of elliptic curves to achieve more efficient and versatile proofs.
   • Foundation for Advanced Cryptography: This property is an essential concept that leads to the development and understanding of more sophisticated systems like zk-SNARKs, which utilize different mathematical structures for enhanced functionality.

2.3.1. Forward Computation

2.3.2. Inverse Problem: Elliptic Curve Discrete Logarithm Problem (ECDLP)

2.4.1. Zero-Knowledge Proofs of Calculations

2.4.2. Properties Leveraged

1. Linear Verification with Traditional ECC
   
   • Linear Relationships:
     • Given:
       • \( P = pG \)
       • \( Q = qG \)
       • \( R = rG \)
     • Verification:
       • Check if \( 5P + 7Q = 11R \).
       • This corresponds to verifying \( 5p + 7q = 11r \) without knowing \( p \), \( q \), or \( r \).
   • Why It Works:
     • Point Addition and Scalar Multiplication:
       • Elliptic curve operations preserve linear relationships.
     • Security Aspect:
       • Due to the ECDLP, knowing \( P \), \( Q \), \( R \), or \( G \) doesn't reveal \( p \), \( q \), or \( r \).
2. Multiplicative Relations Verified with Pairings
   
   • Pairings on Elliptic Curves:
     • Definition: A pairing \( e \) is a function that maps two points on an elliptic curve to an element in a finite field.
     • Bilinearity Property:
       • \( e(aP, bQ) = e(P, Q)^{ab} \).
       • This property allows the pairing to convert point multiplications into exponentiations.
   • Verifying Multiplicative Relationships:
     • Objective: Verify \( p \times q = r \) without revealing \( p \), \( q \), or \( r \).
     • Given:
       • \( P = pG \)
       • \( Q = qG \)
       • \( R = rG \)
     • Verification Steps:
       1. Compute \( e(P, Q) \):
          • \( e(P, Q) = e(pG, qG) = e(G, G)^{pq} \).
       2. Compute \( e(G, R) \):
          • \( e(G, R) = e(G, rG) = e(G, G)^{r} \).
       3. Compare:
          • If \( e(P, Q) = e(G, R) \), then it follows that \( pq = r \).
     • Explanation:
       • The pairing function's bilinearity translates the multiplicative relationship into a form that can be compared in the finite field.