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]