Seeing Is Believing
Introducing a notion that captures information flow
|
| [ Her own hall ] |
Anita Jones is, of course, a famous computer scientist, a famous Carnegie Mellon University graduate, and a decorated past government official. She was the Director for all U.S. Defense Department research—except nuclear—for 1993 to 1997. She has won numerous awards—perhaps the coolest is that the U.S. Navy honored her by naming a seamount in the North Pacific Ocean for her. Here is what Google Maps returns when given the coordinates 51
|
Today I want to discuss a recent paper of hers.
Okay, not so recent. Well it was published in 1976. It is a joint paper of ours. The topic was information flow with applications to security and cryptography: “The Enforcement of Security Policies for Computation.” Anita and I thought that is was a pretty neat paper. The paper was eventually accepted for the the operating system conference (SOSP) conference in 1975 and later appeared in the JCSS journal—see here.
Missing The Boat
Two comments on our paper. It was indeed accepted to SOSP, but the acceptance was complicated. It might make a good story, but it happened so long ago that I doubt anyone who would be interested. The paper also totally missed the boat. We had a good idea, a good topic, but we totally missed getting the right model. Totally.
Here is the boat we missed:
|
|
We missed it because we looked for a deterministic theory of information flow. An application of the theory was to be to security and cryptography. It was at least partially successful in explaining several puzzles that were around then. But we missed seeing that the best theory had to be probabilistic. That a good theory of information flow needs to argue about probabilities… We missed this totally.
Seeing A Value
So we are going to introduce a probabilistic theory of 
means that 
-
If
and
, then
.
-
If
.
-
If
and
is a non-zero constant, then
-
Suppose that
always, then
Applications
Here is a real application to demonstrate the notion of “seeing”. It comes not directly from security but from a 2017 paper by Saminathan Ponnusamy and Victor Starkov on the Jacobian Conjecture. We have however covered cryptographic aspects of the conjecture. The authors look at functions 
where 
They give a proof that this function is invertible. Here is one using our “seeing” notion:
Then we get that
and recall that
Thus by subtraction it follows that we get 
Note, the proof in the above paper is quite short. However it is a bit complicated and we believe that the above proof is quite transparent.
Open Problems
Is this notion of any use? Also how hard will it be to formally define this notion?
Bitta latex issues.
Had to be fixed manually.
I can think of a couple of concepts close to this one. One is “measurability.” To say that a function if s measurable with respect to a finitely generated sigma algebra is akin to say that “f is seen given the sigma-algebra” (and it means that f can be written as a Borel function of the algebra generators). I’m sure the word “observable” can be fitted there somewhere.
Then there is the notion of a finitely generated algebra over a ring A, something of the form A[y_1,..,y_n]. In your proof, the predicate “is seen” corresponds to “is an element of A[y_1,..,y_n].” Your examples about E_1, E_2 are almost the formal characterization of an algebra over A. The equality condition also can be interpreted as a property of the canonical morphism of the algebra of polynomials in (algebraically independent) n generators and A[y_1,…,y_n].
Vive la conjecture jacobienne!
${\Box E}$ is defined globally, but it would be interesting to formalize it as knowledge possessed by an observer, ${\Box_O E}$. For example, the Sam and Polly problem could be expressed as something like:
$3 \le x \le y \le 97 \wedge {\Box_S x + y} \wedge {\Box_P x \cdot y} \implies {\Box_S \left( \not \Box_P x \wedge \not \Box_P y \right)$
$\Box_P \text{all of the above} \implies {\Box_P x \wedge \Box_P y}$
$\Box_S \text{all of the above} \implies {\Box_S x \wedge \Box_S y} \implies x=13 \wedge y=16$
Your seeing notion looks like a notion of efficiency, and it has the flavor of a non-standard concet. But, if efficiency is likewise a non-standard concept that’s correctly captured by that of polynomial time, then the set of polynomial problems in NP can’t be known. Indeed, the class of non-standard elements in a set is not a set!
It reminded me of these too, but “seeing” differs both from efficiency and the “non-standard” tag as in Nelson’s internal set theory.
If box meant polynomial time, we wouldn’t have:
$latex ${\Box E_1}, ${\Box (E_1 \times E_2)} \implies ${\Box E_2}$
If box meant “non standard”, we would have:
$latex ${\Box E_1}, ${\Box (E_1 + E_2)} \implies ${\Box E_2}$
OK thanks. I might as well have talked of a fuzzy concept, rather than nonstandard. That’s what can be said of the notion of feasibility. The idea is that, if a fuzzy concept such as feasibility is properly conveyed by the clear-cut notion of polynomial time, then its fuzziness should turn into P vs NP being undecidable.