التطبيقات العملية متماثل الشكل خوارزميات التشفير?

Question

يبدو أنه كانت هناك أشياء مثيرة للاهتمام يحدث في التشفير:أول متماثل الشكل التشفير مخطط ظهرت مؤخرا (تفسير, HT).تحدث تقريبا ، بل هو وسيلة من الترميز x في f(x) بحيث يمكنك حساب f(x+y) بسهولة معرفة f(x) و f(y) حتى ولو كنت لا يمكن استعادة بسهولة x و y (و نفس f(x*y)).

ما هي التطبيقات العملية على مخططات من هذا النوع (بمجرد أن يستتب الأمن)?بالنسبة لي, يبدو أنها يمكن أن تجعل كتابة الخوارزميات لمعالجة البيانات الخاصة أسهل بكثير.

هنا أفكاري:

1. التصويت الإلكتروني
2. التحقق من سلامة البيانات الخاصة
3. هل هناك فرصة من شأنها أن تساعد على الخصوصية بشكل عام ؟

على سبيل المثال:لدي حسابات مع البنوك A, B, C.الكيان X يريد تأكيد لدي أكثر من 1000 دولار المجموع ؛ فإنه بسعادة تقبل البيانات من البنوك A, B, C أو D ، ولكن للأسف ليس لدي ما يكفي من المال في حساب واحد.البنك بتشفير المعلومات عن $500 دولار مع المفتاح العام;وبالمثل فإن البنوك B و C تشفير المعلومات التي لدي 200 دولار و 300 دولار على التوالي.أنها ترسل هذه البيانات إلى العاشر من يضيف لهم بعض العدد التي لا تثبت في الواقع المشفرة 1000 دولار (عن طريق تشفير 1000 دولار مع المفتاح العام و مما يدل على أن النتيجة هي نفسها).لقد أثبت شيئا دون الكشف عن أن X كم من المال يجب في كل حساب.

مثال آخر:جيد المواطنين X_1, ..., X_n وكفريق واحد لاختيار واحد من اثنين من المرشحين ، واحدة منها هي اتيه-شرب يبرAl في حين آخر هو بible-تحمل بندقية الحبيب (جميع أسماء خيالية).قرروا أنهم يريدون التصويت أن تكون خاصة ولكن سريعة.يرسلون أصواتهم في شكل النواقل (1, vote_A, vote_B, vote_None) مشفرة إلى لجنة الانتخابات التي يضيفها علنا ويحصل على النتيجة في شكل (count, count_A, count_B, count_None).بعد التحقق من أن count = count_A + count_B + count_None, المسؤولين إعلان فوز أحد المرشحين بعد الانتخابات باطلة من قبل القاضي لسبب لا علاقة لها التصويت الإلكتروني قاتلوا في المحكمة لمدة 10 سنوات لكن هذه ليست مشكلتي على أي حال.

ملاحظات:- أعتقد أن هذه المثال كان من الممكن مع RSA حتى قبل لأنه يتطلب فقط homomorphicity في عملية واحدة.الأمل هو أننا يمكن أن يكون جذريا من الأشياء أكثر إثارة للاهتمام مع المزيد من العمليات -- لذلك تأتي مع الأمثلة!

• وأود بصفة خاصة أن نرى الإجابات التي تحتوي على رمز و/أو تطوير أطر فرصة المستخدمة في الممارسة العملية ، والسبب في ذلك هو علوم الكمبيوتر النظريه لوحة المناقشة.

• على متماثل الشكل الخوارزمية ، أن أكرر ما قيل أدناه في التعليقات ، يسمح لإنشاء برنامج إدارة البيانات دون معرفة منهم.للأسف أنواع محدودة إلى حد ما:لا يمكن أن يكون if (x=0) ... لأن x يتم تشفير كل خطوة بطيئة جدا (هناك بعض الأسوار المعنية).

Answer 1

وهنا البرية طلقة في الظلام:

نحن نفكر في حماية عادي من الشخص الذي يقوم الحساب على ذلك.ولكن ماذا لو كان الهدف حماية كل عادي و الخوارزمية ؟

خذ على سبيل المثال أجهزة التصوير بالرنين المغناطيسي.أغلى جزء من آلة التصوير بالرنين المغناطيسي هي خوارزمية في الجهاز الذي يحلل الرنين المغناطيسي البيانات.بسبب هذا, فهي محمية بشكل كبير من قبل الأجهزة مصممة لتدمير البرنامج قبل السماح نفسها للفحص من قبل طبيب غير موثوق بها الطرف (أو أي شخص لهذه المسألة).

إن التصوير بالرنين المغناطيسي صانع تركيز التصوير بالرنين المغناطيسي البيانات والحوسبة سيكون رائع في الحد من خطر فقدان الخوارزمية.بيد أن قوانين تمنعهم من الوصول إلى القطاع الخاص بيانات المريض.

لذلك!متماثل الشكل التشفير يسمح لهذا أن يحدث فيها المريض البيانات الخوارزمية على حد سواء المحمية.في 'الكامل' تشفير متماثل الشكل (أيحمل حلقة homomorphism على البيانات المشفرة) يسمح أكثر من ذلك بكثير فعالة وقوية مجموعة من حسابات للعمل على البيانات.

Answer 2

كما PKI المهوس ، إذا كان متماثل الشكل cryptofunction كانت أيضا assymmetric نظام المفتاح ، ثم لديك بعض الاحتمالات المثيرة للاهتمام في العالم من التوقيع.الموقع يمكن أن يوقع الرسالة المتلقي يمكن أن المعاد جزء الرسالة المقابلة جزء من النص المشفر إلى طرف ثالث.

في وظيفة التدوين ، التي من شأنها أن تكون:

المستخدم:

علامة(عادي, المفتاح الخاص) = المشفر

وينقل:

إرسال(نص عادي, المشفر, شهادة)

التطبيق يحصل على قطاعات:

عادي = desiredPlaintext + otherPlaintext

و يحسب نفسه تحويل النص المشفر باستخدام شيء من هذا القبيل:

إذا كان النص المشفر::عادي بعد ذلك؟؟::desiredPlaintext

العثور على desiredCiphertext

تطبيق الأمام المحتوى المطلوب فقط إلى الخدمات الخارجية:

إرسال(desiredPlaintext, desiredCiphertext شهادة)

و الخدمة يمكن التحقق من هذه الرسالة كما لو كان المستخدم إرسالها مباشرة.

هذا يعتمد على خوارزمية التجزئة المستخدمة لضغط عادي أيضا متماثل الشكل.إذا لا, هذا ليس الذهاب إلى العمل...أو أنه لا يوجد خوارزمية التجزئة يتم تطبيقها.

هذا يمكن أن تكون مفيدة جدا في الحالات حيث تريد خدمة خارجي أن تفعل شيئا ردا على توقيع طلب المستخدم ، ولكن كنت لا تريد فضح كل شيء للمستخدم إرسالها إلى الخدمة الخارجية.

ومن الأمثلة على ذلك مجموعة بسيطة يأمر النظام - أرسل التطبيق على شبكة الإنترنت طلب شراء مجموعة من العناصر.أن تكون فائقة آمنة أوقع أمر الشراء الذي يؤكد أن أريد (ووعد لدفع ثمن) بعض # البنود التي يتم شحنها إلى بعض موقع معين ، من خلال تاريخ محدد ، مع بعض معلومات الدفع.الآن..التطبيق على شبكة الإنترنت سوف تريد أن يكون لها العديد من الأمور:

• والتمويل يحتاج لشحن حسابي ، والبدء في الحصول على دفعة من لي
• المخزون يحتاج إلى سحب العناصر من المخزون ، أو التعامل مع أي من الأسهم مشاكل
• الشحن يجب أن تتلقى من المخزون و تحريك الأشياء إلى عنواني

لا يوجد سبب المخزون أو الشحن إلى معرفة كيف أدفع الفاتورة.و قد لا يكون هناك سبب المالية أن تعرف عنوان الشحن الخاص بي...في كل حالة ، desiredPlaintext و desiredCiphertext التغيرات اعتمادا على من المتلقي.هذا هو أكثر فعالية في نظام مثل Amazon.com الكتب المستعملة حيث الكيان اشتريتها من (أمازون) يختلف عن الكيان توفير البند (المستخدمة كتاب البائع).

قراءة ورقة حول التشفير شعرية, يبدو أكثر مثل مفتاح متماثل نظام...الذي لا يفضي ذلك إلى توقيع الرسائل.

على مفهوم "لا تقل أبدا", أنا لا أقول أنه من غير المعقول أن استخدامه الخصوصية التطبيقات.ولكن يبدو بوضوح مزعجة التي يمكنك أن تجد طرق متعددة للوصول من النص المشفر إلى نص عادي.

Answer 3

أكبر تطبيق تشفير متماثل الشكل سيكون في التنقيب عن البيانات ، IMHO.استخدام هذه algo يمكن حل مشاكل الخصوصية و الاتجاه الاكتشاف في نفس الوقت.على سبيل المثال, شركة يستضيف انها مبيعات معلومات عن بعض SAS مزود.الآن أنه مزود يمكن أن تعطيك بيانات متطورة خدمات التعدين ، دون الحاجة إلى الكشف عن المعلومات الخاصة بك الحقيقي .في الأساس, هل سيكون قادرا على إرسال البيانات إلى حساب مزود يكون له الاستفادة من دورات وحدة المعالجة المركزية لحساب نيابة عنك, و نرسل لك تشفير البيانات مرة أخرى.سيكون ذلك حقا رائعة الشركات الذين يتطلعون إلى الانتقال إلى سحابة على أساس النظم ، ولكن الخصوصية / IP المخاوف منعهم من القيام بذلك.

آخر محتمل التطبيق على أقل المستوى الشخصي سيكون في التعامل مع جميع أنواع البيانات المالية.ايليا المثال الموسعة يمكن أن تنطبق على تقديم الإقرارات الضريبية قبل المحاسب الخاص بك دون رؤية الواقع المعلومات المالية الخاصة بك, معالجة بطاقات الائتمان وغيرها.

ومع ذلك, كنت أمسك بلدي الإثارة حتى مخطط يتم اختبار صارم و التي تعتبر آمنة.التشفير ألجوس لديك عادة سيئة السمعة من الفشل في أول اختبار الذهاب مراجعة وتكرار دورة حتى وهم "معتمد" من قبل بعض سلطة الحكومة.

Answer 4

كنت قد تكون مهتمة في مشاهدة بروس شنير بدلا مدوي سلبية تأخذ على متماثل الشكل التشفير في:

http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html?nc=11

Answer 5

أنا لا أعرف كم تكلفة f(x) + f(x) حساب ستكون ، ولكن ربما أنها يمكن أن تستخدم كوسيلة لتنفيذ بيانات مشفرة.

يمكنك تخزين 1 مليون الصفوف من بعض البيانات مشفرة ، f(x_1), f(x_2), ... f(x_n).هل يمكن أن تفعل

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

والتي يمكن أن تحسب من خلال القيام SUM(f(x)) ثم فك الشفرة على SUM(x).

Answer 6

مع هذا يمكنك تنفيذ التعسفي غير متكررة الدائرة ويحدها من العمق بحيث تعطى لوغاريتمي طول المفتاح يمكنك تنفيذ NC1 خوارزمية (الأساس تغذية إلى الأمام منطقية الدائرة).

لذا كيف يمكنك استخدام هذا ؟

يتيح إلقاء نظرة على الخريطة/تقليص الدوائر والحد الخطة على مجموعة من المدخلات.

أولا البيانات:

ربما لا تريد أن يكون للعميل بتشفير جميع البيانات التي نحن بصدد البحث, حتى تتمكن من توفير مشفر 1 و مشفرة 0 إلى الخادم ، وتتيح استخدام الخاتم هيكل لبناء التعسفي المشفرة الصحيحه بالنسبة لنا ، أو يمكننا استخدام هذه مباشرة كما بت.بهذه الطريقة يمكن توفير بعض أو كل البيانات التي نقوم تبحث عن طريق.من أجل الاعداد الصحيحه يمكن بناء عليها من قبل الفلاحين الحسابي (مزدوجة أو ضعف وإضافة 1 لكل بت) ، بت فقط يوفر مناسبة مشفرة قليلا.

يمكننا أن مزيج المباراة منطقية و القيم الصحيحة في التصاميم الحصول على إذا/إذن/آخر (الذي يتطلب تقييم كل فروع SIMD نمط) من خلال تقييم cond * ثم + (1 - cond) * آخر باستخدام 1 صحيح و 0 كاذبة في cond, لذا يمكنك الحصول على بعيدا مع استخدام المدمج في الحساب الخاص بك خاتم لجعل الدوائر الخاصة بك أكثر الضحلة.

ومن ناحية أخرى ، قد يكون لدينا ما قبل تشفير بعض البيانات ، ولكن منذ سيكون لديك للحفاظ على تدوير نفس المفتاح تعيين لاستخدام هذا يصبح على محمل الجد صعبة للحصول على حق.

حتى الآن لدينا خادم البيانات المقدمة.الآن, تشفير أشياء لا تريد أن الخادم أن أعرف ما هو عليه كنت تبحث عن ، ويكون لهم تغذية في الدائرة في نقطة كما يقول إضافية الإدخال إلى الخريطة الخاصة بك وظيفة.

يجب أن تكون قادرة على خريطة التعسفي NC1 مثل الدوائر على كل المدخلات إلى استخراج حقل ضرب بعض القيم و عموما اعرض الخريطة في شكل يمكنك تقليل بثمن بخس.

ثم خفض تلك الشظايا باستخدام أكثر الدوائر الصغيرة ، مثل بسيط مونويد التي لديها لطيف الحجم-يحدها النتيجة.(أيكنت الخريطة للحصول على قليلا أن يشير إلى ما إذا كان يمكنك العثور على تطابق ، ومن ثم تقليل من عد هذه البتات صغيرة الأفعى الدائرة)

حيث تحتاج فقط إلى بناء الدائرة منطقيا ومحاكاة تنفيذه على هذه المشفرة بت في متماثل الشكل الدائري ، ربما يمكن تنفيذه بسرعة نسبيا باستخدام صغيرة DSL ، أيشيء مثل الحمم البركانية في هاسكل ، على افتراض أنك حصلت على متماثل الشكل التشفير قطع على التوالي.

كما نضع في اعتبارنا أن كل بوابة على محمل الجد تكلفة تنفيذ.

لذا لتلخيص ،

1. تعطي سيرفر مشفر 1 و 0 و أي تشفير metainfo على الخريطة الخاصة بك وخفض الوظائف.
2. لكل نقطة بيانات ، ترميز إلى متماثل الشكل الدائري, تغذية الخريطة الدائرة كل من المدخلات المعلومات الوصفية إلى الحصول على قيمة مناسبة الحد.
3. في متوازن شجرة ثنائية (أو غير متوازنة الترتيب للحد من ارتفاع الشجرة), تطبيق الخاص بك الحد من عملية الإخراج من دائرة أي تشفير خريطة metainfo.
4. من ناحية النتيجة إلى العميل فك التشفير

Answer 7

المشكلة مع القائمة متماثل الشكل خوارزمية التشفير هو أنه يمكنك فقط تنفيذ polylogarithmic (NC1) الدائرة مع ذلك ، مما يستبعد أي شيء تقريبا مثيرة للاهتمام حسابيا.

بالإضافة إلى أنه لا يبدو أن تعقيد الترميز في أي حال من الأحوال أقل من تعقيد تنفيذ polylogarithmic الدائرة نفسك, حتى أنك لم تلتقط أي عمل خالية من أول وهلة ، إلا إذا كنت تفعل شيئا لا سيما صعبة مع ذلك.

Answer 8

الحوسبة الموزعة مثل SETI@Home, البروتين للطي المشاريع ، وما إلى ذلك ، هي شعبية إلى حد ما لأنهم الاستفادة من التبرع من الوقت وحدة المعالجة المركزية و الكهرباء من الآلاف من المستخدمين.حتى أكثر إثارة للاهتمام أن يكون نموذجا حيث يمكن للناس الحصول على أموال لتوفير هذه الموارد للمشاريع التجارية.ومع ذلك ، لا الشركة المسؤولة يريد أن السفينة البيانات إلى الآلاف من مجهول أجهزة الكمبيوتر للمعالجة.إذا كنت يمكن أن بكفاءة تطبيق خوارزميات تشفير البيانات ، يصبح من الممكن أن يفوض معالجة أي شخص دون علاقة ثقة.

Answer 9

التصويت الإلكتروني هو في الواقع التطبيق العملي تشفير متماثل الشكل ، أي http://heliosvoting.org/

Answer 10

بعض التطبيقات المصرفية ربما تصبح أسرع مع مساعدة من متماثل الشكل التشفير.

فإنها يمكن أن تؤدي عمليات تشفير البيانات على السحابة بدلا من الاستيلاء عليها من سحابة المحلية ووضع مرة أخرى على السحابة.أيضا لا تحتاج إلى تشفير-فك-تنفيذ عمليات تشفير أنابيب تشفير-أداء العمليات سوف تكون على ما يرام.