Programmability in the Generic Ring and Group Models

 

Mario Larangeira and Keisuke Tanaka

 

Tokyo Institute of Technology

W8-55, 2-12-1 Ookayama Meguro-ku, Tokyo 152-8552, Japan

larangeira.m.aa@m.titech.ac.jp, keisuke@is.titech.ac.jp

 

Abstract

The programmability has long been used as a tool to prove security of schemes in the random

oracle model (ROM) even in the cases where schemes do not seem to have a security proof in the

standard model [3, 8, 10]. On the other hand, it seems that a similar property has never been studied in

the generic models, i.e., the generic ring and group models, respectively the GRM and the GGM. This

work 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 reduction R

from a problem P to an adversary breaking the scheme in some sense, and (2) use the GRM/GGM

to find a lower bound in the complexity of solving P. We observe that in such a model the simulator

can choose the outputs for the generic operation oracle in a similar fashion as the programmability

property of the ROM. We introduce four models named programmable and non-programmable for

the GGM and analogously for the GRM. We show that in the programmable generic models it is

possible to turn around the negative result by Nielsen [21], regarding the non-committing encryption

in the presence of an adversary who corrupts the receiver. We illustrate our idea by proving that the

Goldwasser-Micali encryption scheme is a non-committing encryption scheme regarding corruption

of the receiver in the programmable GRM. Whereas, for the programmable GGM, we show that the

popular ElGamal encryption scheme is also non-committing despite the corruptions of the receiver

and the sender. In both schemes the attack exposes the secret key.

 

Keywords: Non-committing, programmability, generic ring model, generic group model

 

Journal of Internet Services and Information Security (JISIS), 1(2/3): 57-73, August 2011 [pdf]