Research On Signature Schemes Applicable For Devices With Limited Computing Capability

With the rapid development of computer network communication technology and software technology, how to ensure and strengthen information security and integrity has become the major issue in the international community. Digital signature came into being. Digital signature is one of the most important directions of public key cryptography. In public key cryptography, key is a key pair composed by a public key and a private key. Signer uses the private key for encryption, while receiver uses the public key for decryption. Because it is difficult to compute the private key from the public key, the public key would not jeopardize the security of the private key. The public key can be publicly disseminated without being kept secret, while the private key should be preserved confidentially. Thus, if some one uses his private key to encrypt a message, which can be corretly decrypted, it can be sure the message is a signature of that person. This is the basic principle of digital signatures.The devices with limited computing capability includes smart card, wireless sensor, RFID, electronic key etc.. Now, using of these devices is very popular all over the world. However, they tend to have a feather in common: limited computational capability and equally limited power (at most operate on batteries), very limited response time. Thus, the designing of signature schemes applicable for these devices should mainly focus on the computational efficiency. Now, many kinds of signature systems been suitable for the devices with limited computing capability, includes multivariate signature systems, braid group based signature systems, and lattice based signature systems which belongs to the new fast public key cryptosystems; and online/offline signature systems, server-aided verification signature systems which belongs to the signature with special properties systems.This thesis is jointly supported by National Basic Research Program of China(973 Program)(No. 2007CB310704), National Natrual Science Foundation of China (No. 90718001 and No. 60821001), the 111 Project(No. B08004) and Sony (China) research laboratory supportedThe principal contributions of the work presented in this thesis are:1. We designed an efficient and secure multivariate signature scheme. For our construction, we utilized this fact that squaring is a linear operation on an extension field of F₂. The newly designed multivariate signature scheme can resist the known attacks on multivariate public key cryptosystems, including linearization equation attack, Rank attack, XL/Grobner basis algorithm attack, and differential attack.2. We improved the probabilistic perturbed method, and made the public key length of it be greatly reduced. We redesigned a proper central map according to the characteristics of the probabilistic perturbed method. We analysized the security of the signature scheme composed by the new central map and the improved probabilistic perturbed method.3. We researched the optimal online/offline signature, and improved and designed two concrete schemes which have the feathers in common: no computational cost is needed in the online phase; the offline phase is also efficient. They are especially suitable for the devices with limited computing capability.4. We improved the security model of server-aided verification signature, and analysis the two short signature based schemes proposed by Wu et al. under the new security model. We constructed a new server-aided verification signature scheme based on Paillier signature by using the homomorphic property. In our scheme, by executing the server-aided verification protocol with the server, the verifier only need perform 362 modular multiplications, while he should execute 2049 modular multiplications in the original scheme. The computational cost of verification is decreased by 80%. Furthermore, we proposed a generic construction of server-aided verification signature scheme. 5. We designed a highly efficient proxy signature scheme. Compared with other scheme, it needs no modular exponentiation and pairing in the signing algorithm. Thus, it is suitable for the low end devices. We proved that it is secure under the random oracles. Finally, we extended proxy signature scheme, and proposed a new kind of proxy signature scheme - Infinitesimal proxy signature.6. We research some properties of cubic residues, and based on which, we constructed an efficient ID-based signature scheme. Compared with other scheme, it has a very efficient signing algorithm, which only needs 161 modular multiplications at security level of 2⁸⁰. We proved that it is secure against the adaptively chosen messages and ID attack.