شفٹ نیٹ ورکس || ریاضی ∩ پروگرامنگ

ہومومورفک خفیہ کاری کے اپنے حالیہ جائزہ میں ، میں نے ریاضی (سم ڈی اسٹائل) ہومومورفک خفیہ کاری اسکیموں کے ساتھ کام کرتے وقت ڈیٹا کی ترتیب کی اہمیت کو کم سمجھا۔ ایف ایچ ای دنیا میں ، ڈیٹا لے آؤٹ کی حکمت عملیوں کو دیئے گئے نام کو “پیکنگ” کہا جاتا ہے ، کیونکہ یہ ایک سے زیادہ سادہ ڈیٹا کو RLWE Ciphertexts میں احتیاط سے منتخب کردہ طریقوں سے گھومتا ہے جو آپ ان کارروائیوں کے ساتھ اچھی طرح سے میش کرتے ہیں جو آپ انجام دینا چاہتے ہیں۔ “میش ویل” کے ذریعہ میرا مطلب ہے کہ اس سے اضافی ضرب اور گردشوں کی تعداد کم ہوجاتی ہے جس کی ضرورت صرف اعداد و شمار کے عناصر کو صحیح طریقے سے سیدھ میں لانا ہے ، بجائے اس کے کہ آپ اصل حساب کتاب کریں۔ پیکنگ ایک اعلی درجے کا موضوع ہے ، لیکن یہ کارکردگی کے لئے اور ایف ایچ ای تحقیق کے جدید کنارے کے قریب ہے۔

اس موضوع میں تین طرح کے ذیلی مسائل ہیں:

• آپ کسی خاص آپریشن یا کسی پروگرام کے سبسیٹ کے لئے ایک اچھی پیکنگ کس طرح ڈیزائن کرتے ہیں؟ (شروعات کرنے والوں کے لئے یہ مضمون دیکھیں)
• ایک بار جب آپ پیکنگ کے قائم ہوجاتے ہیں تو آپ کس طرح تبدیل ہوجاتے ہیں؟ (یہ مضمون)
• جب اچھے پیکنگ ، سوئچنگ کی لاگت ، اور انجام دیئے گئے آپریشنوں کی پروفائل پر غور کرتے ہو تو ، آپ پورے پروگرام میں صحیح پیکنگ کے انتخاب کے لئے کس طرح مکمل طور پر بہتر بناتے ہیں؟

یہ مضمون دوسرے مسئلے کے بارے میں ہے: آپ پیکنگ کے مابین کیسے تبدیل ہوتے ہیں؟ اس مضمون میں تمام کوڈ گٹ ہب پر دستیاب ہے۔

(2025-10-01): 2024 سے ابتدائی نفاذ نے اجازت کے مطابق VOS-vos-erkinکن الگورتھم کے سب سیٹ کی حمایت کی۔ سر میں اوپر دیئے گئے کوڈ ریپوزٹری میں اب الگورتھم کا مکمل نفاذ ہے جو صوابدیدی نقشوں کی حمایت کرتا ہے۔ کوڈ کو دیکھنے کے لئے جیسا کہ یہ مضمون لکھا گیا تھا ، اس کمٹ میں ریپو دیکھیں۔

شروع کرنے کے لئے ، ہمیں کمپیوٹیشنل ماڈل کے لئے کسی حد تک انٹرفیس فراہم کرنے کی ضرورت ہے۔

کمپیوٹیشنل ماڈل

سم ڈی اسٹائل ایف ایچ ای کمپیوٹیشنل ماڈل کو مندرجہ ذیل کے طور پر آسانی سے خلاصہ کیا گیا ہے۔

• ڈیٹا ایک مقررہ لمبائی (جیسے ، 4096) اور فکسڈ بٹ پریسجن (جیسے ، 16 بٹس) کے ایک یا زیادہ ویکٹروں میں محفوظ کیا جاتا ہے۔ ویکٹر rlwe ciphertexts ہیں ، لیکن کمپیوٹیشنل ماڈل کا مطالعہ اس بات کی زیادہ پرواہ کیے بغیر کیا جاسکتا ہے کہ خفیہ کاری کس طرح کام کرتی ہے۔
• آپ ویکٹروں پر عنصر کے اضافے یا ضرب کا اطلاق کرسکتے ہیں۔
• آپ ایک جامد طور پر مشہور شفٹ کے ذریعہ ویکٹر کو چکرا کر گھوم سکتے ہیں۔
• ضرب بہت مہنگا ہے ، گردش کچھ مہنگا ہے ، اس کے علاوہ سستا ہے۔
• جبکہ ضرب مہنگا ہے ، متوازی ضربیں بہترین ہیں۔ دوسرے لفظوں میں ، جب ضرب ضروری ہے تو ، متوازی عنصر کے مطابق ضرب اوپس ڈیٹا پر منحصر سیریل ضرب (یعنی ، “کم ضرب گہرائی” کا مقصد) سے بہتر ہیں۔

اس کے ساتھ جانے کے ل I ، میں نے ایک سادہ ازگر آبجیکٹ کو نافذ کیا جو کمپیوٹیشنل ماڈل کی نمائندگی کرتا ہے۔ حقیقت پسندانہ طور پر کسی ایف ایچ ای اسکیم کو نافذ کرنے کے بجائے ، یہ صرف API کو اجازت دی گئی کارروائیوں تک محدود کرتا ہے۔ میرے پیکنگ اسٹریٹیجیز آرٹیکل سے قرض لینے سے ، فائل کمپیوٹیشنل_موڈل ڈاٹ پی وائی میں ایک کلاس موجود ہے جو API کو اجازت کی کارروائیوں تک محدود رکھتی ہے ، اور وضاحت کے لئے تھوڑا سا صحت سے متعلق حدود کو نظرانداز کرتی ہے۔

class Ciphertext:
    def __init__(self, data: list(int)):
        self.data = data(:)
        self.dim = len(data)

    def __add__(self, other: "Ciphertext") -> "Ciphertext":
        assert self.dim == other.dim
        return Ciphertext((self.data(i) + other.data(i) for i in range(len(self.data))))

    def __mul__(self, other) -> "Ciphertext":
        if isinstance(other, Ciphertext):
            assert self.dim == other.dim
            return Ciphertext((self.data(i) * other.data(i) for i in range(len(self.data))))
        elif isinstance(other, list):
            # Plaintext-ciphertext multiplication
            assert self.dim == len(other) and isinstance(other(0), int)
            return Ciphertext((x * y for (x, y) in zip(self.data, other)))
        elif isinstance(other, int):
            # Plaintext-ciphertext multiplication
            return Ciphertext((other * x for x in self.data))

    def rotate(self, n: int) -> "Ciphertext":
        n = n % self.dim
        return Ciphertext(self.data(-n:) + self.data(:-n))

    ... (other helpers) ...

تبادلوں کو پیک کرنے کے پیچھے لازمی مسئلہ یہ ہے کہ ایک بار جب کسی خفیہ کردہ سائفر ٹیکسٹ میں ڈیٹا بچھایا جاتا ہے تو ، آس پاس کے اعداد و شمار کو پیش کرنے کے لئے کوئی ابتدائی “شفل” آپریشن نہیں ہوتا ہے۔ لہذا اگر آپ عنصر کے اضافے یا ضرب کو کرنا چاہتے ہیں ، اور آپ کے آدانوں کو صحیح طریقے سے منسلک نہیں کیا جاتا ہے تو ، آپ کو ان کو سیدھ میں لانے کے لئے گردش ، ضرب اور اضافے کا استعمال کرنا ہوگا ، اور ان کارروائیوں میں غیر معمولی اخراجات ہیں۔

مسئلہ بیان

ایک عدد قیمت والے ویکٹر $ V $ کی لمبائی $ N $ ، اور S_N $ میں ایک نیا ویکٹر $ W $ کی تعمیر کریں $ W_I = V _ {\ سگما (i)} $ صرف مندرجہ ذیل آپریشنز کا استعمال کرتے ہوئے: ایک نیا ویکٹر $ W $ بنائیں:

• عنصر کے علاوہ
• مستقل ویکٹروں کے ذریعہ عنصر کی ضرب
• ایک مستقل شفٹ کے ذریعہ چکرو گردش

اور ایسا اس طرح کریں جس سے آپریشنز کے پیدا کردہ سرکٹ کی لاگت کے کچھ واضح فنکشن کو کم سے کم کیا جائے۔

شائی ہالیوی اور وکٹر شاپ کے ذریعہ ہیلب میں کاغذ الگورتھم میں ، وہ اس مسئلے کو کہتے ہیں سب سے سستا شفٹ نیٹ ورک مسئلہ اور قیاس آرائیاں مشکل ہے۔

مجھے اب بھی بالکل سمجھ نہیں آرہی ہے دائیں لاگت کا کام ہونا چاہئے۔ میرے ابتدائی اندازوں میں شامل ہیں:

• میرے خیال میں ضرب گہرائی کو کم سے کم کرنا (اگرچہ مستقل کے ذریعہ ضرب اتنا برا نہیں ہے جتنا کہ شور کی نشوونما کے لحاظ سے سائفر ٹیکسٹ-سیفر ٹکسسٹ ضرب ، میرے خیال میں)۔
• گردشوں کی کل تعداد کو کم سے کم کرنا۔
• استعمال شدہ الگ الگ گردش مستقل کی تعداد کو کم سے کم کرنا (جو اضافی کلیدی مواد سے مطابقت رکھتا ہے جو مؤکل کے ذریعہ تخلیق کرنا چاہئے اور سرور کے ذریعہ برقرار رکھنا چاہئے)۔
• صارف کے منتخب کردہ وزن کے ساتھ مذکورہ بالا کے کچھ لکیری فنکشن کو کم سے کم کرنا۔

بولی طریقہ

بولی طریقہ ، جو بہت سے معاملات میں میرے لئے اتنا برا نہیں لگتا ہے ، یہ ہے کہ عام گردشوں کے سیٹوں میں اس اجازت نامے کو تقسیم کیا جائے۔

یعنی ، ہر ایک کا نقشہ بنائیں \ i \ mapsto s_i = \ سگما (i) – i $ اس رقم کے طور پر آپ کو اس کی صحیح پوزیشن پر $ i $ th عنصر حاصل کرنے کے لئے گھومنے کی ضرورت ہے۔ دیئے گئے $ S_I of کی پیش کش ان تمام اشاریوں کا مجموعہ ہے جو ایک ہی گردش میں حصہ لے سکتے ہیں ، لہذا اسے اے کال کریں گردش گروپ.

اس کے بعد ، آپ ہر گردش گروپ کے اشاریوں پر “بٹ ماسک” لگانے کے لئے ضرب کے ذریعہ ضرب استعمال کرسکتے ہیں ، ہر گروپ کو اس کی شفٹ کی رقم سے گھوم سکتے ہیں ، اور پھر تمام نتائج کو ایک ساتھ شامل کرسکتے ہیں۔

کوڈ میں:

from collections import defaultdict
from computational_model import Ciphertext


def create_mask(indices: set(int), n: int) -> list(int):
    """Create a mask of length n with 1s at the indices specified."""
    return (1 if i in indices else 0 for i in range(n))


def mask_and_rotate(input: Ciphertext, permutation: dict(int, int)) -> Ciphertext:
    """Naively permutate the data entries in an FHE ciphertext."""
    # maps a shift to the indices that should be rotated by that amount
    rotation_groups = defaultdict(set)
    for i, sigma_i in permutation.items():
        rotation_groups(sigma_i - i).add(i)

    result = Ciphertext((0) * len(input))
    for shift, indices in rotation_groups.items():
        mask = create_mask(indices, len(input))
        result += (input * mask).rotate(shift)

    return result

بدترین صورت میں ، بولی نقطہ نظر میں ان پٹ ویکٹر کے سائز میں متعدد گردش گروپوں کے لکیری کی ضرورت پڑسکتی ہے۔ بدترین صورتحال میں سبوپٹیمیٹی قدرے واضح ہے: اس مثال کو کھانا پکانا آسان ہے جہاں ایک عنصر کو 3 ، دوسرا 2 ، اور تیسرا سے 1 کے ذریعہ منتقل کرنے کی ضرورت ہوتی ہے ، اور جس عنصر کو 3 کے ذریعہ منتقل کیا جاتا ہے وہ 1 اور 2 کے لئے گردش کے گروپوں پر واپس گلگ کر سکتا ہے۔

ایسا لگتا ہے کہ 2 کی طاقتوں کے ذریعہ گردشوں کو دوبارہ استعمال کرکے گردشوں کو بڑھانے کا طریقہ کار ہونا چاہئے۔ کچھ لاگت کے ماڈلز کے ل this ، یہ بہت اچھا ہوگا کیونکہ اس سے گردش گروپوں کی تعداد (لکیری کے لاجارتھمک) میں کفایت شعاری میں کمی کے ل the شفٹ نیٹ ورک کی گہرائی میں تھوڑا سا اضافہ ہوگا۔

ہیلب میں کاغذ الگورتھم بینز نیٹ ورکس نامی ایک تکنیک کا استعمال کرتے ہوئے کرتے ہیں۔ میں ابتدا میں خود اس پر عمل درآمد کرنا چاہتا تھا ، لیکن مجھے وضاحتیں بجائے الجھن میں مل گئیں اور اس کو سمجھنے کے کوڑے کو ختم نہیں کیا۔ ایسا بھی لگتا تھا کہ ان کا نفاذ کسی حد تک لکیری تھا۔ ہر گردش صرف دوبارہ قابل استعمال گردشوں کے بڑے نیٹ ورک کی تعمیر کے بجائے پچھلی گردش پر منحصر ہوتی ہے۔ لہذا اس کے بجائے ، مجھے ایک حالیہ مقالہ ملا جس میں اس میں بہتری لانے کا دعوی کیا گیا ہے ، اور میں نے اس پر عمل درآمد کیا۔

VOS-vos-rekin کا ​​گراف رنگین نقطہ نظر

جیل ووس ، ڈینیئل ووس ، اور زیکیریا ایرکین کے ذریعہ ، سطح والے ہومومورفک سیفرٹیکسٹس میں بھرے ہوئے اقدار کو اجازت دینے اور ان کی نقشہ سازی کے لئے کاغذ کے موثر سرکٹس ، مطلوبہ گھومنے کی بائنری نمائندگی کے مطابق دو کی طاقتوں کے ذریعہ ہر مطلوبہ گردش کو گھومنے کی ترکیب میں تقسیم کرکے ایک طریقہ کی وضاحت کرتے ہیں۔ یعنی ، $ 5 = 101_2 by کی گردش 1 اور پھر 4 کی طرف سے گردش ہے۔ تمام انڈیکس جن کو کم سے کم اہم بٹ سیٹ کیا جاتا ہے وہ ایک ہی وقت میں 1 کے ذریعہ گھمایا جاتا ہے ، اور اسی طرح گھومنے کے لئے 2 ، 4 ، 8 ، وغیرہ۔

تاہم ، یہ نقطہ نظر اس وقت ٹوٹ جاتا ہے جب دو عناصر کو ایک ہی انٹرمیڈیٹ پوزیشن میں گھمایا جائے گا۔ مثال کے طور پر ، آپ انڈیکس 3 کے ذریعہ 5 پوزیشنوں کو انڈیکس 8 پر گھوم سکتے ہیں ، پہلے اسے 1 سے پوزیشن 4 سے گھومتے ہیں ، پھر 4 سے پوزیشن 8 سے گھومتے ہیں۔ چونکہ ، بولی طریقہ کار کی طرح ، نقاب پوش اور گھومنے والے ویکٹر ایک ساتھ شامل کردیئے جاتے ہیں (غیر استعمال شدہ پوزیشنوں میں متوقع زیرو کے ساتھ) ، اس کے نتیجے میں دو عناصر کو غلط طریقے سے ایک ساتھ شامل کیا جائے گا۔

کاغذ اس مسئلے کو حل کرنے کے دو طریقوں کی نشاندہی کرتا ہے۔ سب سے پہلے ، آپ تصادم سے بچنے کے لئے پاور آف دو گردشوں کا ایک مختلف ترتیب منتخب کرسکتے ہیں۔ مذکورہ بالا مثال میں ، پہلے 4 سے گھومنا ، یا پہلے 8 تک ، تصادم سے بچ جائے گا۔ تاہم ، اس سے دوسرے تنازعات کو متعارف کرایا جاسکتا ہے ، اور کچھ تنازعات ناگزیر ہوسکتے ہیں۔ لہذا دوسرا خیال یہ ہے کہ تصادم سے بچنے کے لئے گردشوں کے الگ الگ سیٹ بنائیں۔ مذکورہ بالا مثال میں ، آپ دونوں اشاریوں کو ایک ہی گردش میں گھمانے کی کوشش کرنے کے بجائے 4 کے ذریعہ دو مختلف گردشیں رکھتے ہوں گے۔

تصادم میں قدرتی گراف رنگنے کا مسئلہ شامل ہے۔ آپ جس پاور آف دو گردشوں کو انجام دینے کا ارادہ رکھتے ہیں اس کا آرڈر طے کریں۔ ایک گراف $ G_ \ سگما کی وضاحت کریں جس کے عمودی ان پٹ ویکٹر کے اشارے ہیں ، اور جن کے کنارے انڈیکس کے جوڑے ہیں جو اوپر دیئے گئے الگورتھم کے مطابق سڑنے اور گھومتے وقت اجازت نامے کے لئے ٹکراؤ کرتے ہیں۔

اس کے بعد آپ گراف کو کم سے کم رنگوں سے رنگ دیتے ہیں۔ ہر رنگ پاور آف دو گردشوں کے ایک مکمل سیٹ سے مطابقت رکھتا ہے ، اور رنگ کے لئے تفویض کردہ اشارے $ C $ تمام ایک ہی گردش گروپوں میں پاور آف دو گردشوں کے اسی سیٹ کے لئے حصہ لیتے ہیں۔

کوڈ میں ، عمل درآمد میں مندرجہ بالا اعداد و شمار میں ٹیبل کے عمومی ورژن کی تشکیل نو شامل ہے ،

import itertools
from dataclasses import dataclass
import networkx as nx


@dataclass(frozen=True)
class RotationGroup:
    """A group of input vector indices that can safely be decomposed into
       power-of-two shifts and rotated without conflicts."""
    indices: frozenset(int)


def vos_vos_erkin(n: int, permutation: dict(int, int)) -> list(RotationGroup):
    """Partition the input indices into groups that can be safely decomposed
       and rotated together."""
    assert set(permutation.keys()) == set(range(n))

    shifts = ((permutation(i) - i) % n for i in range(n))
    format_string = f"{{:0{n.bit_length() - 1}b}}"

    # LSB-to-MSB ordering of bits of each shift
    shift_bits = (
        (int(b) for b in reversed(format_string.format(shift))) for shift in shifts
    )

    # Here we compute the coresponding table of values after each rotation,
    # used to identify conflicts that would occur if the rotations were
    # performed naively.
    rounds = ()
    for i in range(n.bit_length() - 1):
        rotation_amount = 1 << i
        last_round = rounds(-1) if rounds else {x: x for x in range(n)}
        rounds.append(
            {
                x: (last_round(x) + rotation_amount if bits(i) == 1 else x)
                for (x, bits) in zip(range(n), shift_bits)
            }
        )

    # Any two keys with colliding values in a round require an edge in G.
    G = nx.Graph()
    for round in rounds:
        for x, y in itertools.combinations(round.keys(), 2):
            if round(x) == round(y):
                G.add_edge(x, y)

    coloring = nx.coloring.greedy_color(G, strategy="saturation_largest_first")

    indices_by_color = (() for _ in range(1 + max(coloring.values())))
    for index, color in coloring.items():
        indices_by_color(color).append(index)

    return (
        RotationGroup(indices=frozenset(group)) for group in indices_by_color
    )

ہم گراف رنگنے کی گنتی کے لئے نیٹ ورک ایکس کا استعمال کرتے ہیں ، جس میں ایک لالچی ہورسٹک استعمال ہوتا ہے جس کا نام Dsator نامی ہے جو “سنترپتی کی ڈگری” کے ذریعہ ویکٹیس کا حکم دیتا ہے۔ یہ طریقہ خاص طور پر اہم نہیں ہے ، اور کوئی بھی مہذب رنگین الگورتھم کرے گا۔

نوٹ مذکورہ بالا کوڈ رنگین گراف کو گردشوں کے سرکٹ میں تبدیل نہیں کرتا ہے ، یہ صرف ایک اچھی تقسیم کی نشاندہی کرتا ہے ، اور پھر ہر تقسیم کو دو کی طاقتوں میں گھٹا دیا جائے گا ، اور mask_and_rotate بولی طریقہ کار سے فنکشن استعمال کیا جاسکتا ہے جس کی بنیاد پر بٹس مرتب کی گئی ہیں۔

VOS-vos-erkin پر اضافی نوٹ

اس کاغذ میں کچھ اضافی ہورسٹکس اور نوٹ تھے کہ ان کے طریقہ کار کو بہتر بنانے کے لئے کیا کیا جاسکتا ہے۔

• ایک مختلف ہندسوں کی بنیاد (جیسے ، بیس 3) کا استعمال کریں جب اس سے گردشوں یا تصادم کی تعداد کو کم کرنے میں مدد ملتی ہے ، ورنہ بیس کے دستیاب طاقتوں کا صرف ایک ذیلی سیٹ استعمال کریں۔
• تصادم کی تعداد کو کم کرنے کی کوشش کرنے کے لئے تصادفی طور پر گردشوں کے آرڈر کا دوبارہ آرڈر کریں۔ یہ کچھ بار کریں اور بہترین نتیجہ لیں۔

سب سے سستا شفٹ نیٹ ورک کے مسئلے کے ل other دوسرے طریقوں پر چڑھنا

سب سے سستے شفٹ نیٹ ورک کے مسئلے کے بارے میں ایک اچھی بات یہ ہے کہ میں اپنے ایف ایچ ای مرتب ، وارث میں حل نافذ کرنا چاہتا ہوں۔ اور چونکہ ایف ایچ ای پروگرام نسبتا small چھوٹے ہیں ، اور کئی بار چلانے سے پہلے صرف ایک بار مرتب کرنے کی ضرورت ہے ، لہذا بہتر پروگراموں کو حاصل کرنے کے ل slow آہستہ تالیف وقت کے لئے رواداری روایتی مرتب کرنے والے سے کہیں زیادہ ہے۔

لہذا جب یہ مسئلہ کچھ اچھے ہورسٹک حلوں کے طور پر ہے ، مجھے دلچسپی ہوگی کہ کچھ اور ہیوی ویٹ کی کوشش کروں۔ میں نے انٹیجر لکیری پروگرام (ILP) اور contraint پروگرامنگ (CP-SAT) فارمولیشنوں کے ساتھ گھوما ، لیکن مجھے بہت دور نہیں ملا۔ مشکل کی بات یہ ہے کہ یہ اس معنی میں سرکٹ ترکیب کی طرح محسوس ہوتا ہے کہ نیٹ ورک کا ڈھانچہ پہلے سے طے نہیں ہوتا ہے ، جس کی وجہ سے ILP کی حیثیت سے انکوڈ کرنا مشکل ہوجاتا ہے۔ اس مسئلے کا ویکٹرائزیشن پہلو بھی ایسا لگتا ہے کہ ایسا لگتا ہے کہ اس کے علاوہ اور بھی بہت زیادہ ادب نہیں ہے جس کا مجھے پتہ چلتا ہے کہ براہ راست لاگو ہوتا ہے۔ مثال کے طور پر ، ویکٹرائزنگ پروگراموں میں زیادہ تر لٹریچر لوپ کو چھوٹی لمبائی کے ویکٹرائزڈ آپریشنوں میں تبدیل کرنے کے بارے میں ہے ، جبکہ ہمارے پاس بنیادی طور پر ایک سیدھے لکیر کا پروگرام ہے جس میں بڑے ویکٹر سائز (طول و عرض 4096-65536) اور ایک بہت ہی محدود کام ہے۔

میں سرکٹ ترکیب کے ل use لوگ استعمال کرنے والے اصل طریقوں سے اتنا واقف نہیں ہوں ، لہذا میں آپ سے سننا پسند کروں گا اگر آپ کو لگتا ہے کہ آپ کو کوئی ہتھوڑا مل گیا ہے جو اس کیل کو فٹ بیٹھتا ہے۔ یا اگر آپ کو کسی بھی این پی کے مکمل مسائل کے بارے میں معلوم ہے جیسے ایسا لگتا ہے ، تو شاید ہم یہ ثابت کرسکتے ہیں کہ یہ مشکل ہے ، حالانکہ اس سے میری اور میرے مرتب ساتھیوں کی مدد نہیں ہوگی۔