Score:1

Crypto

Is there a secure two party protocol that makes P1 (with x as input) gets rx+r' and P2 gets (r,r')

mactep Cheng

1/26/23, 6:30 AM

It should be a secure two party protocol against malicious adversary.

P1's input is X in Zp* (p is a prime number); P2's input is nothing. P1's output is rX+r'. r,r' are random numbers from Zp* P2' output is r and r'.

Is there any efficent protocol to realize this functionality other than by using homomorphic encrytion? If only HE solves this problem, which is the most efficent one?

Thanks for help!

0 + 0

multiparty-computation

protocol-design

homomorphic-encryption

Mikero

1/26/23, 8:38 PM

This is a well-known problem called Oblivious Linear function Evaluation (OLE).

mactep Cheng

1/27/23, 1:50 AM

Thanks for help!

Score:0

Crypto

Daniel S

1/26/23, 8:21 AM

You can do this with any additive/logarithmically homomorphic scheme with $p$ dividing the order of the plaintext group. The Okamoto-Uchiyama system has plaintext space size exactly $p$ and may be suitable if you have no quantum resistance required.

The protocol is as follows:

P1 creates a public key for the scheme as well as encryptions of $X$ and 1, say $c_0=E(X)$ and $c_1=E(1)$. These are passed to P2.

Assuming a log-homomorphic scheme, P2 chooses random $r$ and $r’$, computes $c_2:=c_0^rc_1^{r’}=E(rX+r’)$ and sends this value to P1.

P1 decrypts $c_2$ to recover $rX+r’$.

0 + 0

mactep Cheng

1/26/23, 8:29 AM

thank you! how about its efficiency compared with the Paillier scheme? I want an efficient one because I want it be secure against malicious adversary. Do you know any method other than HE?

mactep Cheng

1/26/23, 8:33 AM

And I also want a random r and r', but in your scheme, r and r' are decided by P2 which could be malicious.

Daniel S

1/26/23, 8:41 AM

O-U is similar in efficiency to Paillier, and often more efficient for the same level of security. I don’t know of any non-HE solution.

Daniel S

1/26/23, 8:45 AM

To defend against malicious P2, P1 can choose random $s1$ and $s2$ and form $(r+s1)X+(r’+s2)$. Sending $s1$ and $s2$ to P2 allows them to form $r+s1$ and $r’+s2$

mactep Cheng

1/26/23, 8:54 AM

Thanks! I will study O-U scheme. But i thinks to make it secure, some additonal ZKP may have to be added; things like proving the public parameter is rightly generated etc.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is there a secure two party protocol that makes P1 (with x as input) gets rx+r' and P2 gets (r,r')

TH: มีโปรโตคอลสองฝ่ายที่ปลอดภัยหรือไม่ที่ทำให้ P1 (โดยที่ x เป็นอินพุต) ได้รับ rx+r' และ P2 ได้รับ (r,r')

RO: Există un protocol securizat pentru două părți care face ca P1 (cu x ca intrare) să primească rx+r' și P2 să primească (r,r')

RU: Существует ли безопасный двухсторонний протокол, который заставляет P1 (с x в качестве входных данных) получать rx+r', а P2 получает (r, r')

VI: Có giao thức hai bên an toàn nào làm cho P1 (với x là đầu vào) nhận được rx+r' và P2 nhận được (r,r')

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.