Multi-Party Computation (MPC) là một khái niệm được các nhà mật mã học đắn đo nghiên cứu tận những thập niên 80 thế kỷ trước. Xuất phát tự nhiên từ những bài toán học búa trong cuộc sống phải đặt ra một giao thức hay ho hơn để đánh đố nhau. Ví dụ năm 1982 đó là bài toán triệu phú của anh Yao (1982 Andrew Yao  1), diễn Nôm đơn giản là anh Bin có số A tiền, còn anh Job có số B tiền. Hai anh trong một cuộc nhậu lỡ thách nhau xem ai có nhiều tiền hơn ai . Nhưng hai anh đều không muốn lộ ra tổng số tiền mình có cho nhau biết. Do đó mới nảy sinh bài toàn chứng minh bất đẳng thức A ≥ B mà không lộ thông tin nào của A và B cho bất cứ ai, kể cả 2 anh Bin và anh Jobs. Giải quyết xong bài toàn này đã mở ra một kỷ nguyên mới cho bảo mật thông tin đặc biệt là thương mai điện tử, data mining khi muốn so sánh các giá trị, tính toán cộng trừ nhân chia mà vẫn bảo vệ được thông tin mật như số tiền, tổng tiền trong tài khoản khách hàng, thông tin nhân khẩu học v.v.

1. MPC

Tổng quát hóa bài toán của Yao đó là: giả sử có n thành viên  bảo mật cho n giá trị tương ứng , và tất cả các thành viên thực hiện phép tính  sao cho các giá trị  được bảo mật hoàn toàn. Trong định nghĩa này, bài toán của Yao là trường hợp nhỏ với và phép tính 

Ví dụ thứ hai đó là trò chơi tình yêu, như các bạn đọc biết yeuchimse là một thanh niên ủy mị ướt át, sến rện hay nghĩ lung tung. Sẻ đệ lần đầu tiên không dám tỏ tình vì sợ người ấy không thích mình thì thật là quê độ nên đã yêu cầu chuymichxinhdep thiết kế một giao thức sao cho:

• Eligibility: được thổ lộ và chỉ thổ lộ môt lần.
• Privacy: đảm bảo không lộ thông tin đã thổ lộ cho bất kỳ ai biết, cho dù đó là người ấy hay chính chuymichxinhdep 
• Universal Verifiability: ai cũng có thể check được kết quả là 2 đứa nó có đến được với nhau hay không để đảm bảo tính công bằng của cuộc chơi tình ái.
• Robustness: Mọi hành động gian trá ví dụ như thổ lộ có yêu sau đó lại thay đổi ý kiến là không yêu đều bị cấm.

4 tiền đề trên các bạn đọc nào thông minh có thể áp dụng vào bầu cử điện tử, tuy nhiên giao thức chuymichxinhdep thiết kế dưới đây sau này được biết đến rộng rãi dưới cái tên  Five-Card Trick (Bert den Boer, Eurocrypt 1989) như sau:

Với 5 lá bài Át, mặc định một chiếc lá Át cơ đỏ đặt sẵn trên bàn. Với các câu trả lời giữa 2 người tham gia trò chơi là Yêu hoặc không Yêu tương ứng với 2 cách xếp bài Át cơ, Át bích. Sau khi đặt bài xuống bàn (có thể thay đổi chiều hàng 5 bài để không ai biết câu trả lời của mình ở bên nào) thì kết quả cả 2 người đều có cảm tình với nhau chỉ xảy ra khi có 3 quân Át cơ nằm cạnh nhau. Trường hợp kết quả 2 người không hợp nhau thì vẫn đảm bảo cô gái không biết được đối phương trả lời là Yêu hay không Yêu. (Thật là vi diệu phải không? )

Để giải thích cách giải này, thực chất đó chính là bảng AND toán tử ở bảng này:

Kết quả xy=1 thì rõ khi và chỉ khi x=1 và y=1. Còn với xy=0 thì ta chỉ kết luận có 1 trong x hoặc y trả lời 0 mà không thể khẳng định rõ ai trả lời 0 hay 1. Kết quả lần thực nghiệm protocol đó như các bạn đã biết, cuộc sống rất ồn ào, có những kẻ thất tình không biết trốn vào đâu để ngồi một mình và tìm sự tĩnh lặng cho riêng mình nên đành chơi CTF. “Em chưa lấy chồng là lỗi của anh!”. Với love game thì đen bạc còn đỏ tình nhưng yeuchimse đen thôi, đỏ vẫn vậy. 

2. OT

Để hóc búa hơn, người ta đã phát minh ra giao thức rất hay ho đó là Chuyển giao không lộ thông tin ( Oblivious Transfer ) đơn giản thế này:  Anh Mao giữ 2 giá trị  là bít tức là chỉ có 0 hoặc 1, chị MaiAnh giữ một giá trị secret s, tất nhiên, cũng chỉ là bít 01. Chị chọn một số u ngẫu nhiên khá to trong tập nguyên Z và chị tính với . Do s là bit nên lúc này chị có 2 giá trị , chị gửi cả 2 giá trị này lại cho Mao với mục đích làm Mao không biết giá trị u, s là gì, kể cả giá trị ở đây là generator chung mà cả 2 đều biết, thì theo bạn ElGamal đối với máy tính cổ lỗ của Mao là con MBP 15 inch đời giữa 2015, tới lúc bốc mộ cũng không giải ra được u (à mà với điều kiện là chị MaiAnh có u rất to nhé). Sau bước này thì Mao chọn 2 giá trị cũng ngẫu nhiên trong tập nguyên để tính một phương trình phức tạp hơn đó là:

Rồi Mao chuyển lại cặp để cho MaiAnh tính ra . Như vậy, Mao không để lộ cả 2 giá trị , trong khi MaiAnh không để lộ mà vẫn lấy được về. Mao cũng không biết được MaiAnh đã lấy số nào về mà chỉ biết MaiAnh đã lấy được 1 số. Tóm tắt lại trong hình như sau:

Câu hỏi đặt ra OT sẽ được áp dụng như thế nào, ví dụ anh Mích đang làm hệ thống e-Health sức khỏe y tế điện tử. Vì anh là bên thứ 3 làm tin học nên tất nhiên anh không được ông quan thanh liêm nào cho tiếp cận vào hồ sơ y tế của bệnh nhân. Do đó anh quyết định ký hợp đồng với bệnh viện sử dụng OT để làm API truy cập thông tin. Lúc này anh làm demo nên cơ sở dữ liệu mới có thông tin HIV của 2 bệnh nhân lưu dưới dạng dương tính (1) và âm tính (0). Áp dụng OTP anh Mích đã có thể biết trạng thái HIV của 1 trong 2 bệnh nhân mà bệnh viên không biết anh đã query bệnh nhân nào.

3.ZKP

Bệnh cạnh việc dùng OT để chia sẻ không lộ thông tin, người ta còn nghĩ ra nhiều trò phức tạp khác dưới cái tên ZKP (Zero Knowledge Proof) điển hình là bài toán lên bar của chụy Mích được trình bày như sau: Trong một lần trên bar hơi muộn vào khoảng 2 giờ sáng thì các anh pokemon ập vào đòi kiểm tra hành chính với lý do trên 18 tuổi mới được ngồi bar hút thuốc bú diệu như một số hoa hậu nào đó. Vốn là một người tôn trọng quyền con người chụy không muốn ai phán xét vì hút thuốc lá là quyền tự do của mỗi người. Chụy chân thành chúc mừng bạn chụy nếu em bỏ được thuốc, còn không em cũng đừng buồn vì sau một thời gian nghỉ, điếu thuốc sắp tới em hút đảm bảo nó sẽ ngon không bút nào tả xiết. Ngoài ra lại vốn là một người tôn trọng quyền con người chụy cũng không muốn để lộ liễu ngày sinh nhật của mình giữa chốn đông người. Thay vì trình ID CMND hay bằng lái chụy đã show thẻ ngân hàng của mình để quẹt bill cho các anh xem. Với luật trên 18 tuổi mới được làm credit card nên mặc nhiên chụy đã chứng minh mình đã trên 18 tuổi mà không để lộ ngày sinh của mình .

Một ví dụ ZKP thứ 2 đó là ví dụ hang động của AliBaBa:

Nhi tuyên bố rằng cô biết mật mã để mở cửa hang. Líp hỏi cô phải chứng minh tuyên bố của mình. Nhưng Nhi không thể nói mật khẩu cho Líp vì như vậy thật là lộ liễu . Do đó chụy Mích đã chỉ cho Nhi một cách như sau:

• Líp đứng quay mặt tụt quần ở một khoảng cách khá xa và chờ Nhi bước vào hang.
  Sau đó, Líp đến cửa hang rõ ràng anh ta không biết Nhi đã đi sang bên nào.
• Líp tùy ý hét lên yêu cầu Nhi bước ra từ bên trái hoặc bên phải.
• Hai đứa lặp lại trò chơi này cho đến khi Líp bị thuyết phục hoặc Nhi chán không chơi nữa.

Rõ ràng nếu Nhi đã ở phía bên trái và Líp yêu cầu cô ấy đến từ bên trái thì quả này Nhi đã may mắn . Nếu không, Nhi chỉ có thể đến từ bên trái nếu cô ấy biết mật mã để mở cửa hang phải không nào (!?).

4.Hệ mật đồng cấu( Homomorphic cryptosystem)

Để tiếp tục là cuộc chơi thêm phần phức tạp, các nhà mật mã học lại tiếp tục nghĩ ra Hệ mật đồng cấu được định nghĩa:

Hệ mã hoá Elgamal có tính chất đồng cấu, nhờ nó có thể tính được kết quả trong cuộc bỏ phiếu “chọn một trong hai”, mà không cần giải mã từng lá phiếu. Sơ đồ chia sẻ bí mật Shamir phối hợp với hệ mã hoá Elgamal còn có tính chất đặc biệt hơn nữa, nhờ nó có thể chia lá phiếu thành nhiều mảnh, cử tri gửi mỗi mảnh cho một thành viên ban kiểm phiếu, khi khớp các mảnh phiếu lại sẽ được nội dung đầy đủ của lá phiếu. Bài báo này trình bày các tính chất trên và chỉ ra ứng dụng của chúng trong bỏ phiếu từ xa.Hệ mã hoá Elgamal có tính chất đồng cấu, nhờ nó có thể tính được kết quả trong cuộc bỏ phiếu “chọn một trong hai”, mà không cần giải mã từng lá phiếu. Sơ đồ chia sẻ bí mật Shamir phối hợp với hệ mã hoá Elgamal còn có tính chất đặc biệt hơn nữa, nhờ nó có thể chia lá phiếu thành nhiều mảnh, cử tri gửi mỗi mảnh cho một thành viên ban kiểm phiếu, khi khớp các mảnh phiếu lại sẽ được nội dung đầy đủ của lá phiếu. (ref2 Trịnh Nhật Tiến, Đặng Thu Hiền, Trương Thị Thu Hiền, Lương Việt Nguyên)

Để rõ thêm về vấn đề này, bạn đọc có thể xem lại bài Introduction to Threshold signature scheme. Lưu ý Elgamal có tính chất đồng cấu còn RSA thì không nhé . Ở khuôn khổ bài viết này chỉ trình bày thêm về hệ mã Paillier công bố năm 1999 như sau:

Giả sử n = pq và g là một phần tử đặc biết của nhóm cyclic Z dựa theo lũy thừa n sao cho . Khóa bí mật , khóa công khai (g, n). Với plaintext là thông điệp và một số r nguyên dương ngẫu nhiên thì hàm mã hóa được định nghĩa:

Lưu ý lcm = least common multiple ước chung nhỏ nhất. Và người ta thường chọn g=n+1 để thỏa mãn tính chất generator như sau:

Còn quá trình giải mã thì phức tạp hơn chút, đó là:

Vậy tại sao có RSA phổ cập nông thôn đã chất chơi người dơi rồi, các nhà mật mã học lại phải nghĩ ra hệ mật oái ăm này . Ấy là vì ở đây ta có random r, mỗi lần mã hóa lại có ciphertext khác nhau. Ngoài ra với mỗi ciphertext nếu không biết random r thì lại ra vô số message m thỏa khác nhau. Ngoài ra với tính chất đồng cấu giúp cho phép cộng (+) và lũy thừa (^) ta có thể thiết kế các giao thức mã hóa gửi đi ciphertext để một bên thứ ba tính toán, bên tính toán này chỉ trả về kết quả phép tính mà không biết giá trị mà bên cần tính đưa ra là gì 

Ví dụ giao thức đơn giản Alice có publickey (để mã hóa) và 2 số tiền của 2 orders mà Bob đặt hàng đã được mã hóa [a], [b]. Alice không thể giải mã để biết a, b nhưng lại muốn tính tổng tiền [a+b]. Bob ở đây có secretkey có khả năng giải mã để tính phép cộng cho Alice nhưng hệ thông không muốn Bob biết Alice đang muốn tính gì.

Alice bằng việc sử dụng random khiến cho Bob không biết đường nào mà lần, dù anh có giải mã ra a mũ và b ngã thì vẫn không đoán được a,b là gì. Tuy nhiên cũng xin lưu ý ở đây rằng, để đảm bảo giao thức hoạt động ngon thì random cần có một độ dài k bits cần thiết nhé. Lúc implement bị hack thì đừng đổ cho chụy không nói trước .

5. Ví dụ ứng dụng

Phần này với bạn đọc nào hiểu rõ học thuật rồi có thể skip sang luôn phần like subcribe comment và share trên phây búc. Dưới đây chỉ là bài toán ví dụ đơn giản trẻ con sử dụng Pailler để bảo vệ các thông tin như: tuổi, thu nhập bằng Python.

Đầu tiên, giả sử tôi có một hệ cơ sở dữ liệu cần mã hóa Paillier với 3 cột: Tên, tuổi, thu nhập. Tôi xin ăn cắp thư viện Pure Python Paillier Homomorphic Cryptosystem (3) để mã hóa dưới đây:

from paillier.paillier import *
from timer import Timer
import random,string

def encrypt_db():
	print "Encrypting...."
	for p in session.query(Person):
		p.age = str(encrypt(pub, int(p.age)))
		p.income = str(encrypt(pub, int(p.income)))
		p.name = str(int(p.name.encode("hex"),16))
	session.commit()

def decrypt_db():
	print "Decrypting...."
	for p in session.query(Person):
		print decrypt(priv, pub, int(p.age)) ,decrypt(priv, pub, int(p.income)) , hex(decrypt(priv, pub, int(p.name ))).replace("0x","").replace("L","")

print "Generating keypair..."
priv, pub =  generate_keypair(2048)

Với quyền query lên database toàn bộ bị mã hóa, tôi có 2 bài toán cần giải quyết đó là:

• Nhập lên một số x, yêu cầu trả lời câu hỏi có bao nhiêu người có độ tuổi lớn hơn x mà không làm lộ số x đang được hỏi.
• Tính tổng thu nhập của tất cả những người có độ tuổi lớn hơn x mà không làm lộ thông tin thu nhập của từng người.

Đề giải quyết 2 bài toán trên, tôi tham khảo giao thức tính toán không làm lộ dữ liệu được cải tiến của Zerkin (4) bạn tôi như sau:

Hàm gửi lên để lấy kết quả ta chỉ cần quan tâm tới hàm A(pub, enc_a, enc_b). Ở đây được code như sau (code bừa hơi dài đề nghị không gạch đá ):

from paillier.paillier import *
import random,string

l=17
def A(pub, enc_a, enc_b):
	enc_z = e_add(pub, e_add(pub, enc_a, encrypt(pub, 2**l)), invmod(enc_b,pub.n_sq))
	r = random.randrange(2**(80+l+1))

	r_bin = bin(r).replace("0b","").replace("L","")
	r_bin = "0"* (l-len(r_bin))+r_bin
	r_bin = r_bin[::-1]
	enc_r = encrypt(pub, r)
	enc_d = e_add(pub, enc_z , enc_r)
	enc_d1, enc_d2 , enc_t = B1(enc_d)
	s = [-1,1][random.randint(0,1)]

	h = [0]*l
	v = [0]*l
	enc_c = [0]*l
	enc_e = [0]*l
	for i in range(l):
		while True:
			h[i] = random.getrandbits(long(round(math.log(pub.n, 2))))
			if h[i] > 0 and h[i] < pub.n and gcd(h[i], pub.n) == 1:
				break

	for i in range(l):
		v[i] = s - int(r_bin[i])
		for j in range(i+1,l):
			v[i] -= (2**j) * int(r_bin[j])
		if v[i] < 0: 
			v[i] = pub.n + v[i]
		enc_c[i] = e_add(pub, encrypt(pub, v[i]), enc_t[i])
		enc_e[i] = pow (enc_c[i], h[i],pub.n_sq)

	enc_lamda = B2(enc_e)
	if s != 1:
		enc_lamda = e_add(pub, encrypt(pub,1), invmod(enc_lamda,pub.n_sq))
	enc_zl = e_add(pub, e_add(pub, enc_d2, invmod(encrypt(pub,(r / 2**l)),pub.n_sq)), invmod(enc_lamda,pub.n_sq))
	return B3(enc_zl)

def B1(enc_d):
	d= decrypt(priv, pub, enc_d)
	d1 = d%(2**l)
	d2 = d/(2**l)
	d_bin = bin(d1).replace("0b","").replace("L","")
	d_bin = "0"* (l-len(d_bin))+d_bin
	d_bin = d_bin[::-1]
	t = [int(0)]*l
	for i in range(l):
		t[i] = int(d_bin[i])
		for j in range(i+1,l):
			t[i] += (2**j) * int(d_bin[j])
		t[i] = encrypt(pub, t[i])
	return encrypt(pub,d1) , encrypt(pub,d2),t
def B2(enc_e):
	e = [int(0)]*l
	for i in range(l):
		e[i] = decrypt(priv, pub, enc_e[i])
		if e[i] ==0: return encrypt(pub,1)
	return encrypt(pub,0)


def B3(enc_zl):
	return decrypt(priv,pub, enc_zl)

Vậy với bài toán 1, để biết bao người có số tuổi từ x đổ lên ta chỉ cần query bằng hàm A():

index = [-1]*len(income)	
for i in range(len(age)):
	enc_x = encrypt(pub, x)
	if int(A(pub, age[i],  enc_x))>0:
		index[number] = i
		number+=1

Với bài toán 2, để thêm phần bảo mật ta nhét thêm một số random r thật dài vào mỗi lần query như sau:

	r = random.randrange(2**(80+32))
	for i in index:
		if i>-1:
			totalincome = e_add(pub, totalincome, income[i])
	totalincome = e_add(pub, totalincome, encrypt(pub,r))
	totalincome = decrypt(priv,pub,totalincome) - r

Thật là đơn giản phải không , nếu bạn vẫn chưa hiểu, xin đừng liên hệ tôi vì tôi sẽ không giải thích đâu. Xin mời bạn đọc phần appendix nhé.

1. "Protocols for secure computations". FOCS. 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982): 160–164.doi:10.1109/SFCS.1982.88
2. Mã hoá đồng cấu và ứng dụng http://tapchi.vnu.edu.vn/tckh/news/?1887/635/Ma-hoa-dong-cau-va-ung-dung.htm
3. https://github.com/mikeivanov/paillier
4. Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, R. L. Lagendijk and T. Toft, Privacy- Preserving Face Recognition, 9th International Symposium on Privacy Enhancing Technologies, LNCS 5672, pp. 235-253, August 2009.

Appendix:

Ứng dụng hệ mã hóa đồng cấu trong nhận dạng hình ảnh tội phạm (vẫn đảm bảo quyền bảo vệ hệ thống hình ảnh tội phạm, cũng như không làm lộ khuôn mặt người cần kiểm tra):

Tính toán không lộ thông tin (ghi chú phần 4)