Cryptology ePrint Archive: Report 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.

Category / Keywords: Cloud Computing, Verifiable Remote Computing, Delegation of Polynomial, Proofs of Storage, One-way function

Date: received 31 Aug 2011, last revised 7 Sep 2011

Contact author: jiaxu2001 at gmail com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Version: 20110908:053839 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]