关键词: 非确定的公钥密码, 确定的公钥密码, 解密成功率, Euler-φ_q函数, N-HFMS

Abstract: First, we introduced the concept of the nondeterministic public key cryptography (PKC) and decryption success rate (DSR),
 and gave its implementation scheme NHFMS based on the difficulty of the multivariate problem over finite field
. Then， we analyzed the number of nonsingular matrices in F_q［M］ and deduced the accurate counting formula of nonsingular matrices in F_q［M］ by using Euler-φ_q function. The results show that the method can not only accurately estimate the DSR of any specific instance of NHFSM, but also deduce the the lower limit of DSR of NHFSM scheme, which theoretically proves the feasibility of NHFMS. By using NHFSM scheme, the session key can be agreed, thus secure communication can be realized.

Key words: nondeterministic PKC(NPKC), deterministic PKC(DPKC), decryption success rate(DSR), Euler-φ_q function, N-HFMS