Join Log in
Score:2
avatar Crypto

Given a program, obtain a program that can operate on encrypted data

in flag
James

Suppose I have a program $P$. I would like to obtain an encryption function $e$, a decryption function $d$, and a program $Q$ such that $P(x) = d(Q(e(x)))$ for all inputs $x$. Ideally, the encryption would be asymmetric ($d$ cannot be obtained from $e$).

This would allow making a decentralized computing platform similar to Ethereum, but where contracts can store private data, only accessible by those with the decryption key.

Does something like this exist?

58
0 + 6
Manish Adhikari avatar
us flag
Manish Adhikari
There are such things called homomorphic encryption schemes. You can check them out.
6
Reply
fgrieu avatar
ng flag
fgrieu
You would need to restrict what $P$ can do. Good luck if it's e.g. a program that outputs if $x$ is prime.
3
Reply
SEJPM avatar
us flag
SEJPM
The requirement in question does look a lot like the correctness property of fully homomorphic encryption.
3
Reply
fgrieu avatar
ng flag
fgrieu
@SEJPM: Yes it _looks_ like a requirement for fully homomorphic encryption. But wouldn't FHE as we know it limit $P$ to be a polynomial function of $x$; and then in a particular finite field? For general-purpose program $P$, zk-SNARK comes to mind, but I'm uncomfortable with these, thus will not attempt an answer.
2
Reply
SEJPM avatar
us flag
SEJPM
@fgrieu without having checked I'm 95% sure that you can formulate arbitrary (arithmetic) circuits with most FHE schemes (in the given field of course) which should allow you to formulate arbitrary computations (using a circuit) and not just polynomials.
1
Reply
fgrieu avatar
ng flag
fgrieu
@SEJPM: at some level of theory, there's no difference between "polynomial .. in a particular finite field" and "arbitrary (arithmetic) circuits.. in the given field". If the field has order $n$ it's easy to make a poly of degree $n-1$ that evaluates to 1 at a specified point, and to 0 at all others; and from that build a poly of degree $n-1$ for any function. So I agree with what you are 95% sure, both in theory, and in practice for small fields. But I have much doubt for practice and large field. If the question gave an idea of what it wants to compute, that would help...
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.