Efficient proof of knowledge of arbitrarily large data which remains unexposed
View Patent ↗This invention establishes means and protocols to secure data, and practice online authentication, using large undisclosed amounts of randomness, replacing the algorithmic complexity paradigm. Computation is limited to basic primitives like transposition, and bit-flipping. Security is credibly appraised through combinatorics calculus, and this transfers the security responsibility to the user who determines how much randomness to use.
1. A method for a party regarded as a Prover sharing with another party regarded as a Verifier a secret S in a form of a bit string which is t bits long, to prove to the Verifier that the Prover is in possession of S by
(i) the Prover applying a shared string-parceling algorithm, PARCEL, which will parcel string S to n≤t sub strings s 1 , s 2 , . . . s n such that these n substrings concatenate to S:S=s 1 ∥s 2 ∥ . . . ∥s n , then
(ii) the Prover applying a source of randomness to transpose the n substrings into a different permutation, where s i is placed in position j, and marked s ij , for i,j=1,2, . . . n, then
(iii) the Prover reassembling the n substrings according to the selected permutation, to create string S* comprised oft bits: S*=s i1 ∥s k2 ∥ . . . ∥s ln , where i,k,l are integers from the set 1,2, . . . n, then
(iv) the Prover communicating S* to the Verifier;
(v) the Verifier applies PARCEL to S and generates the same n substrings s 1 , s 2 , . . . s n , then
(vi) the Verifier performs, a re-arranging permutation, PUZZLE test, checking that these n substrings, (s 1 , s 2 , . . . s n ) can be re-arranged in a different permutation such that when these strings are concatenated according to the new permutation, they form string S*; the test is regarded ‘successful’ if such a permutation is found, and is regarded ‘failure’ if no such permutation is found; then
(vii) if the PUZZLE test is successful, the Verifier accepts the Prover, as the party which shares the possession of secret S, and when the PUZZLE test fails the Verifier rejects the Prover as possessing S.
2. The method of claim 1 , further comprising the Verifier randomly selecting a number R, communicating R to the Prover, then both the Verifier and the Prover use an agreed upon algorithm, MIX, to mix R with S to generate a string Q=MIX(S, R), shared only by the Verifier and the Prover who share the secret S; wherein Q instead of S is used in the PARCEL function and the PUZZLE test.
3. The method of claim 1 , wherein no repetition exists among the n substrings: s i ≠s j for i≠j, for i,j=1,2, . . . n.
4. The method of claim 1 , wherein the PARCEL function is defined as follows:
(i) parceling S to s 1 of length 1 bit, as the leftmost 1 bit in S, and to the rest of S, string S 1 , then
(ii) parceling S 1 to s 2 , of length 2 bits, as the leftmost 2 bits in S 1 , and the rest of S 1 , string S 2 , and so on,
(iii) parceling S (i-1) to s i , of length i bits, as the leftmost i bits in S (i-1) , and the rest of S (i-1) , string S i , and so on until s (n−1) , then
(iv) assigning s n =S (n−1) .
5. The method of claim 1 , wherein two parties share a secret string S comprised of t bits to exchange a secret transposition key T with which to transpose a permutation comprised of n entities to any one of the possible n! permutations, by regarding each s ij as an instruction to move the entity in position i to position j: i→j for i=1,2, . . . n.