| The competition between cryptographic scheme designers and cryptanalysts has never stopped since the ancient times.Especially,the advent of electronic computers since World WarⅡhas fundamentally increased the power of the two belligerents and escalated the competition.When considering the computational power,people care more about how long it takes to break a cryptographic scheme or how secure a cryptographic scheme is.In modern cryptography,one approach,called security proof,is applied to measure the security of a scheme using rigorous mathematical tools,and it aims to provide people confidence for the resulting scheme.Security proof gives designers the advantage in the war of modern cryptography against cryptanalysts.But the bad news for the designer is the tradeoff between the efficiency and the security proof.Generally,in order to provide security proof,additional redundancy has to be added into cryptographic schemes which results in efficiency loss.Therefore,a basic problem in the design of cryptography is how to simplify a cryptographic scheme to improve its efficiency without undermining its desired security.To solve this problem,different types of techniques for simplified design have been provided during the past decades.In this thesis,we focus on the simplification of three schemes in public key encryption,digital signature and zero-knowledge.Public key eneryption.Public key cryptography was first introduced by Diffie and Hellman.The first concrete public key encryption schemes were later proposed by Rivest,Shamir and Adleman and by Merkle and Hellman.But the most widely used security notion for encryption,known as chosen ciphertext security,was introduced by Naor and Yung.Afterwards,Rackoff and Simon provided a stronger notion called indistinguishability under adaptive chosen ciphertext attack (IND-CCA2).So far adaptive chosen ciphertext security has become a standard notion for the security of public key encryption.The early constructions of adaptive chosen ciphertext secure encryption,such as,were based on non-interactive zero-knowledge proofs,which are not quite practical in real world applications.To construct an efficient and adaptive chosen ciphertext secure encryption scheme,many encryption techniques have been proposed in the socalled random oracle model.The random oracle model,however,is one of the most controversial issues in cryptography.A notable argument against the random oracle model was made by Canetti,Goldreich and Halevi who demonstrated that there existed cryptographic schemes that were secure in the random oracle model but insecure for any instantiation of the random oracle.Recently,Leurent and Nguyen showed that instantiations of full domain hash functions(random oracles) proposed in the literature are insecure.To address the concern over random oracles,an obvious approach is to design an adaptive chosen ciphertext secure public key encryption scheme that does not rely on a random oracle.The often cited adaptive chosen ciphertext secure encryption scheme proposed by Cramer and Shoup represents the first concrete result in this line of research.A multiple number of techniques have since been proposed and studied by many cryptographers.Especially,the hybrid encryption(KEM/DEM),which was first generalized by Cramer and Shoup,attracts a lot of attention from the cryptography community.Kurosawa and Desmedt presented a more efficient hybrid encryption scheme by using a KEM which is not necessarily adaptive chosen ciphertext secure.More recently,Kiltz,Pietrzak,Stam and Yung improved on the Kurosawa-Desmedt technique and proposed a new approach to design adaptive chosen ciphertext secure hybrid encryption schemes without a random oracle.Their main technique employs an efficient transformation from a 1-universal hash proof system to a 2-universal hash proof system,using a 4-wise independent hash function.Another important progress was made by Hofheinz and Kiltz.They proposed a new public key encryption scheme based on factoring.Their scheme requires only roughly two exponentiations in encryption and roughly one exponentiation in decryption.For the encryption schemes based on discrete logarithm,DHIES is one of the most efficient schemes without random oracle,although it is not proven under the standard assumption.Notice that most of these encryption schemes in the standard model or standard assumptions,however,share a common drawback that impedes their possible adoption in practice,that is,they generally require at least a few times more computation than their random oracle based counterparts.A major advantage of a random oracle based scheme lies in its simplicity.To preserve the simplicity while not relying on a random oracle for security proofs,new computational assumptions have been examined. One such effort is made by Pandey,Pass and Vaikuntanathan who introduced a few complexity theoretical hardness assumptions that abstract out concrete properties of a random oracle.Based on these assumptions,they are able to solve a number of open problems,including the construction of a non-interactive concurrently non-malleable string commitment.Their results point to an interesting approach towards designing efficient and provably secure cryptographic schemes without random oracles.We note that although these assumptions are stronger than traditional cryptographic hardness assumptions,they seem quite reasonable and it is conceivable that,like many other assumptions in the field such as the decisional Diffie-Hellman assumption,this type of new assumptions may gain wider acceptance after further screening by peers in the field.By abstracting concrete properties of the random oracle model,we examine a variant of Pandey et al.'s assumption,called the adaptive DDH assumption.Based on the adaptive DDH assumption,a modified version of Zheng and Seberry's encryption scheme proposed in is proved to be adaptive chosen ciphertext secure without a random oracle.Zheng and Seberry proposed three simple methods for immunizing public key cryptosystems against chosen ciphertext attacks.The nature of the three methods is the same.They immunized a public key cryptosystem by appending to each ciphertext a tag that is correlated to the message to be encrypted.Based on the Gap Diffie-Hellman assumption(GDH),Baek and Zheng provided a security proof for the first scheme,denoted by Zheng-Seberry1wh,in the random oracle model,leaving as an open problem proofs for the other two schemes.The focus of our work is to modify the second scheme in,denoted by Zheng-Seberryuh,so that the resultant scheme is adaptive chosen ciphertext secure.The scheme Zheng-Seberryuh is worth studying for the following reasons:First,the scheme immunizes public key encryption against adaptive chosen ciphertext attacks with the help of a universal hash function.This allows the scheme to steer clear of a one-way hash function with non standard output size,whereby successfully averting potential risks recently discovered in.Second, the input length of a plaintext can be arbitrary,while the overhead of the corresponding ciphertext is a constant.As a result,the ratio between the length of the ciphertext and that of the plaintext can be close to 1 as the length of the plaintext increases.Compared with Kiltz et al.'s concrete scheme which relies on the DDH assumption and AE-OT secure symmetric encryption,our modified Zheng-Seberryuh scheme is conceptually much simpler and relies only on the adaptive DDH assumption. More important,this newly modified scheme requires significantly less computation time than Kiltz et al.'s.Compared with DHIES which relies on the Oracle Diffie-Hellman(ODH) assumption together with the security of symmetric encryption and a message authentication code,our modified scheme relies only on the adaptive DDH assumption and preserves the computational efficiency of Zheng-Seberryuh.However,it is fair to say that our modified Zheng-Seberry scheme and DHIES are comparable,each having its own pros and cons in practice.With DHIES,all three assumptions on symmetric encryption,MAC and ODH are responsible for the security of DHIES and it is relatively easy to select proper candidates to realize each function of the assumption.With our modified Zheng-Seberry scheme,the adaptive DDH assumption which is solely responsible for the security of the scheme is slightly stronger than the ODH assumption required by DHIES. Ring signatures.The notion of public key digital signature was introduced by Diffie and Hellman and the early concrete implementations were proposed by Rivest,Shamir and Adleman.For the security notions of digital signature,a comprehensive work was presented by.As we know,the aim of signatures is to authenticate the source of a message and possibly to ensure that a message has not been altered during transmission.In some applications,we need to hide the identity of a signer,which results in the invention of group signatures and ring signatures.Ring signature,introduced by Rivest,Shamir and Tauman,is used to provide anonymity for the signer.It is closely related to the notion of group signature,which also provides anonymity for the signer.But unlike group signatures,there is no central group manager,prearranged group of users or procedures for setting,changing or deleting groups in ring signature scheme.Many works about ring signatures are subsequently proposed,such as,etc..Most of the works are proven secure in the random oracle model.Some works are proposed in the standard model,but those works are not so satisfactory:Xu,Zhang and Feng provided a ring signature scheme in the standard model,but their proof is flawed;Chow,Liu,Wei and Yuen's scheme is based on a new assumption;Bender,Katz and Morselli's scheme is based on trapdoor permutations,but their scheme uses generic ZAPs for NP,which is impractical. However,gave a detailed discussion of security models for ring signatures.Recent years,two efficient ring signature schemes without random oracles have been proposed by Shacham and Waters and Boyen.Especially,it is the first efficient ring signature scheme without random oracles based on standard assumptions. In,Shacham and Waters construct a linear size ring signature in common random string model based on computational Diffie-Hellman and decisional subgroup assumptions. For l members of a ring,their scheme has the size of 2l + 2 group elements,and requires 2l+3 pairings to verify.They show that their scheme is provably secure in the strongest security model proposed by Bender,Katz,and Morselli.With respect to a concrete application environment,we show that the ring signature scheme can be used in a more efficient way,based on the idea of. In,Dodis,Kiayias,Nicolosi and Shoup introduced a group public key for the ring signature through the accumulators with one way domain,which can be computed by any member in the ring.Such kind of structure of ring signatures allows one group public key to correspond to many ring members' secret keys.Thanks to the group public key for the ring,they pointed out that the size of the ring signature can be constant in some cases,e.g.,the ring stays the same for a long period of time.We show that we can apply Dodis et al.'s structure to Shacham and Waters scheme,as it can produce "group public key" for the ring,and such "group public key" can play the role of tag for linking.Consider the case that signer A stays in a ring for a long time, and she usually needs to send her ring signature to receiver B,while A wants to assure B that these signatures are produced by the same member in the ring.Our modified scheme is more efficient than conventional ring signature without random oracles when applied to the above case.As the signer can decide whether to provide linkability by herself,we call the special Shacham and Waters scheme self linkable ring signature.Concurrent Statistical Zero-Knowledge Arguments.Zero-knowledge proof, introduced by Goldwasser,Micali and Rackoff,is an interactive method for one party to prove to another party that a statement is true,without revealing anything other than the validity of the statement.The party who provides the proof is called the prover and the party who verifies the proof is called the verifier.Unlike the traditional mathematical proofs which is a fixed sequence consisting of evidence that are commonly agreed,zero-knowledge proof emphasizes the interaction between the prover and the verifier.The notion of the concurrent ZK first introduced by Dwork,Naor and Sahai requires that the protocol remains ZK even many copies of the proof are run in an asynchronous environment,such as the Internet.Canetti,Kilian,Petrank,and Rosen showed that no languages beside BPP have constant-round black-box concurrent ZK proofs in the standard model(where no public key infrastructure is available),and they also gave a o(log n/log log n) lower bound on the number of rounds for such protocols. Richardson and Kilian first presented a family of concurrent ZK protocols for all languages in NP.Their analysis was improved by Kilian and Petrank,who showed that a polylogarithmic number of rounds is sufficient for the concurrent ZK protocol.Subsequently,Prabhakaran et al.improved their analysis to prove thatω(log n) rounds are enough.As Micciancio and Petrank pointed out,although the concurrent zeroknowledge protocol in the standard model is less efficient than that in the PKI model, the standard model can be used where a PKI is not possible,or to set up a public key infrastructure or establish common random strings.For instance,the standard protocol can be used to register public keys with a certification authority and bootstrap the system.Micciancio and Petrank provided an efficient method for converting any public-coin HVZK proof system to a concurrent ZK proof system based on the decisional Diffie-Hellman(DDH) assumption.However,their transformation does not preserve the statistical ZK.The first concurrent statistical ZK argument for all languages in NP from any one-way function was presented by Goyal,Moriarty,Ostrovsky and Sahai who gave that a general transformation from any honest verifier statistical ZK argument to a concurrent statistical ZK argument.They applied their transformation to the statistical zero-knowledge argument presented by Nguyen,Ong and Vadhan to get the first concurrent statistical ZK argument for all languages in NP from any one-way function.They used the modified PRS preamble,which requires O(l2) commitments(l denotes the number of rounds of the preamble).The verifier uses the randomness of the coin flipping protocol and the computational ZK proofs.The most difficult problem they overcame was the soundness proof.Since the commitment used by the verifier is statistically binding(computationally hiding),the prover may potentially cheat the verifier.Hence,the soundness is not obvious.However,the computational ZK proof was used to successfully overcome this problem by the hybrid argument.By analyzing the security property of Goyal et al.'s concurrent statistical zeroknowledge arguments,we point out that their protocol can be further simplified to a more practical protocol using the witness indistinguishable protocol.More precisely, some of the computational ZK proofs in Goyal et al.'s protocol are replaced with the ∑OR-protocol,which is witness indistinguishable proof of knowledge(WIPOK).We then prove that this WIPOK protocol is sufficient for the proof of soundness.Furthermore, we use the structure of Richardson and Kilian's preamble which requires only O(l) commitments instead of the PRS preamble.In addition,the WIPOK protocols are executed in "parallel",so that they not only play the role of preamble but also remove some computational ZK proofs in Goyal et al.'s protocol.The soundness proof problem is successfully overcome by the hybrid argument with the soundness proof of this protocol being a little more subtle than that of Goyal et al.,since the WIPOK protocol is not zero-knowledge.
|
PDF Full Text Request