0
$\begingroup$

Is it possible to construct an efficient-to-compute function $F: X \rightarrow Y$ such that

  1. Given samples $(x_1, F(x_1))...(x_n, F(x_n))$, any efficient adversary ($F$ itself is kept secret) can't figure out $F(x)$ for a new $x \neq x_i$.
  2. The function $F$ preserves locality in a sense that, for some constant $L$ and norm $||\cdot ||_2$, $$ ||F(x)-F(y)||_2 \le L||x-y||_2 $$

As we know, any encryption scheme with a secret key satisfies the first property, and any simple function satisfies the second property, so I'm wondering whether or not there's something lying in between.

Any help or impossibility result is appreciated.

$\endgroup$
4
  • 2
    $\begingroup$ Do you want to put some constraints on the norm? Your requirements can be trivially met by the norm $||0|| = 0$, $\forall x \ne 0: ||x|| = 1$; however I don't believe that's what you meant... $\endgroup$
    – poncho
    Commented Mar 12 at 0:05
  • 2
    $\begingroup$ Your title asks about encryption, and the body of your question asks about what looks like a MAC or PRF (hard to predict a new value). Can you clarify? I believe the answer to your question is "no" for any reasonable encryption scheme, and "it depends on $L$" for a MAC. $\endgroup$
    – Mikero
    Commented Mar 12 at 0:45
  • $\begingroup$ Hi @poncho, sorry for the inaccurate notation. By the second condition, I want to mean that the image is close if and only if the preimage is close. So maybe we can restrict it to 2-norm for more clarity. $\endgroup$
    – Marc_12
    Commented Mar 12 at 1:57
  • $\begingroup$ @Mikero, thank you for the note and sorry for my inaccuracy in the notation or usage of nouns. You're right, I'll change the question statement for more clarity soon. $\endgroup$
    – Marc_12
    Commented Mar 12 at 1:58

3 Answers 3

2
$\begingroup$

It seems to me that if the image is close if and only if the pre-image is close, this is violating a basic security property, isn't it?

Local search will then be feasible unless you appeal to some kind of chaotic or fractal function definition--which presents its own problems for cryptography. There are questions about security properties of chaotic sequence generators here which are problematic to prove/verify. Such a definition would require a second coefficient $L'$ which would lower bound the distance between $f(x)$ and $f(x')$ for points $x,x'$ that are too close.

$\endgroup$
1
  • 1
    $\begingroup$ Yeah I know it violates the basic definition of security, but what if our goal is that it's hard to find y s.t. $||y-f(x)|| < \epsilon$, given that $min(||f(x)-f(x_i)||) $will be at least $O(1)$? (i.e. Intuitively, it means that, the adversary only knows the range of $f(x)$ by the given properties, but have no idea further.) $\endgroup$
    – Marc_12
    Commented Mar 12 at 3:40
2
$\begingroup$

If you are OK with $L$ exponential in the security parameter, then you can do the following simple thing: Treat strings from $\{0,1\}^\lambda$ as integers in the usual way, let $F$ be a secure PRF with $\lambda$ output bits, and define

$$ F'(K,X) = 2^\lambda \cdot X + F(K,X) $$

In other words, $F'(K,X)$ is the integer whose bit representation is $X \| F(K,X)$.

  • $F'$ is a secure MAC if $F$ is; you can't guess $F'(K,X)$ without also guessing $F(K,X)$.
  • We also have $\bigl| F'(K,X)- F'(K,Y)\bigr| \le 2^\lambda \bigl| X - Y + 1 \bigr|$.

If you require $L$ polynomial in the security parameter, then it is impossible. A simple attack is to request $F'(K,X)$ and then guess $F'(K,X+1)$. We know that $F'(K,X+1)$ must come from the set $\{ F'(K,X)+1, \ldots, F'(K,X)+L \}$ -- i.e., there are only polynomially many candidates so the value can be guessed with non-negligible probability (at most) $1/L$.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer. It's really helpful. However, I'm wondering that, if the samples are given (i.e. the adversary is not permitted to make arbitrary queries), and for another random $x$, our goal is that, with high probability, any efficient adversary can not make an $\epsilon-$close guess (here the high probability can be in the form of $1-poly(\epsilon)$), is there any $L$ polynomial in the security parameter possible? $\endgroup$
    – Marc_12
    Commented Mar 12 at 16:43
  • 1
    $\begingroup$ In the attack I describe, it is not important for the adversary to choose $X$. $\endgroup$
    – Mikero
    Commented Mar 12 at 18:27
0
$\begingroup$

It should suffice for you to take any “linear algebraic” hash function. The main example I know of is the SWIFFT hash function.

Like said in another answer though, the lipschitz constant will be quite bad. Still, i thought its worth mentioning that an independently-interesting hash has your desired property.

$\endgroup$
2
  • $\begingroup$ can you expand on how the required properties arise from SWIFFT? $\endgroup$
    – kodlu
    Commented Mar 14 at 15:36
  • 1
    $\begingroup$ The compression function is of the form $\sum_i a_i(x)\ast y_i(x)$, where $y_i$ are the inputs encoded into binary polynomials. One can rewrite this as matrix-vector multiplication (one replaces the multiplication by $a_i(x)$ by a matrix in the standard way). One can then bound the lipschitz constant of this by computing singular values of the corresponding matrix, for example. They will likely be very large though, so its mostly interesting as you can reduce bounding $L$ to a very explicit linear algebraic question. $\endgroup$
    – Mark Schultz-Wu
    Commented Mar 14 at 18:12

Your Answer

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

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