Patent ID: 8422683

Claim:
A method for requesting a proof of a security policy by a verifier, wherein the security policy is described by a graph G 1 of a prover system described by a graph G 2 , the method comprising: sending a query to the prover system; receiving attestation data at the verifier from the prover system responsive to the query, wherein the attestation data comprises graph F 1 comprising a permutation of graph G 1 , and graph F 2 comprising a permutation of graph G 2 , wherein G 1 is a subgraph of G 2 ; requesting from the prover system, by the verifier, a proof of a property between two or more of G 1 , G 2 , F 1 , and F 2 , wherein the proof is an NP-complete problem comprising proof that F 1 is isomorphic to a subgraph of F 2 randomly requested from a set of proofs comprising: proof that F 1 and F 2 are isomorphic to G 1 and G 2 respectively, and proof that F 1 is isomorphic to a subgraph of F 2 ; requesting encryption keys for a property of the graphs F 1 and F 2 , wherein the property is consistent with F 1 being isomorphic to a subgraph of F 2 ; decrypting edges of the graphs F 1 and F 2 corresponding to the encryption keys for the property of the graph; and determining whether the property is met, and indicating a successful proof of the security policy when the property is met, and indicating an unsuccessful proof of the security policy when the property is not met.