Abstract

The programmability has long been used as a tool to prove security of schemes in the random oraclemodel (ROM) even in the cases where schemes do not seem to have a security proof in the standardmodel [3,8,10]. On the other hand, it seems that a similar property has never been studied in thegeneric models, i.e., the generic ring and group models, respectively the GRM and the GGM. Thiswork introduces this study. We start by proposing the use of the GRM and the GGM in simulation-based security proofs, instead of the classical two-step approach: (1) find an efficient reductionRfrom a problemPto an adversary breaking the scheme in some sense, and (2) use the GRM/GGMto find a lower bound in the complexity of solvingP. We observe that in such a model the simulatorcan choose the outputs for the generic operation oracle in a similar fashion as the programmabilityproperty of the ROM. We introduce four models namedprogrammable and non-programmableforthe GGM and analogously for the GRM. We show that in the programmable generic models it ispossible to turn around the negative result by Nielsen [21], regarding the non-committing encryptionin the presence of an adversary who corrupts the receiver. We illustrate our idea by proving that theGoldwasser-Micali encryption scheme is a non-committing encryption scheme regarding corruptionof the receiver in the programmable GRM. Whereas, for the programmable GGM, we show that thepopular ElGamal encryption scheme is also non-committing despite the corruptions of the receiverand the sender. In both schemes the attack exposes the secret key.