# Tag Info

9

Oblivious transfer is mostly studied as a theoretic construction, as it is an important component in achieving interesting protocols (like secure two-party computation and secure function evaluation). The interest in 1-2 OT is that it is a minimal definition theoretically, and most results that limit themselves to 1-2 are designed to improve some basic ...

9

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 ...

6

the securty of 1-n OT is a function of the security of a 1-2 OT. So in analysis it is easy to use 1-2 OT for security proofs. A 1-n OT is essentially a multiple run of a 1-2 OT. (somewhat like a byte is made of 8 bits) So IMO the question is like asking why use bits when you can use bytes for communication. [it depends on the application]

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 ...

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: ...

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) ...

3

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 ...

3

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 ...

2

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, ...

1

At first glance, it doesn't look like that interesting of a function. If we define: f(b, c) = (b*c)%k - (b*c)/k then we always have: f(b, c) == b*c (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 (b*c) % (k+1); sometimes it is negative. At first glance, I don't see any ...

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