There are three well-known identification schemes: the Fiat-Shamir, GQ and Schnorr identification schemes. All of them are proven secure against the passive or active attacks under some number-theoretic assumptions. However, efficiencies of the reductions in those proofs of security are not tight, because they require "rewinding" a cheating prover. We show an identification scheme IDKEA1, which is an enhanced version of the Schnorr scheme. Although it needs the four exchanges of messages and slightly more exponentiations, the IDKEA1 is proved to be secure under the KEA1 and DLA assumptions with tight reduction. The idea underlying the IDKEA1 is to use an extractable commitment for prover's commitment. In the proof of security, the simulator can open the commitment in two different ways: one by the non-black-box extractor of the KEA1 assumption and the other through the simulated transcript. This means that we don't need to rewind a cheating prover and can prove the security without loss of the efficiency of reduction.

Non-malleability is an important security property of commitment schemes. The property means security against the man-in-the-middle attack, and it is defined and proved in the simulation paradigm using the corresponding simulator. Many known non-malleable commitment schemes have the common drawback that their corresponding simulators do not work in a straight-line manner, requires rewinding of the adversary. Due to this fact, such schemes are proved non-malleable only in the stand-alone cases. In the multiple-instances setting, i.e., when the scheme is performed concurrently with many instances of itself, such schemes cannot be proved non-malleable. The paper shows an efficient commitment scheme proven to be non-malleable even in the multiple-instances setting, based on the KEA1 and DDH assumptions. Our scheme has a simulator that works in a straight-line manner by using the KEA1-extractor instead of the rewinding strategy.