Büyük şifrelenmiş veriler üzerinde homomorfik işlemler uygulayın
Şu anda PALISADE kitaplığını kullanarak homomorfik şifreleme üzerinde deneyler yapıyor .
Büyük şifreli girişlere eklemeler ve çarpmalar gibi basit işlemleri uygulamak istiyorum. Örnek girişi için A[3200]ve giriş B[4096]hem vektörler / uluslararası değerlerinin dizileri şifrelenir olsun. Bu iki girişli Enc(A)ve Enc(B)ben bir çarpma uygulamak istiyorum:
EvalMult(Enc(A[0]), Enc(B[42]))
*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed
Benim ilgilendiğim kadarıyla, yukarıda açıklanan gerekliliklerin uygulanması iki farklı şekilde çözülebilir:
Girişleri tek bir şifreli metinde (SIMD benzeri) paketleyin ve operasyonlar
EvalIndexAt()için şifreli girişten doğru değeri elde etmek için kullanabilirim .A ve B'deki her değeri ayrı ayrı şifreleyin.
Verimlilik açısından açıklanan çözümlerden hangisinin en iyisi olacağından tam olarak emin değilim . İlk yaklaşım, tüm girdi için yalnızca bir şifreleme işleminin gerekli olması gibi büyük bir avantaja sahiptir, ancak bu, EvalAtIndex()yöntemi kullanarak her zaman doğru öğeye erişmek zorunda olmam ve girdiler ne kadar büyük olursa, elde edilenlerin hesaplanması o kadar yavaş EvalAtIndexKeyGen()olur. (En azından benim makinemde)
İkinci yaklaşım daha uygun görünmektedir çünkü EvalAtIndex()gerekli değildir, ancak her bir değeri ayrı ayrı şifreleme maliyeti ile birlikte gelir ve bu da oldukça zaman alır.
Herhangi bir fikir önerisi var mı?
Yanıtlar
Soru için teşekkür ederim
Yaklaşım # 1'in (SIMD) ana yararı, tek bir homomorfik toplama veya çarpma (çok verimli) kullanarak vektörlerin (4096 veya daha fazla tam sayı / gerçek sayı) toplama ve çarpma işlemlerini gerçekleştirebilmenizdir. Döndürme ( EvalAtIndexPALISADE'de denir ), tek tek endekslere erişim sağlayan veya verimli toplama (iç üründe olduğu gibi), matris çarpımı, vb. Sağlayan ekstra bir işlemdir. Bu yaklaşım aynı zamanda çok daha küçük bir şifreli metin genişletme faktörüne (4096x veya daha fazla) sahiptir. yaklaşım # 2. Pratikte genellikle 1. seçenek tercih edilir (ve 2. seçenekle gitmek isteyeceğim gerçek bir kullanım durumu düşünemiyorum).
Çarpma maliyetini en aza indirmek için, belki vektörü bitişik bloklar halinde paketleyebilirsiniz, böylece bir blok için tek bir dönüşe ihtiyacınız olur. Örneğin,
EvalMult(Enc(A[0:5]),Enc(B[42:47))
Kullanabileceğiniz başka bir teknik de EvalFastRotation(yalnızca PALISADE v1.10.x'te CKKS ve BGVrns için mevcuttur). Aynı şifreli metnin birden fazla dönüşüne ihtiyacınız varsa, şifreli metin için bir şeyi önceden hesaplayabilir ve ardından daha ucuz rotasyonlar kullanabilirsiniz (en fazla fayda BV anahtar geçişinden elde edilir) - bkz.https://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp örnek olarak.
Birden fazla dönüşe ihtiyaç duyuyorsanız (yalnızca gereken dönüş sayısının kabaca bir karekökünü hesaplayın), örneğin, şu bölümde açıklanan bebek adımı dev adım tekniğini kullanarak, üretilecek anahtar sayısını en aza indirmenin yolları da vardır. https://eprint.iacr.org/2018/244 (bu teknikler PALISADE tabanlı uygulamanızda uygulanabilir).
Çarpma işlemini gerçekleştirme modeli biliniyorsa, bir vektörü paketlemek için özel bir sıra da kullanabilirsiniz (bu şekilde, dönüşünüz tek bir döndürme işlemi kullanarak vektör boyunca birkaç blok hazırlayacaktır). # Düz metin yuvaları (toplu iş boyutu) ring dimension/ 2'ye eşit olduğunda, döndürmeler hem CKKS hem de BGVrns'de döngüseldir (etrafına sarılır). Bundan daha küçük bir vektörünüz varsa, küçük vektörü her zaman gerektiği kadar klonlayabilir / çoğaltabilirsiniz doldurmak için ring dimension/ 2.
Özetle, probleminizi SIMD benzeri vektörler açısından düşünürseniz en büyük verimlilik artışı elde edilebilir. Ardından, HE'nin sağladığı araç setinden tam olarak yararlanmak için probleminizi / modelinizi yeniden biçimlendirebilirsiniz. Bir bakıma, bu, vektörleştirilmiş komutlar, örneğin AVX veya matris yönelimli programlama (MATLAB'daki gibi) kullanarak programlamaya benzer.