Praktische Anwendungen von homomorphes Verschlüsselungsalgorithmen?

Question

Es scheint, gibt es interessante Dinge, die sich in der Kryptographie gab es: die erste Seite homomorphe Verschlüsselung Schema erschien vor kurzem ( Erklärung , HT ). Grob gesagt, es ist ein Weg, x in f(x) der Codierung, so dass Sie f(x+y) leicht f(x) und f(y) zu wissen, berechnen können, auch wenn man nicht so leicht x und y (und gleich für f(x*y)) wiederherstellen.

Was sind praktische Anwendungen für Systeme dieser Art (einmal ihre Sicherheit festgestellt wurde)? Für mich scheint es, sie private Daten Schreiben Algorithmen zur Manipulation viel einfacher machen könnte.

Hier sind meine Gedanken :

1. Vote électronique
2. die Integrität von privaten Daten Überprüfung
3. gibt es eine Chance, dass die Privatsphäre im Allgemeinen helfen würde?

Beispiel: : Ich habe Konten bei Banken A, B, C. Entity X will ich muss bestätigen, mehr als $ 1000 insgesamt; es sei glücklich Aussagen von Bänken A, B, C oder D, akzeptiert aber leider habe ich nicht genug Geld in jedem einzelnen Konto. Bank A verschlüsselt die Informationen über meinen $ 500 Dollar mit meinem öffentlichen Schlüssel; In ähnlicher Weise verschlüsseln Banks B und C die Informationen, die ich jeweils $ 200 und $ 300 haben. Sie senden diese Daten an X, die sie bis zu einem gewissen Zahl addiert, die ich zeige, in der Tat zu verschlüsselnden $ 1000 (von $ 1000 mit meinem öffentlichen Schlüssel verschlüsselt und die zeigen, dass das Ergebnis das gleiche ist). Ich habe etwas bewiesen, ohne Offenlegung X, wie viel Geld ich in jedem Konto haben.

Ein weiteres Beispiel: : Gute Bürger X_1, ..., X_n sich zusammen, um eine von zwei Kandidaten zu wählen, von denen latte trinken liber ist A l, während ein anderer ist ein B ible tragenden Gewehrliebhaber (alle Namen sind frei erfunden). Sie entscheiden, sie wollen, dass die Abstimmung privat, aber schnell zu sein. Sie schicken ihre Stimmen im Vektorformat (1, vote_A, vote_B, vote_None) an die Wahlkommission verschlüsselt, die sie öffentlich ergänzt und erhält das Ergebnis in Form (count, count_A, count_B, count_None). Danach count = count_A + count_B + count_None Überprüfung erklären die Beamten den Sieg einer der Kandidaten, wonach die Wahl der Richter aus irgendeinem Grunde in keinem Zusammenhang mit elektronischer Stimmabgabe und kämpften im Gericht für die nächsten 10 Jahre für ungültig erklärt wird, aber, hey, das ist nicht mein Problem trotzdem.

Notizen : - Ich glaube, diejenigen spezielles Beispiel möglich war, mit RSA bereits vor, da es erfordert nur homomorphicity in einem Arbeitsgang. Die Hoffnung ist, dass wir radikal interessantere Dinge mit mehr Operationen haben können - so, kommen mit Beispielen

• Ich möchte vor allem Antworten wie Code enthält, um zu sehen und / oder Rahmenbedingungen schaffen, die eine Chance haben, in der Praxis verwendet wird, ist der Grund, SO ist keine theoretische Informatik Diskussionsrunde.

• Der homomorphes Algorithmus, zu wiederholen, was unten in den Kommentaren gesagt wurde, ermöglicht es, um ein Programm zu erstellen, die sie Daten ohne zu wissen, verwalten würden. Leider sind die Arten von Programmen etwas begrenzt: Sie nicht if (x=0) ... haben können, weil x verschlüsselt ist, und jeder Schritt ist sehr langsam (es gibt einige Gitter beteiligt)

.

Answer 1

Hier ist eine wilde Schuss im Dunkeln:

Wir denken über den Klartext von der Person zum Schutz der Berechnung auf, es zu tun. Was aber, wenn das Ziel war, sowohl den Klartext zu schützen und den Algorithmus?

Nehmen wir zum Beispiel MRI-Maschinen. Der teuerste Teil der MRI-Maschine ist der Algorithmus, bei dem die Maschine der Magnetresonanzdaten analysiert. Aus diesem Grunde sind sie stark von Hardware-Geräten geschützt entworfen, das Programm zu zerstören, bevor so dass ich von einer nicht vertrauenswürdigen Partei geprüft werden (oder jemand für diese Angelegenheit).

Wenn ein MRI-Hersteller MRI-Daten-Computing zentralisieren könnte, wäre es eine fantastische Verringerung des Risikos ihres Algorithmus zu verlieren sein. Jedoch verhindern, dass sie Gesetze von privaten Patientendaten zugreifen.

So! Homomorphe Verschlüsselung ermöglicht dies geschehen kann, wo die Patientendaten und der Algorithmus beide geschützt sind. Das ‚vollständig‘ homomorphe Verschlüsselungs (das heißt einen Ringhomomorphismus auf die verschlüsselten Daten zu induzieren) ermöglicht einen wesentlich effizientere und robusten Satz von Berechnungen an den Daten zu arbeiten.

Answer 2

Als PKI Aussenseiter, wenn die homomorphe cryptofunction war auch ein asymmetrisches Schlüsselsystem, dann haben Sie einige sehr interessante Möglichkeiten in der Welt der Unterzeichnung. Der Unterzeichner könnte möglicherweise die Nachricht unterschreiben und ein Empfänger könnte erneut übertragen Teil der Nachricht und dem entsprechenden Teil des Chiffretext an einen Dritten.

In Funktion Notation, das wäre:

Benutzer Zeichen:

Zeichen (Klartext, private Schlüssel) = Chiffretext

und sendet:

send (Klartext, Geheimtext, Zertifikat)

Anwendung erhält Segmente:

Klartext = desiredPlaintext + otherPlaintext

und die gleiche Umwandlung von Chiffretext berechnet, mit so etwas wie:

Wenn chiffrierten Text :: Klartext dann ?? :: desiredPlaintext

finden desiredCiphertext

Anwendung vorwärts gewünschten Inhalt nur an externe Dienstleister:

send (desiredPlaintext, desiredCiphertext, Zertifikat)

Und der Service kann diese Nachricht bestätigen, als ob der Benutzer es direkt geschickt hatte.

Dies ist abhängig von dem Hash-Algorithmus verwendet, um den Klartext auch homomorphes sein zu komprimieren. Wenn nicht, wird dies nicht funktionieren ... oder dass kein Hash-Algorithmus angewandt wird.

Dies könnte sehr nützlich sein, in Fällen, in denen Sie einen externen Service wollen etwas in Reaktion auf eine unterzeichnete Benutzeranforderung zu tun, aber Sie wollen nicht alles, was den Benutzer zu diesem externen Dienst gesendet belichten.

Ein Beispiel wäre ein einfaches Paket Bestellsystem sein - ich sende eine Web-Anfrage App eine Sammlung von Gegenständen zu kaufen. Um super-sichere ich eine Bestellung unterzeichnen, die bestätigt, dass ich will (und versprechen zu bezahlen) einige Anzahl der Elemente, bis zu einem gewissen bestimmten Ort geliefert, von einigen bestimmten Datum, und mit einigen spezifischen Zahlungsinformationen. Nun .. die Web-App wollen mehrere Dinge haben passieren:

• Finanzen muss mein Konto aufzuladen, und starten Sie eine Zahlung von mir bekommen
• Inventar muss die Elemente aus Lager ziehen, oder die Zusammenarbeit mit ausverkauften Problemen umgehen
• Versand muss aus dem Inventar und bewegen Sie die Sachen an meine Adresse
erhalten

Es gibt keinen Grund für Inventar oder Versand zu wissen, wie ich meine Rechnung bezahlen. Und vielleicht gibt es keinen Grund für die Bereiche Finanzen, um meine Lieferadresse zu wissen ... In jedem Fall sind die desiredPlaintext und desiredCiphertext ändert, je nachdem, wer der Empfänger ist. Dies ist sogar noch potenter in einem System wie Amazon.com Bücher verwendet, in denen das Unternehmen I aus (Amazon) gekauft von der Einheit verschieden ist die Bereitstellung die Artikel (der verwendete Buchhändler).

das Papier über Gitter Kryptographie Lesen, es eher wie ein symmetrischer Schlüssel-System klingt ... die Signieren nicht so förderlich ist.

Auf dem Konzept der „niemals nie sagen“, würde ich nicht sagen, dass es unvernünftig war es Anwendungen für die Privatsphäre zu verwenden. Aber es scheint deutlich lästig, dass Sie mehrere Möglichkeiten, sich von chiffrierten Text zu Klartext finden.

Answer 3

Die größte Anwendung von homomorphe Verschlüsselung würde in Data Mining sein, IMHO. Die Verwendung dieses algo könnten die Probleme sowohl Privatsphäre und Trend Entdeckung zugleich lösen. Zum Beispiel, sagen, dass Ihre Firma beherbergt es Verkäufe Informationen über einige SAS-Anbieter ist. Nun könnte, dass Anbieter Ihnen anspruchsvolle Data-Mining-Dienste geben, ohne dass Sie tatsächlich Ihre realen Daten zu offenbaren. Grundsätzlich wäre Sie in der Lage sein, Ihre Daten an eine Rechenanbieter zu senden, haben ihn seine CPU-Zyklen verwenden in Ihrem Namen zu berechnen, und Sie können die verschlüsselten Daten zurückschicken. Das wäre wirklich fantastisch für Unternehmen, die sich um Cloud-basierte Systeme zu bewegen, aber haben Privatsphäre / IP Bedenken sie daran zu verhindern, so.

Eine weitere mögliche Anwendung, auf einer unteren und einer persönlicheren Ebene, bei der Handhabung aller Arten von Finanzdaten sein würde. Ilyas Beispiel erweitert, um Einreichung von Steuererklärungen von Ihrem Steuerberater anwenden kann, ohne tatsächlich Ihre finanziellen Informationen zu sehen, Kreditkarten Verarbeitung etc.

Allerdings würde ich meine Aufregung halten, bis das System rigoros getestet und als sicher. Encryption algos haben eine berüchtigte Gewohnheit ihren ersten Test versagt, gehen für eine Revision und Wiederholen des Zyklus, bis sie „zertifiziert“ durch eine Regierungsbehörde sind.

Answer 4

Sie können bei der Betrachtung Bruce Schneier eher resoundingly negativ nimmt auf homomorphe Verschlüsselung bei interessiert sein

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

Answer 5

Ich weiß nicht, wie teuer die f(x) + f(x) Berechnung sein wird, aber vielleicht könnte es als eine Möglichkeit der Implementierung verschlüsselte Datenbank verwendet werden.

Sie können speichern 1 Million Zeilen einiger Daten verschlüsselt, wie f(x_1), f(x_2), ... f(x_n). Sie tun können,

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

Welche indem zuerst tun SUM(f(x)) dann berechnet werden, könnte es zu entschlüsseln SUM(x).

Answer 6

das mit Ihnen eine beliebigen nicht-rekursive Schaltung von beschränkter Tiefe ausführen können, so eine logarithmische Schlüssellänge gegeben Sie einen NC1-Algorithmus (im Grunde eine Feed-Forward Boolesche Schaltung) ausführen können.

Also, wie können Sie verwenden das?

Lets auf Karte sehen / eine Schaltung und Reduzierungsplan über einen Satz von Eingängen zu reduzieren.

Zuerst werden die Daten:

Wir wollen wahrscheinlich nicht der Kunde auf alle Daten haben, müssen verschlüsselt wir suchen wollen, so können Sie ein 1 verschlüsselt bereitstellen und eine 0 auf dem Server verschlüsselt, und lassen Sie es die Ringstruktur verwenden zu konstruieren beliebige verschlüsselte Zahlen für uns, oder wir können nur diejenigen, die direkt als Bits verwenden. Auf diese Weise kann der Server einige oder alle der Daten, die wir suchen durch. Für ganze Zahlen kann er sie durch Bauer arithmetische Konstrukt (Doppel- oder Doppel und füge 1 für jedes Bit), für die Bits liefert es nur das entsprechende Bit verschlüsselt.

Wir können in unseren Entwürfen mischen und Werte boolean und Integer-Spiel, eine if / then / else zu erhalten (das erfordert beiden Zweige SIMD Stil Auswertung) durch Auswertung cond * dann + (1 - cond) * sonst 1 als wahr mit und in cond 0 als falsch, so dass Sie mit der Verwendung des in der Arithmetik des Rings aufgebaut wegkommen können Ihre Schaltungen flachen.

machen

Auf der anderen Seite, wir können vorab verschlüsselt als auch einige Daten haben, aber da Sie den gleichen Schlüsselsatz halten müssen würden Recycling, es zu benutzen, wird dies ernsthaft heikel richtig zu machen.

So, jetzt haben wir den Server zur Verfügung gestellten Daten. Nun verschlüsseln das Zeug Sie nicht den Server wollen wissen, wie das, was es ist Sie suchen, und haben sie das auch an den richtigen Stellen in den Kreislauf zuzuführen, sagen als zusätzliche Eingabe Ihrer Map-Funktion.

Wir sollten in der Lage, eine beliebige NC1 artige Schaltung über jeden Eingang zur Karte ein Feld zu extrahieren, multiplizieren einige Werte, und es in der Regel in eine Form der Karte, die Sie kostengünstig reduzieren.

Dann diese Fragmente reduzieren unter Verwendung von mehreren kleinen Schaltungen, wie beispielsweise für eine einfache monoid, die eine schön größen begrenzt Ergebnis hat. (D Karten Sie ein Bit zu erhalten, die angibt, ob Sie eine Übereinstimmung gefunden, und sie dann reduzieren, indem diese Bits mit einem kleinen Addierschaltung mitgezählt)

Da Sie nur die Schaltung logisch konstruieren müssen und simulieren ihre Ausführung auf diesem verschlüsselten Bits im homomorphe Ring, werden Sie wahrscheinlich es relativ schnell implementieren könnten einen kleinen DSL verwenden, also so etwas wie Lava in Haskell, Sie unter der Annahme, bekam die homomorphe Verschlüsselung Stücke gerade.

Auch im Auge behalten, dass jedes Tor ist ernst teuer auszuführen.

Also, um zusammenzufassen,

1. Geben Sie den Server ein verschlüsselt 1 und 0 und alle verschlüsselt Metainformationen für die Karte und reduzieren Funktionen.
2. Für jeden Datenpunkt, kodieren sie in die homomorphe Ring, füttern Ihre Karte Schaltung sowohl die Eingabe und die Meta-Informationen einen geeigneten Wert für die Reduktion zu erhalten.
3. In einem ausgeglichenen binären Baum (oder andere symmetrische Anordnung Baumhöhe zu minimieren), gelten für die Ausgabe von Ihrer Schaltung und eine verschlüsselten Karte metainfo Ihre Reduktionsoperation.
4. Hand des Ergebnis über den Client für die Entschlüsselung

Answer 7

Das Problem mit dem vorhandenen homomorphes Verschlüsselungsalgorithmus ist, dass Sie nur mit ihm eine polylogarithmischen (NC1) Schaltung ausführen können, die aus algorithmisch fast alles interessant regiert.

Plus es scheint nicht, dass die Komplexität der Codierung in irgendeiner Weise niedriger als die Komplexität der polylogarithmischen Schaltung selbst ausgeführt wird, so haben Sie keine freie Arbeit auf dem ersten Blick abgeholt, wenn Sie etwas tun, besonders heikel mit es.

Answer 8

Verteiltes Rechnen wie SETI @ Home, Proteinfaltung Projekte, etc., ist ziemlich beliebt, weil sie die Spende von CPU-Zeit und Strom aus Tausenden von Anwendern nutzen. Noch interessanter wäre ein Modell, wo die Menschen bezahlt werden können, diese Ressourcen für kommerzielle Projekte zur Verfügung zu stellen. Doch keine verantwortlichen Unternehmen wollen seine Daten aus, um Tausende von anonymen Computern zur Verarbeitung versenden. Wenn Sie effizient Algorithmen auf verschlüsselte Daten anwenden können, wird es möglich, die Verarbeitung zu jedermann ohne eine vertrauenswürdige Beziehung zu delegieren.

Answer 9

Elektronische Abstimmung ist in der Tat eine praktische Anwendung von homomorphe Verschlüsselung, dh http://heliosvoting.org/

Answer 10

Einige Bankanwendungen vielleicht schneller werden mit Hilfe von Homomorphe Verschlüsselung.

Sie können Operationen mit verschlüsselten Daten auf Cloud ausführen, anstatt es von Wolke zu lokalen nehmen und wieder auf Wolke setzen. Auch keine Notwendigkeit zu verschlüsseln-entschlüsseln-Operationen ausführen zu verschlüsseln Pipeline, Encrypt-Operationen ausführen OK wären.