Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Sigma protocol for faster proof of simultaneous homomorphism relations

The -protocols for homomorphism relations are one of the cryptographic protocols which are used to prove knowledge of homomorphism relations. The Schnorr protocol is one of the most famous -protocols used for proving knowledge of discrete logarithm (DL) relation in which the verifier essentially performs one double-exponentiation (i.e. a group computation of the form axby ). A direct application of the Schnorr protocol for proving simultaneous knowledge of n DLs with a common base leads to a -protocol in which the verifier performs n double-exponentiations. In this study, the authors propose another -protocol for homomorphism relations. The proposed -protocol has fast verification when is used to prove the simultaneous homomorphism relations with a common homomorphism. Also, when the DL instantiation (DL-instantiation) of the proposed -protocol is used to prove simultaneous knowledge of n DLs with a common base, it leads to a -protocol in which the verifier performs n+1 single-exponentiations.

References

    1. 1)
      • 19. Neff, A.C.: ‘A verifiable secret shuffle and its application to e-voting’. Proc. of the 8th ACM Conf. on Computer and Communications Security, Philadelphia, Pennsylvania, USA, November 2001, pp. 116125.
    2. 2)
      • 11. Vassil, S.D., Jullien, G.A., Miller, W.C.: ‘Complexity and fast algorithms for multi exponentiations’, IEEE Trans. Comput., 2000, 49, pp. 141-147.
    3. 3)
      • 10. Avanzi, R.M.: ‘On multi-exponentiation in cryptography’, IACR Cryptol. ePrint Archive, 2002, pp. 610.
    4. 4)
      • 16. Chaum, D., Pedersen, T.P.: ‘Wallet databases with observers’. Advances in Cryptology - CRYPTO'92, 12th Annual Int. Cryptology Conf., Santa Barbara, California, USA, August 1992, pp. 89105.
    5. 5)
      • 14. Chow, S.S.M., Ma, C., Weng, J.: ‘Zero-knowledge argument for simultaneous discrete logarithms’. Computing and Combinatorics, 16th Annual Int. Conf., COCOON 2010, Nha Trang, Vietnam, July 2010, pp. 520529.
    6. 6)
      • 13. Möller, B.: ‘Algorithms for multi-exponentiation’. 8th Annual Int. Workshop Selected Areas in Cryptography (SAC 2001), Toronto, Ontario, Canada, August 2001, pp. 165180.
    7. 7)
      • 6. Bangerter, E.: ‘Efficient zero-knowledge proofs of knowledge for homomorphisms’. PhD thesis, Ruhr-University Bochum, 2005.
    8. 8)
      • 1. Cramer, R.: ‘Modular design of secure yet practical cryptographic protocol’. PhD thesis, University of Amsterdam, 1996.
    9. 9)
      • 4. Damgård, I.: ‘On Σ-protocols’. Available at http://www.cs.au.dk/ivan/Sigma.pdf, accessed 2004.
    10. 10)
      • 18. Ciampi, M., Persiano, G., Scafuro, A., et al: ‘Improved OR composition of Sigma protocols’. Theory of Cryptography Conf., Tel Aviv, Israel, January 2016, (LNCS), pp. 112142.
    11. 11)
      • 12. Menezes, A., van Oorschot, P.C., Vanstone, S.A.: ‘Handbook of applied cryptography’ (CRC Press, Boca Raton, FL, USA, 1996).
    12. 12)
      • 8. Maurer, U.: ‘Unifying zero-knowledge proofs of knowledge’. Progress in Cryptology - AFRICACRYPT 2009, Second Int. Conf. on Cryptology in Africa, Gammarth, Tunisia, June 2009, pp. 272286.
    13. 13)
      • 3. Goldwasser, S., Micali, S., Rackoff, C.: ‘The knowledge complexity of interactive proof systems’, SIAM J. Comput., 1989, 18, pp. 186208.
    14. 14)
      • 2. Bellare, M., Goldreich, O.: ‘On defining proofs of knowledge’. Advances in Cryptology - CRYPTO'92, 12th Annual Int. Cryptology Conf., Santa Barbara, California, USA, August 1992, pp. 390420.
    15. 15)
      • 17. Bellare, M., Juan, A.G., Rabin, T.: ‘Fast batch verification for modular exponentiation and digital signatures’. Advances in Cryptology - EUROCRYPT'98, Int. Conf. on the Theory and Application of Cryptographic Techniques, Espoo, Finland, June 1998, pp. 236250.
    16. 16)
      • 7. Cramer, R., Damgård, I., Schoenmakers, B.: ‘Proofs of partial knowledge and simplified design of witness hiding protocols’. Advances in Cryptology - CRYPTO'94, 14th Annual Int. Cryptology Conf., Santa Barbara, California, USA, August 1994, pp. 174187.
    17. 17)
      • 5. Hazay, C., Lindell, Y.: ‘Efficient secure two-party protocols-techniques and constructions’ in Basin, D., Maurer, U. (Eds.): ‘Information security and cryptography’ (Springer, New York, 2010), pp. 147175.
    18. 18)
      • 15. Chow, S.S.M., Ma, C., Weng, J.: ‘Zero-knowledge argument for simultaneous discrete logarithms’, Algorithmica, 2012, 64, pp. 246266.
    19. 19)
      • 20. Ciampi, M., Persiano, G., Scafuro, A., et al: ‘Online/offline OR composition of Sigma protocols’. Advances in Cryptology - EUROCRYPT 2016, Vienna, Austria, May 2016, pp. 6392.
    20. 20)
      • 9. Schnorr, C.P.: ‘Efficient identification and signatures for smart cards’. Advances in Cryptology - EUROCRYPT'89, Workshop on the Theory and Application of Cryptographic Techniques, Houthalen, Belgium, April 1989, pp. 239252.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2018.5167
Loading

Related content

content/journals/10.1049/iet-ifs.2018.5167
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address