One-More Paillier Inversion and Concurrent Secure Identification
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [17]
  • |
  • Related
  • | | |
  • Comments
    Abstract:

    This paper revisits Paillier's trapdoor one-way function, focusing on the computational problem underlying its one-wayness. A new computational problem called the one-more Paillier inversion problem is formulated. It is a natural extension of Paillier inversion problem to the setting where adversaries have access to an inversion oracle and a challenge oracle. The relation between the one-more Paillier inversion problem and the one-more RSA problem introduced by Bellare, et al. It is shown that the one-more Paillier inversion problem is hard if and only if the one-more RSA problem is hard. Based on this, a new identification scheme is proposed. It is shown that the assumed hardness of the one-more Paillier inversion problem leads to a proof that the proposed identification scheme achieves security against concurrent impersonation attack.

    Reference
    [1]Paillier P.Public-Key cryptosystems based on composite degree residuosity classes.In:Wiener MJ,ed.Proc.of the EUROCRYPT'99.LNCS 1592,Springer-Verlag,1999.223-238.
    [2]Goldwasser S,Micali S.Probabilistic encryption.Journal of Computer and System Sciences,1984,28(2):270-299.
    [3]Cohen JD,Fischer M.A robust and verifiable cryptographically secure election scheme.In:Proc.of the 26th Annual IEEE Symp.on Foundations of Computer Science.IEEE,1985.372-382.
    [4]Naccache D,Stern J.A new public key cryptosystem based on higher residues.In:Proc.of the 5th Symp.on Computer and Communications Security.ACM Press,1998.59-66.
    [5]Okamoto T,Uchiyama S.A new public-key cryptosystem as secure as factoring.In:Nyberg K,ed.Proc.of the EUROCRYPT'98.LNCS 1403,Springer-Verlag,1998.308-318.
    [6]Damgard I,Jurik M.A generalisation,a simplification and some applications of Paillier's probabilistic public-key system.In:Kim K,ed.Proc.of the PKC 2001.LNCS 1992,Springer-Verlag,2001.119-136.
    [7]Catalano D,Gennaro R,Howgrave-Graham N,Nguyen PQ.Paillier's cryptosystem revisited.In:Proc.of the 8th ACM Conf.on Computer and Communications Security.ACM Press,2001.206-214.
    [8]Galbraith SD.Elliptic curve Paillier schemes.Journal of Cryptology,2002,15(2):129-138.
    [9]Ostrovsky R,Skeith III WE.Private searching on streaming data.In:Shoup V,ed.Proc.of the CRYPTO 2005.LNCS 3621,Springer-Verlag,2005.223-240.
    [10]Blake IF,Kolesnikov V.Conditional encrypted mapping and comparing encrypted numbers.In:Di Crescenzo G,Rubin A,eds.Proc.of the FC 2006.LNCS 4107,Springer-Verlag,2006.206-220.
    [11]Bellare M,Namprempre C,Pointcheval D,Semanko M.The one-more-RSA inversion problems and the security of Chaum's blind signature scheme.Journal of Cryptology,2003,16(3):185-215.
    [12]Cramer R,Damgard I,Schoenmakers B.Proofs of partial knowledge and simplified design of witness hiding protocols.In:Desmedt Y,ed.Proc.of the CRYPTO'94.LNCS 839,Springer-Verlag,1994.174-187.
    [13]Guillou L,Quisquater J.A practical zero-knowledge protocol fitted to security microprocesors minimizing both transmission and memory.In:Güther CG,ed.Proc.of the EUROCRYPT'88.LNCS 330,Springer-Verlag,1988.123-128.
    [14]Okamoto T.Provably secure and practical identification schemes and corresponding signature schemes.In:Brickell EF,ed.Proc.of the CRYPTO'92.LNCS 740,Springer-Verlag,1993.31-53.
    [15]Cramer R,Shoup V.Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack.SIAM Journal on Computing,2003,33(1):167-226.
    [16]Bellare M,Palacio A.GQ and Schnorr identification schemes:Proofs of security against impersonation under active and concurrent attack.In:Proc.of the CRYPTO 2002.LNCS 2442,Springer-Verlag,2002.162-177.
    [17]Bellare M,Namprempre C,Neven G.Security proofs for identity-based identification and signature schemes.In:Proc.of the EUROCRYPT 2004.LNCS 3027,Springer-Verlag,2004.268-286.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

宋 焰.多一次Paillier求逆问题与并发安全的鉴别方案.软件学报,2008,19(7):1758-1765

Copy
Share
Article Metrics
  • Abstract:3968
  • PDF: 5778
  • HTML: 0
  • Cited by: 0
History
  • Received:November 20,2006
  • Revised:May 31,2007
You are the first2035295Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063