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${^\circ}$. 25′ N and 159${^\circ}$ 10′ W.

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 ${\dots}$ No we are still interested in deterministic information flow. We wish to introduce the notion of seeing a value. The intuition is that often in making arguments we may need to say that we can “see” a certain value. This happens naturally in arguments in cryptography. For example, we can express that a function is invertible as: if we can see the value of ${F(x)}$ we can see the value of ${x}$. Let ${\Box E}$ mean that we can see the value ${E}$. Think of the symbol ${\Box}$ as an “eye” that can see the value of the expression ${E}$. Thus

$\displaystyle \Box F(x) \implies \Box x$

means that ${F}$ is an invertible function. Rather than formally define ${\Box}$ let’s give some simple rules that should explain the notion.

• If ${\Box E_{1}}$ and ${\Box E_{2}}$, then ${\Box (E_{1} + E_{2})}$.

• If ${\Box E_{1}}$ and ${\Box E_{2}}$, then ${\Box (E_{1} \times E_{2})}$.

• If ${\Box cE}$ and ${c}$ is a non-zero constant, then ${\Box E}$.

• Suppose that ${E_{1} = E_{2}}$ always, then

$\displaystyle \Box E_{1} \implies \Box E_{2}.$

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 ${F(x)=y}$ of the form

$\displaystyle y_{k} = x_{k} + \gamma_{k} \left( a_{1}z^{2} + \cdots + a_{m}z^{m} \right),$

where ${z = x_{1} + \cdots + x_{n}}$ and

$\displaystyle \sum_{k} \gamma_{k} = 0.$

They give a proof that this function is invertible. Here is one using our “seeing” notion:

$\displaystyle \begin{array}{l} \Box\, y_{k} \text{ for all } k. \\ \Box \left( x_{k} + \gamma_{k} \left( a_{1}z^{2} + \cdots + a_{m}z^{m} \right) \right) \text { for all } k. \\ \Box \left( \sum_{k} x_{k} + \gamma_{k} \left( a_{1}z^{2} + \cdots + a_{m}z^{m} \right) \right) \text { adding up.} \\ \Box \left( x_{1} + \cdots + x_{n} \right) \text { by assumption } \sum_{k} \gamma_{k}=0. \\ \Box\, z \text{ by definition.} \end{array}$

Then we get that

$\displaystyle \Box \left( a_{1}z^{2} + \cdots + a_{m}z^{m} \right),$

and recall that

$\displaystyle \Box \left( x_{k} + \gamma_{k} \left( a_{1}z^{2} + \cdots + a_{m}z^{m} \right) \right) \text { for all } k.$

Thus by subtraction it follows that we get ${\Box x_{k}}$ for each ${k}$. This proves that ${F}$ is invertible.

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?

1. April 9, 2019 11:04 am

Bitta latex issues.

• April 9, 2019 4:07 pm

2. April 10, 2019 4:50 pm

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!

3. April 12, 2019 12:15 am

${\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$

April 12, 2019 7:25 am

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!

April 12, 2019 3:38 pm

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}$

April 14, 2019 4:31 pm

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.