| SEMANTIC ENCODING | ----------------- | | This agent illustrates Semantic Encoding, a highly secure method and system | of protecting a database against unauthorized use. | | The method and system is joint work with Professor Paul Benjamin. | | As a simple example, suppose we wish to protect the table: | | | | this-person has an address in this-state | ================================================ | George Bush Texas | George Bush Washington D. C. | Rick Perry Texas | Tom Ridge Washington D. C. | | | Instead of storing the table, we store its projections T1 and T2, with scrambled row numbers: | | | the table T1 this-i this-u the table T2 this-i this-u | =============================== ==================================== | 4 Rick Perry 1 Texas | 10 George Bush 9 Washington D. C. | 11 Tom Ridge | | | | We also store a padded, encoded interconnection table: | | | | the padded interconnection table T12pad this-i this-j | ====================================================== | 0 4 | 1 7 | 4 3 | 4 8 | 7 2 | 9 6 | 9 8 | 11 0 | 12 6 | | | | An authorized user knows some constants 3, 5, and 13 that are used to define | a function h and its inverse function g that is used in encoding. So, he can | decode T1, T12pad, and T2 to get back a copy Td the original table T using this rule: | | | the table T1 eg-i eg-u | the function h applied to eg-i yields eg-i' | the padded interconnection table T12pad eg-i' eg-j' | the function g applied to eg-j' yields eg-j | the table T2 eg-j eg-v | ---------------------------------------------- | decoded table Td eg-u eg-v | | | Of course, in real use, we would define a more complicated function h, | or we could even use a source of genuinely random numbers. | We could also optionally pad T1 and T2 with nonsense rows. | | US and International Patents are pending for Semantic Encoding | | To get a copy of a white paper that explains the method in detail, | please send an email to adrianw@snet.net . the table T1 eg-i eg-u the function h applied to eg-i yields eg-i' the padded interconnection table T12pad eg-i' eg-j' the function g applied to eg-j' yields eg-j the table T2 eg-j eg-v ---------------------------------------------- decoded table Td eg-u eg-v the table T1 eg-i eg-u the padded interconnection table T12pad eg-i eg-j the table T2 eg-j eg-v -------------------------------------------------- attack table Ta eg-u eg-v the padding row number eg-k consisting of eg-i' eg-j' is to be added to T12 --------------------------------------------------------------------------- the padded interconnection table T12pad eg-i' eg-j' the interconnection table T12 eg-i' eg-j' -------------------------------------------------- the padded interconnection table T12pad eg-i' eg-j' the table T1 eg-i eg-u the function h applied to eg-i yields eg-i' the table T2 eg-j eg-v the function h applied to eg-j yields eg-j' table T eg-u eg-v ---------------------------------------------- the interconnection table T12 eg-i' eg-j' eg-i is a number in the range 0 to eg-r minus one the table eg-T is in use not : the table eg-T has a row number eg-i ------------------------------------------------- the table eg-T does not use the row number eg-i count : the table P1 of available padding eg-i' eg-j' = some-number-of-rows -------------------------------------------------------------------------- the table P1 of available padding has that-number-of-rows available row some-k of the available padding is to be added to T12 row number eg-k the table P1 of available padding eg-i' eg-j' --------------------------------------------------------------------------- the padding row number eg-k consisting of eg-i' eg-j' is to be added to T12 the table P1 of available padding has some-number-of-rows available we want some-s padding rows added to T12 that-number-of-rows divided by that-s = some-k remainder some-r1 some-t is a number in the range 1 to that-s that-t * that-k = some-t-times-k that-k divided by 2 = some-k-on-2 remainder some-r2 that-t-times-k - that-k-on-2 = some-tkm that-tkm + 1 = some-i ----------------------------------------------------------------- row that-i of the available padding is to be added to T12 we want some-s padding rows added to T12 -------------------------------------------- 1 is a number in the range 1 to that-s we want some-s padding rows added to T12 some-t1 is a number in the range 1 to that-s that-t1 is less than that-s that-t1 + 1 = some-t --------------------------------------------- that-t is a number in the range 1 to that-s we want this-s padding rows added to T12 ================================================ 4 row eg-k : the table P1 of available padding eg-i' eg-j' ------------------------------------------------------------ row number eg-k the table P1 of available padding eg-i' eg-j' the table T1 does not use the row number eg-i' eg-j' is a number in the range 0 to eg-r minus one g of eg-i' is not used in T1 or g of eg-j' is not used in T2 ------------------------------------------------------------ the table P1 of available padding eg-i' eg-j' eg-i' is a number in the range 0 to eg-r minus one the table T2 does not use the row number eg-j' g of eg-i' is not used in T1 or g of eg-j' is not used in T2 ------------------------------------------------------------ the table P1 of available padding eg-i' eg-j' the function g applied to eg-i' yields eg-i the table T1 does not use the row number eg-i --------------------------------------------- g of eg-i' is not used in T1 the function g applied to eg-j' yields eg-j the table T2 does not use the row number eg-j --------------------------------------------- g of eg-j' is not used in T2 g of eg-i' is not used in T1 eg-j' is a number in the range 0 to eg-r minus one ------------------------------------------------------------ g of eg-i' is not used in T1 or g of eg-j' is not used in T2 eg-i' is a number in the range 0 to eg-r minus one g of eg-j' is not used in T2 ------------------------------------------------------------ g of eg-i' is not used in T1 or g of eg-j' is not used in T2 the table eg-T eg-i eg-u ------------------------------------ the table eg-T has a row number eg-i the table eg-T eg-i eg-u ------------------------ the table eg-T is in use row eg-i : table T projected on column 1 eg-u the function scramble1 applied to eg-i yields eg-i' ----------------------------------------------------- the table T1 eg-i' eg-u row eg-j : table T projected on column 2 eg-v the function scramble2 applied to eg-j yields eg-j' ----------------------------------------------------- the table T2 eg-j' eg-v table T eg-u eg-v ---------------------------------- table T projected on column 1 eg-u table T eg-u eg-v ---------------------------------- table T projected on column 2 eg-v | Next is the original table to be encoded. In real use it is represented by its row-numbered projections. this-person has an address in this-state ======================================== George Bush Texas George Bush Washington D. C. Rick Perry Texas Tom Ridge Washington D. C. some-person has an address in some-state --------------------------------------- table T that-person that-state eg-i is a number in the range 0 to eg-r minus one the parameters for a-function are eg-p eg-q and eg-r eg-p * eg-i = eg-pi eg-pi + eg-q = eg-piplusq eg-piplusq divided by eg-r = a-quotient remainder some-i' ------------------------------------------------------------ the function that-function applied to eg-i yields eg-i' the function h applied to eg-i yields eg-k ---------------------------------------------- the function g applied to eg-k yields eg-i | Next is a table containing key information. In real use, the table would not be present. the parameters for this-function are eg-p eg-q and eg-r ======================================================= h 3 5 13 scramble1 7 3 13 scramble2 5 4 13 the parameters for h are eg-p eg-q and eg-r ---------------------------------------------- 0 is a number in the range 0 to eg-r minus one the parameters for h are eg-p eg-q and eg-r eg-i is a number in the range 0 to eg-r minus one eg-i + 1 = eg-i1 eg-i1 is less than eg-r -------------------------------------------------- eg-i1 is a number in the range 0 to eg-r minus one