American Institute of Mathematical Sciences

Advanced
May  2020, 14(2): 177-205. doi: 10.3934/amc.2020015

Malleability and ownership of proxy signatures: Towards a stronger definition and its limitations

Sanjit Chatterjee 1, and  Berkant Ustaoğlu 2,

1. 

Department of Computer Science and Automation, Indian Institute of Science, India
2. 

Izmir Institute of Technology, Urla, Izmir, 35430 Turkey

Received  July 2017 Revised  January 2018 Published  May 2020 Early access  September 2019

Proxy signature is a cryptographic primitive that allows an entity to delegate singing rights to another entity. Noticing the ad-hoc nature of security analysis prevalent in the existing literature, Boldyreva, Palacio and Warinschi proposed a formal security model for proxy signature. We revisit their proposed security definition in the context of the most natural construction of proxy signature – delegation-by-certificate. Our analysis indicates certain limitations of their definition that arise due to malleability of proxy signature as well as signature ownership in the context of standard signature. We propose a stronger definition of proxy signature to address these issues. However, we observe that the natural reductionist security argument of the delegation-by certificate proxy signature construction under this definition seems to require a rather unnatural security property for a standard signature.

Keywords: Proxy signatures, malleability, owndership, multi-user security, provable security.
Mathematics Subject Classification: Primary: 94A60; Secondary: 94A62.
Citation: Sanjit Chatterjee, Berkant Ustaoğlu. Malleability and ownership of proxy signatures: Towards a stronger definition and its limitations. Advances in Mathematics of Communications, 2020, 14 (2) : 177-205. doi: 10.3934/amc.2020015
References:
[1]

A. Bakker, M. van Steen and A. S. Tanenbaum, A law-abiding peer-to-peer network for free-software distribution, in IEEE International Symposium on Network Computing and Applications NCA 2001, Cambridge, MA, USA, IEEE Computer Society, (2001), 60–67. doi: 10.1109/NCA.2001.962516.

[2]

L. Bassham, W. Polk and R. Housley, Algorithms and identifiers for the internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 3279 (Proposed Standard), (2002). Updated by RFCs 4055, 4491, 5480, 5758. doi: 10.17487/rfc3279.

[3]

M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, in 11 CCS'93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, ACM, (1993), 62–73. doi: 10.1145/168588.168596.

[4]

D. J. Bernstein, Multi-User Schnorr Security, Revisited, Cryptology ePrint Archive, Report 2015/996, 2015, http://eprint.iacr.org/.

[5]

S. Blake-Wilson and A. Menezes, Unknown key-share attacks on the station-to-station (sts) protocol, In Public Key Cry.Ptography, (1999), 154–170. doi: 10.1007/3-540-49162-7_12.

[6]

A. Boldyreva, A. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Cryptology ePrint Archive, Report 2003/096, 2003, http://eprint.iacr.org/.

[7]

A. Boldyreva, A. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Journal of Cryptology, 25 (2012), 57-115.  doi: 10.1007/s00145-010-9082-x.

[8]

Certicom Research, SEC 1: Elliptic Curve Cryptography, Version 2.0, 2009. Available at: http://www.secg.org/.

[9]

D. Cooper, S. Santesson, S. Farrell, S. Boeyen, R. Housley and W. Polk, Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 5280 (Proposed Standard), 2008. Updated by RFC 6818 RFC 8398, RFC 8399. doi: 10.17487/rfc5280.

[10]

D. Derler, C. Hanser and D. Slamanig, Privacy-enhancing proxy signatures from non-interactive anonymous credentials, Data and Applications Security and Privacy, 8566 (2014), 49-65.  doi: 10.1007/978-3-662-43936-4_4.

[11]

I. Foster, C. Kesselman, G. Tsudik and S. Tuecke, A security architecture for computational grids, in CCS '98 Proceedings of the 5th ACM Conference on Computer and Communications Security, San Francisco, CA, USA, ACM, (1998), 83–92. doi: 10.1145/288090.288111.

[12]

S. Galbraith, J. Malone-Lee and N. P. Smart, Public key signatures in the multi-user setting, Information Processing Letters, 83 (2002), 263-266.  doi: 10.1016/S0020-0190(01)00338-6.

[13]

S. Goldwasser, S. Micali and R. Rivest, A "paradoxical" solution to the signature problem, Proceedings of the IEEE 25th Annual Symposium on Foundations of Computer Science, (1984), 441–448. doi: 10.1109/SFCS.1984.715946.

[14]

S. Goldwasser, S. Micali and R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. of Computing, 17 (1988), 281-308.  doi: 10.1137/0217017.

[15]

B. Jens-Matthias, S. Röhrich and R. Steinwandt, Key substitution attacks revisited: Taking into account malicious signers, International Journal of Information Security, 5 (2006), 30-36. 

[16]

E. Kiltz, D. Masny and J. Pan, Schnorr Signatures in the Multi-User Setting, Cryptology ePrint Archive, Report 2015/1122, 2015, http://eprint.iacr.org/.

[17]

N. Koblitz and A. Menezes, Another look at security definitions, Advances in Mathematics of Communications, 7 (2013), 1-38.  doi: 10.3934/amc.2013.7.1.

[18]

A. K. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung and C. Wachter, Ron was Wrong, Whit is Right, Cryptology ePrint Archive, Report 2012/064, 2012, http://eprint.iacr.org/.

[19]

M. Mambo, K. Usuda and E. Okamoto, Proxy signatures for delegating signing operation, in CCS '96, Proceedings of the 3rd ACM Conference on Computer and Communications Security, New Delhi, India, ACM, (1996), 48–57. doi: 10.1145/238168.238185.

[20]

U. Maurer, Intrinsic limitations of digital signatures and how to cope with them, in Information Security, (2003), 180–192. doi: 10.1007/10958513_14.

[21]

A. Menezes and N. Smart, Security of signature schemes in a multi-user setting, Designs, Codes and Cryptography, 33 (2004), 261-274.  doi: 10.1023/B:DESI.0000036250.18062.3f.

[22]

NIST National Institute of Standards and Technology, Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, 2007. Available via: http://csrc.nist.gov/publications/PubsSPs.html.

[23]

NIST National Institute of Standards and Technology, Digital Signature Standard (DSS) (FIPS 186-4), 2013.

[24]

T. Pornin and J. P. Stern, Digital signatures do not guarantee exclusive ownership, Applied Cryptography and Network Security, 3531 (2005), 138-150.  doi: 10.1007/11496137_10.

[25]

M. Stevens, A. Lenstra and B. de Weger, Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities, in Advances in Cryptology—EUROCRYPT 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4515 (2007), 1–22. doi: 10.1007/978-3-540-72540-4_1.

[26]

M. Stevens, A. Sotirov, J. Appelbaum, A. Lenstra, D. Molnar, D. A. Osvik and B. de Weger, Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, in Advances in Cryptology-CRYPTO 2009, Lecture Notes in Comput. Sci., Springer, Berlin, 5677 (2009), 55–69. doi: 10.1007/978-3-642-03356-8_4.

[27]

S. Vaudenay, Digital signature schemes with domain parameters: Yet another parameter issue in ECDSA, in ACISP, Lecture Notes in Computer Science, Springer, 3108 (2004), 188–199. doi: 10.1007/978-3-540-27800-9_17.

[28]

P. Yee, Updates to the internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 6818 (Proposed Standard), (2013), updates: RFC 5280. doi: 10.17487/rfc6818.

[29]

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.0), 2017, http://www.sagemath.org.

show all references

References:
[1]

A. Bakker, M. van Steen and A. S. Tanenbaum, A law-abiding peer-to-peer network for free-software distribution, in IEEE International Symposium on Network Computing and Applications NCA 2001, Cambridge, MA, USA, IEEE Computer Society, (2001), 60–67. doi: 10.1109/NCA.2001.962516.

[2]

L. Bassham, W. Polk and R. Housley, Algorithms and identifiers for the internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 3279 (Proposed Standard), (2002). Updated by RFCs 4055, 4491, 5480, 5758. doi: 10.17487/rfc3279.

[3]

M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, in 11 CCS'93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, ACM, (1993), 62–73. doi: 10.1145/168588.168596.

[4]

D. J. Bernstein, Multi-User Schnorr Security, Revisited, Cryptology ePrint Archive, Report 2015/996, 2015, http://eprint.iacr.org/.

[5]

S. Blake-Wilson and A. Menezes, Unknown key-share attacks on the station-to-station (sts) protocol, In Public Key Cry.Ptography, (1999), 154–170. doi: 10.1007/3-540-49162-7_12.

[6]

A. Boldyreva, A. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Cryptology ePrint Archive, Report 2003/096, 2003, http://eprint.iacr.org/.

[7]

A. Boldyreva, A. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Journal of Cryptology, 25 (2012), 57-115.  doi: 10.1007/s00145-010-9082-x.

[8]

Certicom Research, SEC 1: Elliptic Curve Cryptography, Version 2.0, 2009. Available at: http://www.secg.org/.

[9]

D. Cooper, S. Santesson, S. Farrell, S. Boeyen, R. Housley and W. Polk, Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 5280 (Proposed Standard), 2008. Updated by RFC 6818 RFC 8398, RFC 8399. doi: 10.17487/rfc5280.

[10]

D. Derler, C. Hanser and D. Slamanig, Privacy-enhancing proxy signatures from non-interactive anonymous credentials, Data and Applications Security and Privacy, 8566 (2014), 49-65.  doi: 10.1007/978-3-662-43936-4_4.

[11]

I. Foster, C. Kesselman, G. Tsudik and S. Tuecke, A security architecture for computational grids, in CCS '98 Proceedings of the 5th ACM Conference on Computer and Communications Security, San Francisco, CA, USA, ACM, (1998), 83–92. doi: 10.1145/288090.288111.

[12]

S. Galbraith, J. Malone-Lee and N. P. Smart, Public key signatures in the multi-user setting, Information Processing Letters, 83 (2002), 263-266.  doi: 10.1016/S0020-0190(01)00338-6.

[13]

S. Goldwasser, S. Micali and R. Rivest, A "paradoxical" solution to the signature problem, Proceedings of the IEEE 25th Annual Symposium on Foundations of Computer Science, (1984), 441–448. doi: 10.1109/SFCS.1984.715946.

[14]

S. Goldwasser, S. Micali and R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. of Computing, 17 (1988), 281-308.  doi: 10.1137/0217017.

[15]

B. Jens-Matthias, S. Röhrich and R. Steinwandt, Key substitution attacks revisited: Taking into account malicious signers, International Journal of Information Security, 5 (2006), 30-36. 

[16]

E. Kiltz, D. Masny and J. Pan, Schnorr Signatures in the Multi-User Setting, Cryptology ePrint Archive, Report 2015/1122, 2015, http://eprint.iacr.org/.

[17]

N. Koblitz and A. Menezes, Another look at security definitions, Advances in Mathematics of Communications, 7 (2013), 1-38.  doi: 10.3934/amc.2013.7.1.

[18]

A. K. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung and C. Wachter, Ron was Wrong, Whit is Right, Cryptology ePrint Archive, Report 2012/064, 2012, http://eprint.iacr.org/.

[19]

M. Mambo, K. Usuda and E. Okamoto, Proxy signatures for delegating signing operation, in CCS '96, Proceedings of the 3rd ACM Conference on Computer and Communications Security, New Delhi, India, ACM, (1996), 48–57. doi: 10.1145/238168.238185.

[20]

U. Maurer, Intrinsic limitations of digital signatures and how to cope with them, in Information Security, (2003), 180–192. doi: 10.1007/10958513_14.

[21]

A. Menezes and N. Smart, Security of signature schemes in a multi-user setting, Designs, Codes and Cryptography, 33 (2004), 261-274.  doi: 10.1023/B:DESI.0000036250.18062.3f.

[22]

NIST National Institute of Standards and Technology, Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, 2007. Available via: http://csrc.nist.gov/publications/PubsSPs.html.

[23]

NIST National Institute of Standards and Technology, Digital Signature Standard (DSS) (FIPS 186-4), 2013.

[24]

T. Pornin and J. P. Stern, Digital signatures do not guarantee exclusive ownership, Applied Cryptography and Network Security, 3531 (2005), 138-150.  doi: 10.1007/11496137_10.

[25]

M. Stevens, A. Lenstra and B. de Weger, Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities, in Advances in Cryptology—EUROCRYPT 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4515 (2007), 1–22. doi: 10.1007/978-3-540-72540-4_1.

[26]

M. Stevens, A. Sotirov, J. Appelbaum, A. Lenstra, D. Molnar, D. A. Osvik and B. de Weger, Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, in Advances in Cryptology-CRYPTO 2009, Lecture Notes in Comput. Sci., Springer, Berlin, 5677 (2009), 55–69. doi: 10.1007/978-3-642-03356-8_4.

[27]

S. Vaudenay, Digital signature schemes with domain parameters: Yet another parameter issue in ECDSA, in ACISP, Lecture Notes in Computer Science, Springer, 3108 (2004), 188–199. doi: 10.1007/978-3-540-27800-9_17.

[28]

P. Yee, Updates to the internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 6818 (Proposed Standard), (2013), updates: RFC 5280. doi: 10.17487/rfc6818.

[29]

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.0), 2017, http://www.sagemath.org.

Figure 1.  Different attack scenarios
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Neal Koblitz, Alfred Menezes. Critical perspectives on provable security: Fifteen years of "another look" papers. Advances in Mathematics of Communications, 2019, 13 (4) : 517-558. doi: 10.3934/amc.2019034
[2]

Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022026
[3]

Neal Koblitz, Alfred Menezes. Another look at security definitions. Advances in Mathematics of Communications, 2013, 7 (1) : 1-38. doi: 10.3934/amc.2013.7.1
[4]

Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413-426. doi: 10.3934/amc.2007.1.413
[5]

Zongmin Li, Jiuping Xu, Wenjing Shen, Benjamin Lev, Xiao Lei. Bilevel multi-objective construction site security planning with twofold random phenomenon. Journal of Industrial and Management Optimization, 2015, 11 (2) : 595-617. doi: 10.3934/jimo.2015.11.595
[6]

Shuai Ren, Tao Zhang, Fangxia Shi, Zongzong Lou. The application of improved-DAA for the vehicle network node security in single- and multi-trusted domain. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1301-1309. doi: 10.3934/dcdss.2015.8.1301
[7]

Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2021, 15 (2) : 257-266. doi: 10.3934/amc.2020057
[8]

Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021009
[9]

Riccardo Aragona, Alessio Meneghetti. Type-preserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235-251. doi: 10.3934/amc.2019016
[10]

Archana Prashanth Joshi, Meng Han, Yan Wang. A survey on security and privacy issues of blockchain technology. Mathematical Foundations of Computing, 2018, 1 (2) : 121-147. doi: 10.3934/mfc.2018007
[11]

Philip Lafrance, Alfred Menezes. On the security of the WOTS-PRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185-193. doi: 10.3934/amc.2019012
[12]

Meenakshi Kansal, Ratna Dutta, Sourav Mukhopadhyay. Group signature from lattices preserving forward security in dynamic setting. Advances in Mathematics of Communications, 2020, 14 (4) : 535-553. doi: 10.3934/amc.2020027
[13]

Jian Mao, Qixiao Lin, Jingdong Bian. Application of learning algorithms in smart home IoT system security. Mathematical Foundations of Computing, 2018, 1 (1) : 63-76. doi: 10.3934/mfc.2018004
[14]

Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial and Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143
[15]

Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021004
[16]

Yu-Chi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021053
[17]

Stamatios Katsikas, Vassilli Kolokoltsov. Evolutionary, mean-field and pressure-resistance game modelling of networks security. Journal of Dynamics and Games, 2019, 6 (4) : 315-335. doi: 10.3934/jdg.2019021
[18]

Jose-Luis Roca-Gonzalez. Designing dynamical systems for security and defence network knowledge management. A case of study: Airport bird control falconers organizations. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1311-1329. doi: 10.3934/dcdss.2015.8.1311
[19]

Yang Lu, Jiguo Li. Forward-secure identity-based encryption with direct chosen-ciphertext security in the standard model. Advances in Mathematics of Communications, 2017, 11 (1) : 161-177. doi: 10.3934/amc.2017010
[20]

Shan Liu, Hui Zhao, Ximin Rong. Time-consistent investment-reinsurance strategy with a defaultable security under ambiguous environment. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1185-1222. doi: 10.3934/jimo.2021015

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (671)
  • HTML views (1128)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy