“Beberapa rumah sakit riset ingin menggabungkan data sekuens genom pasien kanker mereka untuk menjalankan studi asosiasi genomik (GWAS), namun undang-undang privasi (GDPR / HIPAA) melarang keras keluarnya satu byte pun data mentah pasien dari rumah sakit.” “Bank-bank komersial yang saling bersaing ingin melacak jaringan pencucian uang lintas bank secara bersama-sama tanpa pernah mengungkap daftar nasabah atau grafik transaksi internal mereka satu sama lain.”

Sekilas, tuntutan ini tampak mustahil secara logika: untuk menghitung fungsi $f(x_1, x_2, \dots, x_n)$, bukankah harus ada Pihak Ketiga Tepercaya (Trusted Third Party, TTP) yang mengumpulkan seluruh input $x_i$ dalam bentuk teks biasa terlebih dahulu? Namun pada akhir 1980-an, kriptografi modern membuktikan teorema yang luar biasa: bahkan tanpa pihak ketiga tepercaya sama sekali, para peserta yang saling tidak percaya dapat menghitung fungsi apa pun $f(x_1, \dots, x_n)$ secara bersama-sama sehingga setiap pihak memperoleh hasil yang tepat tanpa mempelajari satu bit pun informasi tambahan mengenai input rahasia $x_i$ milik pihak lain.

Bidang ini disebut Komputasi Multi-Pihak Aman (Secure Multi-Party Computation, MPC). Dalam artikel ini, kita berangkat dari dua eksperimen pikiran klasik untuk menurunkan dua mesin matematika utama MPC: pembagian rahasia ambang batas $(t, n)$ Adi Shamir (interpolasi Lagrange, protokol BGW, dan tripel Beaver) serta pendekatan sirkuit Boolean melalui Oblivious Transfer ($\text{OT}_1^2$) Rabin dan Garbled Circuits Yao.

1. Dua Eksperimen Pikiran Paradoksal: “Rata-Rata Gaji Tanpa Bos” dan “Masalah Jutawan Yao”

1.1 Eksperimen Pikiran 1: Menghitung Rata-Rata Gaji Tanpa Mengungkap Gaji Individu

Tiga insinyur $A, B,$ dan $C$ ingin mengetahui rata-rata gaji tahunan mereka $\bar{x} = \frac{x_A + x_B + x_C}{3}$ tanpa seorang pun mengetahui gaji individu $x_A, x_B,$ atau $x_C$ milik rekan lainnya. Dengan pembagian rahasia aditif (masking One-Time Pad), mereka dapat melakukannya hanya dengan kertas dan pena:

1. Masker Acak dan Bisikan Pertama ($A \to B$): Ketiganya menyepakati modulus publik besar $M$ (misalnya $M = 10^9$). Insinyur $A$ memilih angka acak seragam $r \xleftarrow{\$} \mathbb{Z}_M$ secara rahasia, menambahkannya ke gajinya $x_A$, dan membisikkan hanya $s_1 = (x_A + r) \bmod M$ kepada $B$. Karena $r$ terdistribusi seragam di $\mathbb{Z}_M$, maka $s_1$ juga terdistribusi seragam sempurna berapa pun nilai $x_A$: menurut teorema Shannon tentang One-Time Pad, informasi bersama adalah $I(X_A; S_1) = 0$. $B$ mempelajari tepat nol bit tentang $x_A$.
2. Penjumlahan Berantai ($B \to C \to A$): $B$ menambahkan gajinya sendiri $x_B$ dan membisikkan $s_2 = (x_A + x_B + r) \bmod M$ kepada $C$; $C$ menambahkan $x_C$ dan menyerahkan $s_3 = (x_A + x_B + x_C + r) \bmod M$ kembali kepada $A$.
3. Pelepasan Masker: $A$ mengurangi angka acaknya $r$ modulo $M$, memperoleh total eksak $S = x_A + x_B + x_C$, dan mengumumkan rata-rata $\bar{x} = S / 3$.

[!NOTE] Mengapa Diperlukan Minimal 3 Peserta ($n \ge 3$)? Jika hanya ada dua orang ($A$ dan $B$), meskipun malaikat jujur memberi tahu mereka rata-rata $\bar{x} = \frac{x_A + x_B}{2}$, $A$ dapat langsung menghitung $x_B = 2\bar{x} - x_A$. Ini bukan kelemahan protokol, melainkan sifat matematis dari fungsi itu sendiri. MPC menjamin tidak ada bit tambahan yang bocor selain apa yang secara logis dapat disimpulkan dari input sendiri dan hasil akhir.

1.2 Eksperimen Pikiran 2: “Masalah Jutawan” Andrew Yao (1982)

Penjumlahan bersifat linear, tetapi bagaimana dengan perbandingan ukuran non-linear? Pada tahun 1982, ilmuwan komputer Andrew Chi-Chih Yao (peraih Turing Award) menerbitkan “Protocols for Secure Computations” dan mengajukan Masalah Jutawan (Millionaires’ Problem): dua jutawan, Alice (kekayaan $x$ juta dolar) dan Bob (kekayaan $y$ juta dolar), ingin menghitung hanya satu bit kebenaran $f(x, y) = [x > y] \in \{0, 1\}$ (siapa yang lebih kaya?) tanpa pihak ketiga dan tanpa mengungkap nilai $x, y$ maupun selisihnya $x - y$.

2. Formalisasi Keamanan MPC: Paradigma Simulasi Dunia Ideal/Nyata

Untuk membuktikan secara matematis tidak adanya kebocoran informasi, Goldreich, Micali, dan Wigderson (GMW 1987) merumuskan Paradigma Simulasi Dunia Ideal / Dunia Nyata (Ideal/Real Simulation Paradigm):

  flowchart TD
    subgraph IdealWorld["Dunia Ideal (Ideal World): Standar Emas Privasi Absolut"]
        direction TB
        PA1["Pihak P1 (Input Rahasia x1)"] -->|"Saluran Privat Aman"| TTP["Fungsionalitas Ideal Tak Terkorupsi F"]
        PA2["Pihak P2 (Input Rahasia x2)"] -->|"Saluran Privat Aman"| TTP
        PAn["Pihak Pn (Input Rahasia xn)"] -->|"Saluran Privat Aman"| TTP
        TTP -->|"Hanya mengembalikan y = f(x1,...,xn)"| Out1["Semua pihak hanya tahu output y (Nol kebocoran proses)"]
        Out1 --> Sim["Simulator S (Membuat transkrip palsu hanya dari input pihak korup & output y)"]
    end

    subgraph RealWorld["Dunia Nyata (Real World): Protokol Kriptografi Aktual Π"]
        direction TB
        RB1["Pihak P1 (Input Rahasia x1)"] <-->|"Ciphertext & Share Acak"| RB2["Pihak P2 (Input Rahasia x2)"]
        RB2 <-->|"Ciphertext & Share Acak"| RBn["Pihak Pn (Input Rahasia xn)"]
        RB1 <-->|"Ciphertext & Share Acak"| RBn
        RB2 --> View["Pandangan Lengkap View_A(x1,...,xn) yang Diamati Penyerang A"]
    end

    Sim <-->|"Distribusi Probabilitas Tak Terbedakan (View_A ≈ Sim)"| View

Dalam model musuh, dibedakan antara musuh semi-jujur (Semi-Honest / Passive) yang mematuhi aturan protokol tetapi menganalisis log pesan, dan musuh jahat (Malicious / Active) yang secara aktif memalsukan pesan.

3. Mesin 1: Pembagian Rahasia Ambang Batas $(t, n)$ Shamir, Interpolasi Lagrange, dan BGW / SPDZ

3.1 Polinomial di Atas Medan Hingga $\mathbb{F}_p$ dan Rekonstruksi Lagrange

Sebaliknya, dengan $t - 1$ bagian atau kurang, setiap kandidat rahasia $s' \in \mathbb{F}_p$ memiliki peluang yang sama persis ($H(S \mid \text{Shares}_{t-1}) = H(S)$, keamanan teoritis-informasi sempurna).

3.2 Protokol BGW dan Tripel Perkalian Beaver

4. Mesin 2: Oblivious Transfer ($\text{OT}_1^2$) Rabin dan Garbled Circuits Yao

Untuk perbandingan biner ($x > y$), pendekatan sirkuit Boolean menyelesaikan evaluasi hanya dalam jumlah putaran konstan $O(1)$:

  flowchart TD
    subgraph Step1["1. Alice (Garbler): Mengenkripsi Sirkuit Boolean"]
        W["Buat dua kunci AES 128-bit acak (k_i^0, k_i^1) untuk setiap kabel w_i"] --> G["Enkripsi ganda ke-4 baris tabel kebenaran gerbang: Enc(k_a^α, k_b^β, k_c^g(α,β))"]
        G --> P["Acak urutan ke-4 ciphertext pada setiap gerbang (Garbled Table)"]
    end

    subgraph Step2["2. Transfer Kunci melalui 1-out-of-2 Oblivious Transfer (OT_1^2)"]
        P -->|"Kirim Garbled Tables + kunci input aktif Alice k_a^x"| Eval["Bob (Evaluator)"]
        BobIn["Bit input rahasia Bob y ∈ {0,1}"] --> OT["1-out-of-2 Oblivious Transfer (OT_1^2)"]
        W -->|"Pasangan kunci kandidat (k_b^0, k_b^1)"| OT
        OT -->|"Bob HANYA menerima k_b^y (Alice tidak tahu nilai y)"| Eval
    end

    subgraph Step3["3. Bob (Evaluator): Evaluasi Buta Gerbang demi Gerbang"]
        Eval --> Dec["Dekripsi tepat 1 dari 4 baris per gerbang dengan (k_a^x, k_b^y) -> kunci output k_c^z"]
        Dec --> Out["Petakan kunci kabel output akhir ke hasil teks biasa z = f(x,y)"]
    end

Melalui 1-out-of-2 Oblivious Transfer ($\text{OT}_1^2$) Michael Rabin, Bob memperoleh kunci $k_b^y$ yang sesuai dengan bit rahasianya $y$ tanpa Alice mengetahui $y$. Tiga optimasi modern — Point-and-Permute (bit warna menunjuk langsung baris yang harus didekripsi), Free-XOR ($k_i^1 = k_i^0 \oplus \Delta$ membuat semua gerbang XOR bebas ciphertext dan bebas operasi AES), serta Half-Gates (memangkas setiap gerbang AND menjadi hanya 2 ciphertext) — mempercepat Garbled Circuits lebih dari $1000$ kali lipat.

5. Implementasi Lengkap Python: Shamir Secret Sharing & Tripel Beaver di Atas $\mathbb{F}_p$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import secrets
from typing import List, Tuple

PRIME = (1 << 61) - 1  # Bilangan prima Mersenne 61-bit p = 2^61 - 1

def mod_inv(a: int, p: int = PRIME) -> int:
    return pow(a % p, -1, p)

def shamir_share(secret: int, t: int, n: int, p: int = PRIME) -> List[Tuple[int, int]]:
    coeffs = [secret % p] + [secrets.randbelow(p) for _ in range(t - 1)]
    shares = []
    for i in range(1, n + 1):
        y = 0
        for c in reversed(coeffs):
            y = (y * i + c) % p
        shares.append((i, y))
    return shares

def lagrange_reconstruct(shares: List[Tuple[int, int]], p: int = PRIME) -> int:
    secret = 0
    k = len(shares)
    for i in range(k):
        xi, yi = shares[i]
        num, den = 1, 1
        for j in range(k):
            if i != j:
                xj, _ = shares[j]
                num = (num * (-xj)) % p
                den = (den * (xi - xj)) % p
        secret = (secret + yi * num * mod_inv(den, p)) % p
    return secret

def mpc_add(sa, sb, p=PRIME):
    return [(xa, (ya + yb) % p) for (xa, ya), (_, yb) in zip(sa, sb)]

def mpc_sub(sa, sb, p=PRIME):
    return [(xa, (ya - yb) % p) for (xa, ya), (_, yb) in zip(sa, sb)]

def mpc_scalar_mul(c, sa, p=PRIME):
    return [(xa, (c * ya) % p) for xa, ya in sa]

def mpc_add_const(c, sa, p=PRIME):
    return [(xa, (ya + c) % p) for xa, ya in sa]

def generate_beaver_triple(t: int, n: int, p: int = PRIME):
    u, v = secrets.randbelow(p), secrets.randbelow(p)
    return shamir_share(u, t, n, p), shamir_share(v, t, n, p), shamir_share((u * v) % p, t, n, p)

def mpc_beaver_mul(sx, sy, triple, t: int, p: int = PRIME):
    su, sv, sw = triple
    d = lagrange_reconstruct(mpc_sub(sx, su, p)[:t], p)
    e = lagrange_reconstruct(mpc_sub(sy, sv, p)[:t], p)
    res = mpc_add(mpc_add(sw, mpc_scalar_mul(d, sv, p), p), mpc_scalar_mul(e, su, p), p)
    return mpc_add_const((d * e) % p, res, p)

if __name__ == "__main__":
    t, n = 3, 5
    salaries = [85000, 92000, 78000]
    shared = [shamir_share(s, t, n) for s in salaries]
    total_shares = shared[0]
    for s in shared[1:]:
        total_shares = mpc_add(total_shares, s)
    print("Total gaji yang direkonstruksi:", lagrange_reconstruct(total_shares[:t]))

6. Perbandingan Teknologi Peningkatan Privasi (PETs) dan Aplikasi Industri

Mulai dari lelang ganda kuota bit gula Denmark tahun 2008 hingga studi kesenjangan upah Boston (BWWC), pemeriksaan kebocoran kata sandi di Google Chrome dan Apple iCloud (Private Set Intersection, PSI), studi genomik lintas rumah sakit (Secure GWAS), serta dompet kripto ambang batas MPC (Fireblocks, Coinbase), MPC kini menggantikan kepercayaan institusional dengan kepastian matematika.