Cryptography-Digest Digest #889, Volume #12 Tue, 10 Oct 00 13:13:00 EDT
Contents:
Re: A new paper claiming P=NP (Jeremy Spinrad)
Re: Why trust root CAs ? ("Brian Hetrick")
Re: AES Runner ups (Runu Knips)
Re: The science of secrecy: Simple Substition cipher ("IanM")
Re: A new paper claiming P=NP (Mark William Hopkins)
Re: A new paper claiming P=NP (Mark William Hopkins)
Re: What is meant by non-Linear... (Anton Stiglic)
Re: FTL Computation (ca314159)
Re: Why trust root CAs ? ([EMAIL PROTECTED])
Re: On block encryption processing with intermediate permutations (Mok-Kong Shen)
Re: Quantized ElGamal (Anton Stiglic)
Re: A new paper claiming P=NP (David C. Ullrich)
Re: A new paper claiming P=NP (Rajarshi Ray)
Re: Why trust root CAs ? (Anne & Lynn Wheeler)
Re: A new paper claiming P=NP (Christian Bau)
Re: NIST RNG Tests ("Paul Pires")
US Bombe reports (Frode Weierud)
Re: NSA quote on AES ("Brian Gladman")
Re: A new paper claiming P=NP (Rajarshi Ray)
Rijndael implementations (lcs Mixmaster Remailer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jeremy Spinrad)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 10 Oct 2000 15:05:10 GMT
A couple of notes on the difficulty of reviewing a paper. First, recall that
reviewing a proof that P = NP is a completely thankless job, while the
author would gain great fame for a correct proof. Seems fair to make the
author do a little extra work to spare the reviewer some time.
>From my unfortunately considerable experience in refereeing incorrect papers,
it is more commonly the case that in incorrect claims of first polynomial time
algorithms for a problem, errors are in the correctness of the algorithm rather
than in proof of the time bound. Errors in time bound come most frequently from
pseudopolynomial algorithms, which are relatively easy to spot.
Errors also come up when a step is not completely specified; the author may
assume that something is easy to do, but is actually hard. This issue would be
caught if there was an actual program.
By the way, I certainly do not advocate creating a program for every algorithmic
paper submitted. Proving P = NP is a special case here. Basically, most people
will not believe that it is true, since too many false claims have been
disproved, and it behooves an author to do some extra work before the community
takes it seriously. I know that if I proved P = NP, I would be happy to do an
enormous amount of work to have it accepted; my reward would be very large for
the work put in.
Jerry Spinrad
------------------------------
From: "Brian Hetrick" <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Tue, 10 Oct 2000 11:16:02 -0400
<[EMAIL PROTECTED]> wrote ...
> Is there a chain of trust from any institution that I might trust,
> such as my bank, back to the root CAs ?
Trust in what way?
Suppose you have an X.509 certificate owned by, say, Amazon.com,
signed by, say, VeriSign. What this means is "VeriSign asserts that
when we signed this public key Amazon.com had the corresponding
private key." That is the _only_ thing it means.
Now, an implications of this is that if you can verify an electronic
signature with the public key, then it was signed with the private key
VeriSign asserted was once in the posession of Amazon.com. If you
trust Amazon.com not to lose control of its private key, then you can
conclude the signature was made by Amazon.com (whatever it means to
say a business entity "signed" something). If the key is being used
to set up a secure browser session, then you can conclude your browser
session is with Amazon.com rather than Joe's Discount Browser Session
Hijacking.
A certificate is not magic pixie dust that makes the computer world
safer or more wonderful than the real world. It is a means to prevent
an attack on a vulnerability unique to the computer world. In the
real world, I can look around me and know I'm in front of a real
physical store of the correct name. That's hard to do in a web
browser; we have certificates instead.
Now, none of this certificate complexity says Amazon.com is a
trustworthy business or will protect your personal information or
credit card data or will ship on time or will not defraud you. All it
says is your browser is actually talking with Amazon.com -- assuming a
number of things are true. One of the things that must be true is
that the identity assertions in the hierarchical chain are
"trustworthy" to assert identities. They do not need to be good
businesses, or to pay their bills, or to be kind to kittens and small
children -- just to correctly assert identities.
You don't need to trust the identity assertions if you don't want to.
If you decide not to trust VeriSign to assert identities, for example,
then remove its certificate from your browser, or modify the trust
parameters. (In Internet Exploder 5, it's Tools | Internet Options |
Content | Certificates | Trusted Root Certification Authorities;
highlight the certificate, and either press DELETE or click
"Advanced." Other browsers have similar methods.) If you have your
own opinion about the "chain of trust" when you visit a web site, show
the certificate and, if you want, modify the trust parameters for the
certificates in the issuing chain. (In Internet Explorer 5, it's File
| Properties | Certificates | Certification Path; highlight the
appropriate certificate, install it, and set the trust parameters you
want.)
If you trust your bank to assert VeriSign's identity, remove your
VeriSign root certificates, get your bank's certificate in a manner
you trust, and install the VeriSign certificate from your bank's
certificate into your browser -- assuming your bank's certificate is
rooted at VeriSign....
All the browser's pre-loaded certificates mean is "Microsoft (for
example) trusts these CAs to know their business." You don't have to.
If you don't, rip 'em out, or set their trust parameters.
------------------------------
Date: Tue, 10 Oct 2000 17:21:47 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: AES Runner ups
Sam Simpson wrote:
>
> Runu Knips <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> <SNIP>
> > Btw, another really good cipher is AFAIK CAST-128 which
> > didn't made it to the second round but is used, for
> > example, in GnuPG.
>
> CAST128 (AKA CAST5) is a 64-bit block /128-bit key cipher predating
> AES by several years and certainly is employed in GnuPG and NAI/PGP.
>
> I guess you mean CAST-256, which isn't (AFAIK) widely deployed at
> all...........
Ooops sorry my error.
------------------------------
From: "IanM" <[EMAIL PROTECTED]>
Subject: Re: The science of secrecy: Simple Substition cipher
Date: Tue, 10 Oct 2000 16:24:01 +0100
http://www.ics.uci.edu/~eppstein/cryptogram/
this java applet deciphers it with just one letter wrong
(by E.A. Joe)
------------------------------
From: [EMAIL PROTECTED] (Mark William Hopkins)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 10 Oct 2000 15:34:31 GMT
In article <[EMAIL PROTECTED]> "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
writes:
>Mark William Hopkins wrote:
>> Therefore, it should be fairly easy to spot the flaw in the paper. No
>> demo programs are needed.
>
>Hmmm. Assuming the conclusion. Useful technique that. ;-)
No, actually it's: asserting the 'conclusion' and refuting the assumption.
This is, of course, a valid form of argumentation when the assertion is
true. Very few people believe that it's false and that P = NP.
------------------------------
From: [EMAIL PROTECTED] (Mark William Hopkins)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 10 Oct 2000 15:40:48 GMT
In article <8rvb76$n5g$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Jeremy
Spinrad) writes:
>I know that if I proved P = NP, I would be happy to do an enormous amount of
>work to have it accepted; my reward would be very large for the work put in.
I don't think you fully realise the seriousness of the understatement you
just made. There is a $1,000,000 bounty out there for the first correct
resolution to this issue.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: What is meant by non-Linear...
Date: Tue, 10 Oct 2000 11:41:52 -0400
Tom St Denis wrote:
> Aw but in f(x) = ax + b the upper bits can be nonlinear.
Can you give an example to illustrate?
Anton.
------------------------------
From: ca314159 <[EMAIL PROTECTED]>
Crossposted-To: sci.astro,sci.physics.relativity,sci.math
Subject: Re: FTL Computation
Date: Tue, 10 Oct 2000 15:40:24 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> ca314159 wrote:
> >
> > If the projection of a spot of light can virtually move FTL
> > then so too can the projected images of a slide rule's slides.
> > The computation 'in effect', takes place FTL.
> >
>
> But the time between when you move the slide and you see
> the projection is still the round trip light travel time
> to the thing you're projecting the slide onto.
You're right; I/O is a bottleneck.
That's not my point though.
Whether you call this effect lighthouse, waterhose, headlight
or scissors... it can be used to do very interesting things.
I don't just think so, I know so.
>
> The real limitation is how fast you can transmit information.
>
First, one has to know what "information" is.
What's your definition ?
> John Anderson
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why trust root CAs ?
Date: Tue, 10 Oct 2000 15:41:09 GMT
In article <8rsrlp$2r5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Vernon Schryver) wrote:
> Note that in my view, all of those are nits. If you need to
authenticate
> an IP address--DNS name association (and sometimes you must), then the
> place to do it is in DNS, not in some other protocol that involves
third,
> fourth, and more parties. I think most (but not quite all) of what
> Verisign/Thawte is peddling snake oil. I consider the business
connection
> between Network Solutions and Verisign proof of their common nature.
I could associate with your claim on "snake oil" if all Versign was
doing was providing an encryption/authentication service that is
essentially already embedded with SSL; Or, Versign simply provided
services equivalent to a IP/DNS WHOIS lookup. However, Verisign
provides a service that goes well beyond what anyone currently does with
the existing tools. True, Verisign uses those same tools in providing
services. Just don't get the tools confused with the services that uses
the tools. Before Verisign issues a business certificate, Verisign
checks up on the legitamacy of the business, including checking up on
articles of incorporation, DUNS numbers, and assorted other information
that establishes the existence of a business. In essence, the
certificate tell me, the consumer, that a site meets the minimum
standards identified in Verisign's Certification Practices Statement.
In the world of digital signatures and Public/Private keys, it's easy to
lose focus on what service Verisign is really providing here.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Tue, 10 Oct 2000 18:11:54 +0200
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> > > Mok-Kong Shen wrote:
> [...]
> > > > Permutations are discrete entities. Nevertheless, one can
> > > > say that there are permutations that are close to one
> > > > other, i.e. neighbours. What if I use permutations that
> > > > are not the identity but close to it? Does it mean that
> > > > the job then becomes 'suddently' extremely easy as you
> > > > claimed?
> > >
> > > Please do not fabricate claims or quotes and attribute them to
> > > me.
> >
> > Is the following a genuine quote from a previous post of
> > yours or not???
>
> Of course, and it would take you mere seconds to
> confirm.
>
> > > > Olson:
> > > > | You specified a pseudo-random permutation. I wrote that a
> > > > | block with the properties that support the attack probably
> > > > | exists among about a thousand blocks. If the identity is
> > > > | one of the inter-round permutations, such a block will not
> > > > | exist.
> >
> > If the answer is 'no' please kindly say that and clearly.
> > If the answer is 'yes', then my response was the following
> > in my last post (which you however snipped):
> >
> > In practice it is not easy to obtain good PRNG and hence
> > good random permutations. To get bad ones, including the
> > identity, is rather simple. According to your previous
> > post, I could make one of the inter-round permutations to
> > be the identity and be immune to your attack. That's no
> > problem for me, if necessary. There being n rounds (cycles),
> > I can afford to have one inter-round permutation being
> > the special one, the identity.
>
> I don't see how it could possibly be unclear what scheme
> my attack applies to. The modified scheme is not relevant
> to the questions at issue.
Since I proposed my scheme, I naturally want it to be
useful, i.e. not being cracked. So, since you told the
way that prevents your attack to function, I modify it
accordingly so that it is immune to it. Why not, since
the modification is trivial??
>
> > So through this trivial modification (simply leaving out
> > one inter-round permutation, while maintaining the other
> > inter-round permutations as before) my scheme becomes
> > immune to your attack according to what is quoted from
> > you above exactly. Do you have anything to say to that
> > now??
>
> The FAQ says it well:
>
> If you don't have enough experience, then most likely
> any experts who look at your system will be able to find
> a flaw. If this happens, it's your responsibility to
> consider the flaw and learn from it, rather than just
> add one more layer of complication and come back for
> another round.
It suffices for me that you apparently don't have anything
to say to what I wrote above now.
M. K. Shen
==================================================
Was sich ueberhaupt sagen laesst, | Whatever can be said
laesst sich klar sagen; | can be clearly said;
und wovon man nicht reden kann, | and silence must be kept
darueber muss man schweigen. | on what one cannot tell.
|
Ludwig Wittgenstein | (a translation)
(1889 - 1951)
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Quantized ElGamal
Date: Tue, 10 Oct 2000 11:57:05 -0400
> An immediate way to prevent timing attacks is to make all operations
> take exactly the same amount of time.
> I believe that's what's meant by "quantized."
And another way of preventing the attack is to use
blinding schemes (such as first described by Chaum
in a different context), this solution was present
in Kocher's paper.
So instead of directly computing m^a mod p, where a
is the secret, you first blind your secret exponent:
Choose random k, compute k*m mod p and k^(-a) mod p
then instead of directly computing m^a mod p, compute
tmp <- (k*m)^a mod p
then compute tmp*k^(-a) mod p, the final result is
m^a mod p. The attacker doesn't know what k is, thus
doesn't know what k*m is, nor what k^(-a).
Kocher describes a way to "recycle" k, you can simply
square the old value of k to obtain the new one (this
is cheaper than choosing a new random value all the time).
See the paper from Kocher.
-- Anton
------------------------------
From: David C. Ullrich <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 15:53:06 GMT
In article <8rvb76$n5g$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jeremy Spinrad) wrote:
> A couple of notes on the difficulty of reviewing a paper. First,
recall that
> reviewing a proof that P = NP is a completely thankless job, while the
> author would gain great fame for a correct proof. Seems fair to make
the
> author do a little extra work to spare the reviewer some time.
>
> From my unfortunately considerable experience in refereeing incorrect
papers,
> it is more commonly the case that in incorrect claims of first
polynomial time
> algorithms for a problem, errors are in the correctness of the
algorithm rather
> than in proof of the time bound.
Ah, didn't realize that was the sort of error you were
referring to. Yes of course an actual working program would
be a help with that, and yes certainly someone claiming something
like this should be willing to help to that extent.
My only point was that observing the running time for
n < 1000000000 does not _prove_ anything about whether
the algorithm is actually polynomial time or not. This
is so obvious that probably people thought I must have
been claiming more than that (but the post I originally
replied to seemed to be implying that we _could_ verify
that something ran in polynomial time "empirically".)
> Errors in time bound come most
frequently from
> pseudopolynomial algorithms, which are relatively easy to spot.
>
> Errors also come up when a step is not completely specified; the
author may
> assume that something is easy to do, but is actually hard. This issue
would be
> caught if there was an actual program.
Absolutely - again, I didn't realize that was the sort
of error you were talking about.
> By the way, I certainly do not advocate creating a program for every
algorithmic
> paper submitted. Proving P = NP is a special case here. Basically,
most people
> will not believe that it is true, since too many false claims have
been
> disproved, and it behooves an author to do some extra work before the
community
> takes it seriously. I know that if I proved P = NP, I would be happy
to do an
> enormous amount of work to have it accepted; my reward would be very
large for
> the work put in.
Like if you were claiming you could prove Fermat's Last
Theorem you'd be willing to define the terms you used, eh?
(Sorry, wrong thread.)
> Jerry Spinrad
>
--
Oh, dejanews lets you add a sig - that's useful...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Rajarshi Ray <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 16:14:57 GMT
"David C. Ullrich" wrote:
>
> On Tue, 10 Oct 2000 00:34:56 +0300, Stas Busygin
> <[EMAIL PROTECTED]> wrote:
>
> >"David C. Ullrich" wrote:
> >>
> >> On Mon, 09 Oct 2000 04:47:22 GMT, Rajarshi Ray <[EMAIL PROTECTED]>
> >> wrote:
> >>
> >> [...]
> >> >Is it not possible to implement the presented algorithm and try it out
> >> >on examples to see the growth rate, just as a preliminary check?
> >>
> >> No. Suppose that a(n) is a sequence of integers and
> >> a(n) = 2^(2^(^n)) for all n less than 10^(10^10). Does a(n)
> >> have polynomial growth?
> >The complexity of the algorithm is bounded as O(n^6) by the author.
>
> ??? I was talking in general, not referring to the specific
> algorithm that started all this.
Perhaps Mr. Busygin is restating the proposed algorithm's complexity
because just doesn't believe that O(n^6) bounds could hide monstrosities
like the one you suggested ?? That would have been one of my initial
reactions, I guess.
- Rajarshi
--
"The most incomprehensible thing about the universe is
that it is comprehensible."
- Albert Einstein
------------------------------
Subject: Re: Why trust root CAs ?
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Tue, 10 Oct 2000 16:20:10 GMT
Daniel James <[EMAIL PROTECTED]> writes:
> Most of the certificates in use today associate a public key with an identity
> that is expressed in terms of a person's name and address. X.509 rather
> presupposes that that's the sort of thing people will want to do when it sets
> out the fields that can exist in a DName. It doesn't really have to be that
> way - a certificate needs /something/ to identify the owner, but that
> something doesn't have to contain a name and address as long as it's unique to
majority of the certificate use today is the SSL domain name server
certificate (aka HTTPS or secure web), possibly >95% all all instances
where an event occurs where a certificate is authenticating ... and
possibly 99.99999999% of the casess where a client is authenticating a
sever.
The SSL domain name server certificate associates the public key and
the host name or domain name. The client checks the name in the
certificate against the web address.
The authoritative resource for domain name ownership is the domain
name infrastructure ... which CA's have to rely on when authenticating
a request for a SSL domain name server certificate.
--
Anne & Lynn Wheeler | [EMAIL PROTECTED], finger for pgp key
http://www.garlic.com/~lynn/
------------------------------
From: [EMAIL PROTECTED] (Christian Bau)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 17:30:21 +0100
In article <8rve0u$8dn$[EMAIL PROTECTED]>, David C. Ullrich
<[EMAIL PROTECTED]> wrote:
> Like if you were claiming you could prove Fermat's Last
> Theorem you'd be willing to define the terms you used, eh?
> (Sorry, wrong thread.)
Defining the terms just makes it so much harder to claim you have a proof...
Now serious: One problem that remains if you implement the algorithm is this:
You implement the algorithm. You produce a sequence of test cases, run the
test cases and check the output and the time needed by the algorithm. The
times indicate that an execution time of O (n^6) might be correct (of
course you cannot be sure of this, but you could make an educated guess).
Now the problem: If you test the algorithm with a problem that takes 24
hours to run, and it comes up with what it claims is a minimal set of
cliques, how could you prove that the algorithm is wrong? If the problem
is indeed NP-complete, there might be no way that you can ever find a
smaller set of cliques in a reasonable amount of time, even if one exists.
If this algorithm takes 24 hours on my computer to find a smallish but not
minimal set of cliques covering a graph, then there might be no algorithm
that will find a smaller set in the next thousand years.
Of course you could construct problems where you know the solution to
start with. But then it would be possible that the algorithm is designed
so that it will find the solutions for these cases and not for others.
For example, if you take the complement of any planar graph, then the
algorithm should always find a set of four cliques covering that
complement, and for some graphs find a set of three or fewer cliques. If
the algorithm ever ends with five cliques, it is wrong. However, if it
produces a set of four cliques, proving that this set is not minimal is
NP-complete.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: NIST RNG Tests
Date: Tue, 10 Oct 2000 09:39:15 -0700
<[EMAIL PROTECTED]> wrote in message news:8runi9$maq$[EMAIL PROTECTED]...
> I have actually compiled the code on a Sun computer running the Solaris
> OS. I was hoping maybe that version would work properly. I have run it
> on some data but i can't check it against anything.
>
> The test data mentioned in the user documentation provided by NIST
> doesn't seem to be present when i unpack the compressed files (sts.tar &
> sts.data.tar).
>
> I will email the implementors to see if they can provide me with test
> data.
>
> Brice.
>
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >
> > [EMAIL PROTECTED] wrote:
> >
> > > I have finally managed to compile the new NIST Random Number
> Generator
> > > tests. However, i don't have any data to make sure the code does
> what
> > > it's supposed to do. Could anyone supply me with some data they have
> > > used and then i could compare my results with theirs?
> >
> > As discussed recently, the package could have some problems
> > on PC. Please contact the implementors at NIST and let us
> > know that the suite runs correctly on PC and about the
> > checks you mentioned.
A buddy helped me out and I have a copy copiled to run under Windows
I have not had time to work with it yet (work intrudes). NIST could have
specified a simple, concise confidence check since they opted not to
release compiled and verified code. I hope to be back at it later this
week and will advise on what I find.
Paul
> >
> > M. K. Shen
> >
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Frode Weierud)
Subject: US Bombe reports
Date: 10 Oct 2000 16:30:33 GMT
Reply-To: [EMAIL PROTECTED]
You receive this message because you are on a Mailing List related to
cryptography or because you have previously shown an interest in the
electronic publication of "Turing's Treatise on Enigma" also called the
"Prof's Book".
The Editors of "Turing's Treatise on Enigma" have now released two
documents dealing with the US Navy Bombe. The documents which have
been written by Joseph Desch, NCR, and Alan Turing are:
Joseph Desch, "Memo of Present Plans for an Electro-Mechanical Analytical
Machine"
and
Alan M. Turing, "Visit to National Cash Register Corporation of Dayton,
Ohio".
Both documents are available from my Turing Web page at:
http://frode.home.cern.ch/frode/crypto/Turing/index.html
Or directly from the US Bombe page at:
http://frode.home.cern.ch/frode/crypto/Turing/USBombe.html
I should also like to draw you attention to the recent article on Joseph
Desch, NCR and the US Bombes which appeared in the July / September 2000
issue of the IEEE Annals of the History of Computing. A full reference and
a link to the abstract is available on the US Bombe page.
Frode
--
Frode Weierud Phone : +41 22 7674794
CERN, SL, CH-1211 Geneva 23, Fax : +41 22 7679185
Switzerland E-mail : [EMAIL PROTECTED]
WWW : home.cern.ch/frode/
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: NSA quote on AES
Date: Tue, 10 Oct 2000 17:40:20 +0100
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Brian Gladman <[EMAIL PROTECTED]> wrote:
>
> : The point at which cryptographic systems are broken by breaking the
> : algorithms used are now in the past [...]
>
> I doubt this is true.
I am not suggesting that this is true for all algorithms - clearly it won't
be true if a bad choice of algorithm is made.
I was making the assumption that the algorithm chosen is one of a number of
well established modern algorithms such as, for example, the AES finalists.
Brian Gladman
------------------------------
From: Rajarshi Ray <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 17:00:27 GMT
"David C. Ullrich" wrote:
>
> In article <8rvb76$n5g$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Jeremy Spinrad) wrote:
> > A couple of notes on the difficulty of reviewing a paper. First,
> recall that
> > reviewing a proof that P = NP is a completely thankless job, while the
> > author would gain great fame for a correct proof. Seems fair to make
> the
> > author do a little extra work to spare the reviewer some time.
> >
> > From my unfortunately considerable experience in refereeing incorrect
> papers,
> > it is more commonly the case that in incorrect claims of first
> polynomial time
> > algorithms for a problem, errors are in the correctness of the
> algorithm rather
> > than in proof of the time bound.
>
> Ah, didn't realize that was the sort of error you were
> referring to. Yes of course an actual working program would
> be a help with that, and yes certainly someone claiming something
> like this should be willing to help to that extent.
>
> My only point was that observing the running time for
> n < 1000000000 does not _prove_ anything about whether
> the algorithm is actually polynomial time or not. This
> is so obvious that probably people thought I must have
> been claiming more than that (but the post I originally
> replied to seemed to be implying that we _could_ verify
> that something ran in polynomial time "empirically".)
> [snip]
No, all I meant was that an implementation _could_ be useful in giving
support to the algorithm's polynomial complexity, if it was true. So I
agree that there are quite a few caveats for this to be useful, and if
the algorithm is very difficult to implement it may not be worth the
effort after all.
- Rajarshi
--
"The most incomprehensible thing about the universe is
that it is comprehensible."
- Albert Einstein
------------------------------
Date: 10 Oct 2000 17:00:16 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Rijndael implementations
What is the intellectual property status of the Rijndael
implementations at the NIST web site?
http://csrc.nist.gov/encryption/aes/round2/r2algs-code.html#Rijndael
It is known that the algorithm itself is public domain, but what about
the implementations (a separate issue)? Is this source code free for
commercial use?
Names appearing on the C implementations include Paulo Barreto, Antoon
Bosselaers & Vincent Rijmen. There is no IP statement in the source
files; no claim of copyright, no explicit release to the public domain.
Rijmen is of course one of the creators of Rijndael, and his staements
may have publicly disclaimed his rights, but what about the others?
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
