A common way to produce signature schemes is to apply the Fiat-Shamir transform to an identification scheme, which preserves security in the Random Oracle Model (ROM). In this thesis, we present two results concerning security in the ROM.
First, we show that for every canonical identification scheme, the corresponding Fiat-Shamir signature scheme is secure in the ROM. Previously, only “non-trivial” canonical identification schemes were known to yield Fiat-Shamir signature schemes which are secure in the ROM.
Second, we show how to modify a certain discrete logarithm-based public-key encryption scheme so that it becomes CCA2-secure in the ROM.
This work was supervised by Charlie Rackoff.