New answers tagged

0

There is a relevant scenario for order queries but not with the ORAM security guarantee. It hides the content of the DB to the user, in a zero-knowledge fashion: eprint.iacr.org/2014/632 . The guarantee from the server point of view is tied to verifiability


0

In general, no, you cannot do that. That is why frameworks like universal composability exist. In the UC framework, you prove a protocol, $\pi_1$ is secure according to some adversary model. You do this by showing how $\pi_1$ is indistinguishable from some ideal functionality $\mathcal{F}_1$, where the ideal functionality is secure by definition (e.g., via ...


-2

Without the value of both A and B, I guess a conclusive decision might not be possible. But, I think I've got a probablistic method that determines (B>=A)==true when the gap B-A is large enough, and determines (B>=A)==false when B<A or A and B are so close that the algorithm cannot give correct answer with enough confidence. The method has 4 ...


2

It is not enough to be able to simulate the view of a single party, because corrupted parties may cooperate. As mentioned in the book, it may be easier to view all the corrupted parties as a single entity. It is the view of this single entity that we must simulate. If $m$ is fixed, the order of quantifiers does not matter, because the number of subsets $I$ ...


1

When the servers may collude then if they are all corrupted it's exactly the same as 1-server PIR. Thus, in information-theoretic PIR, it is always assumed that only some subset of the servers are corrupted. It is unclear to me what you would gain by running MPC between the servers. One possibility is to simulate a single-server PIR with many servers. But ...


5

The answer to your question can be found in a SPDZ follow up paper; it is described as contribution (2) in the intro (top of page 2). There is a new version of SPDZ called MASCOT that uses OT instead of somewhat homomorphic encryption, and is supposed to be about 200 times faster. So, I would recommend looking at that as well.


4

In addition to Paul's answer there is even an ORAM module inside a processor architecture, fully implemented: “A secure processor architecture for encrypted computation on untrusted programs” Abstract: This paper considers encrypted computation where the user specifies encrypted inputs to an untrusted program, and the server computes on those encrypted ...


3

There has been a spike in research interest in ORAM in the past few years for a couple different reasons. The most important one (IMO) is the rise of cloud computing, and the concomitant rise in funding for research related to cloud computing security. The question of what memory access patterns leak to an untrusted server was esoteric and theoretical in ...


4

Yes. We work under the assumption that the protocol is not secure, which means that for infinitely many $n$, there is a pair of inputs $(x,y)$ on which the simulation fails (i.e., when the inputs are $x$ and $y$ the view generated by the simulator for at least one of the parties can be distinguished from a real one). Thus, when running on security parameter ...


7

Yes. There is an $\Omega(\log n)$ lower bound on ORAM. Therefore directly using ORAM to transform a non-oblivious algorithm to oblivious algorithm would incur a logN overhead. It is an open problem to design an ORAM matching the lower bound. No. There exists algorithms that do not have more efficient solution. As an apparent example, accessing a memory cell ...


10

The answer to this question is not straightforward and has a lot to do with the "conference culture" of computer science. Unlike other fields, the main publication venues for CS are conferences and not journals. This isn't to say that journals don't have an important role; rather, you don't follow journals to see what research is being done - you follow ...


1

Why do most of papers in the well-known conferences provide only the proof sketch? Space constraints, mostly (the paper has to fit in a certain number of pages). Often, the full proofs are given in the preprint version, available from the author's home page or the ePrint archive.


0

It depends on how you make shares out of a polynomial. Consider for example Shamir secret sharing, using which a party can share a secret $s \in F$ (where $F$ is a finite field) with $n$ parties by doing the following: Construct a polynomial $f(x) = s + a_1x+a_2x^2+\dots + a_nx^t$, for some $t$, where $a_i \in_R F$ for all $1 \leq i \leq n$. Send the value ...



Top 50 recent answers are included