Advanced Cryptography Concepts via Classical to Post-Quantum

Cryptography has a strange history for a field that’s now load-bearing for the entire internet. A lot of the number theory underneath it was developed by mathematicians who were doing pure math for its own sake, with zero interest in secrets or spies. Then, starting in the 1970s, people realized that certain “hard” problems in number theory (the kind that are easy to state but brutal to solve at scale) were exactly what you needed to build systems where two strangers could agree on a secret over a public channel, or where you could prove your identity without ever handing over a password. This post is a walk through that stack, from the classical number-theoretic foundations, through the protocols built on top of them, and finally into the post-quantum schemes that exist because a sufficiently large quantum computer would tear a hole through most of what came before.

I’ll keep code snippets around where they help make an algorithm concrete, but the real point of each section is the “why”: why the underlying problem is believed to be hard, what happens when the assumptions get violated, and how the pieces fit together into the systems you actually use every day (TLS, signed software updates, blockchains, whatever).

Mathematical Foundations of Modern Cryptography

Number Theory and Cryptography

It’s worth pausing on why number theory, of all things, turned out to be the right tool for this job. Cryptography needs a specific shape of problem: something that’s cheap to compute in one direction and (as far as anyone can tell) enormously expensive to invert, unless you happen to know a secret shortcut. Mathematicians call these “trapdoor” functions, and it turns out modular arithmetic over integers, and later over other algebraic structures, is a rich source of them. Multiplying two large primes together is trivial. Taking the product and recovering the original primes is not, at least not with any algorithm we know of. That asymmetry, computable one way, intractable the other way, is the entire foundation everything else in this post rests on. If someone ever finds a fast general algorithm for factoring or for the discrete logarithm problem, a huge chunk of the internet’s security model breaks overnight. That’s not a hypothetical worry either; it’s precisely what quantum computers threaten to do, which is why the last third of this post exists at all.

Prime Numbers and Factorization

RSA, still one of the most deployed public-key systems on the planet despite being nearly fifty years old, leans entirely on the fact that factoring is hard. Here’s the intuition for why: pick two large random primes, p and q, and multiply them to get n = p * q. Given n alone, finding p and q back out requires (as far as we know) something close to exponential effort as the numbers get bigger, even though generating n in the first place took a fraction of a second. This gap between the cost of the forward operation and the cost of the reverse operation is what lets you publish n to the whole world as part of your public key while keeping p and q secret.

def generate_rsa_keys(bits=2048):
    p = generate_large_prime(bits // 2)
    q = generate_large_prime(bits // 2)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = mod_inverse(e, phi)
    return ((n, e), (n, d))

A few details in that snippet are doing more work than they look like they are. phi is Euler’s totient of n, which for a product of two distinct primes works out to (p-1)(q-1). It counts how many integers less than n are coprime to n, and it’s the key fact that lets Euler’s theorem guarantee d and e are mutual inverses modulo phi(n). That inverse relationship, e * d ≡ 1 (mod phi(n)), is exactly what makes encryption and decryption undo each other: raising a message to the e-th power and then to the d-th power modulo n returns you to where you started, because of how modular exponentiation interacts with the group structure Euler’s theorem describes.

The choice of e = 65537 looks arbitrary until you know the reasoning. It’s 2^16 + 1, which in binary is a single 1 bit followed by fifteen 0s and a trailing 1, making modular exponentiation with it fast via repeated squaring. It’s also prime, so it’s very likely to be coprime with phi(n) (a requirement for the inverse d to exist), and it’s large enough to avoid a handful of low-exponent attacks that plagued early, careless RSA implementations that used e = 3. None of this is a coincidence; it’s the accumulated result of decades of people finding attacks and the community converging on parameters that dodge them.

The actual danger in practice is almost never “someone factored a 2048-bit modulus directly.” It’s much more mundane: bad randomness when generating p and q (if two RSA keys anywhere in the world happen to share a prime factor, anyone can recover both keys instantly via a GCD computation), improper padding that leaks information about plaintexts, or side-channel leakage from how long modular exponentiation takes on real hardware. RSA-the-math-problem is solid; RSA-the-implementation has a long history of getting undermined by details that have nothing to do with factoring at all. That distinction, between a hard problem and a hardened implementation of it, comes up constantly in cryptography and is worth internalizing early.

Discrete Logarithm Problem

A second family of systems, including Diffie-Hellman key exchange and ElGamal encryption, relies on a different hard problem: the discrete logarithm problem, or DLP. The setup: you work in the multiplicative group of integers modulo a large prime p, pick a generator g (an element whose powers cycle through, ideally, the entire group), and consider the map x -> g^x mod p. Computing that forward is cheap, just repeated squaring again. But going backward, given h = g^x mod p, finding x is believed to require something close to exponential time in the size of p for a well-chosen group. That’s the discrete logarithm problem:

Given a prime modulus p, a generator g and a value h, find x such that:

$$g^x \equiv h \pmod{p}$$

What makes this genuinely useful, rather than just another one-way function, is that it has a nice algebraic structure that supports key agreement between two people who’ve never met. That’s Diffie-Hellman, and it’s worth walking through because the trick is elegant: both parties agree publicly on p and g, then each picks a private random exponent and publishes only g raised to that exponent. Because exponentiation is commutative in the exponent ((g^a)^b = (g^b)^a = g^{ab}), each side can combine their own secret exponent with the other side’s public value and land on the exact same shared secret, g^{ab} mod p, without either of them ever having transmitted a, b, or the shared secret itself over the wire.

def diffie_hellman_key_exchange():
    p = large_prime
    g = primitive_root(p)
    a = random.randint(2, p-2)
    A = pow(g, a, p)
    b = random.randint(2, p-2)
    B = pow(g, b, p)
    s_alice = pow(B, a, p)
    s_bob = pow(A, b, p)
    return s_alice

An eavesdropper watching the whole exchange sees p, g, A, and B, and needs to somehow combine them into g^{ab} mod p without knowing a or b. That’s called the computational Diffie-Hellman problem, and while it’s not proven to be exactly as hard as the discrete logarithm problem, in practice cracking one without the other hasn’t happened, so the two are treated as equivalent for security purposes.

It’s worth noting the classic gap in plain Diffie-Hellman: it gives you confidentiality of the shared secret, but nothing about authentication. Without some separate mechanism to verify who you’re actually exchanging keys with, a man-in-the-middle can just run the protocol twice, once pretending to be you to the other party, once pretending to be the other party to you, and quietly relay (and read) everything in between. Real-world protocols like TLS bolt signatures on top of Diffie-Hellman specifically to close that hole, which is a good early example of a theme that runs through all of applied cryptography: a hard math problem gives you one property, but a usable protocol usually needs several properties stacked together, and it’s the seams between them where things go wrong.

Elliptic Curve Cryptography (ECC)

Elliptic curve cryptography solves a practical annoyance with RSA and classic Diffie-Hellman: as computers get faster and factoring/DLP attacks get better, you need to keep growing your key sizes, and those keys grow uncomfortably large. ECC gets you equivalent security with dramatically smaller keys (a 256-bit elliptic curve key is roughly comparable in strength to a 3072-bit RSA key), which matters a lot for things like mobile devices, smart cards, and any protocol where you’re paying for every byte on the wire.

The idea is to replace “integers modulo a prime” with a different algebraic structure: the points on an elliptic curve over a finite field. An elliptic curve over F_p is the set of points (x, y) satisfying:

$$ y^{2 = x}3 + a x + b \pmod{p} $$

plus a special “point at infinity” that acts as the identity element. What makes this useful for cryptography is that you can define an addition operation on these points (geometrically, draw a line through two points on the curve, find where it hits the curve a third time, and reflect across the x-axis) that turns the set of points into a group. Once you have a group, you get “scalar multiplication” for free: kP just means adding the point P to itself k times, computed efficiently via double-and-add, the elliptic-curve analog of repeated squaring.

That scalar multiplication is the trapdoor function here. Going from k and P to Q = kP is fast. Going backward, from P and Q to k, is the Elliptic Curve Discrete Logarithm Problem (ECDLP), and it’s believed to be considerably harder than the classic DLP for a comparably sized modulus, which is exactly why the key sizes can shrink so much while keeping the same security margin. There’s no known sub-exponential algorithm for ECDLP on a well-chosen curve, whereas the classic DLP and integer factorization both have sub-exponential algorithms (the number field sieve, roughly speaking) that just haven’t been beaten down to polynomial time yet. That extra structural resistance is the whole selling point of ECC.

ECDSA, the elliptic-curve signature scheme, builds directly on this. Signing hashes the message, picks a fresh random nonce k, computes a curve point from it, and combines everything with the private key into a signature pair (r, s):

def ecdsa_sign(message, private_key, curve):
    z = hash_message(message)
    k = generate_secure_random(1, curve.n - 1)
    R = curve.multiply(curve.G, k)
    r = R.x % curve.n
    s = (mod_inverse(k, curve.n) * (z + r * private_key)) % curve.n
    return (r, s)

That k deserves special attention because it’s the single most common way real-world ECDSA implementations get broken. The nonce has to be fresh and unpredictable for every single signature. If you ever reuse the same k for two different messages signed with the same key, an attacker who sees both signatures can do a bit of algebra on the two s equations and solve directly for the private key. This isn’t a theoretical concern: Sony famously got their PlayStation 3 signing key extracted this way because they used a static k instead of a random one, and various Bitcoin wallets have lost funds to the same mistake when their random number generators turned out to be weaker than assumed. The math of ECDSA is sound; the operational requirement of “never, ever repeat a nonce” is where the danger lives, which is exactly the same lesson as with RSA and bad prime generation. Modern deployments increasingly favor deterministic nonce derivation (RFC 6979) or newer signature schemes like EdDSA that are designed to make this whole class of mistake structurally impossible rather than merely discouraged.

Advanced Cryptographic Protocols

The number-theoretic foundations above give you primitives: encrypt, decrypt, sign, agree on a shared secret. The next layer up is protocols that combine those primitives to do something genuinely surprising, like proving a fact about a secret without revealing the secret, or computing on data you can’t actually read.

Zero-Knowledge Proofs

A zero-knowledge proof lets a prover convince a verifier that some statement is true (I know a password, I know a valid solution to this puzzle, this transaction is valid) without revealing anything beyond the bare fact that it’s true. That sounds almost paradoxical until you see the classic intuition pump: imagine a circular cave with a locked door that only opens with a secret word, connecting the two branches of a fork in the path. The prover walks in and randomly picks a branch. The verifier, standing outside where they can’t see which branch was chosen, shouts which branch they want the prover to come back out of. If the prover actually knows the secret word, they can always come out the requested side, going through the door if needed. If they don’t know the word, they only get it right half the time by luck. Repeat this enough times and the probability of the prover faking it through pure chance becomes vanishingly small, while the verifier never once learns the secret word itself. That’s the essence of every zero-knowledge protocol: completeness (a true statement can be proven), soundness (a false statement can’t be proven except with negligible probability), and zero-knowledge (the verifier learns nothing beyond validity).

ZK-SNARKs

The cave analogy is intuitive but interactive and inefficient for real use. ZK-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) compress that whole back-and-forth into a single short, non-interactive proof that anyone can verify quickly, which is why they’ve become the workhorse behind privacy coins and blockchain scaling systems. The “succinct” part is doing a lot of work in that acronym: the proof stays small and cheap to verify no matter how large or complex the computation being proven actually was.

Getting there involves a genuinely clever chain of transformations. First, whatever computation you want to prove (say, “I know the private inputs that make this circuit output true”) gets compiled into an R1CS, a Rank-1 Constraint System, which is just a way of expressing the computation as a set of quadratic equations over the wires of an arithmetic circuit. R1CS then gets converted into a QAP, a Quadratic Arithmetic Program, which re-expresses those same constraints as polynomial identities. This step matters because polynomials have a property integers and circuits don’t: you can check whether two polynomials are equal by testing them at a single random point, and if they agree there, they’re overwhelmingly likely to be identical everywhere. That’s the mathematical trick that lets you compress “verify thousands of constraints” down into “check one polynomial equation at one point,” which is where the succinctness actually comes from.

def zk_snark_prove(circuit, private_inputs, public_inputs):
    r1cs = circuit_to_r1cs(circuit)
    qap = r1cs_to_qap(r1cs)
    witness = compute_witness(qap, private_inputs, public_inputs)
    proof = generate_proof(witness, proving_key)
    return proof

The catch, and it’s a real one, is that most SNARK constructions need a trusted setup: a one-time generation of public parameters that involves some random secret values which must be destroyed afterward. If whoever ran that ceremony kept the secret, they could forge false proofs that verify as true. This is why real-world SNARK deployments run elaborate multi-party ceremonies where dozens of independent participants each contribute randomness, with the guarantee that the setup is secure as long as at least one participant honestly destroyed their share. Newer proof systems (STARKs, and some newer SNARK variants) trade a bit of proof size or verification speed to eliminate the trusted setup entirely, which is a meaningful security win in exchange for a real efficiency cost. That tradeoff, transparency versus succinctness, is one of the more active design tensions in the whole field right now.

Homomorphic Encryption

Zero-knowledge proofs let you prove things about secrets. Homomorphic encryption lets you compute on secrets directly, without decrypting them first. Concretely, a homomorphic scheme lets you take two ciphertexts, perform some operation on them, and get back a ciphertext that decrypts to the result of applying the corresponding operation to the original plaintexts, all without the party doing the computation ever seeing the plaintext at any point.

def fhe_operations(encrypted_data1, encrypted_data2, operation):
    if operation == 'add':
        result = homomorphic_add(encrypted_data1, encrypted_data2)
    elif operation == 'multiply':
        result = homomorphic_multiply(encrypted_data1, encrypted_data2)
    else:
        raise ValueError("Unsupported operation")
    return result

There’s an important distinction hiding in that “FHE” abbreviation. Partially homomorphic schemes support just one operation indefinitely (RSA, as a side effect of its multiplicative structure, is actually homomorphic under multiplication; Paillier encryption is homomorphic under addition). Somewhat homomorphic schemes support both addition and multiplication, but only up to a limited number of operations before accumulated noise destroys correctness. Fully homomorphic encryption (FHE), first realized by Craig Gentry in 2009 using lattice-based constructions, supports arbitrary computation, in principle any circuit at all, on encrypted data.

The reason this took until 2009 to solve, decades after the question was first posed, comes down to noise management. Most workable homomorphic schemes encrypt a message by burying it under a bit of random noise; that noise is what makes the ciphertext look indistinguishable from random to anyone without the key. Every homomorphic operation you perform on the ciphertext also amplifies that noise a little, and multiplication is especially rough on it, growing the noise multiplicatively rather than additively. Do enough operations in a row and the noise eventually overwhelms the signal, and decryption starts returning garbage. Gentry’s breakthrough was “bootstrapping”: periodically running the decryption circuit itself, homomorphically, to refresh a noisy ciphertext into a fresh low-noise one encrypting the same value, letting computation continue indefinitely. It’s a beautiful idea and also brutally expensive in practice, which is why FHE, despite being over fifteen years old now, still hasn’t seen wide production deployment; the computational overhead compared to plaintext operations is routinely several orders of magnitude. Homomorphic encryption is one of those rare cases in cryptography where the theoretical problem was solved well before the engineering caught up enough to make it practical, and a lot of current research is really just chasing that gap down.

Post-Quantum Cryptography

Everything up to this point (RSA, Diffie-Hellman, ECC) shares a quiet dependency: they’re all secure because factoring and discrete logarithms are hard for classical computers. In 1994, Peter Shor showed that a sufficiently large quantum computer can solve both problems in polynomial time. That’s not an incremental speedup, it’s a fundamentally different complexity class, and it means that the day a large enough fault-tolerant quantum computer exists, essentially every RSA and ECC key in the world becomes breakable in a feasible amount of time. Nobody has built a quantum computer anywhere near that scale yet, and there’s real debate about the timeline, but the encrypted traffic being captured and stored right now by adversaries with patience (“harvest now, decrypt later”) is already at risk for anything with a long confidentiality horizon. That threat is why post-quantum cryptography, systems based on problems believed to resist quantum algorithms too, has moved from academic curiosity to something NIST has actually standardized and organizations are actively migrating toward.

The problems below all have one thing in common: nobody has found a quantum algorithm anywhere close to Shor’s for solving them, and the structures involved (lattices, error-correcting codes, hash functions) are different enough in kind from “factor a number” that the same quantum trick doesn’t obviously transfer.

Lattice-Based Cryptography

Lattice problems are currently the most popular foundation for post-quantum schemes, and for good reason: they support rich functionality (encryption, signatures, even FHE, as mentioned above), they’ve held up well under decades of cryptanalysis, and they tend to be reasonably efficient. A lattice, in this context, is just the set of all integer linear combinations of some basis vectors in n-dimensional space, an infinite regular grid of points. The hard problems live in the geometry of these grids: given a description of the lattice, find the shortest non-zero vector in it (the Shortest Vector Problem), or given an arbitrary point in space, find the closest lattice point to it (the Closest Vector Problem). Both get intractable fast as the dimension grows, and critically, nobody has found a quantum algorithm that meaningfully helps.

NTRU Encryption

NTRU is one of the older lattice-based schemes, predating the current post-quantum standardization push by decades, and it works over rings of polynomials rather than plain integers, which is where a lot of its efficiency comes from. Key generation picks two “small” polynomials f and g (small meaning their coefficients are tiny compared to the modulus, which matters a lot for what follows), and combines them with a public modulus to produce the public key.

# Simplified NTRU key generation
def ntru_key_generation(N, p, q):
    f = generate_small_polynomial(N)
    g = generate_small_polynomial(N)
    while not is_invertible(f, q) or not is_invertible(f, p):
        f = generate_small_polynomial(N)
    f_q = polynomial_inverse(f, q)
    h = polynomial_multiply(p * g, f_q) % q
    return (h, f)

The security intuition is that recovering f and g from the public polynomial h alone is equivalent to finding an unusually short vector in a particular lattice built from the NTRU parameters, exactly the Shortest Vector Problem mentioned above. An attacker without the private key can compute with h all day but can’t easily separate it back into its small, structured factors. The person holding f and g, meanwhile, can decrypt efficiently precisely because they know the small polynomials that make the underlying lattice problem trivial for them and only them, which is the trapdoor. NTRU’s main practical appeal is speed: because it operates on polynomial rings with fast multiplication algorithms, it tends to outperform RSA and even some competing post-quantum schemes, which is why it’s been a perennial finalist in post-quantum standardization efforts even without ever becoming the single dominant choice.

Ring-LWE Encryption

Ring Learning With Errors is arguably the most influential post-quantum construction, forming the backbone of Kyber, the scheme NIST actually selected as its primary standard for post-quantum key encapsulation. The “Learning With Errors” name describes the underlying hard problem well: given a bunch of noisy linear equations, b = a*s + e where e is small random error, recover the secret s. Without noise, this is trivial linear algebra, just Gaussian elimination. With even a small amount of structured noise added to each equation, it becomes as hard as worst-case lattice problems, which is a genuinely remarkable reduction because it means breaking a random instance of LWE is provably at least as hard as solving the hardest instance of certain lattice problems, a much stronger guarantee than most cryptographic assumptions get.

# Simplified Ring-LWE encryption
def ring_lwe_encrypt(public_key, message, parameters):
    n, q, sigma = parameters
    a = public_key
    s = random_polynomial(n, q)
    e1 = sample_error(n, sigma)
    e2 = sample_error(n, sigma)
    b = (polynomial_multiply(a, s) + e1) % q
    m = encode_message(message, q)
    v = (polynomial_multiply(b, s) + e2 + m) % q
    return (b, v)

The “Ring” in Ring-LWE means the arithmetic happens over polynomial rings instead of plain integer vectors, the same move NTRU makes, and for the same reason: it dramatically shrinks key sizes and speeds up the arithmetic compared to working with plain (unstructured) LWE, at the cost of relying on the extra ring structure not introducing some exploitable weakness. So far that structure has held up under intense scrutiny, but it’s worth flagging as a genuine assumption layered on top of the base LWE hardness assumption, not a free lunch. The two error terms, e1 and e2, are what make this scheme probabilistic (encrypting the same message twice gives different ciphertexts) and are also, just like in FHE, a resource that gets consumed; parameters have to be tuned so the error stays small enough for correct decryption but large enough to keep the LWE problem hard, and that tension between correctness and security is a recurring design constraint across essentially all lattice-based cryptography.

Hash-Based Cryptography

If you want a post-quantum signature scheme whose security rests on the fewest possible assumptions, hash-based signatures are about as conservative as it gets: their security reduces essentially just to “this hash function is collision-resistant and preimage-resistant,” properties hash functions were already assumed to have long before anyone worried about quantum computers, and properties that survive quantum attacks reasonably well (Grover’s algorithm gives only a quadratic, not exponential, speedup against hash functions, so you just double your hash output size and you’re basically fine).

Merkle Signature Scheme

The catch with the underlying building block, one-time signature schemes like Lamport signatures, is right there in the name: a single keypair can only safely sign one message. Sign twice with the same one-time key and you leak enough information for a forger to sign arbitrary messages. Ralph Merkle’s insight was to generate a large batch of one-time keypairs upfront, then build a Merkle tree (a binary tree of hashes) over their public keys, using the tree’s single root hash as the actual long-term public key.

def merkle_sign(message, private_keys, tree):
    key_index = get_unused_key_index()
    private_key = private_keys[key_index]
    signature = one_time_sign(message, private_key)
    auth_path = generate_auth_path(tree, key_index)
    return (signature, key_index, auth_path)

To sign a message, you pick an unused one-time keypair, sign with it the normal way, and attach an “authentication path,” the sibling hashes up the tree, that lets a verifier recompute the path from that specific one-time public key up to the known root and confirm it belongs in the tree. This is genuinely elegant: it takes something fragile (a one-time key) and, by committing to a whole batch of them under one hash root, turns it into something that behaves like a many-time key from the outside. The obvious operational cost is that you have to track which keys have already been used and never reuse one, and the total number of signatures you can ever produce is capped by how many leaves you put in the tree at setup time. Modern descendants of this idea, like XMSS and SPHINCS+, refine the bookkeeping (SPHINCS+ notably manages to become “stateless,” removing the need to carefully track key usage, which is the single biggest operational footgun with the original scheme) but the Merkle-tree-over-one-time-keys core idea is exactly the same.

Code-Based Cryptography

The third major post-quantum family repurposes a tool built for a completely different problem: error-correcting codes, the same math that lets a CD survive a scratch or a satellite link survive noise. The McEliece cryptosystem, proposed all the way back in 1978, is actually the oldest scheme on this list, older than RSA-successor schemes people usually think of as “modern,” and it has an unusually long track record of resisting cryptanalysis, classical or quantum, for a scheme its age.

def mceliece_encrypt(public_key, message):
    G_pub, t = public_key
    m = message_to_vector(message)
    c1 = matrix_multiply(m, G_pub)
    e = generate_error_vector(len(c1), t)
    c = (c1 + e) % 2
    return c

The idea: pick a linear error-correcting code (classically a Goppa code) that has an efficient decoding algorithm known only to you, then disguise its generator matrix G by scrambling it with random invertible transformations before publishing the result as G_pub. Encryption takes the message, encodes it with the disguised matrix, and then deliberately adds a controlled amount of random error, t bit-flips worth. To anyone without the secret structure, decrypting means solving general syndrome decoding, decoding a linear code with no special structure to exploit, which is NP-hard in the worst case and has no known efficient algorithm, classical or quantum. The legitimate recipient, who knows the original undisguised Goppa code and its efficient decoder, can undo the scrambling, strip out the deliberately introduced errors using that decoder, and recover the message directly.

McEliece’s biggest practical drawback has nothing to do with its security margin and everything to do with its public key size: those disguised generator matrices are enormous, often hundreds of kilobytes to a megabyte, versus a few hundred bytes for RSA or ECC keys. That’s exactly why, even though McEliece has aged better than almost any other public-key scheme on this list, it never saw wide deployment until the quantum threat made people willing to eat the size cost. NIST’s post-quantum standardization process ended up selecting Classic McEliece as one of its finalists specifically because of this decades-long track record, even while acknowledging the ciphertext and key sizes make it a poor fit for constrained environments.

Practical Applications and Implementations

The primitives above are building blocks. The last piece worth covering is what happens when you want multiple mutually distrusting parties to compute something together, without any of them having to fully trust any of the others, or any single server, with the underlying secret data.

Secure Multi-Party Computation (MPC)

MPC lets a group of parties jointly compute a function over their private inputs while none of them learn anything about each other’s inputs beyond what the output itself reveals. A classic toy example, and a genuinely useful one, is computing a sum of private salaries without anyone disclosing their individual salary to anyone else, including the person running the computation.

def mpc_sum(private_values, parties):
    shares = []
    for i, value in enumerate(private_values):
        party_shares = share_secret(value, len(parties))
        shares.append(party_shares)
    received_shares = [[] for _ in range(len(parties))]
    for i in range(len(parties)):
        for j in range(len(parties)):
            received_shares[j].append(shares[i][j])
    local_sums = [sum(shares) for shares in received_shares]
    final_sum = sum(local_sums)
    return final_sum

The mechanism behind that snippet is secret sharing: each party splits their private value into random-looking pieces (shares) that individually reveal nothing about the original value, distributes one share to each participant, and then everyone locally sums up the shares they’ve received from everyone else. Because addition distributes over the sharing, summing the local partial sums across all parties reconstructs the true total, even though at no point did any single party ever see anyone else’s raw input, only meaningless fragments of it. This particular scheme is additively homomorphic in spirit for exactly the same underlying reason Paillier encryption is: the operation you want to perform on the secrets commutes nicely with the operation used to split them into shares. General-purpose MPC protocols (garbled circuits, or MPC built on top of more general secret-sharing schemes like the Shamir scheme below) extend this same basic idea to arbitrary functions, not just sums, though the communication and computation overhead climbs steeply as the function being computed gets more complex, which is the main reason MPC deployments in production tend to stick to fairly narrow, well-optimized computations rather than arbitrary general-purpose code.

Threshold Cryptography

Threshold cryptography answers a slightly different question: instead of splitting a secret so everyone has to cooperate to use it, how do you split it so that any t out of n parties can reconstruct or use it, but any smaller group learns nothing at all? That “any t of n” flexibility matters enormously in practice, since requiring literally all n parties to always be available is a reliability nightmare, but you still don’t want a single party (or a small colluding minority) to be able to act alone.

Shamir’s Secret Sharing is the cleanest solution to this and it’s built on a genuinely pretty piece of math: polynomial interpolation. Any polynomial of degree t-1 is uniquely determined by any t points on it (fewer than t points leave the polynomial, and hence the secret hidden in it, completely undetermined, information-theoretically, not just computationally). So to share a secret among n parties with a threshold of t, you construct a random polynomial of degree t-1 whose constant term (the value at x=0) is the secret itself, then hand each party a distinct point on that polynomial.

def shamir_share_secret(secret, n, t):
    coefficients = [secret] + [random.randint(1, PRIME-1) for _ in range(t-1)]
    shares = []
    for i in range(1, n+1):
        y = evaluate_polynomial(coefficients, i)
        shares.append((i, y))
    return shares

def shamir_reconstruct_secret(shares, t):
    secret = 0
    for i, share_i in enumerate(shares[:t]):
        x_i, y_i = share_i
        lagrange_basis = 1
        for j, share_j in enumerate(shares[:t]):
            if i != j:
                x_j, _ = share_j
                lagrange_basis *= (0 - x_j) * mod_inverse(x_i - x_j, PRIME)
        secret = (secret + y_i * lagrange_basis) % PRIME
    return secret

Reconstruction uses Lagrange interpolation: given any t of the (x, y) points, there’s a unique degree t-1 polynomial passing through all of them, and you can recover its value at x=0 (the secret) by combining the shares with the right weighted coefficients, the Lagrange basis polynomials computed in that inner loop. All the arithmetic happens modulo a large prime specifically so this works over a finite field rather than the reals, which keeps every intermediate value bounded and every division (via modular inverse) well-defined.

What makes this scheme special, and it’s a genuinely strong guarantee, is that it’s information-theoretically secure below the threshold: with only t-1 shares, an attacker with literally unlimited computing power, including a quantum computer, learns absolutely nothing about the secret, because every possible secret value is exactly as consistent with t-1 points as every other one. That’s a categorically different, and stronger, kind of security guarantee than “computationally hard to break,” which is what nearly everything else in this post relies on. It’s also exactly why Shamir’s scheme shows up everywhere threshold cryptography is needed in practice: splitting root signing keys for certificate authorities, distributing custody of cryptocurrency wallets across multiple guardians, and recovering encrypted backups when some but not all of your recovery devices are available. The tradeoff is that it protects a static secret rather than letting you compute on distributed data the way general MPC does, so real systems often layer the two together, using Shamir-style sharing to protect the long-term key material and MPC protocols to actually operate on it without ever reassembling the full secret in one place.