Algebraic Membership Obfuscation

Abstract

An algebraic set is the solution set of a system of algebraic equations. The usual way to determine if a point is in an algebraic set is to determine if the point satisfies all the equations. This dissertation studies how to give membership testing of an algebraic set without selling out the equations. The discrete logarithm problem (DLP) is reduced to the subset product problem (SP). The twin subset product problem (TSP) with respect to twin points is defined. The multiple subset product problem (MSP) with respect to relative points is defined. A lattice attack to low density MSP with identical points is given. In order to avoid the attack, the subset product with errors problem (SPE) is proposed. SP is reduced to SPE. The twin subset product with errors problem (TSPE) is proposed. The multiple subset product with errors problem (MSPE) is proposed. With a DLP algorithm, MSPE can be converted into a similar form to the learning with errors problem (LWE). The ideal subset product with errors problem (ISPE) is proposed. SPE, TSPE, MSPE and ISPE are conjectured to be post-quantum hard. A new obfuscation for small superset and big subset testing is given based on SP. A new obfuscation for conjunctions is given based on TSP. The new obfuscations are more elegant than the previous works. An obfuscation for algebraic set membership testing is given based on small superset obfuscation. This is the first solution to tackle the problem in great generality. From algebraic membership obfuscation, a general obfuscation method is given to deal with membership problems in generic topological spaces. Topology is generalized to genology, giving a more flexible way to represent mathematical objects that have finite generators. The general method gives a new view to look at several open problems, revealing a fundamental relation between these seemingly unrelated problems.