From owner-mcg-talk Mon Jul 14 17:52:36 1997
Received: (from majordom@localhost)
by localhost (8.8.6/8.8.6) id RAA04060
for mcg-talk-outgoing; Mon, 14 Jul 1997 17:50:10 -0300
Message-Id: <199707142050.RAA04060@localhost>
Date: Mon, 14 Jul 1997 17:50:07 -0300 (EST)
From: "416720"
To: MCG
Subject: Is certification a metric? And so what?
Sender: owner-mcg-talk@localhost
Status: RO
X-Status:
Following some requests, this e-mail advances material which is being
prepared for publication, on the formal methods used in intrinsic
certification, when viewed as intrinsic metric. I would like to have the
list's opinion on the definitions and proofs. It is not neccessary to
follow the proofs in order to apply the concepts, because the end results
are rather intuitive from simple geometry -- when the geometry analogy of
certification is followed, as done in the intrinsic.txt msg.
This msg proves that certification defines a metric, by construction --
ie, by presenting a function on the set of certificates which obeys all
four conditions of metric-functions AND which allows a certificate to be
correctly either accepted or rejected.
A more concise presentation is available at the revised text
http://http://mcwg/mcg/intrinsic.txt
Also, one has two further references, related to this subject:
- the e-mail "Exposition" authored by 173447, which is quoted and used as
a reference in the cie.htm paper, available at
http://mcwg/mcg/exposition.txt
- the e-mail "Checking Validity" authored by 111229, available at
http://mcwg/mcg/pub9x.txt
1. ******* Definition of certificate (generic) ******
Given an issuer I which has a public-key i and a private-key i', a
certificate c:I issued by I is defined by the ordered set:
c:I = ([c], [c]', [I])
where:
[] is a known bijective mapping to the field of natural numbers
c = a data vector with subject's and certificate's fields such as
(subject's public-key, name, e-mail, authorizations,...;
certificate's validity, serial number, class, revocation
address, ...)
I = a data vector with public fields from the issuer, such as
(issuer's public-key, etc.)
{}i' means encrypted using i'
and the following two conditions must be obeyed:
[c]' = {[c]}i'
[c] = {[c]'}i
********************************************************
NOTE: The above definition is generic and does not need to further define
the bijective mapping [] to the field of natural numbers, nor the
encryption algorithm {} used. Some of the fields of c may contain the
actual values of each element or mappings, one-way hash-functions, etc.
The last element of c:I, corresponds to the publicly available issuer's
data, especially the issuer's public-key i, which may be given indirectly
(as a hash-function and an address) but must allow the public-key i to be
obtained.
2. ******************************** certificate metric *********
A metric-function for the set of certificates C:I = [c:I, d:I, e:I..]
is a function M on the cartesian product C:I x C:I to the natural numbers
such that for all certificates c:I and d:I of C:I,
M(c:I, d:I) = | {[c]'}i - [d] |
********************************************************************
NOTE: M is defined only for certificates from the same issuer, otherwise
it would be operating on elements from different sets, but any issuer can
be used at a time.
Proof that M is a metric-function: (i is known because I is known)
For any c:I, d:I and e:I of C:I, the following properties are obeyed:
(i) M(c:I,d:i) = M(d:I,c:I)
proof: because c:I and d:I belong to C:I, then {[c]'}i = [c] and [d] =
{[d]'}i, which means that | {[c]'}i - [d] | = | [c] - {[d]'}i | =
| {[d]'}i - [c] |
using the same equalities such as {[c]'}i = [c],
(ii) M(c:I,e:i) + M(e:i,d:I) >= M(c:I,d:I)
proof: | {[c]'}i - [e] | + | [e] - [d] | >= | {[c]'}i - [d] |
(iii) M(c:I,d:I) = 0 if c:I = d:I
proof: | {[c]'}i - [d] | = 0 if {[c]'}i = [d] if c:I = d:I
(iv) if M(c:I,d:I) = 0, then c:I = d:I
proof: if | {[c]'}i - [d] | = 0, then {[c]'}i = [d], then c:I = d:I
Now, we must define a certification function, modelling the process of
accepting a certificate on the basis of a set of trusted issuers.
3. ************* Definition of certification function **********
Certification is a function F on the cartesian product of a decision-space
D = [x, y, ...], where any x that belongs to D is given by x = (x1, x2,
x3) and x1, x2 or x3 are natural numbers, times a key-space of
public-keys of chosen issuers K = [i, j, ...] to the boolean space of
[0,1], given by:
F(x,i) = 0 if and only if {x2}i = x1
F(x,i) = 1 otherwise,
which is 0 if x is accepted as a certificate or 1 otherwise. If x is
accepted as a certificate, then [I] = x3, and x is designated by c:I.
*****************************************************************
Note that, here, certification means acceptance of the certificate as
being issued by a chosen issuer I. The other step, which is to actually
use the certificate, will depend on methods to be chosen by the verifier,
such as checking the public-key or expiration date -- for example, an
expired certificate may be acceptable in certain cases, but a false
certificate should never be accepted. Also, checking the public-key with a
challenge-response method may not be necessary or possible -- for example,
PGP does not check the public-key before using the certificate for data
transmission of e-mail.
Of course, the certification function is NOT a metric, but -- as we see
below -- it easily allows a metric-function to be defined.
4. *************** certification as a metric-function *****
The certification function F(c,i) defines a certification metric in C:I,
given by CM, which operates on the cartesian product C:I x C:I to the
boolean set of [0,1], such that for all certificates c:I and d:I of C:I,
CM(c:I,d:I) = F(c,i) if and only if c:I = d:I
CM(c:I,d:I) = 1 otherwise
*************************************************************
This means that certification defines a certification metric-function CM
(which is not necessarily unique).
Using a geometric analogy, the "distance" between two "points" is thus
zero (ie, CM = 0) if and only if the two "points" are "equal" (ie, the
certificates are equal AND issued by I).
Proof:
M(c:I,d:i) is a metric-function as already proved. If M' is
defined by
M'(c:I,d:I) = 0 if and only if M(c:I,d:I) = 0
M'(c:I,d:I) = 1 if and only if M(c:I,d:I) > 0
then it is easy to prove that M' is also a metric-function. However,
inspection shows that M' = CM, thus CM is a metric-function.
5. ********** Definition of certification metric-space *********
A certification metric-space is a pair (C:I,CM) such that CM is a
certification metric for C:I.
*****************************************************************
This means that certification, as provided by certificates issued by I,
defines a certification metric-space.
Further properties can now be defined, for later use, briefly summarized
below:
6. *************** Definition of hereditary property ********
A property of space is C hereditary if and only if each subspace of C also
has the same property
*************************************************************
As proven in Topology, a metric is hereditary, which means that after a
certification metric-function CM is defined, any subspace of (C:I,CM) also
has CM as a certification metric-function. This means that certification
algorithms could profit well from Object-Oriented methodology -- such as
MCs do.
7. ************** Definition of a gauge-function **********
A gauge-function is a metric-function M(x,y) that is smaller than a gauge
value g if and only if x and y are considered equivalent.
************************************************************
Here, a gauge-function can allow certificates to be accepted as a fucntion
of a high degree of correlation, eg, between a stored digitized
fingerprint and an online image of the same.
Yours,
Ed Gerck
__________________________________________________________________________
Dr.rer.nat. E. Gerck Phone/Fax: +55-19-2429533
ed@gerck.com http://mcwg
P. O. Box 1201 - CEP 13001-970 - Campinas - SP - Brazil