I'm looking for an encryption with as small numbers as possible.

Given a small group of identities ($G$) (e.g. numbers from $1$ to $N$). Given one entry (or a small number) $e_i$ allows to compute another entry (like existence of a known generator/function). With this all group elements can get generated (which should take very long) or a constant fraction of it (which are a low amount ($<100, <<N$) of disjoint sets). All elements generated this way should lay in this initial group ($G$) or there need to exist a function $f$ which generates a unique element out of this initial group ($f(e_i) \in G$). That means $e_i$ don't need to be in $G$ iff all elements we can generate $E=\{e_i, \forall i \in [1..|G|]\}$ and $\{f(e_i), \forall i \in [1..|G|]\} = \{G\}$

Now given two random entries it should be hard to derive how one could be computed out of the other. Hard means it should take at least one year of computation for a current consumer PC for most cases (longer would be much better). There should be a way to generate each (or nearly) entry without the knowledge of any other or inner structure. E.g. for the example above were the identities are the numbers from $1$ to $N$ that could be just a random number. For an elliptic curves it would be some function which finds an element out of a random number.

In use case it will run at user PC. That means an attacker has access to the whole source code. Each user gets a random entry.

Toy example:

prime $P=13$

elements: $1,..,12$

generator: prime root $g=7$

$e \equiv g^a \mod P$ for $a=1,..12$ generates all elements

Given one random number $r \in [1..12]$ as entry each other element can get generated out of it:

$\{r \cdot g^a \mod P\} = \{g^a \mod P\} $

Now given another random $r'$ it is hard to compute $a$ for :

$r' \equiv r \cdot g^a \mod P$

(at least for big numbers, discrecte logarithm).

If not a prime root for $g$ is picked, e.g. $g=4$ then each given random $r'$ can only produce one of two disjoint sets which would also be OK for use case.

Now the toy example only works for large $P$ and with this a large number of group of identities. Now I'm looking for a way to do this with as small as possible groups. I'm also thankful for ideas which might work. Has this kind of encryption a special name?

Identity group size is less than 64-bit. As far as I know toy example or elliptic curves aren't safe for those small numbers.

  • $\begingroup$ Format preserving encryption is the right keyword. It's a symmetric cipher mode $\endgroup$ – Natanael Jul 21 '19 at 21:29

Your Answer

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

Browse other questions tagged or ask your own question.