Efficient proof of knowledge of arbitrarily large data which remains unexposed

• US 10,594,480 B2
• Filed: 02/12/2018
• Issued: 03/17/2020
• Est. Priority Date: 05/13/2016
• Status: Active Grant

• Current Assignee: Gideon Samid
• Original Assignee: Gideon Samid
• Inventors: Samid, Gideon
• Primary Examiner(s): Colin, Carl G
• Assistant Examiner(s): Yang, Han
• Application Number:
  US15/594,637
• Publication Number:
  US 20170331624A1
• Time in Patent Office: 764 Days
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

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.

Claims

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₁, s₂, . . . s_n such that these n substrings concatenate to S;

S=s₁∥

s₂∥

. . . ∥

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₁, s₂, . . . s_n, then

(vi) the Verifier performs, a re-arranging permutation, PUZZLE test, checking that these n substrings, (s₁, s₂, . . . 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₁ of length 1 bit, as the leftmost 1 bit in S, and to the rest of S, string S¹, then

(ii) parceling S¹ to s₂, of length 2 bits, as the leftmost 2 bits in S¹, and the rest of S¹, string S², 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ⁱ, and so on until s<sub>(n−

1)</sub>, then

(iv) assigning s_n=S<sup>(n−

1)</sup>.

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.