بروتوكولات Sigma وتحديد هوية Schnorr

يتكون بروتوكول سيغما من 3 رسائل: (1) الالتزام: يرسل المُثبِت التزامًا بقيمة عشوائية. (2) التحدي: يرسل المدقق تحديًا عشوائيًا. (3) الاستجابة: يرسل المُثبِت استجابة محسوبة من التحدي والسر. يقبل المدقق البرهان أو يرفضه.

يعرف المُثبِت السر x (المفتاح الخاص)؛ والمفتاح العام = g^x mod p (أو النقطة X = x*G على منحنى إهليلجي). الهدف هو إثبات معرفة x دون كشفه. وهذا برهان على معرفة اللوغاريتم المتقطع.

(1) يختار المُثبِت قيمة r عشوائية، ويرسل الالتزام R = r*G. (2) يرسل المدقق التحدي c (عددًا صحيحًا عشوائيًا). (3) يرسل المُثبِت الاستجابة s = r + c*x. (4) يتحقق المدقق من أن s*G == R + c*X. وإذا كان ذلك صحيحًا، يقبل. يعرف المُثبِت x؛ ولا يمكن حساب الاستجابة s إلا باستخدام x.

الاكتمال: يحقق المُثبِت الصادق دائمًا العلاقة s*G = r*G + c*x*G = R + c*X. المتانة: ينتج عن سجلَّي حوار لهما R نفسه، لكن بتحديين مختلفين c وc'، استجابتان s وs' يمكن من خلالهما استرجاع x = (s-s')/(c-c') — ولذلك لا يستطيع المحتال إنشاء استجابتين صحيحتين لـ R نفسه.

المُحاكي (من دون معرفة x): يختار s وc عشوائيًا، ويعيّن R = s*G - c*X. ويشكّل الثلاثي (R, c, s) توزيعًا صالحًا لسجل الحوار. لا يستطيع المدقق التمييز بين سجلات الحوار الحقيقية والمحاكاة — ولذلك يحقق Schnorr المعرفة الصفرية أمام مدقق صادق.

اجعل بروتوكول Schnorr غير تفاعلي: استبدل تحدي المدقق بـ c = Hash(R || message). يحسب المُثبِت c بنفسه ثم يرسل الاستجابة. والنتيجة برهان مكوّن من عنصرين (R, s) يمكن لأي شخص التحقق منه. وهذا هو نظام توقيعات Schnorr.

Sign(x, m): r ← random؛ R = r*G؛ c = Hash(R||m)؛ s = r + c*x. التوقيع = (R, s). Verify: s*G == R + Hash(R||m)*X. توقيع صغير الحجم (64 بايتًا لـ P-256)، ويمكن التحقق منه على دفعات، وآمن برهانيًا في ROM. اعتُمد في Taproot الخاص بـ Bitcoin ‏(BIP-340).

C = r*G + v*H حيث إن H مولّد مستقل ثانٍ. يلتزم بالقيمة v باستخدام العشوائية r. خاصية الإلزام: لا يمكن فتحه على قيمة v مختلفة (بسبب اللوغاريتم المتقطع). خاصية الإخفاء: C موزع توزيعًا منتظمًا. تُستخدم هذه الالتزامات في براهين النطاق المعتمدة على Schnorr وفي Bulletproofs.

إثبات معرفة x1 وx2 معًا: شغّل بروتوكولي Schnorr باستخدام التحدي نفسه (تشارك التحدي عبر Fiat-Shamir). لا يقبل المدقق إلا إذا كان كلا البرهانين الفرعيين صحيحًا. وهذا يتيح إثبات عبارات متعددة في تفاعل واحد.

إثبات معرفة x1 أو x2 دون كشف أيهما: استخدم المُحاكي لأحد الفرعين لحساب سجل حوار زائف، ثم قسّم التحدي بين الفرعين. يرى المدقق سجلَّي حوار يبدوان صحيحين ومجموع تحدييهما يساوي التحدي الحقيقي. وتُسمّى هذه «توقيعات حلقية».

هويات Schnorr: جوازات السفر الإلكترونية (بروتوكول PACE). توقيعات Schnorr: Bitcoin Taproot وMonero (يستخدم RingCT براهين OR من Schnorr) وSignal Protocol (اتفاق مفاتيح X3DH). التزامات Pedersen: المعاملات السرية، وBulletproofs، وتشفير ملاحظات Zcash Sapling.

بروتوكولات سيغما: التزام ثم تحدٍّ ثم استجابة. يثبت Schnorr معرفة لوغاريتم متقطع. يجعل Fiat-Shamir البروتوكول غير تفاعلي (توقيع Schnorr). التالي: zk-SNARKs لبراهين موجزة غير تفاعلية.