The isomorphism of polynomials with two secret (IP2S) problem is one candidate of computational assumptions for post-quantum cryptography. The idea of identification scheme based on IP2S is firstly introduced in 1996 by Patarin. However, the scheme was not described concretely enough and no more details are provided on how to transcribe the idea into a real-world implementation. Moreover, the security of the scheme has not been formally proven and the originally proposed security parameters are no longer secure based on the most recent research. In this paper, we propose a concrete identification scheme based on IP2S with the idea of Patarin as the starting point. We provide formal security proof of the proposed scheme against impersonation under passive attack, sequential active attack, and concurrent active attack. We also propose techniques to reduce the implementation cost such that we are able to cut the storage cost and average communication cost to an extent that under parameters for the standard 80-bit security, the scheme is implementable even on the lightweight devices in the current market.

Lossy identification schemes are used to construct tightly secure signature schemes via the Fiat-Shamir heuristic in the random oracle model. Several lossy identification schemes are instantiated by using the short discrete logarithm assumption, the ring-LWE assumption and the subset sum assumption, respectively. For assumptions concerning the integer factoring, Abdalla, Ben Hamouda and Pointcheval [3] recently presented lossy identification schemes based on the φ-hiding assumption, the QR assumption and the DCR assumption, respectively. In this paper, we propose new instantiations of lossy identification schemes. We first construct a variant of the Schnorr's identification scheme, and show its lossiness under the subgroup decision assumption. We also construct a lossy identification scheme which is based on the DCR assumption. Our DCR-based scheme has an advantage relative to the ABP's DCR-based scheme since our scheme needs no modular exponentiation in the response phase. Therefore our scheme is suitable when it is transformed to an online/offline signature.

We propose a generic conversion from a key encapsulation mechanism (KEM) to an identification (ID) scheme. The conversion derives the security for ID schemes against concurrent man-in-the-middle (cMiM) attacks from the security for KEMs against adaptive chosen ciphertext attacks on one-wayness (one-way-CCA2). Then, regarding the derivation as a design principle of ID schemes, we develop a series of concrete one-way-CCA2 secure KEMs. We start with El Gamal KEM and prove it secure against non-adaptive chosen ciphertext attacks on one-wayness (one-way-CCA1) in the standard model. Then, we apply a tag framework with the algebraic trick of Boneh and Boyen to make it one-way-CCA2 secure based on the Gap-CDH assumption. Next, we apply the CHK transformation or a target collision resistant hash function to exit the tag framework. And finally, as it is better to rely on the CDH assumption rather than the Gap-CDH assumption, we apply the Twin DH technique of Cash, Kiltz and Shoup. The application is not “black box” and we do it by making the Twin DH technique compatible with the algebraic trick. The ID schemes obtained from our KEMs show the highest performance in both computational amount and message length compared with previously known ID schemes secure against concurrent man-in-the-middle attacks.

We present a new methodology for constructing an efficient identification scheme, and based on it, we propose a lightweight identification scheme whose computational and storage costs are sufficiently low even for cheap devices such as RFID tags. First, we point out that the efficiency of a scheme with statistical zero-knowledgeness can be significantly improved by enhancing its zero-knowledgeness to perfect zero-knowledge. Then, we apply this technique to the Girault-Poupard-Stern (GPS) scheme which has been standardized by ISO/IEC. The resulting scheme shows a perfect balance between communication cost, storage cost, and circuit size (computational cost), which are crucial factors for implementation on RFID tags. Compared to GPS, the communication and storage costs are reduced, while the computational cost is kept sufficiently low so that it is implementable on a circuit nearly as small as GPS. Under standard parameters, the prover's response is shortened 80 bits from 275 bits to 195 bits and in application using coupons, storage for one coupon is also reduced 80 bits, whereas the circuit size is estimated to be larger by only 335 gates. Hence, we believe that the new scheme is a perfect solution for fast authentication of RFID tags.

GPS is an efficient identification (ID) scheme based on Schnorr ID scheme designed for applications where low cost devices with limited resources are used and a very-short authentication time is required. Let P and V be a prover and a verifier in GPS and < g > be a multiplicative group. P holds a secret key S∈[0,S) and publishes I=g-s. In each elementary round: (1) P sends to Vx=gr where r is chosen randomly from [0,A), (2) V sends to P a random C∈[0,B), and (3) P sends y=r+cs (no modulus computation). Since there is no modular reduction on y, a key issue is whether GPS leaks information about s. It has been proved that GPS is statistical zero-knowledge, if in asymptotic sense, BS/A is negligible, where is the number of elementary rounds in one complete identification trial. In this paper, first we will show the followings. (1) We can construct a concrete attack procedure which reveals one bit of secret key s from the specified value range of y unless BS/A is negligible. We reconfirm that we must set A extremely large compared to BS. (2) This drawback can be avoided by modifying GPS into a new scheme, GPS+, in which P does not send the value of y in the specified range where y reveals some information about s. GPS+ ensures perfect ZK only by requiring both A > BS and A being a multiple of the order of g, while it allows an honest P to be rejected with probability at most BS/(2A) in one elementary round. Under the standard recommended parameters for 80-bit security where =1, |S|=160, and |B|=35, |A|=275 is recommended for GPS in GPS' paper. On the other hand, GPS+ can guarantee 80-bit security and less than one false rejection on average in 100 identifications with only |A|=210 with the same parameters as above. In practice, this implies 275-210=65 bits (≈24%) reductions on storage requirement. We have confirmed that the reduce of A also reduces approximately 4% of running time for online response using a certain implementation technique for GPS+ by machine experiment.

In [13], we proposed new decision problems related to lattices, and proved their NP-completeness. In this paper, we present a new public-key identification scheme and a digital signature scheme based on one of the problems in [13]. We also prove the security of our schemes under certain assumptions, and analyze the efficiency of ours.

Hwang-Lo-Lin proposed a user identification scheme [3] based on the Maurer-Yacobi scheme [6] that is suitable for application to the mobile environment. Hwang-Lo-Lin argued that their scheme is secure against any attack. Against the Hwang-Lo-Lin argument, Liu-Horng-Liu showed that the Hwang-Lo-Lin scheme is insecure against a Liu-Horng-Liu attack mounted by an eavesdrop attacker. However, Liu-Horng-Liu did not propose any improved version of the original identification scheme which is still secure against the Liu-Horng-Liu attack. In this paper, we propose an identification scheme that can solve this problem and a non-interactive public key distribution scheme also.

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.

Schnorr's identification scheme is the most efficient and simplest scheme based on the discrete logarithm problem. Unfortunately, Schnorr's scheme is not provably secure, i.e., the security has not been proven to be reducible to well defined intractable problems. Two works have already succeeded to construct provably secure variants of Schnorr's scheme. They have been constructed with a common approach, i.e., by modifying the formula to compute the public key so that each public key has multiple secret keys. These multiple secret keys seem to be essential for their provable security, but also give rise to a penalty in their efficiency. In this paper, we describe a new approach to constructing a provably secure variant, where we never modify the formula, and show that with our approach, we can construct a new efficient provably secure scheme.