Design And Analysis Of Cryptographic Schemes Based On Braid Groups

Since the invention of the concept of public key cryptography (PKC), PKC has beendeveloped for about thirty years. Many excellent public key cryptosystems have been pro-posed and improved. But, the recent development of quantum computation creates potentialmenace to the security of current public key cryptosystems. In order to enrich cryptographyas well as not to put all eggs in one basket, people have made lots of effort on develop-ing alternative PKC based on different mathematical foundation. Braid group-based PKC isjust one of the eggs outside the basket. From the publication of the first braid-based PKCscheme due to Ko et al. in 2000, the research on braid-based PKC has been undergoingsome sinuation and keeping active. Recently, progress on algorithms casts distrust on thebasic assumption of braid-based PKC, i.e., the intractability of conjugator search problem(CSP)—But people have not reached any definite conclusion as so far. In addition, manypublished braid-based PKC schemes lack of provably secure models, resulting in that even ifthose underlying assumptions were sound, these schemes had failed to meet the most desiredsecure properties. Therefore, in this paper, we focus onComplexity of published methods for solving CSP;Braid-based signatures which can reach EUF-CMA security;Self-distributive systems.The originality of this paper is stated in the following:1. We provide detailed algorithmic descriptions for published algorithms for solving CSP,give complexity analysis on these algorithms, and clarify the relationship among thesuper summit set (SSS), the ultra summit set (USS) and the U-orbit. Based on thesework, we prompt our doubt on the claimed efficiency of USS method and draw aconclusion: The complexities of all published methods for solving CSP have no poly-nomial bound, with respect to the scale of input parameters of CSP instances; As a result, the CSP intractability assumption is sound at present. In addition, we pointout a false idea on the relationship between the small cancellation conditions of braidgroups and the intractability of CSP.2. Based on the CSP intractability assumption, we design two braid-based bit commit-ment protocols: The one is the standard bit commitment; The other is called biasedbit commitment, which is a non-trivial generalization. The performance and securityanalysis on our protocols suggest that braid-based bit commitments have advantagesover those based on number theory.3. We propose a new braid-based cryptographic problem—One More Matching Conju-gate Problem (OM-MCP), and prove that in the random oracle model (ROM), Ko etal.'s braid-based signature schemes are EUF-CMA secure under the assumption of theintractability of OM-MCP. As far as we know, this is the first time to conclude thatsome braid-based signatures which can reach EUF-CMA security.4. We propose another new braid-based cryptographic problem—Conjugate AdjoinProblem (CAP), and design a new braid-based signature scheme which is also provedto be EUF-CMA secure under the assumptions of ROM and the intractability of CAP.5. We design several cryptographic schemes based on self-distributive systems. This isthe first time to conduct systematically study on self-distributive systems. And weobtain some interesting results:(a) A signature scheme based on the first type of left self-distributive system (LD1).(b) A signature scheme and a hash function with partial chameleon property basedthe first type of central self-distributive system (CD1).(c) Self-distributive systems taking other fourteen forms.(d) A signature scheme based on the second type of central self-distributive system(CD2).(e) A signature scheme and an authentication scheme based on the first type of rightself-distributive system (RD1).