Protokol Sigma & Identifikasi Schnorr

Protokol Sigma memiliki 3 pesan: (1) Komitmen: pembukti mengirimkan komitmen terhadap nilai acak. (2) Tantangan: pemeriksa mengirimkan tantangan acak. (3) Respons: pembukti mengirimkan respons yang dihitung dari tantangan dan rahasia. Pemeriksa menerima atau menolak.

Pembukti mengetahui rahasia x (kunci privat); kunci publik = g^x mod p (atau titik X = x*G pada kurva eliptik). Tujuannya adalah membuktikan pengetahuan tentang x tanpa mengungkapkannya. Ini adalah bukti pengetahuan logaritma diskret.

(1) Pembukti memilih r acak dan mengirimkan komitmen R = r*G. (2) Pemeriksa mengirimkan tantangan c (bilangan bulat acak). (3) Pembukti mengirimkan respons s = r + c*x. (4) Pemeriksa memeriksa s*G == R + c*X. Jika benar, pemeriksa menerima. Pembukti mengetahui x; respons s hanya dapat dihitung dengan x.

Kelengkapan: pembukti jujur selalu memenuhi s*G = r*G + c*x*G = R + c*X. Kekokohan: dua transkrip dengan R yang sama tetapi tantangan c dan c' yang berbeda menghasilkan s dan s', yang darinya x = (s-s')/(c-c') dapat dipulihkan — sehingga penipu tidak dapat menghasilkan dua respons valid untuk R yang sama.

Simulator (tanpa mengetahui x): pilih s dan c secara acak, tetapkan R = s*G - c*X. (R, c, s) ini memiliki distribusi transkrip yang valid. Pemeriksa tidak dapat membedakan transkrip nyata dari transkrip yang disimulasikan — Schnorr bersifat tanpa pengetahuan bagi pemeriksa jujur.

Jadikan Schnorr non-interaktif: ganti tantangan pemeriksa dengan c = Hash(R || message). Pembukti menghitung sendiri c dan mengirimkan respons. Hasilnya: bukti yang terdiri dari 2 elemen (R, s) yang dapat diverifikasi oleh siapa pun. Ini adalah skema tanda tangan Schnorr.

Sign(x, m): r ← acak; R = r*G; c = Hash(R||m); s = r + c*x. Tanda tangan = (R, s). Verifikasi: s*G == R + Hash(R||m)*X. Ringkas (64 byte untuk P-256), dapat diverifikasi secara batch, dan terbukti aman dalam ROM. Diadopsi dalam Taproot Bitcoin (BIP-340).

C = r*G + v*H, dengan H sebagai generator independen kedua. Komitmen ini menyatakan nilai v dengan keacakan r. Sifat mengikat: tidak dapat dibuka untuk v yang berbeda (logaritma diskret). Sifat penyembunyian: C terdistribusi secara seragam. Digunakan dalam bukti rentang berbasis Schnorr dan Bulletproofs.

Buktikan pengetahuan tentang x1 AND x2 secara bersamaan: jalankan dua protokol Schnorr dengan tantangan yang sama (bagikan tantangan melalui Fiat-Shamir). Pemeriksa menerima hanya jika kedua bukti turunan valid. Ini memungkinkan pembuktian beberapa pernyataan dalam satu interaksi.

Buktikan pengetahuan tentang x1 OR x2 tanpa mengungkapkan yang mana: gunakan simulator untuk satu cabang guna menghitung transkrip palsu, lalu bagi tantangan di antara keduanya. Pemeriksa melihat dua transkrip yang tampak valid dan jumlahnya sama dengan tantangan nyata. Ini disebut "tanda tangan cincin".

Identitas Schnorr: paspor elektronik (protokol PACE). Tanda tangan Schnorr: Taproot Bitcoin, Monero (RingCT menggunakan bukti-OR Schnorr), Protokol Signal (perjanjian kunci X3DH). Komitmen Pedersen: Transaksi Rahasia, Bulletproofs, enkripsi catatan Sapling Zcash.

Dalam protokol identifikasi Schnorr, apa yang diperiksa oleh pemeriksa pada langkah terakhir?

Protokol Sigma: komitmen–tantangan–respons. Schnorr membuktikan pengetahuan tentang logaritma diskret. Fiat-Shamir menjadikannya non-interaktif (tanda tangan Schnorr). Berikutnya: zk-SNARK untuk bukti non-interaktif ringkas.