Evaluating branching programs on encrypted data

Yuval Ishai, Anat Paskin

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

150 اقتباسات (Scopus)

ملخص

We present a public-key encryption scheme with the following properties. Given a branching program P and an encryption c of an input x, it is possible to efficiently compute a succinct ciphertext c' from which P(x) can be efficiently decoded using the secret key. The size of c' depends polynomially on the size of x and the length of P, but does not further depend on the size of P. As interesting special cases, one can efficiently evaluate finite automata, decision trees, and OBDDs on encrypted data, where the size of the resulting ciphertext c′ does not depend on the size of the object being evaluated. These are the first general representation models for which such a feasibility result is shown. Our main construction generalizes the approach of Kushilevitz and Ostrovsky (FOCS 1997) for constructing single-server Private Information Retrieval protocols. We also show how to strengthen the above so that c' does not contain additional information about P (other than P(x) for some x) even if the public key and the ciphertext c are maliciously formed. This yields a two-message secure protocol for evaluating a length-bounded branching program P held by a server on an input x held by a client. A distinctive feature of this protocol is that it hides the size of the server's input P from the client. In particular, the client's work is independent of the size of P.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفTheory of Cryptography - 4th Theory of Cryptography Conference, TCC 2007, Proceedings
الصفحات575-594
عدد الصفحات20
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2007
منشور خارجيًانعم
الحدث4th Theory of Cryptography Conference, TCC 2OO7 - Amsterdam, هولندا
المدة: ٢١ فبراير ٢٠٠٧٢٤ فبراير ٢٠٠٧

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4392 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference4th Theory of Cryptography Conference, TCC 2OO7
الدولة/الإقليمهولندا
المدينةAmsterdam
المدة٢١/٠٢/٠٧٢٤/٠٢/٠٧

بصمة

أدرس بدقة موضوعات البحث “Evaluating branching programs on encrypted data'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا