Public Key Infrastructure (PKI) in Cybersecurity - Time & Space Complexity

Time Complexity: Public Key Infrastructure (PKI)

O(n)

Understanding Time Complexity

Analyzing time complexity helps us understand how the steps in Public Key Infrastructure (PKI) grow as more users or certificates are involved.

We want to know how the time to verify or issue certificates changes when the system scales up.

Scenario Under Consideration

Analyze the time complexity of this simplified PKI certificate verification process.

function verifyCertificateChain(chain) {
  for (let i = 0; i < chain.length - 1; i++) {
    if (!verifySignature(chain[i + 1], chain[i].publicKey)) {
      return false;
    }
  }
  return true;
}
    

This code checks each certificate in a chain by verifying its signature with the previous certificate's public key.

Identify Repeating Operations

Look for loops or repeated checks in the verification process.

• Primary operation: Signature verification inside the loop.
• How many times: Once for each pair of certificates in the chain (chain length minus one).

How Execution Grows With Input

As the certificate chain gets longer, the number of signature checks grows proportionally.

Input Size (n)	Approx. Operations
10	9 signature verifications
100	99 signature verifications
1000	999 signature verifications

Pattern observation: The work increases steadily as the chain length grows, roughly one check per certificate.

Final Time Complexity

Time Complexity: O(n)

This means the time to verify grows directly in proportion to the number of certificates in the chain.

Common Mistake

[X] Wrong: "Verifying the whole certificate chain takes the same time no matter how long it is."

[OK] Correct: Each certificate must be checked one by one, so longer chains take more time.

Interview Connect

Understanding how PKI verification scales shows you can think about security processes in real systems and their efficiency.

Self-Check

"What if the verification process used caching for some certificates? How would that affect the time complexity?"