Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Oblivious transfer refers to a cryptographic protocol in which a sender possesses a set of data and a receiver queries the sender for a particular member of that set in such a way that the sender does not learn which member the receiver requests. In other words, the sender is oblivious of what she ...

0
votes
1answer
34 views

Oblivious Encryption: Oblivious Transfer Based Encryption

I’m aware of a couple of OT protocols, most of which use Public Key Cryptography, Key Establishment (or similar constructs) as the base. I don’t really have specific knowledge on other OT protocols, ...
2
votes
0answers
43 views

Is post-quantum Oblivious Transfer possible

If I’m not mistaken classical OT is not regarded quanum-safe. However I’ve been reading (not really understanding) some papers [1,2] and some reviews[3] on quantum OT and/or post-quantum OT, it seems ...
1
vote
0answers
25 views

Verifying dealer parameters in 1-2 oblivious transfer

I read the description of 1-2 oblivious transfer algorithm in wikipedia. In the algorithm described Alice has two messages $m_0, m_1$. Bob picks value $b \in {0,1}$, and the protocol allows Bob to ...
3
votes
1answer
77 views

Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?

I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
1
vote
0answers
70 views

Optimized Random-OT Security in Standard Model

I was going through the paper - " Efficient Oblivious Transfer and Extensions for Faster Secure Computation" by Asharov et al. where the authors propose an optimized OT protocol along with a Random-OT ...
0
votes
1answer
44 views

1/4 oblivious transfer construction from 1/2?

I have a question about OT? we assume that sender has $m_0,m_1,m_2$, and $m_3$ and selects random $S_0, S_1, S_2, S_3, S_4, S_5$ and compute this statement than sends to receiver. $C_0 = S_0 \oplus ...
2
votes
2answers
58 views

Bandwidth-efficient oblivious transfer

Alice has two 1GB files, and Bob wants one without Alice knowing which. Can this be done with less than 2GB (1GB for each file) of bandwidth between Alice and Bob?
4
votes
1answer
100 views

Can someone explain how OPRF (Oblivious pseudo-Random Function) is based on OT (Oblivious Transfer)?

Can someone explain to me how OPRF is based on OT extensions? I'm currently reading papers about private set intersection problem that uses efficient OT-based protocols based on OPRF, the link of the ...
2
votes
0answers
59 views

Reducing 1/4 OT to 1/2 OT

We can construct a 1/4 OT from 1/2 OT. Proving security for the receiver in 1/4 OT means showing a reduction to the 1/2 OT receiver's security. The protocol I am using is given on page 3 here. I am ...
0
votes
0answers
37 views

Adaptively secure 1-out-of-n oblivious transfer

Following is a basic protocol for adaptively secure 1-out-f-n oblivious transfer. Inputs: P1 has two strings x0, x1 and P2 has a bit σ ∈ {0, 1}. The protocol: 1. P1 chooses random strings r0, r1 and ...
1
vote
1answer
51 views

Naor Pinkas OT - senders security; reduction to DDH

This question concerns the security of the sender in the Naor Pinkas OT. The protocol can be found here. We can reduce the security to the DDH assumption. How exactly is this done? Can someone ...
2
votes
0answers
33 views

Is there any OPRF (oblibivious pseudo random random functions) between one receiver (1 input) and n senders (n inputs)? any references to read?

I am looking for some references for multi-party / distributed Oblivious pseudorandom Functions. I found two party OPRF protocols between a sender $S$ and a receiver $R$ for securely computing a ...
3
votes
0answers
133 views

Public key encryption from (1,2)-oblivious transfer

Prove that any two rounds of (1,2)-oblivious transfer, that is semi honestly secure, imply public key encryption. My ideas so far: Let's say Alice samples two $n$ random strings $(x_1, x_2)$, and ...
0
votes
1answer
101 views

Isn't Socialist Millionaires vulnerable if Alice's and Bob's message are picked from a shared list?

I'm interested in a situation where Alice and Bob each pick cards from a deck of 52, and want to test if they picked the same card without revealing what the card is (a "mental poker" situation). The ...
3
votes
1answer
128 views

Why work in a subgroup for Naor and Pinkas oblivious transfer?

In section 4 (protocol 4.1) of the paper by Naor and Pinkas [1], why did the authors decide to operate in a subgroup? When they say "the messages are in the subgroup" does that mean $x, y, z_0, z_1$, $...
3
votes
1answer
104 views

Understanding pseudo-random functions (used in a Oblivious Transfer Protocol)

Given a family of pseudo-random functions $$\{F_K:\{0,1\}^m\mapsto \{0,1\}^m | K \in \{0,1\}^t \}.$$ I want to understand how the elements behave. Lets say we take some $F_{K_1}$ and evaluate at $x=...
0
votes
0answers
198 views

Is there a way to encrypt a ANY string using homomorphic algorithm?

I have a database which consists of strings as well as numbers, I have to use homomorphic scheme to encrypt fields. I am using Pailliers algorithm for the purpose, but I just find it for numbers or ...
6
votes
1answer
79 views

Is there a studied notion of “party independent transfer”?

I've been thinking about the following set-up involving three parties, Alice, Bob and Charlie: Bob and Charlie decide among themselves who is going to receive a bit from Alice (perhaps by a coin toss)...
4
votes
0answers
53 views

Performing DFS search with garbled boolean circuit

Given $G=(V,E)$ How can i implement a DFS search in the Boolean circuit? ( The output should be to assign each node it's DFS value from a root node) I assume the complexity should be exponential, ...
8
votes
1answer
345 views

Please help me understand this k-out-of-n oblivious transfer protocol

I'm having the following protocol specification of a k-out-of-n oblivious transfer (as part of some E-Voting protocol) and it's bugging me that I fail to understand it with my basic knowledge of ...
3
votes
1answer
94 views

Select a single message without showing which one has been selected

Can anyone suggest a cryptosystem for the following problem? We are working on a university research project. Problem Alice has multiple messages $M_i$, $i = 1,\ldots ,n$. Bob should obtain any, but ...
1
vote
1answer
247 views

DH Key Exchange Protocol (one-out-of two)

Now given this problem, for part 1) I have solved it as follows, (I hope I am correct). The basic idea is this: I Have two prime numbers g and p and I tell you what they are. You choose a secret ...
1
vote
0answers
105 views

Oblivious Transfer in E-Voting

I'm having troubles understanding, why and how an Oblivious Transfer is used in E-Voting systems. According to many descriptions of OT's, a receiver (I supposed that's the Ballot-Collector?) can ...
4
votes
1answer
117 views

Exact communication of the IPS compiler?

I'm reading papers related to the IPS compiler. I'm confused about one point: The paper IPS08 (PDF) proposed a protocol with $O(s)$ communication for a circuit of size $s$ in the OT-Hybrid model. ...
1
vote
1answer
543 views

1 out of n oblivious transfer

So I read some stuff about oblivious transfer and came a ross that 1 out of 2 OT can be used as a black box to build 1 out of n OT. At first it seemed trivial just feeding in 4 messages and 2 chooser ...
1
vote
1answer
140 views

Oblivious Polynomial Evaluation and Encoding Payload

I am trying to parse this paper. I think I do come to understand the general concepts go into this type of Private Set Intersection, based on Oblivious Polynomial Evaluation. I was able to produce a ...
1
vote
0answers
62 views

Secure Communication Protocol Design using oblivious transfer?

I have a problem I need to solve with the following scenario and I hope someone can help me find an approach or direction to start tackling it. Consider Alice as a sender who has $n$ strings which ...
4
votes
0answers
227 views

How do they avoid Zero Knowledge Proofs in the paper Priced Oblivious Transfer: How to sell Digital Goods?

I don't understand a part of the paper Priced Oblivious Transfer - How to Sell Digital Goods. Particularly, the authors avoid using zero knowledge proofs and in section 3.3 they explain how they do ...
1
vote
1answer
69 views

Access control problem in oblivious transfer

I am not sure whether the title is proper or not, but this question comes to my mind when I was reading $k-n$ oblivious transfers. In a $k-n$ oblivious transfer (OT) protocol, a party A has $n$ ...
8
votes
0answers
389 views

Yaos Millionaire Problem: Why distance >= 2?

I'm currently reading about Yao' Millionaire Problem: http://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf Alice and Bob want to know which of them is richer. Let $j \in \{1, \cdots 10\}$ be Bobs ...
3
votes
2answers
323 views

1-out-of-2 OT from Random 1-out-of-2 OT

Last week I came upon this problem in my h.w.: Let $OT^m$ denote 1-out-of-2 oblivious transfer of $m$ bit inputs. Let $RandOT^m$ denote the following primitive: The sender’s input ...
4
votes
2answers
830 views

How to implement 1-out-of-n OT from 1-out-of-2 OT?

How can I implement a 1-out-of-$n$ oblivious transfer protocol from 1-out-of-2 OT protocol which is resistant against passive corruption? Assume we can access 1-out-of-2 OT $n$ times.
0
votes
1answer
283 views

How to implement oblivious transfer where probability of the receiver getting secret is exactly 1 out of 4? [duplicate]

As we know that oblivious transfer is done with probability of 1 out of 2. But how to implement it with probability of 1 out of 3 or 1 out of 4??
4
votes
2answers
430 views

Alice answering Bob without knowing the question

I'm a student and I don't know how to solve the following problem : Alice is proposing a 10 questions list to Bob. Bob choose only 1 question and wants to know the answer without Alice knowing the ...
4
votes
1answer
80 views

Secure “table-look-up” operation

I am thinking about this problem: The server has a two-column table $T=\{c_1,c_2\}$. A user has a query $q$ that is sent to server. The server find an item $x$ in the first column satisfying $x=q$ ...
2
votes
1answer
143 views

A secure function evaluation problem and an alternative of 1 out of n oblivious transfer?

I am considering a "secure function evaluation" problem: Consider two parties: A and B. A has a one-to-one mapping function $f(x)=k$. Basically, the function $f(x)$ can be regarded as a table of two ...
2
votes
2answers
242 views

What if OT breaks in Yao's garbled circuit?

Two semi-honest parties are computing F with Yao's garbled circuit. Sender garbles it with his inputs baked in then sends it to the receiver. At this point the receiver must use OT to get his keys. ...
8
votes
1answer
213 views

Secure multiparty computation of conjunction

Suppose Alice and Bob each have bits a and b, respectively. How can Alice and Bob compute the function ...
1
vote
1answer
161 views

Oblivious transfer variation question

Now I am doing a variation of the oblivious transfer, I have to use 2 people, pebbles, and boxes. I need to find out if who has a larger number between Alice and Bob (variation of Yao's Millionaires' ...
2
votes
1answer
204 views

Private Information Retrieval--Is it still theoretical?

Are there any real world products in which private information retrieval techniques are used?(a data hosting server oblivious of which data item was fetched from it?)If not what are the major barriers ...
3
votes
0answers
76 views

online Vickrey auction using remote coin flip

Is there any published work on implementing a online auction, which uses "remote coin flip" to prevent auctioneer cheating when choosing winner and bid value? Is there any possible way to use remote ...
1
vote
1answer
160 views

Privacy-Preserving relational databases: checking the existence of a record (or multiple records)

I would like to know if there exists a protocol which performs the following operation in a privacy-preserving fashion: User $U$ wants to know whether a record is stored in the database. The primary ...
1
vote
1answer
82 views

server aid secure equality test

The scenario is like this: $P_1$ has $m_1$, $P_2$ has $m_2$, they want to compare whether $m_1=m_2$ via the server $S$. After the protocol, only $S$ knows the result, and there is no interaction ...
2
votes
3answers
239 views

Is there an oblivious decryption scheme?

Alice has $K$; Bob has $E(K, m)$; Is there such a scheme that enables Alice decrypts $E(K, m)$ without knowing $m$, and Bob gets $m$ ?
4
votes
0answers
252 views

Secure Secret sharing

I'm trying to come up with a new way to do oblivious transfer that is faster and requires less computation than existing methods. The basis of my method is shamir secret sharing. Below is an example ...
2
votes
0answers
67 views

Expand 1-n Oblivious Transfer to retreave only an item I, for which permissions exist

To my understanding in a 1-n Oblivious Transfer the Sender has some Values $X_1...X_N$ and the receiver wants to retreave some $X_I$, with $1 \le I \le N$. Can one now somehow guarantee, that the ...
1
vote
1answer
147 views

Cryptography: Oblivious Transfer with at most one transfer?

I am trying find a transfer method for this problem. Suppose Alice and Bob both has access to a function $\text{F}$ with two parameters. $\text{F}(x,y)$ randomly returns $p$ to alice and $q$ to Bob ...
4
votes
1answer
83 views

Oblivious Transfer where neither party learns the index of the message

In a traditional Oblivious Transfer setting, the sender has a list $(x_1, x_2, ... , x_n) \in G$ where $G$ is the chosen group. The receiver has $b \in \mathbb{N}$, such that engaging in the protocol ...
1
vote
1answer
270 views

Outsourcing arbitrary computations securely

Consider the following scheme. Alice wants Bob to make some computations for her, but she doesn't want to reveal the data on which he's going to do it. So, she encrypts the data, sends them to Bob, he ...
3
votes
1answer
510 views

Bit commitment with 1-out-of-2 oblivious transfer

I know a protocol for bit commitment using regular OT (Bob has 1/2 chance of learning the bit Alice transferred to him) which goes like this: COMMITMENT PHASE Alice chooses a bit $b$ For $i=0$...