Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think.com!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <25708:Nov1919:09:2590@kramden.acf.nyu.edu>
Date: 19 Nov 90 19:09:25 GMT
References: <235@smds.UUCP> <16709:Nov1113:56:2390@kramden.acf.nyu.edu> <36568@nigel.ee.udel.edu>
Organization: IR
Lines: 28

In article <36568@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes:
> Actually, for sorting to be linear in the number of bytes sorted, don't
> you need some opperation on the keys other than comparison?

Yes, you do. You need some sort of extraction.

> "I want you to sort this array of encrypted passwords into the same
> order as the user numbers they belong to. Since for security reasons I
> cannot reveal to your program the user number belonging to each
> password, I will provide a function "porder(A,B)" which returns true if
> the user number for password A comes before the user number for
> password B and false otherwise. Since the user number space is very
> sparse, this will not compromise security."

Algorithm R solves problem S. Now you say, ``For security reasons,
something that you do in algorithm R is not allowed. Therefore algorithm
R does not solve problem S.'' Yes, security is a problem---so you should
stick R inside the computing base that evaluates porder().

If comparing two keys is significantly less work than transforming them
into a dictionary-ordered form, then heapsort may indeed be faster than
radix sort. But this had better not be true for porder(). Otherwise your
encryption function is insecure.

If it is indeed impossible to transform keys into a dictionary-ordered
form, then radix sort does not apply.

---Dan