12

I went through it, and while this isn't a complete answer, which should shed some light (and note: when I'm talking about $x$, $y$ and $z$, I'm referring to the ranges those indicies can take on; not any specific index) First rule: if $x$ is even, then $\theta$ is invertible. The proof of that is actually fairly elegant; however it's also rather irrelevant ...


7

This is probably not secure enough for a proof of work. I'll outline some attacks, of increasing sophistication/complexity and increasing effectiveness (decreasing runtime). Brute force The obvious attack is brute force: enumerate all $2^{32}$ possible inputs and check to find the first that produces the desired output. This takes $2^{32}$ time. I'm ...


7

Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation protocols such as the various versions of the Yao protocol or the TinyOT protocol are limited to two parties. So it may sometimes be overemphasized that SPDZ ...


6

The circuit term in the evaluation of functions with FHE is a coming from Electronics. In the notion of FHE circuit, we have almost the same problem; build a circuit of a function $f$ with available FHE operations so that we can evaluate the $f$ with FHE. Somewhat Fully Homomorphic schemes allow us to operations on ciphertexts. In the bitwise case, for ...


6

Hash functions are generally designed by splitting the problem into two parts: A fixed size core function. This is called the compression function in most hashes, but in Keccak it's called the permutation. A domain extender—an algorithm that uses the fixed-size core function to process arbitrary-length inputs. In older hashes like SHA-2 this is the Merkle-...


6

Given a vector $[S_0 S_1 x_1, S_0 S_1 x_2, ...]$, it is quite easy to recover $S_0 S_1$ (by computing the GCD of the various elements). With that information, the attacker can then recover the values $x_1, x_2, ...$, and so yes, a semihonest adversary could easily recover the $X_{reg}$ values.


5

my understanding I could use it to do 2-party computation You are correct, SPDZ can give secure MPC for any number of parties. It is just a matter of generating enough multiplication triples. Should I favor a 3 party setting instead of a 2 party one when using SPDZ? Whichever makes sense in your application is fine. why is not widely use for the 2-...


5

It's actually straight-forward; we'll assume that all the inputs are either encrypted versions of 0, or encrypted version of 1; then: We can replace an AND gate with just an FHE multiplication of the two inputs: $$AND(x,y) = x*y$$ Where $*$ is our Homeomorpic multiplcation operation. This obviously evaluates to an encrypted 1 if both of the inputs are ...


5

What you are seeking for is a special case of secure multiparty computation, namely secure function evaluation or also called secure 2 party computation. However, general solutions to this problem require interaction, meaning that the parties performing the computation need to exchange more than two messages. You write: To compute some arbitrary function ...


5

The answer is definitely yes. You should be able to do what you are looking for. The computation is very simplistic, so using existing MPC protocols will be efficient. Many of the existing protocols are able to evaluate a few blocks of AES using MPC per second, so this computation will be no problem. Typically MPC works by translating your function into a ...


4

Yao's garbled circuit is simple to understand. First of all, note that if we can securely compute $\mathsf{NAND/NOR}$ of two input bit, we can perform any boolean operation. Yao's garbled circuit tries to achieve the same. Lets look at scrambled $\mathsf{OR}$ gate. Alice creates a set of four keys, $K_{x=0},K_{x=1},K_{y=0},K_{y=1}$ She then creates 4 “boxes”...


4

Say $m$ is the number and $h=f(m)$ it will be pretty easy to find $m'$ (not necessarily equal to $m$) such that $f(m)=f(m')$ on a modern computer. Brute Force The output of $f(m)$ is 32 bits. The following python function will do it def find_collision(val): while True: test = random.getrandbits(32) target = ((test*test) >> 16) & 0xffffffff) ...


4

Someone can find a preimage (or prove that there is no such preimage) with about $2^{20}$ trial squares, and no precomputed storage. ACtually, I believe that the below procedure will actually achieve $2^{18}$ trial squares; that requires closer analysis than I feel like at the moment. Here is the key observation that we can take advantage of to show this: ...


3

To be well defined as a function, you need to specify lengths of the $x_i$, which is not the same thing as their entropy. Also, the $H(h_i)$ in your equation should probably be $H(x_i).$ Let's assume each $x_i$ are binary vectors of length $n$ for concreteness. Then what you want in a more general version of this problem would be $$ \mathbb{H}(F(x_1,\ldots,...


3

The problem is known in the literature as private function evaluation (PFE). A sender has input (a function) $f$; a receiver has input $x$, and only the receiver learns $f(x)$. If you are willing to leak the topology of a circuit that computes $f$ (but not the identity of the gates), then using classical garbled circuits / Yao's protocol will work. These ...


3

As discovered by D.W., this is in fact part of recommended IDEA implementation. IDEA uses $a\cdot b \bmod (2^{16}+1)$, with a special case of handling $0$ as $2^{16}$. From the Handbook of Applied Cryptography, note 7.016: Note (implementing $ab \bmod 2^{n}+1$) Multiplication $\bmod 2^{16}+1$ may be efficiently implemented as follows, for $0 \leq a, b ...


2

At first glance, it doesn't look like that interesting of a function. If we define: $$f(b, c) = (b\cdot c)\%k - (b\cdot c)/k$$ then we always have: $$f(b, c) \equiv bc \mod k+1$$ In other words, largely it's just an odd way of doing a modular multiplication. Of course, $f(b, c)$ is not always $(bc) \% (k+1)$; sometimes it is negative. At first glance,...


1

Functional encryption is bigger framework, not necessarily attribute based encryption.It tries to provide a framework for Identity Based Encryption, Attribute Based Encryption and Predicate Encryption. Recently a paper came up showing the connections between Functional Encryption and Fully Homomorphic Encryption. Here. Iam yet to go through it thoroughly ...


Only top voted, non community-wiki answers of a minimum length are eligible