[langsec-discuss] Is computation half the story?

Andrew Ruef munin at mimisbrunnr.net
Thu Apr 2 02:46:39 UTC 2015

isn't this captured in the definitions of quantified information flow?

> On Apr 1, 2015, at 22:28, Taylor Hornby <havoc at defuse.ca> wrote:
>> On 04/01/2015 10:15 AM, Jacob Torrey wrote:
>> I've had similar thoughts, and a rather hasty blog post I wrote a while
>> back may be of interest:
>> http://blog.jacobtorrey.com/towards-a-new-model-of-computational-expressiveness
>> - Jacob
> Thanks for that link. I'm glad to see others thinking about this!
> Your blog post inspired me to try to define "isolation" using Turing
> machines as a model. If you can do it for a Turing machine, then that
> should apply to any more specific model by the Church-Turing thesis.
> I failed terribly. I was trying to say something along the lines of: If
> A and B are disjoint subsets of tape indices, then A is isolated from
> B iff you can freeze the machine at any time, wiggle the tape cells in
> A, and the cells in B won't be affected by your wiggling for the
> remainder of the computation (and vice-versa).
> That doesn't work because the sets A and B have to depend on the input
> length (I'll omit the proof; consider the language of strings containing
> a "1").
> The whole notion doesn't make much sense for a Turing machine on
> a single input (we're just saying "these are cells the TM never
> meaningfully uses, even though it might read/write them"), but if you
> allow parts of the inputs to be chosen by different actors, the idea
> makes more sense.
> You can come up with a reasonable definition for a constant number of
> actors. If there are K actors, let A1, A2, ..., AK be disjoint sets and
> give the TM K read-only input tapes plus one work tape, where input tape
> i is contained in Ai, and so on...
> But that's not good enough. Real systems interact with an arbitrary
> number of actors, each wanting to be isolated from the others.
> So here's a question. Is it possible to give any TM-based definition of
> isolation that (1) doesn't depend on the number of actors or input
> length, and (2) is more insightful than
>    On any K-tuple input (W1, W2, ..., WK) the machine outputs a K-tuple
>    (R1, R2, ..., RK) and if Wi is fixed, Ri is fixed no matter how you
>    change the other Wj's.
> That definition doesn't satisfy me because it has nothing to do with
> computation; it's just a property of a *function* that a TM might
> compute. It doesn't expose any Turing-machine internals to reason about.
> Is there a good definition that does?
> -Taylor
> _______________________________________________
> langsec-discuss mailing list
> langsec-discuss at mail.langsec.org
> https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss

More information about the langsec-discuss mailing list