ISSN: 2229-371X

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.


D.B.Ojha*1, Abhishek Dwivedi2and Akhilesh Dwivedi3
  1. Department of Mathematics, R. K. G. Institute of Technology, Ghaziabad, U.P., India,
  2. Research Scholar Singhania University, Jhunjhunu, Rajsthan, India& Department of M.C.A., Raj Kumar Goel Engineering College, Ghaziabad, U.P., India
  3. M.Tech. (IS) Student A.I.T., New Delhi, affiliated to G.G.S.I.P. University, New Delhi, India
Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences


Commitment schemes are fundamental bricks for guaranteeing fairness in upper level cryptographic protocols. Most commitment schemes in the literature rely on hash functions, which should be strongly collision free for the scheme to be secure. We present a commitment scheme, which avoids hash functions by using a public-key cryptosystem based on braid root problem instead.


Biased bit string commitment, braid group, root problem, non abelian group.


In cryptography, a commitment scheme or a bit commitment scheme is a method that allows a user to commit to a value while keeping it hidden and preserving the user's ability to reveal the committed value later. A useful way to visualize a commitment scheme is to think of the sender as putting the value in a locked box, and giving the box to the receiver. The value in the box is hidden from the receiver, who cannot open the lock (without the help of the sender), but since the receiver has the box, the value inside cannot be changed. Commitment schemes are important to a variety of cryptographic protocols, especially zero-knowledge proofs and secure computation [9, 10]. Over the past two decades, a bulk of excellent protocols based upon bit commitment has been followed by the first constructions on bit commitment [9, 11, 3], many improvements have been proposed [10, 12, 14, 13, 5]. In 1988, Goldreich et al. [12] presented another factoring-based bit commitment scheme which is more efficient than Blum’s [9]. In 1989, Naor [10] reduced the properties of bit commitment schemes on information-theoretically binding and computationally hiding to pseduo-randomness. Shortly afterwards, Naor et al. [10] also reduced the properties of bit commitment schemes on computationally binding and information-theoretically hiding to one-way permutation. In 1992, Pedersen [14] proposed a bit commitment scheme based on discrete logarithm problem.
In 1996, Halevi and Micali [13] also put forward a new bit commitment scheme by using a collision-free one-way hash function. In [10], a general framework was introduced for building bit commitments using one-way functions. The drawback of those early schemes is that they only allow commitment to a single bit, whereas committing to a bitstring is a fundamental need in many cryptographic applications. Most commitment schemes in the literature are based on hash functions, which cause them to share two shortcomings:
1. The hash functions used should be strongly collision free. However, this property can only be empirically checked. It actually turns out that some schemes are inadvertently based on weakly collision-free hash functions [4].
2. Hash functions alone cannot offer non-repudiability.



In a commitment scheme, one party Alice (sender) aim to entrust a concealed message m to the second party Bob (receiver), intuitively a commitment scheme may be seen as the digital equivalent of a sealed envelope. If Alice wants to commit to some message m she just puts it into the sealed envelope, so that whenever Alice wants to reveal the message to Bob, she opens the envelope. First of all the digital envelope should hide the message from, Bob should be able to learn m from the commitment. Second, the digital envelope should be binding , meaning with this that Alice cannot change her mind about m, and by checking the opening of the commitment one can verify that the obtained value is actually the one Alice had in mind originally [2,1].


computationally infeasible if braids of a sufficient size are considered.


A commitment should be non-repudiable: it should not be possible for party A to deny having committed to value. Nonrepudiability can be achieved by having the commitment signed by the committing party. Here we also considers a different non-trivial generalization, Party A commits a number to Party B with a given, fixed bias 1/k, while the basic bit commitment can be viewed as a special case of setting bias value to 1/2.




Therefore, under the assumption that the problem is intractable, A has no way to cheat, i.e., the proposed scheme is computationally binding.


Non-repudiable commitments schemes are an essential part of secure e-gaming and e-gambling protocols. In fact, such schemes are a guarantee that player misbehaviors or deviations from the protocols will be detected. Using the new primitive, one party is allowed to commit a value to another party with a given, fixed bias while the basic bitstring commitment can be viewed as special case when the bias value is set to . Using a public-key cryptosystem to construct a commitment is away of achieving nonrepudiability, a property which cannot be offered by hash functions alone. In this paper, we have presented a commitment scheme that allows a player to commit to a bitstring in a non-repudiable way based on the braid root problems with -biased bitstring commitment scheme, which is information theoretically, hiding and computationally binding.


  1. Alawi A. Al-saggaf, Acharya H. S: Mathematics of Bit-Commitment Schemes, Bulletin of the Marathwada Mathematical Society, Vol. 8, No. 1, June 2007, pages 08– 15.
  2. Alawi A. Al-saggaf, Acharya H. S. “A generalized Framework for Crisp Commitment Schemes”
  3. Shamir, R. L. Rivest, and L. M. Adleman, “Mental poker,” in D. Klarner ed., TheMathematical Gardner, Wadsworth, Belmont, California, 1981, pp. 37-43.
  4. Preneel, “The state of cryptographic hash functions”, in Lectures on Data Security: ModernCryptology in Theory and Practice, LNCS 1561, Berlin: Springer, pp. 158-192, 1999.
  5. Zheng, K. Chen, D. Gu, and J. You, “Efficient bitcommitment schemes,” Journal of China Institute of communications, Vol. 21, 2000, pp. 78-80.
  6. Artin, “Theory of braids,” Annals of Mathematics, Vol. 48, pp. 101-126, 1947.
  7. Johannes Buchmann, Carlos Coronado, Martin D¨oring, Daniela Engelbert, Christophudwig, Raphael Overbeck, Arthur Schmidt, Ulrich Vollmer, Ralf-Philipp Weinmann, “Post-Quantum Signatures”,
  8. K. Ko, S. Lee, J. Cheon, J. Han, J. kang C. Park. New public key cryptosystem using braid groups, Crypto’2000, LNCS 1880, pp.166-183, Springer 2000.
  9. M. Blum, “Coin flipping by telephone: a protocol for solving impossible problems”, Proc. IEEE Computer Conference, pp. 133-137, 1982.
  10. M. Naor, “Bit commitment using pseudorandomness”, in Advances in Cryptology-Crypto’89, LNCS 435, Berlin: Springer, pp.128-136, 1990.
  11. M. Rabin, “How to exchange secrets by oblivious transfer,” Technical Report No.TR-81, Harvard Aiken Computation Laboratory, Cambridge, 1981.
  12. S. Goldreich, S. Micali, and R. Rivest, “A digital signature scheme secure against adaptive chosen message attacks,” SIAM Journal of Computing, Vol. 17, 1988,  pp.281-308.
  13. S. Halevi and S. Micali, “Practical and provably secure commitment schemes from collision free hashing,” in Proceedings on Advances in Cryptology _CRYPTO, LNCS 1109, Springer, 1996, pp. 201-215.
  14. T. P. Pedersen, “Non-interactive and information theoretic secure verifiable secret sharing,” in Proceedings on Advances in Cryptology __CRYPTO, LNCS 576, Springer, 1992, pp. 129-140.