Paper 2011/473

Practically Efficient Verifiable Delegation of Polynomial and its Applications

Jia XU

Abstract

In this paper, we propose a novel one-way function, which is equivalent to large integer factorization. From this new one-way function, we construct a novel verifiable delegation scheme for polynomial. Our contribution is twofold: in the practice aspect, our proposed polynomial delegation scheme is about 100 times faster than the existing solutions~\cite{PolyCommit,PolyDeleg} and has constant key size where the existing works require linear key size w.r.t. the degree of the delegated polynomial; in the theory part, our proposed scheme is provably secure under large integer factorization, which is a much weaker assumption than that of existing works. The efficient polynomial delegation scheme can be applied in constructing proofs of retrievability scheme, verifiable keyword search and verifiable dictionary data structure and so on. Furthermore, our new one-way function may have independent interests.

Note: The proposed scheme has a problem. We are working on it.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
Cloud ComputingVerifiable Remote ComputingDelegation of PolynomialProofs of StorageOne-way function
Contact author(s)
jiaxu2001 @ gmail com
History
2011-09-08: revised
2011-09-06: received
See all versions
Short URL
https://ia.cr/2011/473
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/473,
      author = {Jia XU},
      title = {Practically Efficient Verifiable Delegation of Polynomial  and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2011/473},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/473}},
      url = {https://eprint.iacr.org/2011/473}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.