[Cryptography] A PKI without CRLs or OCSP

[Natanael]

Den 27 okt. 2016 07:35 skrev "Francisco Corella" <fcorella at pomcor.com>:
>
> Jerry,
>
> > How does using a blockchain differ from having a PKI broadcast its
> > entire set of signed public certificates?  Or, equivalently for
> > reasonable efficiency, every delta to its set?  (With a serial number,
> > of course - and the entire delta signed by the CA - so that receivers
> > could detect modifications or missed deltas.)
> >
> > A blockchain supports agreed-to modifications by anyone (to simplify
> > the semantics). But a PKI has just one sender, broadcasting to many
> > receivers.  You don't need a blockchain for that, just signatures.
>
> By PKI we mean a public key infrastructure consisting of a hierarchy
> of CAs.  It wouldn't be practical for the CAs in the hierarchy, nor
> for a single CA, to broadcast certificates.  On the other hand it's
> trivial for a CA to write a certificate hash to a store in its local
> copy of the blockchain, and for a verifier to check whether the hash
> is in the store, in its own local copy of the blockchain.  This
> requires no network access by issuer or verifier besides the
> communications on the peer-to-peer network that are used to keep the
> local copies up to date.  Also, certificates are unsigned, which saves
> the work of siging the certificate for the issuer, and the work of
> verifying the signature for the verifier.

This seems relevant: https://eprint.iacr.org/2016/994 -
Improving Authenticated Dynamic Dictionaries, with Applications to
Cryptocurrencies

Self-authenticating data structures are incredibly useful, and this one
appears to be quite relevant here. This is essentially like an upgraded SPV
mode - the mode with Bitcoin's headers-only sync where clients only verify
that transactions exists in a blockchain with X amounts of accumulated
proof-of-work (ever growing). No actual verification of transactions is
done besides that.

The difference here is that with the linked scheme, you can produce compact
proofs of correct results. Instead of relying on inclusion proofs +
economical game theory as with Bitcoin SPV, you rely on inclusion +
exclusion proofs and the fact that there's a single authorative append-only
chain where everybody agrees on the history of the header hashes, given
that the "miner" must publish all headers which everybody in the network
can cache.

The relevant paragraph:

> Specifically, we propose storing balance information in a dynamic
authenticated dictionary. In such a data structure, provers (who are, in
our case, miners) hold the entire data structure and modify it as
transactions are processed, publishing proofs that each transaction
resulted in the correct modification of the data structure (these proofs
will be included with the block that records the transaction). In contrast,
verifiers, who hold only a short digest of the data structure, verify a
proof and compute the new digest that corresponds to the new state of the
data structure, without ever having to store the structure itself. We
emphasize that with authenticated data structures, the verifier can perform
these checks and updates without trusting the prover: the verification
algorithm will reject any attempt by a malicious prover or
man-in-the-middle who tries to fool the verifier into accepting incorrect
results or making incorrect modifications. In contrast to the
unauthenticated case discussed above, where the verifier must store the
entire data structure, here verifier storage is minimal: 32 bytes suffice
for a digest (at 128-bit security level), while each proof is only a few
hundred bytes long and can be discarded immediately upon verification.

Also relevant, making it useful for a certificate log:

> The specific data structure we wish to implement is a dictionary (also
known as a map): it allows insertion of (key, value) pairs (for a new key),
lookup of a value by key, modification of a value for a given key, and
deletion by key.

The differences here is that the CA would be the only "miner", there's no
need for proof of work (just signatures of the headers) and instead of
transactions there's certificate issuance and revocations being stored. As
noted above the blockchain headers would still have to be published,
obviously (otherwise the chain can be secretly forked, "split brain"
problem if the users don't communicate).

Since proofs are small and easy to verify, they can be transmitted
trivially on request in place of a CRL lookup. And whenever you've
performed a lookup and received a proof, you must need to ask a small group
of trusted peers of they agree on what the blockchain header hashes are -
any conflicting signed header hashes are undeniable proof of misuse (and
likely proof of malice).

The blockchain could be mirrored by whoever is willing to dedicate the
necessary storage. Anybody storing the blockchain can generate proofs. And
AFAICT proofs are at least valid and reusable for as long as the header it
refers to remain the latest valid published header (so the TTL of proofs
should match time remaining until next header is published).

---

I'm not going to argue which is best or worst of this or certificate
transactions or any of the other public log schemes under development. I
just mentioned this because it seems relevant.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20161027/f11b2451/attachment.html>