Subject: RE: TSA Response serialNumber Field

From: "Manger, James H" <[email-masked]>
Date: Fri, 2 Jun 2000 15:13:25 +1000

Thanks Ed,

I was ignoring the incorrect labelling of the uncertainty field (hoping the
next draft would fix it).  I was assuming the quoted uncertainty was 1
standard deviation (hoping the next draft would explicitly state this).

I was assuming the mapping between number of standard deviations and
confidence level was vaguely independent of the exact distribution, at least
independent enough for practical timestamping purposes, so I could use the
mapping that the normal distribution gives.  I knew there were some
theoretical bounds on this mapping, though I could not remember the
specifics.  I was also assuming that converting from one confidence level to
another was possible (e.g. if uncertainty for 68% confidence level is quoted
just double the uncertainty to get a 95% confidence level).

After finding a statistics text book..

Chebyshev's inequality says the probability of being further than n standard
deviations from the mean is always less than or equal to 1 / n^2, regardless
of the distribution.
    Pr(|x - mean| >= n.sd) <= 1/n^2

[I think there are some distribution that don't have a finite standard
deviation so Chebyshev's inequality does not hold.  I hope this does not
apply to practical distribution for TSA time measurements.]

Hence the probability that a sample is not within [mean - n.sd, mean + n.sd]
is:
n    normal    upper bound
1    32%    <= 100%
2    5%    <= 25%
3    0.3%    <= 11%

Now I can repeat my calculations from my previous e-mail using Cebyshev's
inequality instead of a normal distribution.  Instead of calculating the
probability that T2 occurred after T1 the calculation gives an upper bound
on this probability.  In that example the upper bound turns out to be 100%
which is useless.  This highlights the problem with using Cebyshev's
inequality.  It gives a very weak bound, particularly as you get further
from the mean (use a higher confidence level).

Back to the timestamp standard..

For comparing a timestamp to another clock we need time, uncertainty,
confidence level and distribution.  Put the time and uncertainty in the
timestamp (as now), put the confidence level in the standard and the
distribution in the TSA's policy document [in future, if required, a policy
qualifier or extension could be added to describe the distribution in the
actual timestamp].

The standard could state that the uncertainty field is a given number of
standard deviations (e.g. 2) or a given confidence interval (e.g. 95%).
Previous I suggested the former, but (after reading this thread) I can see
advantages with the latter, though I would be happy either way.  Suggested
text (after changing the field name from 'accuracy' to 'uncertainty'):
  "The 'uncertainty' value represents the time deviation, in seconds,
between the 'genTime' value and UTC at a 95% confidence level.  That is,
there is a 95% chance that the 'genTime' value is within +/-'uncertainty'
seconds of UTC.  If the time measurement has a Normal (Gaussian)
Distribution the 'uncertainty' value is approximately 2 standard
deviations."

If a relying party is happy with a 95% confidence interval it does not need
to know the exact distribution.  If a relying party wants a better
confidence level than the standard specifies (e.g. 99.7% instead of 95%) it
has a couple of choices:
(1) assume, say, a normal distribution and adjust the uncertainty
accordingly (e.g. multiple by 3/2); or
(2) use Chebyshev's inequality to get an upper bound of the required
adjustment [can Chebyshev's inequality be reformulated for this, i.e. for
confidence levels (e.g. 95%) instead of standard deviations (e.g. 2 sd)?];
or
(3) determine the actual distribution from the TSA's policy document and
adjust the uncertainty by the amount appropriate to that distribution.
We can leave the choice to the relying party.

---

From: Ed Gerck <[email-masked]>
Date: Thu, 01 Jun 2000 23:56:27 -0700

James:

We are in violent agreement.

Cheers,

Ed Gerck