Suppose a certificate authority (CA) uses a Certificate Revocation Tree (CRT) to

Question

Suppose a certificate authority (CA) uses a Certificate Revocation Tree (CRT) to represent revoked certificates. The CA has issued a total of 500,000 certificates. Of those, 512 have been revoked. What is the height of the CRT? Suppose Alice wants to check whether Bob's certificate is revoked or not. Using this CRT, how many hashes and/or signature verification does she need to compute? If another certificate is revoked, what needs to be updated in the original CRT to support this revocation? After you update the; CRT in (c), what is the; height of the new CRT?

Explanation / Answer

Ans (A) : Height of CRT is O(log n), where n is number of revoked certificates.

Here 512 certificates are being revoked so that height would be : O(log 512) = O(2.7)

(B)Here in the scenario, if Alice wants to check Bob's certificate,

we have several certificates to be reovked like [CERT0,CERT1,CERT2,....CERTM,CERTM+1].Here we have two boundries CERT0 and CERTm+1 represent -infinative and +infinative respectively.
Now to compute the signature of Bob's certificate we have to run hash on all the certificate cahin from first entry to Bob's certificate :
Sign(CERTi) = h(CERTi||CERTi-1||...||h(-infinative))SK
Where h is suitable cryptograpic hash function, || stands for concatenatin and SK is private ket oy BOB's certificate.

(c) In older scenario, when one certificate is revoked than entire tree is to be recomputed and distributed via VA (Validation Authority). but with the help of 2-3 trees dynamic updates through VA would help a lot. In this VA will periodically check for the revoked certificates and populate the list of revoked certificates. So here it will populate new root (VA) of the tree and left most leaf represents least value and right most leaf represents highest value for the revoked certificates.

(d) After updating CRT, likewise n certificates has been revoked and k will be revoked during current time then height would O(k logn), so here O(1log511) = O(2.7), as only one certificate revokation does not chagne the depth of the tree much.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.