Encrypted Search Indices and Multi-Key PKI

As an example of encrypted space operations, consider search indices which are encrypted / hashed.

1. User enters clear text query. Client encrypts and sends to server.
2. Server matches encrypted query to encrypted index. Returns pointers to client indicating result set.
3. Client displays result set.

The pointers, or references to documents, can also be encrypted.

The beauty of this is that the server doesn't suffer so much from the risks associated with aggregation of valuable content. The search server with its index and document pointers is not useful to anyone with inappropriate access to it.

This does raise an interesting question for PKI - can we have a set of data that is encrypted once, but can be decrypted by distinct keys, 1 per distinct authorised client.

You may suggest a simpler solution - why not have an encrypted server disk, with SSL encrypted communication between client and server. The aim here is to have no plain text material at all on the server or on the communication link - not even in memory.

Data Operations in Encryption Space

A key problem with encrypted data is that it needs to be temporarily decrypted before it can be operated on. This opens up an opportunity for security breach, and more sophisticated attacks do take advantage of data in its decrypted form in a CPU, in memory or in transit across a data bus. It isn't enough for the data to be encrypted on a hard disk.

This raises the question of whether data can be operated on meaningfully whilst still in encryption space.

This would mean operators would need to be transformed from unencrypted space to encrypted space. An advantage of this is that the operations are then also encrypted, reducing the amount of information that can be gleaned by eavesdropping on the operations.

Is there a limited class of operators than can be transformed to encryption space? Is this class sufficiently wide enough to be useful? Is this constrained by the type of encryption?

Interpretation of Latent Semantic Indexing

Latent Semantic Indexing is the leading approach to information retrieval which aims to uncover some of the underlying meaning of documentsthrough a transformation in the vector document-term model.

The results are indeed better than simple rerieval based on term matching. In particular you may return relevant documents which happen to contain none of the query terms.

But what is the intuitive interpretation of Latent Smenatic Indexing. What is the meaning of the transformed space?

Deduction, Abduction & Induction

Wikipedia concisely clarifies the distinction between the three forms of inference:

Deductive inference - finding the effect, given the cause and the rule.
Abductive inference - finding the cause, given the rule and the effect.
Inductive inference - finding the rule, given the cause and the effect.

   [ cause ] → → → [ rule ] → → → [ effect ]
  (abduction)     (induction)     (deduction)

Wikipedia gives an example using Hooke's law F=k.x (rule) which relates the force applied (cause) to a spring and its extension (effect). If the force and Hooke's law are known, the elongation of the beam can be deducted. If the elongation and Hooke's law are known, the force acting on the beam can be abducted. If the elongation and the force are known, Hooke's law can be inducted.

Semantic & Syntactic Entailment

Semantic entailment is the same as the implication that we have seen earlier. If all truth assignments that satisfy a set of forumulae S also satisfy A, then S semantically entails A. That is, S→A.

Syntactic entailment is slighly different. If A can be derived from S using a finite application of the propositional inference rules, then S syntactically entails A.

What does it mean if only one of the above applies?

Calculus of Propositional Logic

Propositional logic indeed has a calculus which allows us to verify arguments and prove theorems.

Common algebra has axiomatic inference rules which allow the derivation of new true formulae from assumed true formulae, either as continuations of an existing formula, or as a combination of multiple formulae. Similarly, the propositional calculus provides inference rules for propositional logic.

Inference Rules

The text Schaum's Outline of Logic presents these rules and provides worked examples of their use.

The following summarises the 10 rules of propositonal inference rules. All these rules either introduce or eliminate a propositional logic operator.

The first eight are non-hypothetical:

* Negation Elimination
   From ¬¬p, infer p.
* Conjunction Elimination
   From (p ∧ q), infer p
   From (p ∧ q), infer q.
* Conjunction Introduction
   From p, q, infer (p ∧ q).
* Disjunction Introduction
   From p, infer (p ∨ q)
   From p, infer (q ∨ p).
* Disjunction Elimination
   From (p ∨ q), (p → r), (q → r), infer r.
* Biconditional Introduction
   From (p → q), (q → p), infer (p ↔ q).
* Biconditional Elimination
   From (p ↔ q), infer (p → q)
   From (p ↔ q), infer (q → p).
* Conditional Elimination
   From p, (p → q), infer q.

The final two are hypothetical inference rules in that they temporarily assume the truth of a hypothesis.

* Negation Introduction
   If hypothesis (p→q) leads to (p→ ¬q), infer ¬p.
* Conditional Introduction
   If hypothesis p allows a proof of q, infer (p → q).

Truth Table for Implication

I was surprised the binary implication operator (→), also called the conditional, has a truth table, just as the AND and OR logical operators do. It is as follows:

A B (A→B)
0 0  1
0 1  1
1 0  0
1 1  1

That is, we can only say something about B if A is true. There is a similar table for the binary biconditional operator (↔):

A B (A↔B)
0 0  1
0 1  0
1 0  0
1 1  1

This means we can determine truth tables for compound statements such as A→(B→C).