Subject: Re: General formula, was Re: Attribute certificate lifetimes: way too much math, but getting closer to correct

From: Graham Klyne <[email-masked]>
Date: Tue, 25 May 1999 23:15:55 +0100

I have been reviewing this discussion with interest, but am deeply
uncomfortable with  some of the claims made...  I gather my responses to
three of your postings into this one message...

At 12:25 18/05/99 -0700, Ed Gerck wrote:
[A derivation of a formula for certificate lifetime;  interesting stuff!]

I have some reservations about the statistical validity of "can be
well-approximated by a linear first-degree differential equation" (in
reference [1] of the initial posting), but it sounds plausible.

[...]
>As a practical rule, key-lifetime Tk should be at most 1/3 the shortest 
>attribute lifetime Ta, since for Tk = Ta/3 one has:
>
>1/T = 1/Tk + 1/Ta + ...+ 1/TN =~ 1/Tk + 1/Ta => T =~ 0.75 * Tk

I find this practical rule over-simple:  suppose there are K attributes
with the same minimum key-lifetime Tk, then the result T given by your
formula must be less than or equal to Tk/K.  If K>3 the practical rule
given is somewhat optimistic.

[and later]
At 19:01 18/05/99 -0700, Ed Gerck wrote:
>My assumption is very unassuming ;-)  -- it is simply that any attribute
validity
>in a X.509/PKIX cert is an non-increasing function of time. If you find a
>X.509/PKIX attribute that increases its validity with time then you have
found
>an exception where my formula (and Blackley's, buy extension) is not valid.

What is this "validity" quantity you are describing?

[...]
>As you say -- but this simply means that you need two lifetimes (as I called
>them, two sub-attributes). One lifetime is very long and just leads to that
>slight decay you mention for three years. Then, another lifetime is triggered
>by a delayed sub-attribute, but this lifetime is very short. But, you may
ask, how
>can I take delayed sub-attributes into account? Simple, by considering the
>certitficate lifetime to be given by a piecewise function.

Now I am truly sceptical.  The derivation of your formula was based on
assumption of a differential equation description of the process:  such
descriptions depend upon assumptions of continuity and continuous
differentiability, which I think are broken by the piecewise construction
you advocate.

>... It does NOT include
>the short-lifetime delayed attribute until its maturation period (that you
say is
>3 years), and then adds it as 1/Ts. But, since Ts is small, 1/Ts is large
and its
>effect on the certificate lifetime T is large. So, a small Ts strongly
>*decreases*  certificate lifetime T, since 1/T = (1/T1 + ..1/Tm) + 1/Ts and
>(1/T1 + ...+ 1/Tm) is constant. Clear?

My intuition here is that smaller values for 'Ts' (the second segment of
the piecewise function) are *less* relevant to the overall
period-of-validity, not more so.  (This reinforces my scepticism about the
formula offered:  for it to stand any chance of holding, I think it must
deal with statistical properties that can be stated in a time-invariant
fashion;  e.g. probability of becoming invalid in a given time interval.)

[and yet later]
At 15:37 21/05/99 -0700, Ed Gerck wrote:

>> They certainly don't have to, but in many cases they actually DO.  The
>> example I gave above is one case; the same information encoded
>> on a driver's license for me is a derivative which exemplifies
>> a broad class of certification scenarios from the real world which
>> also have this property.
>
>I disagree. And, there are billions of counter-examples. For example,
>if men's biological lifetime is 70 years this does not mean that all men
>were born at the same time -- and yet they all have the same lifetime.

I think this entirely misses the point that was being made:  a single case
is sufficient for an existence proof, and such was provided by Bob B.

Despite your claims otherwise, I belive you are making an assumption of
independence of attributes:  specifically, independence of time-of-birth.

#g

------------
Graham Klyne
([email-masked])

---

From: Ed Gerck <[email-masked]>
Date: Tue, 25 May 1999 20:30:47 -0700

> three of your postings into this one message...

Graham:

Thanks. I am all for the "doubt till you have proof" approach.
I am leaving in one hour for a cross-country red-eye two day hop
to Washington DC, so I will try to answer you now since I do not
expect to be on e-mail before Friday.

First, let me note that an extensive paper where my "claims" are discussed
has circulated for some months now in a reviewer circuit so, based on those
reviews, I do not expect any major mistake. Second, I could not resist to
present some of my results, even if partially, to this list since I saw the subject
was very timely to the discussions. And, yes, the paper has greatly profited
from the discussions, examples and counter-examples here. I expect to have
it ready for public presentation next week, when I will post here the relevant
URL.

> [A derivation of a formula for certificate lifetime;  interesting stuff!]

Yes, and it applies also to *any* database record -- not only certificates.
In fact, it applies also to common text -- such as this one.

> reference [1] of the initial posting), but it sounds plausible.

It is proved in the paper -- but, since you don''t contest it, I will let
the matter rest until the paper is presented.

> given is somewhat optimistic.

Of course -- the practical rule is simplified, perhaps even over-simplified.
But, it is NOT optimistic and is NOT wrong -- note that I wrote "at most"
and surely Tk/3 > Tk/K for K>3. Agreed?

So, the practical rule "Key-lifetime Tk should be at most 1/3 the shortest
attribute lifetime Ta" will always provide you a correct upper bound -- which
is exactly what I intended to when I wrote "at most".

> What is this "validity" quantity you are describing?

The "attribute validity"  I mention above is described where the equation's
assumptions are described -- reference [1] of the original posting, it is
An -- to wit:

---------------------------------------
 dAn/dt = - An/Tn , for n =1, ...N              (2)

 where d/dt is time derivative (in continuous or discrete form), Tn is the
 effective attribute's a priori lifetime, and An is the attribute validity
                                                                           ^^^^^^^^^^^^
 function at time t:

 An = fraction of valid attributes n at time t, normalized to the ensemble.
------------------------------------------------

> differentiability, which I think are broken by the piecewise construction

No -- the assumption order is reversed from what you thought. The equation is
piecewise valid, *thus* the piecewise solution that obeys it is valid -- not the other
way around.

To exemplify, define the time axis [0,oo) into K intervals, one for each different
K-delayed lifetime needed for *one* attribute -- so that to each K interval there is
*only one* exponential decay lifetime assigned to *that*  attribute. Note that the K
intervals to do not have to be uniform. Each one of these K intervals defines a possible
sub-attribute to that *one* original attribute and for each one of these intervals the
equation:

dA/dt = - A/T

is valid with the following boundary conditions and lifetime:

  CONDITION            INTERVAL      LIFETIME
   A(0) = Ao                    0<= t < t1                 T1
  A(t1-) = A(t1)              t1<= t < t2                 T2
.....
  A(tK-1-) = A(tK-1)    tK-1<= t < oo             TK

which defines a continuous piecewise function A(t) valid in the relevant total
interval [0,oo), with K delayed sub-attributes. Note also that the Tn do not have to
be all different -- in fact, they can be all equal.

> period-of-validity, not more so.

There is a simple confusion here -- the piecewise solution I mention is NOT
in each interval but for staggered intervals. So, in each interval the equation
1/T = (1/T1 + ..1/Tm) + 1/Ts  is NOT piecewise at all. So, you can directly
compare its terms and when Ts is small one must have 1/Ts large -- which
then dominates the sum  (1/T1 + ..1/Tm):

 (1/T1 + ..1/Tm) << 1/Ts

to the extent that

1/T = (1/T1 + ..1/Tm) + 1/Ts  ~ 1/Ts ==> T ~ Ts. In other words, as I am quoted
above, "a small Ts strongly *decreases*  certificate lifetime T".

>  (This reinforces my scepticism about the

Reading the above I suspect that you imagined a piecewise sum for each
interval. This is NOT the case. The piecewise solution is built by considering the
least interval that is needed for all attributes and then using this interval for *all*
attributes -- where any one attribute may be divided into more time slices than
it needs by itself, but such will not hurt ;-)

> is sufficient for an existence proof, and such was provided by Bob B.

Wait -- this is NOT the issue here. Bob Blakley wrote that equal lifetimes
would indicate a "property" -- that the corresponding attributes would
actually be dependent or at least have a tendency to be dependent. I replied
negatively -- such property or tendency does NOT exist. Lifetime distance
does not correlate with attribute independency -- much in the same way that
a pointer's value (lifetime) does not correlate with a pointer's address (attribute).
They are two entirely different concepts, not only different values. Thus, the fact
that the lifetimes are equal or even similar for two attributes does not authorize
me to say anything about the attributes' dependencies.

> independence of attributes:  specifically, independence of time-of-birth.

No, not all -- and, where is this needed?  Nowhere. Please read the first
paragraph of [1]:

[1] Consider an ensemble of certificates, each with a given number M of
attributes, with each attribute defined by a lifetime -- including
the key. This ensemble can include certificates that are issued at the
same time for different keyholders and certificates that are issued at
different times for the same keyholder. The ensemble is an analysis tool,
to be used in order to allow the calculation of average statistics based
on time averages, but note that the M attributes are not supposed to be
independent from one another.

Cheers,

Ed Gerck
______________________________________________________________________
Dr.rer.nat. E. Gerck                                 [email-masked]
  ---  Meta-Certificate Group member -- http://www.mcg.org.br  ---