7. Advanced Topics

 

Advanced Topics

Post-Quantum Cryptography

• Post-quantum cryptography refers to cryptographic algorithms that are secure against attacks by quantum computers.

NTRUEncrypt

• NTRUEncrypt is a lattice-based public key cryptosystem that is believed to be secure against attacks by quantum computers.
• Key Generation: Choose parameters \( N, p, q \) where \( N \) is a product of three distinct prime numbers, and \( p, q \) are smaller integers. Generate a random polynomial \( f(x) \) with coefficients in \( \{-1, 0, 1\} \) of degree less than \( N \). Compute \( g(x) = (1 + x)^p \mod f(x) \), and \( h(x) = (1 + x)^q \mod f(x) \). The public key is \( (N, p, q, h(x)) \), and the private key is \( f(x) \).
• Encryption: To encrypt a message \( m \), choose a random polynomial \( r(x) \) with coefficients in \( \{-1, 0, 1\} \) of degree less than \( N \). Compute \( c(x) = m + 2r(x) \mod p \).
• Decryption: To decrypt a ciphertext \( c(x) \), compute \( c(x) \times f(x) \mod p \), and use the result to recover the original message \( m \).

Zero-Knowledge Proofs

• Zero-knowledge proofs are protocols used to prove the validity of a statement without revealing any information beyond the validity of the statement itself.

Schnorr Protocol

• The Schnorr protocol is a zero-knowledge proof protocol for proving knowledge of a discrete logarithm without revealing the logarithm itself.

Algorithm Steps:

1. Setup: Generate a large prime number \(p\), a generator \(g\) of the multiplicative group modulo \(p\), and a secret key \(x\).
2. Commitment: Choose a random number \(r\) and calculate \(R = g^r \mod p\). Send \(R\) to the verifier.
3. Challenge: The verifier sends a challenge \(c\) to the prover.
4. Response: The prover calculates \(s = r + cx \mod (p-1)\) and sends \(s\) to the verifier.
5. Verification: The verifier checks if \(g^s \equiv R \cdot y^c \mod p\) holds, where \(y = g^x \mod p\).

Homomorphic Encryption

• Homomorphic encryption is a form of encryption that allows computation on ciphertexts, resulting in an encrypted result which, when decrypted, matches the result of the operations performed on the plaintext.

Paillier Cryptosystem

• The Paillier cryptosystem is a partially homomorphic encryption scheme, meaning it supports certain algebraic operations on ciphertexts.
• Key Generation: Choose two large prime numbers \(p\) and \(q\). Compute \(n = p \times q\) and \(\lambda = \text{lcm}(p-1, q-1)\). Select a random \(g\) such that \(g^n \mod n^2 = 1\). The public key is \((n, g)\) and the private key is \(\lambda\).
• Encryption: To encrypt a message \(m\), choose a random \(r\) such that \(0 < r < n\) and compute \(c = g^m \times r^n \mod n^2\).
• Decryption: To decrypt a ciphertext \(c\), compute \(L(c^\lambda \mod n^2) \times \text{lcm}(\lambda, n) \mod n\), where \(L(x) = \frac{{x - 1}}{n}\).
• Homomorphic Properties: Paillier encryption is additively homomorphic, meaning given ciphertexts \(c_1 = g^{m_1} \times r_1^n\) and \(c_2 = g^{m_2} \times r_2^n\), we can compute \(c_3 = c_1 \times c_2 \mod n^2\) such that \(c_3 = g^{m_1 + m_2} \times (r_1 \times r_2)^n\).

Blockchain and Cryptocurrencies

• Blockchain is a distributed ledger technology that enables secure and transparent record-keeping of transactions across a network of computers.
• Cryptocurrencies are digital or virtual currencies that use cryptography for security and operate independently of a central authority.

Blockchain

• Blockchain is a distributed ledger technology that enables secure and transparent record-keeping of transactions across a network of computers.
• Blocks: Each block contains a list of transactions, a timestamp, and a reference to the previous block, forming a chain of blocks.
• Transactions: Transactions represent the transfer of digital assets between users. Each transaction includes the sender's address, receiver's address, and amount transferred.
• Hashing: Blocks are linked together using cryptographic hashes. Each block contains the hash of the previous block, ensuring the integrity and immutability of the blockchain.
• Consensus Mechanisms: Consensus mechanisms are used to achieve agreement among network participants on the validity of transactions and the order of blocks. Examples include Proof of Work (PoW) and Proof of Stake (PoS).

---

Laboratory Activities

Lab 1: Implementing NTRUEncrypt in Python

import numpy as np
from numpy.polynomial import Polynomial as P

def generate_keys(N, p, q):
    # Generate random polynomial f(x)
    f_coeffs = np.random.choice([-1, 0, 1], size=N+1)
    f = P(f_coeffs.tolist())

    # Compute g(x) and h(x)
    g = (P([1, 1])**p) % f
    h = (P([1, 1])**q) % f

    public_key = (N, p, q, h)
    private_key = f

    return public_key, private_key

def encrypt(public_key, m):
    N, p, q, h = public_key
    r_coeffs = np.random.choice([-1, 0, 1], size=N+1)
    r = P(r_coeffs.tolist())
    c = (m + 2*r) % p
    return c

def decrypt(public_key, private_key, c):
    N, p, q, _ = public_key
    f = private_key
    m = (c * f) % p
    return m

# Parameters
N = 7
p = 3
q = 5

# Generate keys
public_key, private_key = generate_keys(N, p, q)

# Message
m = P([2, 0, -3, 0, 1])

# Encrypt
c = encrypt(public_key, m)

# Decrypt
decrypted_m = decrypt(public_key, private_key, c)

print("Original Message:", m)
print("Encrypted Message:", c)
print("Decrypted Message:", decrypted_m)

This lab demonstrates the implementation of the NTRUEncrypt scheme in Python.

Lab 2: Implementing Schnorr Protocol for Zero-Knowledge Proofs in Python

import random

def schnorr_protocol_setup():
    p = 23
    g = 5
    x = random.randint(2, p-2)
    return p, g, x

def schnorr_protocol_commitment(g, p):
    r = random.randint(1, p-1)
    R = pow(g, r, p)
    return r, R

def schnorr_protocol_response(p, x, r, c):
    s = (r + c * x) % (p-1)
    return s

def schnorr_protocol_verify(g, p, R, y, c, s):
    left = pow(g, s, p)
    right = (R * pow(y, c, p)) % p
    return left == right

# Simulation
p, g, x = schnorr_protocol_setup()
y = pow(g, x, p)  # Public key
r, R = schnorr_protocol_commitment(g, p)
c = random.randint(1, 100)  # Challenge
s = schnorr_protocol_response(p, x, r, c)
verification_result = schnorr_protocol_verify(g, p, R, y, c, s)

print("Verification Result:", verification_result)

This lab demonstrates a simulated zero-knowledge proof in Python.

Lab 3: Implementing Paillier Homomorphic Encryption in Python

import random
import math

def generate_keypair(bits):
    p = generate_prime(bits)
    q = generate_prime(bits)
    N = p * q
    lam = lcm(p-1, q-1)
    g = N + 1
    return (N, g), lam

def generate_prime(bits):
    while True:
        p = random.getrandbits(bits)
        if is_prime(p):
            return p

def is_prime(n, k=5):
    if n <= 3:
        return n == 2 or n == 3
    if n % 2 == 0:
        return False
    s, d = 0, n - 1
    while d % 2 == 0:
        s, d = s + 1, d // 2
    for _ in range(k):
        x = pow(random.randint(2, n - 1), d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def lcm(a, b):
    return abs(a * b) // math.gcd(a, b) if a and b else 0

def encrypt(pk, plaintext):
    N, g = pk
    r = random.randint(1, N - 1)
    return (pow(g, plaintext, N ** 2) * pow(r, N, N ** 2)) % (N ** 2)

def decrypt(pk, sk, ciphertext):
    N, _ = pk
    lam = sk
    return (pow(ciphertext, lam, N ** 2) - 1) // N * lam % N

def homomorphic_addition(ciphertext1, ciphertext2, pk):
    N, _ = pk
    return (ciphertext1 * ciphertext2) % (N ** 2)

# Parameters
bits = 128

# Generate keys
public_key, private_key = generate_keypair(bits)

# Encrypt
m1 = 10
m2 = 20
c1 = encrypt(public_key, m1)
c2 = encrypt(public_key, m2)

# Homomorphic addition
c3 = homomorphic_addition(c1, c2, public_key)

# Decrypt
result = decrypt(public_key, private_key, c3)

print("Result of Homomorphic Addition:", result)

This lab demonstrates the implementation of Paillier homomorphic encryption in Python.

Lab 4: Implementing a Simple Blockchain in Python

import hashlib
import json
from time import time

class Blockchain:
    def __init__(self):
        self.chain = []
        self.current_transactions = []

        # Create the genesis block
        self.new_block(previous_hash='1', proof=100)

    def new_block(self, proof, previous_hash=None):
        block = {
            'index': len(self.chain) + 1,
            'timestamp': time(),
            'transactions': self.current_transactions,
            'proof': proof,
            'previous_hash': previous_hash or self.hash(self.chain[-1]),
        }

        # Reset the current list of transactions
        self.current_transactions = []

        self.chain.append(block)
        return block

    def new_transaction(self, sender, recipient, amount):
        self.current_transactions.append({
            'sender': sender,
            'recipient': recipient,
            'amount': amount,
        })
        return self.last_block['index'] + 1

    @staticmethod
    def hash(block):
        block_string = json.dumps(block, sort_keys=True).encode()
        return hashlib.sha256(block_string).hexdigest()

    @property
    def last_block(self):
        return self.chain[-1]

# Instantiate the Blockchain
blockchain = Blockchain()

# Example transactions
blockchain.new_transaction('Alice', 'Bob', 10)
blockchain.new_transaction('Bob', 'Charlie', 5)

# Mine a new block
last_block = blockchain.last_block
last_proof = last_block['proof']
proof = blockchain.proof_of_work(last_proof)

blockchain.new_block(proof)

print("Blockchain:", blockchain.chain)

This lab demonstrates the implementation of a simple blockchain in Python.