0
$\begingroup$

I'm looking for a function that is generally one way from some secret $F(s, A) \rightarrow Y$, where $A$ is known, $Y$ is produced (also known), and $s$ is kept secret. But whose repeated application results in the function being reversible (to determine $s$) at some step $F_n$.

Edit: $A[1,2 \dots n]$ is a set of numbers not known in advance (prior to each successive application of $F$), but of a particular type, say the first 16 bytes of a SHA-256.

It is essential that it can be proven that the function is not reversible at $n-1$ (or that the work necessary to reverse at $n-1$ is very high) and sufficiently easy to reverse at $n$ ($n+1$ etc.), and that this is provable for any s belonging to a certain group.

$F(s, A_1) \rightarrow Y_1\\ F(s, A_2) \rightarrow Y_2 \\ \dots \\ F(s, A_3) \rightarrow Y_n$

Would greatly appreciate a pointer in the right direction (what functions to look at, or even some reading on the subject), thanks.

Improve this question
$\endgroup$
4
  • $\begingroup$ "being reversible at some step N" in the sense of revealing the original A or the immediately preceding A? $\;\;\;$ $\endgroup$
    – user991
    Oct 25, 2014 at 20:04
  • $\begingroup$ A1..A2..An are known values, put through some function (or hash) along with secret s. The idea is to be able to determine s, after Fn operations. $\endgroup$
    – user3467349
    Oct 25, 2014 at 20:07
  • $\begingroup$ Do you want s to remain hidden against an essentially unbounded number of queries that don't include any such chains, or just against less than N total queries? $\;$ $\endgroup$
    – user991
    Oct 25, 2014 at 20:15
  • $\begingroup$ just against less than N total queries, and for any s from a certain Set S. That is to say, that an observer who knowing someone choose a seed s from Set S, would be able to derive s after N applications of some Function F to s and known A[1,2..n]. $\endgroup$
    – user3467349
    Oct 25, 2014 at 20:32

1 Answer 1

Reset to default
0
$\begingroup$

F(s,A) can be

a prefix-free encoding of the number of elements in the finite field encoded by s
|| $\:$ the polynomial R (as described at this link) from that finite field $\;$ ||
the output of the degree-at-most-(N-1) polynomial encoded by s over that finite field at the point A

.


Let SP be the set of polynomials of degree at most N-1 over the finite field. $\:$ N input-output pairs would allow one to efficiently find the encoded element of SP by Lagrange interpolation. $\:$ Observe that for any given field, for all A, evaluate-at-A is a linear map from SP to the field. $\:$ Since Lagrange interpolation will always give a compatible polynomial (and not just find one when there is one), that linear map is surjective. $\:$ Thus, for all integers x in {0,1,2,3,...,N-2,N-1}, for any given N-x input-output pairs and any given z other inputs, the outputs at those x inputs for such a polynomial chosen uniformly from the subset of SP that produces the given N-x input-output pairs are independent and uniformly distributed. $\:$ Observe that any guess at s can only be correct if it gets those outputs correct.
Therefore, for all integers x in {0,1,2,3,...,N-2,N-1}, the probability of guessing s correctly is
at most [[the sampling error for SP] plus [one over [[the number of elements in the field] to the x]]].

This wiki article describes how to do arithmetic over finite fields given an irreducible polynomial over
their characteristic field. $\:$ This paper gives the "simplest" such polynomials for degree at most 10000
over the field with 2 elements, and these two papers give algorithms which can let you confirm that
those polynomials are in fact irreducible (confirming that they're the simplest would be harder).
More generally, over small prime fields, this paper gives a deterministic algorithm
for constructing irreducible polynomials and this paper gives constructions that
are presumably more efficient for degrees divisible by a not-too-small power of 2.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the reply. Shamir's secret sharing, uses a0 = s in the terms of the polynomial over a finite field of size p, where as it sounds like you are suggesting for f a polynomial of degree n-1 whose terms are known over a finite field of size s (which is not known)? $\endgroup$
    – user3467349
    Oct 26, 2014 at 16:07
  • $\begingroup$ No, I was suggesting that f be evaluation of s at A, where s is a polynomial of degree at most N-1. $\:$ However, I now realize that the decoder also needs to know what the finite field is. $\hspace{1.45 in}$ $\endgroup$
    – user991
    Oct 26, 2014 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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