Researches On Key Problems Of Provable Security Under The Random Oracle Model

With the broad implementations of the electronic business and government applications,how to design a secure and feasible cryptosystem becomes more and more significant in theresearch of cryptology. The theory of provable security is a formal analysis technique forwhich the designer defines a precise adversary model in advance, and then proves whether awell-designed cryptosystems can resist the adversary in reality. The classical provable secu-rity is usually based on the standard model, such that the probability of a successful attackcan be reduced to the advantage of resolving a well-known computationally hard problem.Commonly, the schemes that are proven secure in the standard model are less efficient, whichmakes them less practical. The formal analysis under the random oracle model becomes animportant way to balance the provable security and the efficiency in the design of cryptosys-tems. In the random oracle model, by implementing a publicly accessible random oracle,the probability of the successful attack can be reduced to a computationally hard problem aswell. Simultaneously, by using the tight reduction techniques in the random oracle model,the schemes'computational costs will also be remarkably reduced. In fact, many widely-accepted cryptographic schemes and standards had been proven secure under the randomoracle model.Although we enjoy the efficiency of the schemes that are provably secure in the randomoracle model, this model has security problems itself. Many negative results disclosed thatpseudorandom functions and hash functions in reality cannot instantiate the random oraclemanipulated in the simulations. It becomes a red hot topic in this research field on howto design a cryptographic hash function to replace the random oracle in the schemes thatare proven secure under the random oracle model. In this thesis, we summarize the knownresults and trace the security problems in the random oracle model:1. A synthetic indifferentiability analysis of some block-cipher-based hash functions isconsidered. First, a more precise definition is proposed on the indifferentiability adver-sary in block-cipher-based hash functions. Next, the advantage of indifferentiability isseparately analyzed by considering whether the hash function is keyed or not. Finally,a limitation is observed in Chang et al.'s indifferentiable attacks on the four PGV andthe PBGV hash functions. The formal proofs show the fact that those hash functions are indifferentiable from a random oracle in the ideal cipher model with the prefix-freepadding, the NMAC/HMAC and the chop construction.2. The security of the rate-1 double block length hash functions, which based on a blockcipher with a block length of n-bit and a key length of 2n-bit, is reconsidered. Preim-age and second preimage attacks are designed to break Hirose's two examples whichwere left as an open problem. Counter-examples and new attacks are presented on ageneral class of double block length hash functions with rate 1, which disclose thereexist uncovered ?aws in the former analysis by Satoh et al. and Hirose. Some refinedconditions are proposed for ensuring this general class of the rate-1 hash functions tobe optimally secure against the collision attack. In particular, two typical examples,which designed under the proposed conditions, are proven to be indifferentiable fromthe random oracle in the ideal cipher model.For the provable security under the random oracle model, the other key problem is tochoose a tight reduction technique to balance the security and the efficiency in practice. Bysimulating the underlying hash function as a random oracle, we present some well-designedsignature schemes which are efficiently given the reduction proofs in the random oraclemodel. All these reduction proofs can be easily extended to the provable security on similarsignature schemes in the random oracle model.1. Based on the discrete logarithm problem and the Schnorr's blind signature scheme,we propose a new efficient partially blind signature scheme. The computation andcommunication costs are both reduced in our scheme. We also provide a new partiallyblind signature scheme which is based on n-th order characteristic sequences gener-ated by LFSR. By using the forking lemma reduction technique, their securities areproven in the random oracle model. Compares with the finite field based schemes, ourscheme shows advantages on the computation and storage since the reduced represen-tation of finite field elements by LFSR. Both of the schemes can make privacy-orientedapplications, which are based on partially blind signatures, become more practical forhardware-limited environment, such as smart phones and PDAs.2. We propose two certificateless aggregate signature schemes, which are the first aggre-gate signature schemes in the certificateless cryptosystems. The first scheme reducesthe costs of communication and signer-side computation but loses on storage, whilethe second scheme minimizes the storage but sacrifices the communication. We can choose one of the above schemes by considering the implementation circumstance.In advance, our schemes do not need the public key certificate anymore and achievethe Trust Level 3, which is the same level in the traditional PKI. Both of the schemesare provably secure in the random oracle model by assuming the intractability of thecomputational Diffie-Hellman problem over the groups with bilinear maps.