Key Techniques Of Trusted Cryptographic Computation And Their Applications To Electronic Commerce

An investigation of the key techniques of trusted cryptographic computation is taken in this thesis, including efficient knowledge proofs, trusted public-key encryptions and oblivious encryptions, digital signatures and anonymous signatures with high security, and trusted electronic commerce. Attention is focused on improving the security and efficiency of such cryptographic primitives. The main contributions follow below. 1. The first aspect is about knowledge proof techniques. A simple knowledge proof to prove that one secret integer lies in a specific interval is proposed. The proposal is much simpler but more efficient than the proof protocol due to Boudot. 2. The second aspect is about encryptions and trusted encryptions. The core technique in symmetric cryptosystem, i.e., nonlinear S-Box, is first introduced to public-key cryptosystem. Novel public-key cryptosystems are suggested using random high-density knapsack problem to simulate ElGamal/McEliece cryptosystems. Improvements of ElGamal encryption and RSA encryption are proposed. An approach is proposed to efficiently simulate exponentiation operation using iteration of S-Box, and then to implement the key agreement, public-key encryption and digital signature based on discrete logarithm problem. A concrete instance is presented in which the S-Box iteration is much less time-consuming than modular exponentiation. The analog of DLP-based cryptosystems is about 300 times more efficient than RSA cryptosystem or ElGamal cryptosystem. Since it is more difficult to determine the times of iterations from the input and output of S-Box than to compute discrete logarithm, smaller key size is possible to achieve the same security. Therefore, the new method to design public-key cryptosystem is enjoying a promising application. Under the assumption that the random high-density knapsack problem is infeasible, the proposed schemes are provably secure against ciphertext-only attack. The schemes are computationally 14000 times more efficient than RSA cryptosystem. Since knapsack problem is NP-complete, the scheme seems secure against quantum adversaries in the future. The publicly verifiable ElGamal encryption due to Stadler is improved to meet semantic security and extended to multiple-receiver settings. Also, a new publicly verifiable RSA encryption is suggested, which is more efficient than the generic construction. 3. The third aspect is about digital signatures. The computation complexity assumptions and signature pattern are formalized against quantum adversaries. According to the pattern, a digital signature based on random high-density knapsack problem is proposed. Under rational complexity assumptions and security parameters, the scheme enjoys the same computation cost as that of RSA signature but plausible security against quantum adversaries. Digital signatures are first proposed using irreversible physical process. Based on the second principle of thermodynamics, a digital signature is presented and its implementation in discrete model is considered. The generic ring signature method due to Abe is extended to meet knowledge signature using cut-and-choose technique. Based on the graphic isomorphism problem, a ring signature is proposed using the extended method. The concept of shared-key signature is first formalized to implement anonymous signature. It overcomes the born inefficiency of ring signature in which the complexity of signature grows with the possible number of ring members. Based on the NP-complete weak independence problem, a concrete scheme is proposed to exemplify the shared-key signature. 4. The fourth aspect is about trusted oblivious encryptions. Based on discrete logarithm problem, adaptive and non-adaptive oblivious transfers are proposed with optimal online complexity. The schemes are the first ones to realized oblivious transfers with optimal online complexity, i.e., there exists no design with more online efficiency than our schemes. The schemes are also improved to meet public verifiability and ensure the outputs of the protocols are trustable. 5. The fifth aspect is about applications of trusted cryptographic computations. Publicly verifiable electronic auctions are proposed to break the trust bottleneck in electronic auction. The first cryptographic bargain is implemented to ensure the output of protocol is trustable. The scheme is efficient and simple to implement. The thesis implements the trustworthiness of the cryptographic primitives and protocols without trusted third parties. Their trustworthiness is based on computational complexity assumptions rather than trust assumptions.