Hi,

I have posted a similar question subjected "Randomly enlarge number with
sequence preserved". With lot of help and response, I learn more about what
I really need. Since there is some change in the requirement, I just like to
start a new post.

I am looking for algorithms f(p, k), F(P, K) that can fullfill the following
requirements and be practical to be implemented using programmnig language.

p = 8 bytes data
q = 8 bytes data
k = key
K can be equal to k  or can be different from k
F() can be equal to f() or can be different from f()
P = 16 bytes data
Q = 16 bytes data

P = f(p, k)
Q = f(q, k)

1. P < Q, for all p < q

p = F(P, K)
q = F(Q, K)

2. given know pair of (p, P), even with knowledge of functions (i.e. f(),
F()), w/o knowledge of K, it is difficult to guess K
3. given some P and Q, even with knowledge of functions (i.e. f(), F()), w/o
knowledge of K, it is difficult to guess p, q

Thank you.

LT

: I am looking for algorithms f(p, k), F(P, K) that can fullfill the following
: requirements

What I suggested meets almost all your requirements, but it does NOT
provide, easily, once one makes it complicated enough not to be obviously
inverted by an attacker, for an inverse function. (One could be done, and
it would work, knowing the key, but it would require a degree of hunting
for the soluton.)

It may be possible a solution exists, but I don't know of one. You might
want to ask your question on sci.math as well, as you might be more likely
to find someone who did know something useful. I believe that what you are
posing is a difficult problem.

Certainly, sequences having the properties of f and F obviously exist. But
can any of them be computed directly by an algorithm?

If you want it to be hard to invert given _one_ P, but you don't expect an
attacker to intercept both a P and a Q, it's easy enough: P = some random
128 bit number + 5 * p, for example. The randomness of the starting point
protects just one message, while the pattern formed by the successive
equivalents of various p's is very poor.

Maybe this is a hint, though, about how to satisfy your requirement. I wil
continue thinking about the problem.

John Savard

news:ai0ujh$sjd6@imsp212.netvigator.com...

I believe you are over-designing your application.  What you are asking
for would be called an "order-preserving cipher".  I would expect most
ciphers with this property to be relatively weak.

Perhaps you would be so kind as to describe the real problem you are
trying to solve so that we might bring more experience to bear on a
solution?

[snip]

Could you tell the relevance of this condition in
a practical application? Thanks.

M. K. Shen

John E. Hadstate (jh113...@hotmail.com) wrote:

: I believe you are over-designing your application.  What you are asking
: for would be called an "order-preserving cipher".  I would expect most
: ciphers with this property to be relatively weak.

: Perhaps you would be so kind as to describe the real problem you are
: trying to solve so that we might bring more experience to bear on a
: solution?

I would agree that it _may_ be easier to modify the application involved,
to find some other way to meet the needs required, than to construct a
cipher that meets the conditions set forth.

That is not to say, though, that the problem of designing a cipher of that
type is not something of mathematical interest. Simply because it is hard,
it may contain interesting theoretical insights.

John Savard

: P = 16 bytes data
: Q = 16 bytes data

I think you're going to have to accept, in order to meet all your other
requirements, that the size of P and Q will have to be considerably larger
than just twice the size of p and q. Perhaps, say, 256 bytes of data, to
really have a chance of the cipher being secure.

John Savard

: Lisa Tang (lta...@yahoo.com) wrote:
: : P = 16 bytes data
: : Q = 16 bytes data

: I think you're going to have to accept, in order to meet all your other
: requirements, that the size of P and Q will have to be considerably larger
: than just twice the size of p and q. Perhaps, say, 256 bytes of data, to
: really have a chance of the cipher being secure.

I have thought more about the problem, and while the solution I have come
up with does need more than 16 bytes, it is not _too_ bad.

The method I describe uses a number of keys. They can be generated from
some single key using some type of stream cipher, and this is called a key
schedule.

It is based on the idea of a 4-of-8 code.

There are 70 possible combinations of bits of the form:

00001111
00011101
00011110
...
11101000
11110000

that is, where exactly four bits are 1 and four bits are 0.

Each of those can become an order-preserving cipher that takes two bits to
three bits; i.e., the combination

01011001

can be thought of as the cipher

00 -> 001
01 -> 011
10 -> 100
11 -> 111

where if the input is n,  the output is the position of the n-th 1 bit in
the code symbol.

As our first order-preserving step, the input p is changed to

(p, DES(p,k1))

k1 is the first 56 bits of key material that we use. Already, our input
has increased from 8 bytes to 16 bytes in size, and it will grow more.

Our second step is to take the first two bits of the result, and encipher
them using one of these 4-of-8 codes. What we do is to take the last 64
bits of the block, and put them in an accumulator on the side, and
encipher them again using k2. Some sort of checksum of the result is used
to pick one of the 70 possible 4-of-8 codes.

So after the second step, we have:

the first two bits of p, encrypted by a 4-of-8 code picked by
DES(DES(p,k1),k2)

the remaining 62 bits of p

DES(p,k1)

Now we keep repeating the step, but we nibble into the remaining parts of
p, so after the third step we have

the first two bits of p, encrypted by a 4-of-8 code picked by
DES(DES(p,k1),k2)

the next two bits of p, encrypted by a 4-of-8 code picked by
DES(DES(DES(p,k1),k2),k2)

the remaining 60 bits of p

DES(p,k1)

and you keep on going until the whole of p is converted from two-bit
portions to three-bit portions.

After this first layer of encryption, if one is presented with a P value,
one already is _somewhat_ uncertain about the p value that was its source.
But the uncertainty isn't really strong enough.

The result at this point is now 20 bytes long.

Starting with DES(p,k1), and this time encrypting it over and over again
with k3 to determine what you do, you take the 96 bits that begin the
block, and expand them to 127 bits by inserting 31 zero bits randomly.
This can be done, for example, by taking the remainder of
DES(DES(p,k1),k3) modulo 97 to pick where the first zero bit goes in,
taking the remainder of DES(DES(DES(p,k1),k3),k3) modulo 98 to pick where
the second zero bit goes in, and so on.

These 127 bits then have a 127-bit random value added to them, and this
value is another part of the key.

Order is still preserved, and the result is now 24 bytes long.

Now, using k4 instead of k2, use the same procedure as before to expand
the first 128 bits of the block to 192 bits.

You have a 32 byte block at the end of the process, and you can invert the
process, because DES(p,k1) is plainly visible, so you can start by
encrypting it by k4 repeatedly to find the 4-of-8 coding that you need to
reverse for each group of three bits to deal with.

Of course, you can just find p by decrypting the last 64 bits with k1 as
well. However, those last 64 bits could just as easily be DES(H(p),k1)
where H(p) is a one-way-hash of p, or they could just be 32 bits in
length, if deriving the intermediate values in the process from a 32 bit
seed is considered secure enough.

I won't say this process is *highly* secure, though. But it should indeed
create some degree of uncertainty about the value of p given P for an
adversary who hasn't captured *too* many valid (p,P) pairs to work from.

John Savard

: I have posted a similar question subjected "Randomly enlarge number with
: sequence preserved". With lot of help and response, I learn more about what
: I really need. Since there is some change in the requirement, I just like to
: start a new post.

I have come up with another idea.

I thought at first it could be used to enlarge 8 bytes to only 16, but it
would be very insecure that way.

The basic idea is that we find a way to generate, at random, a code that
takes the byte values 0 through 255 to other distinct values from 0 to 255
in a random order. Ways to do this from a key are given in the
descriptions of the Quadibloc ciphers on my web page, at

http://home.ecn.ab.ca/~jsavard/crypto/co0407.htm

Then once we have such a code, we can go through it, and see how many
stretches there are of numbers that are increasing. So we can make a code
that takes 8 bits to 16 bits and preserves order that looks like:

  0 ->   0 137
  1 ->   1  48
  2 ->   1  96
  3 ->   1 201
  4 ->   2  13

where the second byte is the byte in our random permutation, and the first
byte is increased by only the minimum amount needed to maintain order
preservation.

Then we look and see by how much the first byte of the code for 255 falls
short of 255. This lets us know how much freedom we have to increase the
first byte to randomize the code. We could just choose an overall offset,
or choose places at which to add 1 to the first byte of the code in that
place and all following places repeatedly.

Again, use a scrambling of the original p value as the source for picking
these codes somehow.

This has the advantage of spreading things over a wider area than a 4-of-8
code, but it leaves too much structure behind; this is why I think that
perhaps the two methods should be combined, even though this makes the P
values quite long.

One starts with (p,DES(p,k1)) again, and first replaces p by 16 bytes with
this method, and then expands the 16 bytes to in turn to 24 bytes, 32
bytes, and 48 bytes by the other process, to get a 56-byte result.

John Savard

I saw that one reason my previous suggestions required P to be much longer
than 16 bytes was because I was making a mistake.

In my methods, many values for each byte, particularly the first byte, are
not used. This is not good for security.

I have a better method now - and it takes 8 bytes to only 16 bytes as
well! But it may still not be perfect.

Using only the key, create (using some random method) 255 random numbers
from 0 to 2^64 which are in numerical order. The intent is to randomly
partition the space from 0 to 2^64-1 into 256 pieces. Just generating 255
random numbers and sorting them, for example, _may_ not give the ideal
distribution for this; this is a fine point which a mathematician could
perhaps answer, or which I will think of an answer for.

Now, then, given p, comparing it to those 255 numbers shows what the first
byte of the code for p is.

Using the key as input, as well as the value of the first byte of the
code, and the range that first byte corresponds to, now partition that
range into 256 pieces.

The using the key, the first two bytes of the code, and the range we are
now in, work out the partition for the next byte...

and do this eight times.

On average, each set of values for the first eight bytes will correspond
to one value, but some will be empty, and some will have multiple values.

But we have eight bytes left, so even if all the bytes went into one set
of pigeonholes, we can still preserve order and code everything!

Using the remaining range, and the eight bytes of the coded part as input,
work out a random multiplication factor and number to add to the value to
spread out the possible values over the 2^64 possibilities for the last
eight bytes.

Since that is a uniform spacing, there is insecurity if one has two (P,p)
pairs with the same first eight bytes, but it comes much closer to what
you are looking for than my previous suggestions. If you are willing to go
to 24 bytes, though, the chance of problems becomes much smaller.

John Savard

No algorithm that satisfies these properties can be very secure.
In particular, there will always be a trivial chosen-plaintext attack
to recover p given P using just O(log n) encryptions, if p is n bits long.

I don't think you're likely to find a secure algorithm with the
properties you want.  What are you really looking for?  What are you
trying to achieve with the algorithm f?  What is your application, really?
Maybe we can find a better way to solve your application.

Sorry, that should be O(n) encryptions, and I should have mentioned
that the algorithm is simply "binary search".

: No algorithm that satisfies these properties can be very secure.
: In particular, there will always be a trivial chosen-plaintext attack
: to recover p given P using just O(log n) encryptions, if p is n bits long.

: I don't think you're likely to find a secure algorithm with the
: properties you want.  What are you really looking for?  What are you
: trying to achieve with the algorithm f?  What is your application, really?
: Maybe we can find a better way to solve your application.

I agree with you that the order-preserving property places a severe limit
on the possible security, and that for just about any imaginable
application, there would be a better way of doing this.

However, I finally have come up with a solution that meets her
constraints.

For the 16 bytes of the final coded result, one proceeds as follows:

Given the key, one starts with the first byte, and produces a distribution
of the range of the input among the 256 possible coded byte values.

Then, when coding a particular value, or decoding a result with a
particular first byte, one works from the remaining range and the key
(suitably scrambled using the first byte actually used, so that all the
distributions used are different) to make a distribution of the remaining
range among the 256 possible coded byte values.

The nature of the distribution, however, changes with each byte.

For the first byte, the distribution will be made highly uneven so that
possibly just one value has almost all the range - but not necessarily.

So the probability that a 16-byte value beginning with 11101111 might be
an eight-byte value beginning with 000000000000 would NOT be impossibly
low, despite order being preserved. This is why the distribution has to
start out as having a tendency to be very uneven.

For the next few bytes, the distribution may just be random, or it may be
highly uneven - and it will be uneven in the case where in the preceding
bytes, the byte used happened to be the one that got most of the range.

Then, for the remainder of the first eight bytes, the distribution will
basically be a plain random one.

After the first eight bytes, the distribution will be constrained. Thus,
if a lot of values have been allocated to the particular combination of
the first eight bytes in use, the distribution for the ninth byte will be
constrained, so that no possible value covers more than 2^56
possibilities.

The limit for the tenth byte will be 2^48 possibilities for each value,
and so on. This ensures it will always be possible to give every input
value a unique code.

This is it; this is about as good a solution to the problem posed as is
possible. I do hope this wasn't a homework problem.

I know this may not be simple and explicit enough to be perfectly clear,
but if one is trying to do this, one's programmer had better know enough
math to be able to work from an outline at this level. Instead of
generating successive values, as I outlined in the similar proposal, one
should try to randomly generate how many of the possible values go in the
various slots, first by choosing between the desired distributions, and
then randomizing the order of the allocation to the 256 codes.

John Savard

news:cmV09.1424$0f2.380808@localhost...

I suspect it would prove extremely useful in the PKI arena as an
enhancement or alternative to D-H.

news:ai0ujh$sjd6@imsp212.netvigator.com...

Let's try this:

(1) Using your key to seed a PRNG, generate an array of 512 sixteen-bit
numbers.

(2) Sort the array in ascending order.  Scan the array and eliminate all
duplicates.  If there are not at least 256 sixteen-bit numbers left,
generate enough more random numbers to fill the array and repeat step
(2).

(3) Each time the function f(p,k) is called, ignore k and use p as the
subscript into the array generated in step (2).

(4) The inverse function F(P,K) can be computed any number of ways.  You
can do a binary search of the sorted sixteen-bit table looking for which
table entry p contains the value P.  You can create a reverse-lookup
table of 65536 entries, 256 of which contain valid p-values (the rest
can contain 0xFFFF or some such thing).

Does this meet your criteria?

YES> p = 8 bytes data
YES> q = 8 bytes data
YES> k = key
YES> K can be equal to k  or can be different from k
YES> F() can be equal to f() or can be different from f()
YES> P = 16 bytes data
YES> Q = 16 bytes data

YES> P = f(p, k)
YES> Q = f(q, k)
YES> 1. P < Q, for all p < q
YES> p = F(P, K)
YES> q = F(Q, K)
YES> 2. given know pair of (p, P), even with knowledge of
   functions (i.e. f(),F()), w/o knowledge of K, it is
   difficult to guess K
YES> 3. given some P and Q, even with knowledge of functions
   (i.e. f(), F()), w/o
   > knowledge of K, it is difficult to guess p, q
   >

I think this does what you asked-for.  Now, are you really sure that
what you asked-for is what you want? ;-)

[snip]

I don't understand why one uses '256 sixteen-bit numbers'.
According to OP, p has 8 bytes and P has 16 bytes!

M. K. Shen

news:ai0ujh$sjd6@imsp212.netvigator.com...

One possibility which formally meets the above criteria (but I suspect will
not meet the requirements of your application) is:

f(p, k) = p + HASH(k)
F(P, K) = P - HASH(K)

where HASH is a one way function with a normally distributed output, with
mean 2**127 and standard deviation perhaps 2**120, and thus has effectively
0 probability at 0 and at 2**128).  This is needed to get around the edge
conditions such as "if f(p, k)=0, then p=0".

I say that I suspect it doesn't meet the real criteria, because I suspect
criteria 2 really should be "given p, P,Q s.t. p=f(P,K) and P!=Q, it is
difficult to compute f(Q,K)".  Is something like this the correct criteria?
For that matter, what's the real problem you're trying to solve?

--
poncho

Could you elaborate how does your function f deliver
16 bytes with input p of 8 bytes? (How large is HASH(k)
and when p is added to it?) Thanks.

M. K. Shen

John E. Hadstate (jh113...@hotmail.com) wrote:

: I suspect it would prove extremely useful in the PKI arena as an
: enhancement or alternative to D-H.

Hmm. I can't quite see how that would work - my algorithm to do this is
very definitely a symmetric-key method.

I was thinking in terms of very pedestrian applications, such as a
smartcard telling you you have enough money to buy something without
revealing its price, or a case where you need monotonic serial numbers
which don't reveal the exact position of an item in the sequence (maybe
replacing old serial numbers or ID numbers that were compromised).

Perhaps some bizarre deadlock avoidance algorithm in a network which is
attempting to avoid traffic analysis.

John Savard

news:3D447BFC.ECE23B2B@t-online.de...

Bits, bytes, what's the difference ;-)

Seriously, I just flat misread the OP's specs.
I'm busted :-(

However, since my cipher (it is a substitution cipher, by the way) is
order-preserving, it could be applied byte-by-byte to the input to
transform 8 bytes into 16 bytes.  The rest of the conditions, including
order-preservation, will still be met.

Now, if the OP wants to get really kinky, she can recompute the
substitution table for each byte of input.  The cipher will begin to
look like dynamic substitution and will gain some strength at the cost
of a substantial performance penalty.

news:3D447BFC.ECE23B2B@t-online.de...

Bits, bytes, what's the difference ;-)

Seriously, I just flat misread the OP's specs.
I'm busted :-(

However, since my cipher (it is a substitution cipher, by the way) is
order-preserving, it could be applied byte-by-byte to the input to
transform 8 bytes into 16 bytes.  The rest of the conditions, including
order-preservation, will still be met.

Now, if the OP wants to get really kinky, she can recompute the
substitution table for each byte of input.  The cipher will begin to
look like dynamic substitution and will gain some strength at the cost
of a substantial performance penalty.

Egads!  Why would I ever want to do that?

Edward Elliott

: > I was thinking in terms of very pedestrian applications, such as a
: > smartcard telling you you have enough money to buy something without
: > revealing its price,

: Egads!  Why would I ever want to do that?

Yes, I have to count my pennies too... but presumably something
_analogous_ to that which didn't involve purchasing things with a risk of
pauperizing oneself could be the application. I'm just trying to be
comprehensible, not literal.

John Savard

A 'huge' difference I am afraid, if you think
practically. In place of '256 sixteen-bit numbers'
you would get what 'X Y-bit numbers' and in total how
much storage for that array? And you would at least
have quite some difficulties, if you attempt to
address the array in C on your PC, I suppose. (It
might not be feasible even with the current topmost
of the list of world's 500 supercomputers, I would
guess.)

M. K. Shen

Well assuming that these really are the only requirements to be met
(as opposed to actually requiring that it preserve order. The
following will work, and be secure.

primitive1 = AES, except top byte is bit-wise logically OR'd with
11111111 after the encryption
primitive2 = AES, except top byte is bit-wise logically AND'd with
00000000 after the encryption

Observe that primitive1 will always output something that looks like:
11111111XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Primitive2 will always output
00000000XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Now pad p and q with 0's at the front to make 128-bits
So primitive1(X) > primitive2(Y) for all X and Y.
Choose a random R, or two randoms Rs if you'd prefer it won't matter
as long as k and K are different
f(p, K, R) = p XOR primitive1(K, R)
F(q, k, R) = q XOR primitive2(k, R)

This will guarentee that P > Q for all, regardless of p <?> q. Again I
assume that you only care about P > Q being true when p > q, the other
cases don't matter.
           Joe

+---------------
| Edward Elliott (f...@bar.com) wrote:
| : > I was thinking in terms of very pedestrian applications, such as a
| : > smartcard telling you you have enough money to buy something without
| : > revealing its price,
|
| : Egads!  Why would I ever want to do that?
|
| Yes, I have to count my pennies too... but presumably something
| _analogous_ to that which didn't involve purchasing things with a risk of
| pauperizing oneself could be the application. I'm just trying to be
| comprehensible, not literal.
+---------------

To restate John's example in a way that may satisfy Edward:

Suppose you wanted your smartcard to be able to prove to a merchant
that your card has enough money on it to buy an item (or more to the
point, to shop in their store generally), *without* the merchant finding
out exactly how much you *do* have available...

-Rob

-----
Rob Warnock, 30-3-510           <r...@sgi.com>
SGI Network Engineering         <http://www.rpw3.org/>
1600 Amphitheatre Pkwy.         Phone: 650-933-1673
Mountain View, CA  94043        PP-ASEL-IA

[Note: aaanal...@sgi.com and zedwa...@sgi.com aren't for humans ]