***From Cryptographic Primitives to ***Public Key Verificatio: Establishing Trust at Scale in Modern Systems

8 min read7 hours ago

–

Press enter or click to view image in full size

Photo by kangjia song on Unsplash

Introduction: Why Security Is Hard in Distributed Systems

In a distributed system, components run on different machines and communicate over a network that you might not control. Messages travel through routers, servers, and networks owned by other parties. This means messages can be delayed, copied, dropped, replayed, or modified without either sender or receiver immediately knowing. Because of this, security in distributed systems cannot assume a safe network. Instead, systems must be designed under the assumption that the network itself is hostile.

At its core, security in distributed systems answers three fundamental questions:

1. Authenticity— Who am I communicating with?
2. Integrity— Has the data been changed?
3. Confidentiality— Can anyone else read the data?

All cryptographic mechanisms — keys, encryption, hashes, signatures, certificates — exist solely to answer these three questions in a reliable way.

Keys: The Fundamental Building Block

A cryptographic key is best understood as a mathematical function that transforms data. When a key is applied to some data, it produces a new version of that data. The transformation may make the data unreadable, or it may encode proof about who created it.

This idea can be represented simply as:

K(data) → transformed_data

Security systems work by controlling who has access to which keys and what transformations those keys allow. Losing control of a key means losing control of security.

Encryption and Decryption: Locking and Unlocking Data

Encryption is the process of converting readable data (plaintext) into unreadable data (ciphertext). Decryption reverses this transformation. Only someone with the correct key can recover the original data.

Formally:

plaintext = D_K(E_K(plaintext))

In distributed systems, encryption protects data while it is in transit across untrusted networks. However, encryption alone is not sufficient. How keys are shared and verified also determines whether the system is actually secure.

Symmetric Cryptography: One Shared Secret

In symmetric cryptography, the same key is used for both encryption and decryption. For instance, Alice and Bob share a secret key `K`. Alice encrypts her message using `K`, and Bob decrypts it using the same `K`.

Bob_receives = D_K(E_K(data))

This approach is computationally efficient and is well suited for encrypting large volumes of data. However, it introduces a fundamental problem: key distribution. Alice and Bob must already share the secret key, and securely sharing that key over a network is itself a difficult security problem.

For this reason, symmetric cryptography is rarely used alone in distributed systems.

Asymmetric Cryptography: Public and Secret Keys

Asymmetric cryptography solves the key distribution problem by using two mathematically linked keys:

• A public key (PK), which can be shared freely
• A secret key (SK), which must remain private

Data encrypted with one key can only be decrypted with the other:

D_SK(E_PK(data)) = data

This allows secure communication between parties who have never met before.

Confidential Communication: Encrypting for the Receiver

To send private data to Bob, Alice encrypts the data using Bob’s public key:

ciphertext = E_PK_B(data)

Only Bob can decrypt the message, because only Bob has the corresponding secret key:

data = D_SK_B(ciphertext)

Even if an attacker intercepts the message, confidentiality is preserved. However, Bob still does not know who sent the message.

Authenticity: Proving Who Sent the Message

To prove authorship, Alice uses her secret key to create a digital signature. Anyone can verify the signature using Alice’s public key.

signature = E_SK_A(data)verify = D_PK_A(signature)

If verification succeeds, Bob knows that Alice must have created the message. Digital signatures provide authenticity and integrity, but they do not provide secrecy.

Hash Functions: Efficient and Tamper-Evident Fingerprints

Hash functions transform arbitrary-length data into fixed-length outputs:

hash = H(data)

Hash functions have three critical properties:

• Any change in data produces a different hash
• The same data always produces the same hash
• It is infeasible to reconstruct data from its hash

These properties make hashes ideal for verifying integrity.

Digital Signatures in Practice

A digital signature allows the receiver to answer two concrete questions:

• Was this data created by the claimed sender?
• Has this data been modified since it was signed?

It deliberately does not provide confidentiality. Interception is assumed. Suppose Alice wants to send some data to Bob. Alice first computes a hash of the data:

h = H(data)

Alice then signs this hash using her secret key:

signature = E_SK_A(h)

Only Alice can produce this value because only Alice possesses SK_A. Over the network, Alice sends:

• data (in plaintext)
• signature
• an identifier for herself (e.g, a username, domain name, or certificate)
• an identifier for the hash algorithm used

The hash function itself is not secret; Bob already knows how to compute it. When Bob receives the message, he independently performs two computations. Bob hashes the received data:

h1 = H(data)

Bob verifies the signature using Alice’s public key:

h2 = D_PK_A(signature)

Bob compares the results:

h1 == h2

If they match, Bob knows that the data was not altered and that the sender possessed Alice’s secret key.

Press enter or click to view image in full size

Public Key Verification: Establishing Trust

Signature verification only proves that someone with a particular secret key signed the data. It does not, by itself, prove who that key belongs to. This distinction is subtle but foundational.

If Bob accepts any public key without verification, an attacker can generate their own key pair, sign data correctly, and claim to be Alice. The cryptography will succeed while security fails. Public key verification is the process of answering the question:

“Why should I believe that this public key belongs to Alice?”

Get Ayo Akinkugbe’s stories in your inbox

Join Medium for free to get updates from this writer.

This step must occur before signature verification has any real meaning.

Press enter or click to view image in full size

How Public Keys Are Verified in Practice

Public key verification isn’t solved by mathematics alone. It relies on trust relationships that exist outside the cryptographic primitives. These include certificate authorities, key pining , web of trust and key transparency.

Certificate Authorities (CAs)

In the most common model, Alice obtains a certificate from a trusted Certificate Authority (CA). The certificate binds Alice’s identity to her public key:

certificate = { identity, PK_A }

The CA signs this binding:

cert_signature = E_SK_CA(H(certificate))

Bob already trusts the CA’s public key. By verifying the CA’s signature, Bob comes to trust Alice’s public key. This is the model used by HTTPS(HyperText Transfer Protocol Secure) and TLS(Transport Layer Security).

Press enter or click to view image in full size

Key pinning

In some systems, Bob already knows Alice’s public key from a previous secure interaction or an out-of-band exchange. Bob stores this key and rejects future communications if the key changes unexpectedly. This approach avoids third parties but requires careful key management.

Web of trust

In a web-of-trust model, trust propagates socially. Keys are signed by other trusted entities, and Bob decides whether enough trusted endorsements exist. This model is flexible but difficult to scale and automate.

Public Key Verification via Key Transparency

The trust mechanisms discussed so far — Certificate Authorities, key pinning, and web‑of‑trust — share an important limitation: they all answer the question of who to trust at a single point in time. In modern distributed systems, this is often not sufficient. What we increasingly need to know is not only whether a public key is valid, but also whether its history is consistent and untampered with. This leads to a more powerful approach known as key transparency.

The Key Idea

Key transparency replaces blind trust with verifiable history. Instead of asking a trusted authority “Is this Alice’s key?”, clients ask a stronger question:

“Can I cryptographically verify that this key has always been Alice’s key, and that no one has secretly changed it?”

To achieve this, systems maintain an append‑only trust log. Every event related to an identity key — creation, rotation, recovery, or revocation — is:

• Signed
• Appended to the log
• Never deleted or overwritten

The log is constructed so that any attempt to modify past entries is detectable

Press enter or click to view image in full size

How the Trust Log Works

At a high level, the trust log behaves like a ledger:

1. Each identity is associated with a sequence of public keys over time.
2. Each update produces a new log entry.
3. Entries are chained together using cryptographic hashes.
4. Clients can request cryptographic proofs that:

• An entry exists
• The log is append‑only
• The log has not been forked or rewritten

In practice, this is implemented using Merkle trees (often Patricia Merkle Trees), which allow efficient proofs even for very large systems.

Append‑Only Trust Log

Press enter or click to view image in full size

Each new event extends the log. Past entries cannot be removed or changed without breaking the cryptographic chain.

What Clients Actually Verify

When Bob retrieves Alice’s public key, he does not simply accept it. Instead, he verifies:

1. The public key appears in the trust log
2. The log entry is consistent with previous log roots Bob has seen
3. The cryptographic proof confirms the log is append‑only

If an attacker, or even the server itself tries to substitute a different key for Alice, Bob will detect one of the following:

• A missing history
• A forked log
• An inconsistent log root

This means key substitution attacks become detectable, even if the attacker controls the server.

Relationship to Other Trust Models

Key transparency does not replace cryptography(the mathematical primitives that provide security guarantees as explained above); it strengthens trust assumptions:

• Compared to Certificate Authorities, it removes reliance on a single trusted third party.
• Compared to key pinning, it scales to large systems and supports safe key rotation.
• Compared to web‑of‑trust, it avoids social trust graphs and manual verification.

This model is used in real systems today, including:

• Certificate Transparency in TLS
• Signal and WhatsApp key directories
• Apple iCloud Key Transparency

Why is This Important?

Key transparency shifts security from trusting entities to verifying behavior. Instead of assuming honesty, clients continuously audit consistency. This makes large‑scale distributed systems more resilient against:

• Malicious insiders
• Compromised servers
• Silent key replacement
• Rollback and replay attacks

In modern secure systems, this form of verifiable trust is increasingly becoming the standard rather than the exception.

Combining Everything: Secure Communication End-to-End

Press enter or click to view image in full size

Modern systems combine multiple techniques in layers:

1. Verify public keys and their history (e.g, via certificates, pinning, or key transparency logs)
2. Establish a symmetric session key
3. Encrypt data symmetrically for confidentiality
4. Sign data to ensure integrity and authenticity

This layered approach balances performance, security, and trust accountability.

Conclusion

Security in distributed systems is about managing trust under uncertainty. Encryption protects confidentiality, hashes detect tampering, signatures provide authenticity, and public key verification — whether via trusted authorities or verifiable transparency logs — establishes identity over time.

Understanding these relationships allows systems such as TLS, SSH, and modern key-transparent messaging platforms to be understood as applications of the same foundational ideas.