基于Ｚｎ＊中二次剩余问题，Ｇｏｌｄｗａｓｓｅｒ与Ｍｉｃａｌｉ［１］首先提出了一种具有多项式安全的概率公开钥密码体制。由此几种基于Ｚｎ＊中γ—次剩余问题的概率加密体制也被建立起来（本文称之为广义ＧＭ体制）。概率公开钥密码体制只有是多项式安全的，才能体现它作为一种概率加密体制所特有的特点，但广义ＧＭ体制的多项式安全性并没有得到证明。本文用较独特的方法证明了广义ＧＭ体制是多项式安全的。