The old Google Groups will be going away soon, but your browser is incompatible with the new version.
encryption algorithm preserve order
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 Messages 1 - 25 of 43 Newer >

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jul 28 2002, 10:26 am
Newsgroups: sci.crypt
From: "Lisa Tang" <lta...@yahoo.com>
Date: Sun, 28 Jul 2002 22:21:18 +0800
Local: Sun, Jul 28 2002 10:21 am
Subject: encryption algorithm preserve order
Hi,

I have posted a similar question subjected "Randomly enlarge number with
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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 11:08 am
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Sun, 28 Jul 2002 15:08:52 GMT
Local: Sun, Jul 28 2002 11:08 am
Subject: Re: encryption algorithm preserve order

Lisa Tang (lta...@yahoo.com) wrote:

: 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

John Savard

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 11:52 am
Newsgroups: sci.crypt
Date: Sun, 28 Jul 2002 11:52:19 -0400
Local: Sun, Jul 28 2002 11:52 am
Subject: Re: encryption algorithm preserve order

"Lisa Tang" <lta...@yahoo.com> wrote in message

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

> Hi,

> I have posted a similar question subjected "Randomly enlarge number
with
what
> I really need. Since there is some change in the requirement, I just
like to
> start a new post.

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?

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 12:01 pm
Newsgroups: sci.crypt
From: Mok-Kong Shen <mok-kong.s...@t-online.de>
Date: Sun, 28 Jul 2002 17:58:45 +0200
Local: Sun, Jul 28 2002 11:58 am
Subject: Re: encryption algorithm preserve order

Lisa Tang wrote:

[snip]
> 1. P < Q, for all p < q

[snip]

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

M. K. Shen

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 12:55 pm
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Sun, 28 Jul 2002 16:55:36 GMT
Local: Sun, Jul 28 2002 12:55 pm
Subject: Re: encryption algorithm preserve order

: 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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 12:59 pm
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Sun, 28 Jul 2002 16:59:47 GMT
Local: Sun, Jul 28 2002 12:59 pm
Subject: Re: encryption algorithm preserve order
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.

John Savard

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 2:08 pm
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Sun, 28 Jul 2002 18:08:57 GMT
Local: Sun, Jul 28 2002 2:08 pm
Subject: Re: encryption algorithm preserve order
jsav...@ecn.ab.ca wrote:

: 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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 2:25 pm
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Sun, 28 Jul 2002 18:25:14 GMT
Local: Sun, Jul 28 2002 2:25 pm
Subject: Re: encryption algorithm preserve order
Lisa Tang (lta...@yahoo.com) wrote:

: I have posted a similar question subjected "Randomly enlarge number with
: 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

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 3:56 pm
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Sun, 28 Jul 2002 19:56:30 GMT
Local: Sun, Jul 28 2002 3:56 pm
Subject: Re: encryption algorithm preserve order
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

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 4:57 pm
Newsgroups: sci.crypt
From: d...@mozart.cs.berkeley.edu (David Wagner)
Date: Sun, 28 Jul 2002 20:57:42 +0000 (UTC)
Local: Sun, Jul 28 2002 4:57 pm
Subject: Re: encryption algorithm preserve order

Lisa Tang wrote:
>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 = f(p, k)
>Q = f(q, k)

>1. P < Q, for all p < q

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 5:21 pm
Newsgroups: sci.crypt
From: d...@mozart.cs.berkeley.edu (David Wagner)
Date: Sun, 28 Jul 2002 21:21:45 +0000 (UTC)
Local: Sun, Jul 28 2002 5:21 pm
Subject: Re: encryption algorithm preserve order

David Wagner wrote:
>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.

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 5:30 pm
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Sun, 28 Jul 2002 21:30:49 GMT
Local: Sun, Jul 28 2002 5:30 pm
Subject: Re: encryption algorithm preserve order

David Wagner (d...@mozart.cs.berkeley.edu) wrote:

: 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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 6:15 pm
Newsgroups: sci.crypt
Date: Sun, 28 Jul 2002 18:15:04 -0400
Local: Sun, Jul 28 2002 6:15 pm
Subject: Re: encryption algorithm preserve order

<jsav...@ecn.ab.ca> wrote in message

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 6:54 pm
Newsgroups: sci.crypt
Date: Sun, 28 Jul 2002 18:53:30 -0400
Local: Sun, Jul 28 2002 6:53 pm
Subject: Re: encryption algorithm preserve order

"Lisa Tang" <lta...@yahoo.com> wrote in message

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).

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? ;-)

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 7:22 pm
Newsgroups: sci.crypt
From: Mok-Kong Shen <mok-kong.s...@t-online.de>
Date: Mon, 29 Jul 2002 01:19:24 +0200
Local: Sun, Jul 28 2002 7:19 pm
Subject: Re: encryption algorithm preserve order

> 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).

[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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 7:32 pm
Newsgroups: sci.crypt
From: "Scott Fluhrer" <sfluh...@ix.netcom.com>
Date: Sun, 28 Jul 2002 16:18:51 -0700
Local: Sun, Jul 28 2002 7:18 pm
Subject: Re: encryption algorithm preserve order

Lisa Tang <lta...@yahoo.com> wrote in message

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 8:10 pm
Newsgroups: sci.crypt
From: Mok-Kong Shen <mok-kong.s...@t-online.de>
Date: Mon, 29 Jul 2002 02:08:48 +0200
Local: Sun, Jul 28 2002 8:08 pm
Subject: Re: encryption algorithm preserve order

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 8:12 pm
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Mon, 29 Jul 2002 00:12:33 GMT
Local: Sun, Jul 28 2002 8:12 pm
Subject: Re: encryption algorithm preserve order

: 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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 9:03 pm
Newsgroups: sci.crypt
Date: Sun, 28 Jul 2002 21:02:31 -0400
Local: Sun, Jul 28 2002 9:02 pm
Subject: Re: encryption algorithm preserve order

"Mok-Kong Shen" <mok-kong.s...@t-online.de> wrote in message

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 9:03 pm
Newsgroups: sci.crypt
Date: Sun, 28 Jul 2002 21:02:31 -0400
Local: Sun, Jul 28 2002 9:02 pm
Subject: Re: encryption algorithm preserve order

"Mok-Kong Shen" <mok-kong.s...@t-online.de> wrote in message

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 28 2002, 10:24 pm
Newsgroups: sci.crypt
From: Edward Elliott <f...@bar.com>
Date: Mon, 29 Jul 2002 02:24:04 GMT
Local: Sun, Jul 28 2002 10:24 pm
Subject: Re: encryption algorithm preserve order

jsav...@ecn.ab.ca 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?

Edward Elliott

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 29 2002, 12:57 am
Newsgroups: sci.crypt
From: jsav...@ecn.ab.ca ()
Date: Mon, 29 Jul 2002 04:58:07 GMT
Local: Mon, Jul 29 2002 12:58 am
Subject: Re: encryption algorithm preserve order
Edward Elliott (f...@bar.com) wrote:
: jsav...@ecn.ab.ca 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.

John Savard

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 29 2002, 2:31 am
Newsgroups: sci.crypt
From: Mok-Kong Shen <mok-kong.s...@t-online.de>
Date: Mon, 29 Jul 2002 08:29:46 +0200
Local: Mon, Jul 29 2002 2:29 am
Subject: Re: encryption algorithm preserve order

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
might not be feasible even with the current topmost
of the list of world's 500 supercomputers, I would
guess.)

M. K. Shen

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 29 2002, 4:18 am
Newsgroups: sci.crypt
From: ashw...@msn.com (Joseph Ashwood)
Date: 29 Jul 2002 01:18:36 -0700
Local: Mon, Jul 29 2002 4:18 am
Subject: Re: encryption algorithm preserve order

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 29 2002, 4:47 am
Newsgroups: sci.crypt
Followup-To: sci.crypt
From: r...@rigden.engr.sgi.com (Rob Warnock)
Date: 29 Jul 2002 08:47:06 GMT
Local: Mon, Jul 29 2002 4:47 am
Subject: Re: encryption algorithm preserve order
<jsav...@ecn.ab.ca> wrote:

+---------------
| Edward Elliott (f...@bar.com) wrote:
| : jsav...@ecn.ab.ca 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 ]