Cryptographic methods for demonstrating satisfiable formulas from propositional logic
OwnerStefanus A. Brandsinventor
Life of this patent
Estimating the term…
Abstract
Cryptographic methods are disclosed, which allow a prover party, who holds a number of secrets, to demonstrate satisfiable formulas of propositional logic, wherein the atomic propositions are linear relations between the secrets. The demonstration reveals no more information than is contained in the formula itself. Some implementations allow an unlimited number of such demonstrations to be made, without revealing any additional information about the secrets, whereas other implementations ensure that the secrets, or some of the secrets, will be revealed, if a demonstration is performed more than a predetermined number of times. The demonstrations may be zero-knowledge proofs, or signed proofs.
Claims34
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . , xk) of the Prover, satisfy a formula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←g1x1 . . . gkxk
- where g1, . . . , gk are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible;
- and
- means for demonstrating to the verifier knowledge of a representation of a first number with respect to a first vector of numbers, said first nunber and each nunber in said first vector of numbers being a product of powers of numbers in the set, {h, g1, . . . , gk}, and their inverses and wherein said formula is represented by “R1 OR . . . OR Ri” and each sub-formula Ri for 1≦i≦l, connects linear relations in said secrets by zero or more “AND” connectives and at most one “NOT” connective.
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . , xk) of the Prover, satisfy a formula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←g1x1 . . . gkxk
- where g1, . . . , gk are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible;
- and
- means for demonstrating to the verifier knowledge of a representation of a first number with respect to a first vector of numbers, said first number and each number in said first vector of numbers being a product of powers of numbers in the set, {h, g1, . . . , gk}, and their inverses and wherein said formula has at least one “OR” logical connective, said apparatus further comprising simulating means for simulating, using self-chosen challenges and self-chosen responses, the demonstration of knowledge of at least one second number with respect to at least one second vector of numbers.
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . xk) of the Prover, satisfy a formula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←g1x1 . . . gkxk
- where g1, . . . , gk are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible;
- and
- means for demonstrating to the verifier knowledge of a representation of a first number with respect to a first vector of numbers, said first number and each number in said first vector of numbers being a product of powers of numbers in the set, {h, g1, . . . , gk}, and their inverses and said apparatus being operated by at least two parties, each of said at least two parties holding some but not all of said plurality of secrets.
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . , xk) of the Prover, satisfy a formula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←g1x1 . . . gkxk
- where g1, . . . , gk are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible, and
- means for demonstrating to the verifier knowledge of a representation of a first number with respect to a first vector of numbers, said first number and each number in said first vector of numbers being a product of powers of numbers in the set, {h, g1, . . . , gk}, and their inverses and said demonstrating means further comprising:
- randomness generating means, for generating k substantially random numbers, (w1, . . . , wk), each in Zqi
- initial witness computing means, for computing a ← h - w 1 g π ( l ) ∑ i = 1 k α i w i ∏ i = 2 k g π ( i ) w i ;
- response generating means, for computing k response numbers, r1, . . . , rk, in response to a challenge number, c, according to r1←cσ+w1 mod q and ri←Cxx(i)δ+w1 mod q for 2≦i≦k, where δ is equal to ( ( α l + ∑ i = 2 k α i χ π ( i ) ) - x π ( l ) ) - 1 mod q ;
- and
- transmissions means, for transmitting signals representative of at least said k response numbers.
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . , xk) of the Prover, satisfy a formula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives, said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←g1x1 . . . gkxk
- where g1, . . ., gk are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible;
- and
- means for demonstrating to the verifier knowledge of a representation of a first number with respect to a first vector of numbers, said first number and each number in said first vector of numbers being a product of powers of numbers in the set, {h, g1, . . . , gk}, and their inverses, and wherein said formula is represented by a system consisting of at least one independent linear equation and exactly one linear inequality, ( α 11 … α 1 , k - 1 1 0 … 0 ⋮ ⋮ 0 ⋰ ⋰ ⋮ ⋮ ⋮ ⋮ ⋰ ⋰ 0 α l1 ⋯ α l , k - 1 0 ⋯ 0 1 ) ( x π ( 1 ) ⋮ ⋮ x π ( k ) ) = ( b 1 - f 1 ε ⋮ ⋮ b l - f 1 ε ) mod q ,
- where π(−) is a permutation of {1, . . . , k}, q denotes the order of said group and ε is a non-zero difference number in Zq, and said first number is equal to ∏ i = 1 l g π ( k - l + i ) f 1 ,
- and said first vector of numbers is equal to ( h - 1 ∏ i = 1 l g π ( k - l + i ) b 1 , g π ( 1 ) ∏ i = 1 l g π ( k - 1 + l ) - a 1 , … , g π ( k - 1 ) ∏ i = 1 l g π ( k - l + i ) - a l , k - 1 ) .
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . , xk) of the Prover, satisfy a fonrula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←g1x1 . . . gkxk
- where g1, . . . , gk are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible;
- and
- means for demonstrating to the verifier knowledge of a representation of a first number with respect to a first vector of numbers, said first number and each number in said first vector of numbers being a product of powers of numbers in the set, {h, g1, . . . , gk}, and their inverses and wherein said formula is represented by the linear inequality,
- χπ(1)≠α1+α2χπ(2) . . . +αkωπ(k) mod q,
- where π(·) is a permutation of {1, . . . , k} and q denotes the order of said group, and said first number is equal to gπ(−1), and said first vector of numbers is equal to
- (gα(1)α1h−1, gπ(1)α2gπ(2) . . . gπ(1)αkgπ(k))
- said demonstrating means further comprising:
- randomness generating means, for generating k substantially random numbers, (w1, . . . , wk), each in Zqi
- initial witness computing means, for computing a ← h - w 1 g x ( 1 ) ∑ i = 1 k a i w i ∏ i = 2 k g π ( i ) w 1 ;
- response generating means, for computing k response numbers, r1, . . . , rk, in response to a challenge number, c, according to r1←cσ+w1 mod q and r1←Cxπ(i)δ+w1 mod q for 2≦i≦k, where δ is equal to ( ( α 1 + ∑ i = 2 k α i χ π ( i ) ) - x π ( 1 ) ) - 1 mod q ;
- and
- transmissions means, for transmitting signals representative of at least said k response numbers.
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . , xk) of the Prover, satisfy a formula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←g1x1 . . . gkxk
- where g1, . . . , gk are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible;
- and
- means for demonstrating to the verifier knowledge of a representation of a first number with respect to a first vector of numbers, said first number and each number in said first vector of numbers being a product of powers of numbers in the set, {h, g1, . . . , gk}, and their inverses and wherein said formula, or a sub-fornula of said formula, is represented by ( χ π ( 1 ) = α 1 + ∑ i = 2 k α i χ k ( l ) mod q )
- OR ( χ p ( 1 ) = β 1 + ∑ i = 1 k β i χ p ( i ) mod q ,
- where π(·) and ρ(·) are permutation of {1, . . . , k} and q denotes the order of said group.
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . , xk) of the Prover, satisfy a formula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←g1x1 . . . gkxk
- where g1, . . . , gk are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible;
- and
- means for demonstrating to the verifier knowledge of a representation of a first number with respect to a first vector of numbers, said first number and each number in said first vector of numbers being a product of powers of numbers in the set, {h, g1, . . . , gk}, and their inverses and wherein said formula is represented by a system of l<k independent linear relations, ( α 11 ⋯ α 1 , k - l 1 0 ⋯ 0 ⋮ ⋮ 0 ⋰ ⋰ ⋮ ⋮ ⋮ ⋮ ⋰ ⋰ 0 α l1 ⋯ α l , k - l 0 ⋯ 0 1 ) ( I π ( 1 ) ⋮ ⋮ I π ( k ) ) = ( b 1 ⋮ ⋮ b l ) mod q ,
- where π(−) is a permutation of {1, . . . , k} and q denotes the order of said group, and said fist number is equal to ( h ( ∏ i = 1 l g π ( k - l + i ) b i ) ) - 1
- and said first vector of numbers is equal to ( g π ( i ) ∏ i = 1 l g x ( k - l + i ) - α i1 , … , g π ( k - l ) ∏ i = 1 l g π ( k - l + i ) - α i , k - l ) .
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x1, . . . , xk) of the Prover, satisfy a formula from propositional logic, said formula including linear relations in said secrets and being connected by one or more logical connectives said apparatus comprising:
- means for generating a public value h of said Prover, wherein
- h←Y1x1 . . . Ykxkxk+1ν mod n,
- where n is the product of at least two distinct prime numbers, ν is an integer, Y1, . . . , Yk are substantially random numbers of substantially high order in the group Z*n and xk+1 is a number in Z*n;
- and
- means for demonstrating knowledge to said Verifier of a representation of a first number with respect to a first vector of numbers, said first number and all but one of the numbers in said first vector of numbers being a product of powers of numbers in the set, {h, Y1, . . . , Yk}, and their inverses, and the last number in said first vector of numbers being ν.
Dependencies are inferred from the claim text.