Homomorphic linear authentication schemes from ε-ASU₂ functions for proofs of retrievability

• Autorzy: Liu S. , Chem K.
• Języki publikacji: EN

Abstrakty

EN

Proof of Retrievability (POR) refers to interactive auditing protocols executed between a storage server and clients, so that clients can be convinced that their data is available at the storage server, ready to be retrieved when needed. In an interactive POR protocol, clients initiate challenges to the server, and the server feedbacks responses to clients with the help of the stored data. Retrievability means that it should be possible for a client to extract his/her data from the server's valid responses. An essential step leading to retrievability is the server's unforgeability of valid responses, i.e, any server coming up with valid responses to a client's challenges is actually storing the client's data with overwhelming probability. Unforgeability can be achieved with authentication schemes like MAC, Digital Signature, etc. With Homomorphic Linear Authentication (HLA) schemes, the server�' several responses can be aggregated into one, hence reducing the communication complexity. In this paper, we explore some new constructions of ε-almost strong universal hashing functions (ε-ASU₂), which are used to build homomorphic linear authenticator schemes in POR to provide unforgeability. We show the HLA scheme involved in Shacham and Waters' POR scheme (see Shacham and Waters, 2008) is just an employment of a class ε-ASU₂ functions. Using another class of ε-ASU₂ for authentication in POR results in a new HLA scheme, which enjoys unforgability, the same shortest responses as the SW scheme, but reduces the local storage from O_(n+s) to O_(n) for information soundness, and from O_(s) to O₍₁₎ for knowledge-soundness.

Słowa kluczowe

EN

authentication code; proof of retrievability

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2012
• Tom: Vol. 41, no. 2
• Strony: 335--351
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Liu S.

autor

Chem K.

• Department of Computer Science and Engineering Shanghai Jiao Tong University, Shanghai 200240, China

Bibliografia

• Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z. and Song, D. (2007) Provable data possession at untrusted stores. In: De Capitani di Vimercati, S., Syverson, P., eds., CCS’07 Pro ceedings of the 14th ACM Conference on Computer and Communications Security, ACM Press, New York, 598-609.
• Carter, J.L. and Wegman, M.N. (1979) Universal classes of hash functions. Journal of Computer and System Sciences 18(2), 143-154.
• Deswarte, Y., Quisquater, J.-J. and Saldane, A. (2004) Remote integrity checking. In: S. Jajodia, L. Strous, eds., Proceedings of IICIS 2003, IFIP140, 1-11. Kluwer Academic, Dordrecht.
• den Boer, B. (1993) A simple and key-economical unconditional authentication scheme. Journal of Computer Security 2(1), 65-71.
• Dodis, Y., Vadhan S. and Wichs, D. (2009) Proofs of retrievability via hardness amplification. Theory of Cryptography, LNCS 5444, 109-127.
• Filho, D. and Barreto, P. (2006) Demonstrating data possession and uncheatable data transfer. Cryptology ePrint Archive, Report 2006/150, http://eprint.iacr.org/
• Gilbert, E., MacWilliams, F.J. and Sloane, N. (1974) Codes which detect deception. The Bell System Technical Journal 53(3), 405-424.
• Juels, A. and Kaliski, B. (2007) PORs: proofs of retrievability for large files. In: De Capitani di Vimercati, S., Syverson, P. , eds., Proceedings of CCS 2007. ACM Press, New York, 584-597.
• Naor, M. and Rothblum, G. (2005) The complexity of online memory checking. In: E. Tardos, ed., Proceedings of FOCS 2005. IEEE Computer Society, Los Alamitos, 573-584.
• Schwarz, T. and Miller, E. (2006) Store, forget, and check: Using algebraic signatures to check remotely administered storage. In: M. Ahamad, L. Rodrigues, eds., Proceedings of ICDCS 2006. IEEE Computer Society, Los Alamitos, 12-12.
• Shacham, H. and Waters, B. (2008) Compact proofs of retrievability. In: Proceedings of Asiacrypt 2008, LNCS 5350, Springer-Verlag, 90-107.
• Sommons, G.J. (1984) Authentication theory/coding theory. Advances in Cryptology, Proc. Crypto’84, LNCS 196, Springer-Verlag, New York, 411-431.
• Sommons, G.J. (1992) A game theory model of digital message Authentication. Congr. Numer. 34, 413-424.
• Stinson, D.R. (1992) Universal hashing and authentication codes. Advances in Cryptology-CRYPTO’91, LNCS 576, 74-85.
• Stinson, D.R. (1994) Combinatorial techniques for universal hashing. Journal of Computer and System Sciences 48(2), 337-346.
• Stinson, D.R. (1994) Universal hashing and authentication codes. Designs, Codes and Cryptography 4(4), 369-380.
• Wegman, M.N. and Carter, J.L. (1998) New hash functions and their use in authentication and set equality. J. Computer and System Sci. 22, 265-279.