Efficient and Fresh Certification

Efficient and Fresh Certification
October 30, 2000
Speaker: Ivan Nestlerode, MIT/[Bell Labs, Lucent Technologies]
Scribe: Ivan

For the outline of the discussion, see the powerpoint slides.


1. So the EFECT certificates aren't individually signed?

No, they aren't. This and the lack of revocation are the two most
important aspects of EFECT.

2. So to verify the certificate, one needs the hashes up that tree

Yes, instead of a standard digital signature to prove a certificate's
authenticity, you would use the path of hashes as the proof instead.

3. How does this differ from Kocher's scheme (CRT)?

The difference is that Kocher's scheme is only used for revocation. It
is not used for discovery of the certificate itself.  With Kocher's
scheme, you must find a certificate, and then check the CRT for
revocation info. With EFECT, you check the EFECT CVT to discover both
the certificate itself and proof of it's freshness/validity.  Also,
EFECT uses B+trees of arbitrary branching factor while CRT assumes
binary trees.

4. So in the credit card scenario, the stores would need some online

Yes, but only once per day (to get the signed root hash of the day).
All other verification could conceivably take place offline if the
users brought their daily hash paths in on smartcards.

5. This means that users would have to download their certificates and
hashes before coming to the store?

Perhaps not. EFECT is flexible. The stores could provide the option of
connectivity for users who did not bother to download stuff before
coming in. Note that even a lazy user who doesn't download before
shopping will not have to download anything once the first store loads
todays cert and hashes onto his smartcard. The rest of the day's
shopping can proceed offline at that point.

In a sense, each day requires a little bit of connectivity somewhere
both for the system as a whole (signed tree root hash) and per
certificate holder (today's path). But the cost of this connectivity
is amortized over the entire day's transactions.  All subsequent use
in a day is offline. This is important for areas (Europe) with very
expensive phone service.

6. (regarding untrusted directories and non-existence proofs) So this
could be used to prevent directories from covering up their errors to
save face (they accidentally delete half of the tree)?

Yes. If a directory claims something is not in the tree, the client
can ask the directory to prove it (cryptographically).  An incompetent
directory will not be able to prove non-existence if they delete the
part of the tree in question, probably leading the user to look for a
more reliable directory.  The error will not be hideable.

This allows us to distribute the directories widely without requiring
us to trust anyone but the CA.

7. What size of tree were the experiments run on?

A tree with 300,000 certificates.

8. Can you also distribute the CA hash tree generation?  Or can you
otherwise prove that clients cannot assist in the generation of the
Merkle hash tree?  For instance, could a customer download the
siblings to its certificate's path, then compute the hash path up to
the current root?  Could the CA use these hash hints to speed up
generation of the hash tree?  Although hashing is much faster than
signing, cryptographic hashing still has a cost.

Well, not sure.  But this is an interesting question because it could
distribute the workload of the CA crypto even more.

9. Initialization: What if I can't wait 24 hours to get a certificate
issued to me?

Well, EFECT probably can't help you. But then again, no current system
can either (that I know of).  Neither Verisign nor VISA will issue
anything with that kind of turnaround.

10. You server has to keep lots of state, doesn't it?

Yes, but any reasonable CA does as well.  At first glance, it may
appear that Verisign doesn't need to keep state. After all, when
someone wants a revocation statement, they can just bring in the
'suicide note' (self-signed certificate stating that it has been

When you think about it though, Verisign must keep state. If their key
is compromised, they must revoke all outstanding certificates. To do
this, they need a list of everyone with a certificate (the same state
EFECT needs to keep).

Once again, EFECT requires state, but so do current schemes.

11. What about Micali's hash chains (CRS1)?

[The Q/A dribbled off at this point, we don't have further
records of the discussion.]

Brought to you by the MIT LCS Applied Security Reading Group