Nondeterministic Plaintext Space Public Key Cryptosystem And Its Implementaiton

This paper introduced the conception of NPS-PKC and DSR, namely the“Nondeterministic Plaintext space PKC” and “Decryption Success Rate”.Based on the difficulty of the BMQ problem over finite field(using3-coloringproblem of the G-graph, we can prove that the BMQ problem in the finite fieldwith Q elements is the NP complete), firstly, a transitional algorithm(DPS-PKC)is introduced. The explanation and interpretation of the idea of DPS’sconstruction is as follows:The key point is how to search for the matrices sets which is satisfied theconstraint conditions. And gives the method of how to find the ergodic matrix.Next, a method is given to construct a NPS-PKC and to find and constructergodic matrix that is satisfies the NPS-PKC constraints.In order to analyze the DSR of the instance of NPS-PKC, we deduced thecounting formula for nonsingular matrices in Fq M based on the Euler q-function. Let m(x)=p(x)1·p(x)k1k Fq (x)\0where p1(x),,pk(x) aredistinct irreducible polynomials and1,, kare positive integers, ThenBy the formula, we can precisely estimate both the lower bound of DSR of NPS-PKC and the DSR of each NPS-PKC instance. By the estimation results,We have theoretically proved the feasibility of the proposed NPS-PKC scheme.