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