4
$\begingroup$

My question is about this paper:

Privacy-preserving set operations: http://www.cs.cmu.edu/~leak/papers/set-tech.pdf

Let all polynomials be defined over a ring $\mathbb{Z}_p$, where $p$ is a prime number. Here for the sake of simplicity, I picked $p$ instead of $N$ used in the paper.

Assume $p_1,p_2$ are two fixed polynomials of degree $d$. Also, Let $r_1,r_2$ be two randompolynomials of degree $d$.

It is said in $T=p_1\cdot r_1+p_1\cdot r_2=m\cdot gcd(p_1,p_2)$, polynomial $m$ distributed uniformly at random over the polynomial ring.

Note that $gcd(p_1,p_2)$ represents intersection of the two polynomials roots.

Assume we want to use it in a protocol and them proof it. So we use simulation-based proof. So, simulator constructs $T'=m'\cdot gcd(p_1,p_2)$, where $m'$ is a degree $d$ uniformly random polynomial over the ring.

Question: In a full (reduction-based) proof, how to prove that a distinguisher cannot distinguish $m$ from $m'$?

I mean what hard problem we should rely on to show if it can distinguish them it can break the problem ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

From a (hopefully not-too-quick) reading, it seems the "nice" feature of the polynomials $$p_1\cdot r_1 + p_2\cdot r_2$$ [..fixing what I assume was a typo in question above..] is that their coefficients can be shown to be distributed uniformly and independently over the ring $R.$ In particular, this is done using a counting argument in the cited paper's appendix.

That is, this looks like a purely statistical property. You don't need to have a computationally-hard problem (or a simulator, necessarily..) to show that a statistical property holds. For example, the cited paper goes on to encrypt the coefficients of these polynomials (respectively) under an additively homomorphic encryption scheme, for its applications. That's where a computational hardness assumption kicks in (but one isn't needed related to the distribution of these polynomials specifically; they're unconditionally uniformly distributed -- at least in the context of the given paper).

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank you for the answer. So, in a full proof we say that as the paper shows the polynomial's coefficients are distributed uniformly random over the field/ring? so we don't need to use a distinguisher to distinguish a random polynomial in the real model with the one in the ideal model? $\endgroup$
    – user153465
    Aug 19, 2016 at 12:31
  • 1
    $\begingroup$ I recommend reading the full version of the paper (I suspect it answers your questions more so than a few sentences here might :)). See: cs.cmu.edu/~leak/papers/set-tech-full.pdf $\endgroup$
    – Daniel Apon
    Aug 19, 2016 at 12:35
  • 1
    $\begingroup$ Thank I've already read that. But it does not use full proof. It provides just a short sketch of proof for the PSI protocol. $\endgroup$
    – user153465
    Aug 19, 2016 at 12:37
  • 1
    $\begingroup$ Typically, protocols involving random polynomials are relying on the information-theoretic properties of random polynomials. (I'm unfamiliar with the gory details of Kissner/Song..) For example, here's an important follow-up work on a 'robust' version of PSI that may give you an additional perspective on the same (at least, type of) technique: ece.umd.edu/~danadach/MyPapers/set-int.pdf $\endgroup$
    – Daniel Apon
    Aug 19, 2016 at 12:45
  • 2
    $\begingroup$ On a sidenote: coefficients of polynomials are a tricky thing. If you only have a product of polynomials, Gauss' lemma for polynomials has to be considered (for commutative rings in general, see the last section of the wiki page). That's why they probably had to use sums of polynomials (For sums, statistical arguments are much easier to find). $\endgroup$
    – tylo
    Aug 19, 2016 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.