basic question: semantics of "map", "tie", etc in PKI

Anne & Lynn Wheeler lynn at
Tue Jul 8 13:40:29 EDT 2003

At 08:45 AM 7/8/2003 -0700, Fritz Schneider wrote:
>         This is possibly a silly question, but here goes.
>         Reading something PKI-related the other day I was wondering about
>the semantics of different kinds of certificates.  One usually says that
>traditional id certs "map names to keys" or "tie keys to names"[1].  This
>is usually written:
>   name -> key
>Other certs have similar semantics (they "map" and "tie").  For example,
>in order to achieve authorization one could keep an ACL which "maps
>permissions to names" ("ties names to permissions"):
>   permission -> name
>Given these two mappings its then possible to get the mapping:
>   permission -> name -> key
>which authorizes the key for the permission.
>         I actually have two questions.
>         The first is what exactly does "mapping" mean in this sense?  I'm
>not sure that it means "mapping" in the sense of the algebraic definition
>because for each x that is mapped, there should only be only one value to
>which x is mapped, and I think of an ACL or SPKI cert as incompatible with
>this notion.  "Tie" and "bind" seemed to be used in to indicate both a
>mapping or that something is mapped to.
>         My second question is, in mappings like:
>   permission -> name -> key
>why do we think of it as mapping permission to a key and not the other way
>around?  The way I typically think about the task of reasoning about
>authorization seems to work in the opposite direction.
>-- fritz
>[1] RFC2693, for example

basic authentication taxonomy is something like:

1) something you have (like a hardware token)
2) something you know (like a pin/password)
3) something you are (like biometrics)

frequently PKIs talk about certifying (aka CA's are certification 
authorities, certificates represent some certification by a certification 
authority) some binding between something and a public key.

one could claim that the choice of vocabulary was trying to elevate 
something from straight-forward authentication to something like 
identification and non-repudiation ... which would represent much more 
value and therefor the public key owner buying the certificate might pay 
more. Note, however, identification and non-repudiation is primarily of 
benefit to the relying-party that receives the certificate .... but the 
standard TTP business model has the private key owner paying for the 
certificate (not the relying party .... which is receiving the primary 

There has been lots of discussion that PKIs don't actually do 
identification or non-repudiation which requires lots of additional processes.

Certification authorities basically have an entity prove that it can 
generate a digital signature that can be validated with the supplied public 
key ..... basically a form of "something you have" authentication ... the 
entity can prove it has the private key. The certification authority then 
validates some other piece of information (like the entity's email 
address); stores the public key and the certified information in a database 
and then creates a credential/certificate as to the binding between the 
certified information and the certified public key.

Originally, x.509 specification was thought of as heavily overloading a 
certificate with lots of identity related information as well as 
privilege/permission related information ... "bound" to a public key in a 
certificate. It pretty quickly became apparent that a 
credential/certificate heavily overloaded with identity and permission 
information and indiscriminately broadcast all over the world created 
enormous privacy problems.

  Financial institutions in the mid-90s dropped back to relying-party-only 
certificates which basically contain only account number and the public key 
because of the enormous privacy and liability problems. However, a standard 
business process involving certificate has the key-owner  1) creating a 
transaction/message,  2) appending a digital signature, 3) appending the 
certificate ... and transmit the "triple" to the bank.

The bank extracts the account number from the transaction/message, reads 
the account record and validates the digital signature using the public key 
stored in the account record. The relying-party-only certificate containing 
only an account number and public key (because of the enormous liability 
and privacy issues) is never used. It was subsequently observed that such 
relying-party-only certificates were redundant and superfluous.

The original purpose of certificates were to provide various certified 
associations for an offline world (something analogous to letters-of-credit 
from the days of sailing ships). These certificates were a 
stand-in/substitute for situations where it was not possible to directly 
access the real information. Most of them are quickly loosing any reason 
for existence given the extensive proliferation of internet and wireless 
technologies around the world. It is becoming more and more unlikely that 
there wouldn't be some form of connectivity .... especially for 
transactions or authentication events involving anything of value or 

The semantics of private key is basically "something you have" .... however 
given the vagaries of software computing systems, the private key can be 
stored in a hardware token or in a software encrypted file on a general 
purpose computer. The software encrypted file is unlocked with a 
PIN/password ... given some of the characteristics of general purpose 
computers (like personal computers), any kind of file might be considered 
publicly copy'able by anybody in the world. As a result, such an encrypted 
file .... might actually be considered "something you know" authentication 
(as opposed to something that you "uniquely" have). A hardware token that 
generates the key in the chip and never allows the private key to leave the 
chip .... might be considered more representative of "something you have" 

A hardware token that requires a PIN/password to operate can be considered 
two-factor authentication ("something you have" and "something you know"). 
Note that in this situation, the business processes of the token and 
digital signature technology creates an environment that can be used to 
establish "something you have" (aka the hardware token). The digital 
signature technology is not an end in itself ... just a method of proving 
that you posses a specific hardware token (and possibly have knowledge of a 
specific PIN/password).

As previously noted .... sometimes there is PKI documentation that attempts 
to grossly exaggerate the meaning of a digital signature and obfuscate the 
underlying business processes and procedures ....  possibly as part of a 
sales technique to convince public key owners to purchase the certificates 
(obfuscation that attempts to establish certificates as an end in themselves).

misc. past about relying-party-only certificates
Anne & Lynn Wheeler
Internet trivia 20th anv

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list