Re: Truly Random Numbers On A Quantum Computer??

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

On Sat, 29 Mar 2025 20:25:23 -0300, Ethan Carter wrote:
>

There's also an interesting paper by Anna Johnston on entropy, in which
she makes the (correct, in my opinion) remark that entropy really is a
relative notion.

>
That makes sense. I’ve long thought that one’s estimates of the
probabilities of various events depends very much on one’s point of view.

The definition of ``probability'' (in the sense of how to interpret it)
is sort of an open problem.  Knuth takes note of that in section 3.5,
page 142 when he also points the reader to von Mises's book on the
subject.

What you're describing here is a certain notion, which is discussed in
Shell Ross' ``A First Course in Probability'' on section 2.7, chapter 2,
8th edition.

--8<-------------------------------------------------------->8---
Thus far we have interpreted the probability of an event of a given
experiment as being a measure of how frequently the event will occur
when the experiment is con- tinually repeated. However, there are also
other uses of the term probability. For instance, we have all heard such
statements as “It is 90 percent probable that Shake- speare actually
wrote Hamlet” or “The probability that Oswald acted alone in assas-
sinating Kennedy is .8.” How are we to interpret these statements?

The most simple and natural interpretation is that the probabilities
referred to are measures of the individual’s degree of belief in the
statements that he or she is making. In other words, the individual
making the foregoing statements is quite certain that Oswald acted alone
and is even more certain that Shakespeare wrote Hamlet. This
interpretation of probability as being a measure of the degree of one’s
belief is often referred to as the personal or subjective view of
probability.

It seems logical to suppose that a “measure of the degree of one’s
belief” should satisfy all of the axioms of probability. For example, if
we are 70 percent certain that Shakespeare wrote Julius Caesar and 10
percent certain that it was actually Mar- lowe, then it is logical to
suppose that we are 80 percent certain that it was either Shakespeare or
Marlowe. Hence, whether we interpret probability as a measure of belief
or as a long-run frequency of occurrence, its mathematical properties
remain unchanged.
--8<-------------------------------------------------------->8---

I get the feeling here that, by the same token, you could never have a
provably secure cryptosystem because someone knows the private key?

>
None of our cryptosystems are provably secure.

One example of provably secure system is the one-time pad.  It is likely
the simplest.  But there many more.  For example, Michael Rabin's
cryptosystem based on modular square roots is provably secure.  For a
definition of ``provably secure'', take a look at chapter 3 of Douglas
Stinson's ``Cryptography: Theory and Practice'', 4th edition.

--8<-------------------------------------------------------->8---
Another approach is to provide evidence of security by means of a reduc-
tion. In other words, we show that if the cryptosystem can be “broken”
in some specific way, then it would be possible to efficiently solve
some well-studied problem that is thought to be difficult. For example,
it may be possible to prove a statement of the type “a given
cryptosystem is secure if a given integer n cannot be factored.”
Cryptosystems of this type are sometimes termed provably secure, but it
must be understood that this approach only provides a proof of security
relative to some other problem, not an absolute proof of security.
--8<-------------------------------------------------------->8---

RSA depends on the assumed difficulty of two problems: factorizing
large integers, and computing discrete logarithms, and would break if
either one was solved. There is no proof that either of these problems
is actually hard: we simply don’t know of any good algorithms for
them, after decades, even centuries of looking.

That has no effect on the property of a system being provably secure.
See section 6.8, for example, of Stinson's.  Notice his use of the words
``provably secure'' and ``secure''.

--8<-------------------------------------------------------->8---
In this section, we describe the Rabin Cryptosystem, which is
computationally secure against a chosen-plaintext attack provided that
the modulus n = pq cannot be factored. Therefore, the Rabin Cryptosystem
provides an example of a provably secure cryptosystem: assuming that the
problem of factoring is computationally infeasible, the Rabin
Cryptosystem is secure.
--8<-------------------------------------------------------->8---