Patent ID: 6320966
Filing Date: 2001-11-20
Classification: H04L

Abstract:
A communication system comprising an apparatus for demonstrating by a prover entity to a Verifier entity that a plurality of secrets, (x.sub.1, . . . , x.sub.k) 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, whereinh.rarw.g.sub.1.sup.x.sup..sub.1 . . . g.sub.k.sup.x.sup..sub.kwhere g.sub.1, . . . , g.sub.k are substantially random numbers in a group in which computation of discrete logarithms is substantially infeasible; andmeans 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, g.sub.1, . . . , g.sub.k }, and their inverses and wherein said formula is represented by ""R.sub.1 OR . . . OR R.sub.i "" and each sub-formula R.sub.i for 1.ltoreq.i.ltoreq.l, connects linear relations in said secrets by zero or more ""AND"" connectives and at most one ""NOT"" connective.