# Presentation: 933158

## Trusted Computing Amidst Untrustworthy Intermediaries

**Mike Langston**
- Department of Computer Science
- University of Tennessee
- currently on leave to
- Computer Science and Mathematics Division
- Oak Ridge National Laboratory
- USA

## Overview

- Programs

- Data

- Highly Parallel
- Scalable Network
- Variable Topology
- Internet Like
- But Untrusted!

## Possible Solutions

- Accept faulty results.
-       Uh, no thanks.
- Authenticate/verify by central authority.
-       Unrealistic, does not scale.
- Exploit complexity and checkability.
-        Problems in *NP* can be hard to solve -- but they are
-                always easy to check!
-          No need for centralized control, ownership,
-                or verification.

## A Little Complexity Theory 

***The Classic View:***** **

*P*

*NP*

*PSPACE*

*Σ*

**2**

- P

- ...

- ...

- “easy”

## A Little Complexity Theory

***The Classic View: ***

*P*

*NP*

*PSPACE*

*Σ*

**2**

- P

- ...

- ...

- “easy”

- “hard”

*NP*-complete

## A Little Complexity Theory

***The Classic View:***

*P*

*NP*

*PSPACE*

*Σ*

**2**

- P

- ...

- ...

- “easy”

- “hard”

- “fuggettaboutit”

## Parameter Sensitivity: Instance(n,k)

- Suppose our problem is, say, *NP*-complete.
- Consider an algorithm with a time bound such as *O(2**k+n**)**.*
- And now one with a time bound more like *O(2**k**+n)**.*

## Parameter Sensitivity: Instance(n,k)

- Suppose our problem is, say, *NP*-complete.
- Consider an algorithm with a time bound such as *O(2**k+n**)**.*
- And now one with a time bound more like *O(2**k**+n)**.*
- Both are exponential in parameter value(s).

## Parameter Sensitivity: Instance(n,k)

- Suppose our problem is, say, *NP*-complete.
- Consider an algorithm with a time bound such as *O(2**k+n**)**.*
- And now one with a time bound more like *O(2**k**+n)**.*
- Both are exponential in parameter value(s).
- But what happens when *k* is fixed?

## Parameter Sensitivity: Instance(n,k)

- Suppose our problem is, say, *NP*-complete.
- Consider an algorithm with a time bound such as *O(2**k+n**)**.*
- And now one with a time bound more like *O(2**k**+n)**.*
- Both are exponential in parameter value(s).
- But what happens when *k* is fixed?
- Fixed Parameter Tractability: confines superpolynomial behavior to the parameter.

## Complexity Theory, Revised

***Hence, the Parameterized View:***

- FPT

- ...

- ...

- W[1]

- W[2]

- XP

- “solvable
-  (even if
-  NP-complete)”

## Complexity Theory, Revised

***The Parameterized View:***

- FPT

- ...

- ...

- W[1]

- W[2]

- XP

-   “solvable
-   (even if
-  NP-hard!)”

- “heuristics only”

## Complexity Theory, Revised

***The Parameterized View:***

- FPT

- ...

- ...

- W[1]

- W[2]

- XP

-  “solvable
-   (even if
-  NP-hard!)”

- “heuristics only”

- “I said fuggettaboutit!”

## Target Problems

** ****Not membership in *****P***** (assuming *****P******≠NP*****)**
** ****hard to compute**
**  **

## Target Problems

** ****Not membership in *****P***** (assuming *****P******≠NP*****)**
** ****hard to compute**
**  **
** ****Membership in *****NP***
*** *****easy to check**
** ****   **

## Target Problems

** ****Not membership in *****P***** (assuming *****P******≠NP*****)**
** ****hard to compute**
**  **
** ****Membership in *****NP***
*** *****easy to check**
** ****   **
** ****Fixed Parameter Tractable**
** ****use kernelization and branching**

## Kernelization

- Consider Clique and Vertex Cover
- High Degree Rule(s)
- Low Degree Rule(s)
- LP, Crown Reductions
- kernel of linear size, and extreme density
- the “hard part” of the problem instance

## Branching

- Let’s stay with Clique and Vertex Cover
- Bounded tree search
- Depth at most *k*
- With this technique, we can now solve vertex cover in *O(1.28**k**+n)* time
- Easily parallelizable
- No processor sees another’s work, nor the original graph

## . . . . . . 

- . . . . . .

- Untrusted intermediaries
- cannot deduce data

- Data
- decomposition

- Nor can they
- spoof answers

- Answer check
- (*NP *certificate)

- .

**Branching as **
**A Form of **
**Cyber Security**

## Overall Appeal

- Verifiability
- easy to check answers: a faulty or malicious processor cannot invalidate or subvert computations

## Overall Appeal

- Verifiability
- easy to check answers: a faulty or malicious processor cannot invalidate or subvert computations
- Security
- damage from intrusion contained: strong concealment of the total problem is a natural part of this method

## Overall Appeal

- Verifiability
- easy to check answers: a faulty or malicious processor cannot invalidate or subvert computations
- Security
- damage from intrusion contained: strong concealment of the total problem is a natural part of this method
- Scalability
- branching translates into partitioning: no *a priori* bounds on the degree of parallelism

## Overall Appeal

- Verifiability
- easy to check answers: a faulty or malicious processor cannot invalidate or subvert computations
- Security
- damage from intrusion contained: strong concealment of the total problem is a natural part of this method
- Scalability
- branching translates into partitioning: no *a priori* bounds on the degree of parallelism
- Robustness
- subtrees are compartmentalized: processes can be reassigned at will

## Research Thrusts

- Range of amenable problems?
- FPT
- non FPT
- Ubiquity of untrustworthy processors?
- grid computing
- unbrokered resource sharing
- Relationship to traditional forms of security?
- internet-style lightweight security
- no heavyweight authentication needed