Research On Digital Signatures Over Braid Groups

Digital signature is one of the crucial techniques of information security, which can provide authentication, integrity and non-repudiation. The development of quantum computing brings great challenges to traditional signature schemes based on the difficulty of the integer factoring and discrete logarithm problem, which makes schemes based on new difficult problems hot topic. For each integer n ? 2, n-braid groupsBn are infinite non-commutative groups, the structures of which are complicated. There are several difficult problems in braid groups that can be used for constructing signature schemes. And no quantum attack against the difficult problems in braid groups has been proposed.This paper mainly researches on digital signatures over braid groups, including standard signature, blind signature, proxy signature and ring signature. The research covers the definitions of UC security models for those signatures, analysis and constructions of conjugacy signature schemes, the method of constructing signature schemes based on the root extraction problem and the modular design of protocols under the UC framework.The main contributions are as follows.1. UC security models of signaturesAiming at the two levels of definitions for unforgeabilites of standard signature, the corresponding UC security models are proposed, and it is proved that the conclusion holds for both the two models that a complete signature scheme satisfies unforgeability if and only if the corresponding signature protocol securely realizes the ideal functionality. The inconsistencies of the UC definitions of blind signature ideal functionality and signature protocol proposed by Buan are pointed out and the improved definitions are proposed. The security model of proxy signature within the UC security framework is defined as an ideal functionality, which is proved to be equivalent to the game-based security model. A game-based security model is proposed for ring signature and the relations of the unforgeability defined by the new model and those defined by the existing models are presented. It is pointed out that the existing UC security models are not applicable to one kind of ring signature schemes, the signature length of which is proportional to the ring size. Aiming at the different levels of definitions for unforgeabilities, the corresponding UC security models are proposed for ring signature, and it is proved that the conclusion holds for all those models that a ring signature scheme with completeness and unconditional anonymity satisfies unforgeability if and only if the corresponding signature protocol securely realizes the ideal functionality.2. Analysis and constructions of conjugacy signature schemes The reason which destroys the blindness of existing blind signature schemes is pointed out. A blind signature is constructed using a pair of random braids, the product of which is not the identity element, as the blinding factors. The security flaws of existing proxy signature schemes over braid groups are analyzed and two improved schemes are proposed. A new conjugacy proxy scheme is constructed based on the difficulty of the matching conjugacy search problem, which has advantages over the improved schemes considering the security, efficiency and the length of signature.3. Constructions of signature schemes based on the root extraction problemA standard signature scheme, a blind signature scheme, a proxy signature scheme and a ring signature scheme are constructed based on the root extraction problem and the conjugacy search problem, in which the secret key of the signer is protected by conjugacy. In the random oracle model the standard scheme can resist the existential forgery under the adaptive chosen message attack. According to the conclusion proved previously, the scheme is UC secure. The blind scheme uses a random factor to hide the fact that some datas are conjugate and the blindness can be ensured. The proxy signature scheme can resist the existential forgery under the adaptive chosen message and proxy delegation and is UC secure. The ring signature is proved to be complete and unconditionally anonymous. And it is unforgeable even in the strongest game-based model. Hence, it is UC secure.4. The modular design of protocols under the UC frameworkThe ideal functionality of forward secure ring signature is defined, and a concrete protocol securely realizing the ideal functionality is designed based on a UC secure ring signature protocol using the modular design method under the UC security framework.