Cryptography-Digest Digest #886, Volume #11 Mon, 29 May 00 13:13:01 EDT
Contents:
Re: Math problem (P=NP) prize and breaking encryption ("Scott Fluhrer")
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Peter G. Strangman)
Re: Hill's algorithm (Mok-Kong Shen)
Re: Math problem (P=NP) prize and breaking encryption ("Will Critchlow")
Re: Math problem (P=NP) prize and breaking encryption (Boris Kolar)
Re: encryption without zeros (Tim Tyler)
Re: $100 Code Challenge (jungle)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May ("Anarchist Lemming")
Re: $100 Code Challenge (jungle)
Re: Why encrypt email... (jungle)
Re: Traffic Analysis Capabilities ("Trevor L. Jackson, III")
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Dave Howe)
Re: Smart TC1 optimizations? (tomstd)
Re: Smart TC1 optimizations? (tomstd)
Re: encryption without zeros ("Scott Fluhrer")
Re: encryption without zeros (zapzing)
Re: Math problem (P=NP) prize and breaking encryption ("Scott Fluhrer")
Re: Help break SNAPPY (David A. Wagner)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: Mon, 29 May 2000 05:24:40 -0700
Axel Lindholm <[EMAIL PROTECTED]> wrote in message
news:yosY4.2186$[EMAIL PROTECTED]...
> "root" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Hi;
> >
> > In the paper last week there was an article about 7 math
> > problems for the 21st century. One of them (P = NP) was
> > supposed to allow easy breaking of encryption.
> >
> > I went to the site (www.claymath.org) and looked at the
> > problem description. They suggested that if someone could
> > solve a problem like Hamilton Circuit (path through nodes
> > visiting each one only once, ending at starting point), then
> > the safety of encryption is gone.
> >
> > Is this hype? Would it still take a lot of work? How would
> > someone use a solution for Hamilton Circuit to break RSA
> > for instance?
> >
> > I'm certainly not an expert in encryption, but I was curious
> > how such an unrelated problem could have anything to do with
> > breaking encryption.
> >
> > Thanks,
> >
> > stan
> >
>
> There are, today, 2 categorys of problems. P and NP. To understand why RSA
> gets useless we look into what category the RSA problem belongs to. It is
> believed that factoring huge numbers into huge primeparts is NPC (NP
> complete).
Actually, it is generally believed not to be the case (not that it really
matters whether anyone believes it or not -- it is or it isn't, and no one
can prove it one way or the other).
Two reasons why it is generally believed not to be the case:
- It would imply the two sets NP and coNP are the same. There do appear to
be problems that are in NP and not in coNP (the entire set NPC, for
example).
- All known algorithms to solve known NPC problems require exponential time.
Factorization is known to that subexponential time (and would imply
subexponential solutions to all NP problems).
>
> What is NPC then?
> These are the problems that we don't know how to solve quick, the only
> algorithms we know to solve these type of problems have so called
> exponential worst-case complexity. This means that there is no way to
> calculate the solution, but you can check if a guessed solution is correct
> in polynomial time (which is VERY bad). This tells us that NPC actually is
> part of the NP even though all NP problems doesn't have to have worst-case
> complexity.
Actually, a problem in NPC has the additional property that, if you can
solve it quickly (say, you have a magic box, aka oracle), then you can solve
*any* problem in NP quickly (here, quickly == in polynomial time).
And, to answer the OP, yes, Hamilton Circuit is known to be NPC, and so,
yes, it is known that, if you can solve that quickly, you can solve any
problem in NP, including RSA, quickly.
And, as other posters have pointed out, the definition of quickly might be
N**10000000, which is certainly polynomial, but might as well be the halting
problem for practical purposes...
--
poncho
------------------------------
From: Peter G. Strangman <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Mon, 29 May 2000 12:44:20 +0100
Reply-To: [EMAIL PROTECTED]
On Mon, 29 May 2000 10:58:09 +0000, [EMAIL PROTECTED] (David
Boothroyd) wrote:
> It was not huge. Since 1983 Labour manifestos have not been huge. However
> it is not the job of the manifesto to include the complete range of
> policies the party intends to introduce.
Yes it is. Anything less is dishonest. The only thing
a voter has to go on is the manifesto. It is the party's
declaration of what it intends to do. Failing to state
in the manifesto something as important as this shows,
quite clearly, that the party had grave doubts about
its prospects of being elected were it known that it
intended introducing such draconian legislation.
Doing something which is not in the manifesto is just
as deceitful as failing to fulfil promises which are
in it.
--
Peter G. Strangman | Wer weiss was die wohl glauben,
[EMAIL PROTECTED] | Die uns zum Glauben schrauben?
http://www.adelheid.demon.co.uk | (Friedrich von Logau)
XLIV-VII-DCCCII-CCXII-DCCCXXXI |
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Hill's algorithm
Date: Mon, 29 May 2000 14:59:48 +0200
Mark Wooding wrote:
> However, what Mok-Kong Shen doesn't seem to understand is the difference
> between a matrix multiplication as a cipher by itself, which is what
> Hill did, and as a component in a modern block cipher.
>
> Use of a matrix multiplication as a component in a block cipher is not
> Hill's cipher, just as use of modular addition as a component in a block
> cipher isn't Caesar's cipher.
You are adding words into other person's sentences. I said 'Hill's method'
(without qualification), so it refers to Hill's (original) method.
M. K. Shen
------------------------------
From: "Will Critchlow" <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: Mon, 29 May 2000 14:20:45 +0100
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:8gtocv$ieh$[EMAIL PROTECTED]...
> - It would imply the two sets NP and coNP are the same. There do appear
to
> be problems that are in NP and not in coNP (the entire set NPC, for
> example).
>
I understand what NP is (checkable in polynomial time) and (I think) what
NPC is (solvable only in exponential time), but what is coNP?
Thanks
W
--
========================================
B5 New Court, St. John's College
Cambridge. CB2 1TP
01223 522561
ICQ: 51747953
========================================
------------------------------
From: Boris Kolar <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: Mon, 29 May 2000 14:40:54 +0200
Scott Fluhrer wrote:
> Boris Kolar <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> >
> > David Blackman wrote:
> >
> > > Scott Contini wrote:
> > > >
> > >
> > > > Here's my 2 cents:
> > > >
> > > > Factoring is certainly not NP-complete (though a proof of this
> > > > does not exist). We can factor in sub-exponential time, but the
> > > > fastest algorithms for solving general NP-complete problems take
> > > > exponential time.
> > > >
> > > > Scott
> > >
> > > I think there is a proof that if factoring is NP-complete, then either
> > > P=NP, or the extended Riemann hypothesis fails. I vaguely remember this
> > > is referenced in Garey and Johnson (but i've lost my copy). A lot of
> > > people would consider this to prove that factoring is not NP-complete,
> > > although technically it is not quite such a proof.
> > >
> > > It hinges on factoring being (almost certainly) in co-NP.
> >
> > Factoring is in fact in the intersection of NP and co-NP.
> To make this correct statement more explicit, both these decision problems
> have polynomial verifiable proofs:
>
> Given two integers n and a, does there (not) exist integers b>1, c such
> that b*c=n and b<a
>
> In the positive case, a proof can consist of (b, c)
>
> In the negative case, a proof can consist of the factorization of n, along
> with primality proofs of all the factors.
>
> > All problems that are relevant to public-key cryptography are there.
> Question: is that true for all known public-key cryptosystems, or is that
> known to be inherent to public-key cryptography?
My statement was perhaps too strong. All popular problems for public-key
cryptography (such as factoring, discrete logarithm) are in NP and co-NP. There
may be a class of probabilistic public-key cryptography problems (such as
lattice reduction,...) that may be in NP and not in co-NP. Of course, the
following problems are still open:
- NP =? co-NP
- NP _and_ co-NP =? P
>
>
> > The problem:
> > NP and co-NP =? P
> > is even more important, than P =? NP. It's widely believed, that the
> answer
> > is NO (the NO answer would also imply P /= NP).
> >
> > Finding a problem, that is (NP and co-NP)-complete, would also be very
> > important for cryptography.
>
> Actually, I didn't think we knew of a problem that was known to be both NP
> and co-NP, but not P, even if you made the initial assumption that NP!=coNP
>
> --
> poncho
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Reply-To: [EMAIL PROTECTED]
Date: Mon, 29 May 2000 14:31:31 GMT
zapzing <[EMAIL PROTECTED]> wrote:
: rick2 <[EMAIL PROTECTED]> wrote:
:> lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
:> > Rick - You could use a regular encryption function like triple DES,
:> > but if you get an output block which has a zero byte in it, run that
:> > block through the encryption function again, and repeat until you
:> > don't get any zeros.
This proceedure may not always terminate :-(
:> > DES uses 64 bit (8 byte) data, so the chances of getting a block
:> > with a zero is 8/256 or 1/32, so you won't have to repeat the iteration
:> > very often [...]
:> >
:> > To decrypt, do the same thing: decrypt the data block, and if it
:> > comes out with a zero, decrypt it again. This assumes your input doesn't
:> > have any zero bytes either, so that the decryption can recognize
:> > when it is through.
:>
:> Excellent idea! [...]
: That really was an excellent idea!
It strikes me as of rather limited use ;-| Apart from the potential for
infinite loops, instead of removing 0s from the output, you now have to
remove them from the input.
If you *don't* have to be able to handle arbitrary inputs it might
nearly work - but otherwise you've rather pointlessly moved the problem
around to a different position.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ This tagline no verb.
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: $100 Code Challenge
Date: Mon, 29 May 2000 10:41:23 -0400
Jeff Hamilton wrote:
>
> You know, it's people like you who have no clue how to even begin
> Cryptanalysis. You know, why don't you try to do something other than make
> stupid comments. I think his challenge is valid. Just as mine was. In fact
> I'm suprised you didn't knock my challenge.
do you call $100 a challenge ?
------------------------------
From: "Anarchist Lemming" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Mon, 29 May 2000 15:42:47 +0100
"David Boothroyd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <8gs8pa$hf5$[EMAIL PROTECTED]>, "Anarchist Lemming"
> <[EMAIL PROTECTED]> wrote:
> > "David Boothroyd" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > The proposals in the Bill are exactly the same as the ones Labour
> > suggested
> > > before the election so there really isn't anything for anyone to get
> > > worked up about. The Conservatives were planning mandatory key escrow.
> >
> > Wrong. We have every right to get worked up. I wasn't old enough to vote
in
> > the last election (not that I would have) and if it becomes law I could
be
> > facing up to 2 years imprisonment.
>
> The answer is simple: Don't break the law.
>
> > Just because they have an electoral "mandate" doesn't mean it's useless
> > to fight against this kind of legislation. Remember, we stopped the Poll
> > Tax.
>
> I thought you said you were too young. The Poll Tax was replaced because
> Conservative MPs realised it was too unpopular. The idea that the police
> being able to demand that encrypted data (about which they have a
reasonable
> suspicion) be decrypted is in some way unreasonable is absurd.
Well you could keep arguing that until the UK becomes a police state. That's
the way we're heading with the RIP Bill and the Terrorism Bill. The only
effective method to resist tyrannical government is mass civil disobedience.
Also I really think this is irrelevant, but I was at the Poll Tax demo.
Lemming
www.hellnet.org.uk
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: $100 Code Challenge
Date: Mon, 29 May 2000 11:02:43 -0400
are you kidding ?
do you like to encourage some homeless people for this COMPETITION ?
[EMAIL PROTECTED] wrote:
>
> The following is a message encoded using a new routine I have designed.
> The text is a written message in English.
next time do in arabic, that way I could be participating in it ...
> In order to test just how
> strong the encryption is, I have posted it here for anyone interested
> to try to crack it.
did you missed primary school or kindergarten ?
> The first person to successfully crack
how person can crack unsuccessfully ?
> it will get $100. Seriously, $100,
did you allocated your MONEY in escrow account until this stupid competition
expired ?
just in case that any homeless candidate will not be left in the cold when you
decide to withdraw your SERIOUS PRICE CHALLENGE before end date ...
> no kidding.
why not ?
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: Why encrypt email...
Date: Mon, 29 May 2000 11:25:17 -0400
almost done in S/MIME, say 99.99% done ...
Dan Day wrote:
> What's really needed for ubiquitous encryption (and what
> will probably never exist) is an email protocol that
> will TRANSPARENTLY query an intended recipient's email
> server
in S/MIME, no need to query server, signature has public key ...
> for his public key, and then transparently either:
>
> 1. If a public key exists, encrypt the message and
> send it, and cache the public key for future
> use (tagged with a reasonable expiration date,
> *and* a way for messages sent with a cached but
> now expired public key to be auto-bounced back with
> an appropriate message), or
>
> 2. If no public key exists, prompt the sender whether
> he wants to send the message as plaintext, or
> abandon the attempt (this could be set to
> default to a desired yes/no action).
>
> And in any case, the receiving email system should
> decrypt "on-the-fly",
can not be better implemented than in S/MIME ...
> with the recipient seeing nothing
> out of the ordinary except for a "this message was sent
> with encryption" flag on it so that he can know which
> incoming messages were potentially secure or not (similar
> to the little "lock" icon that a browser shows to indicate
> a secure web connection for the current page).
almost done in S/MIME, say 99.99% done ...
------------------------------
Date: Mon, 29 May 2000 11:37:23 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Traffic Analysis Capabilities
Rex Stewart wrote:
> Hmmmm,
>
> "If you have nothing to hide you've probably wasted your life anyway."
>
> I like that. Makes a good tagline. A single line encapsulization of
> what Phil Zimmerman said.
>
> Would you like it attributed to you? (also, this is a good time for
> re-wording if you don't like the way I captured it :-)
I don't claim to have originated the concept so you are welcome to do as you
wish.
------------------------------
From: Dave Howe <DHowe@hawkswing>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Mon, 29 May 2000 17:08:39 +0100
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Sun, 28 May 2000 03:52:21
GMT]), [EMAIL PROTECTED]
(A_Customer_at_an_easyEverything_Cybercafe) said :
>If they want to stop I Love you virii, why dont they just get
>everybody to use a secure mail reader? surely it wouldnt cost them a
>lot to switch to somerthing secure, like pine, or any other *nix mail
>reader, or even some windows readers are not too bad. Why spent money
>on a bill that restricts human rights when you could have abetter
>solution for all for free?
Erm - well, for one thing, the RIP is all about stopping your email
being secure - and for another, the ILoveYou virus had the author's
email address embedded in every copy - and that address wasn't in
england. I fail to see how the right to decrypt encyphered email
and/or encrypted phone conversations could have helped.
------------------------------
Subject: Re: Smart TC1 optimizations?
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 29 May 2000 09:16:20 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> As you can see a p=1/64 goes to another p=1/64 and onto a
p=6/256.
>> What I want is p=>2/256 to move to a lower p=<5/256 value,
and to
>> avoid anything going upwards for example p=<5/256 to p=>5/256.
>>
>> If my bit perm does this it should be resistant to
differential
>> cryptanalysis right?
>
>It looks like you're trying to design your S-box and permutation
>separately, or at least in order. I think that's the wrong
strategy:
>you should design both together, so that they complement[1] and
>strengthen each other.
At http://www.tomstdenis.com/perm1.c is a copy of the new sbox
maker that makes 8x8 sboxes that follow one simple rule. Any
single or double bit change must change at least 3 bits with
high probability.
at http://www.tomstdenis.com/tc1a.c is a copy of TC1 that uses
these sboxes.
Note: your tc1-diff.c program fails an assertation along line
#195 so it can't analyze the F function well at all (upto 8
rounds)
I bet by making the sboxes specifically like this I may
introduced other problems...
Any ideas?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Smart TC1 optimizations?
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 29 May 2000 09:27:34 -0700
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>(Mark Wooding) wrote:
>>tomstd <[EMAIL PROTECTED]> wrote:
>>
>>> As you can see a p=1/64 goes to another p=1/64 and onto a
>p=6/256.
>>> What I want is p=>2/256 to move to a lower p=<5/256 value,
>and to
>>> avoid anything going upwards for example p=<5/256 to
p=>5/256.
>>>
>>> If my bit perm does this it should be resistant to
>differential
>>> cryptanalysis right?
>>
>>It looks like you're trying to design your S-box and
permutation
>>separately, or at least in order. I think that's the wrong
>strategy:
>>you should design both together, so that they complement[1] and
>>strengthen each other.
>
>At http://www.tomstdenis.com/perm1.c is a copy of the new sbox
>maker that makes 8x8 sboxes that follow one simple rule. Any
>single or double bit change must change at least 3 bits with
>high probability.
>
>at http://www.tomstdenis.com/tc1a.c is a copy of TC1 that uses
>these sboxes.
>
>Note: your tc1-diff.c program fails an assertation along line
>#195 so it can't analyze the F function well at all (upto 8
>rounds)
>
>I bet by making the sboxes specifically like this I may
>introduced other problems...
>
>Any ideas?
Damn... I should really check before I post. Please disregard.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Date: Mon, 29 May 2000 09:30:08 -0700
rick2 <[EMAIL PROTECTED]> wrote in message news:rb-17BAC7.22362727052000@news...
> I would like to use some strong encryption but need to have
> the output not have any zeros (needs to fit into zero-terminated
> data chunks). What would be the smallest and fastest way to mask
> the zeros? I've seen some people expand every 7 bits to 8, but
> that seems wasteful (expands to 114% of original size, or so) and
> takes time (every output byte needs to be shifted).
>
> Just for kicks, I'm currently using bit-shifting only, which will
> never produce a zero from a non-zero byte. I guess that's not
> a strong encryption routine, though. Is there any strong routine
> which doesn't make zeros from non-zero data?
One possibility (assuming that the plaintext has no zero bytes): use your
favorite block algorithm in ECB mode. When you encrypt a block, you check
if the ciphertext would contain any zero bytes -- if it does, encrypt the
block again (and repeat until the output doesn't have any zero bytes).
And, on decryption, to use the same procedure, you keep on decrypting until
you get a block without any zero bytes.
There is no ciphertext expansion. This should mean you do an additional 3%
block encryptions (and time taken to check for zero bytes) -- you can judge
if that is acceptable. And, there is no possibility that the procedure will
infinite-loop.
The ECB mode is somewhat weak if plaintext blocks can repeat -- you may want
to have a transformation on the plaintext beforehand to lessen that
possibility -- your current set of bit-shifts may do the job nicely...
(I tried to work out a similar procedure for another mode, but I cannot come
up with way which cannot infinite loop, and whose decryption is
unambiguous...)
--
poncho
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Date: Mon, 29 May 2000 16:37:13 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> zapzing <[EMAIL PROTECTED]> wrote:
> : rick2 <[EMAIL PROTECTED]> wrote:
> :> lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
>
> :> > Rick - You could use a regular encryption function like triple
DES,
> :> > but if you get an output block which has a zero byte in it, run
that
> :> > block through the encryption function again, and repeat until you
> :> > don't get any zeros.
>
> This proceedure may not always terminate :-(
Ah, but it will :-)
There are only 256^8 possible 8 bit blocks.
Imagine a directed graph of all possible blocks, in
which block A is connected to block B iff block A
encrypts into bock B. Mow this graph must consist
of a finite number of loops. No dendrites allowed.
A loop either contains a block without zeros or it
doesn't. So you can see that any block without
zeros will eventually lead to another block
without zeros, through the process that
"Mixmaster" described.
A block encrypting into itself, and/or a block
that takes more than about 10 steps to encrypt,
is highly improbable.
> It strikes me as of rather limited use ;-| Apart from the potential
for
> infinite loops, instead of removing 0s from the output, you now have
to
> remove them from the input.
They are not *in* the input, at least that was my
understanding of the premise of this thread.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: Mon, 29 May 2000 09:49:26 -0700
Will Critchlow <[EMAIL PROTECTED]> wrote in message
news:8gtqrm$f1t$[EMAIL PROTECTED]...
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:8gtocv$ieh$[EMAIL PROTECTED]...
> > - It would imply the two sets NP and coNP are the same. There do appear
> to
> > be problems that are in NP and not in coNP (the entire set NPC, for
> > example).
> >
>
> I understand what NP is (checkable in polynomial time) and (I think) what
> NPC is (solvable only in exponential time), but what is coNP?
NP is the set of all languages that share this property: if there is a
string within the language, there exists a proof that the string is a member
of the language that can be checked in polynomial time.
coNP is the set of all languages that share this property: if there is a
string that is not within the language, there exists a proof that the string
is not a member of the language that can be checked in polynomial time.
In other words, the complement of an NP problem is a coNP problem. That is,
the "co" stands for "complement"
BTW: NPC is not defined to be "solvable in exponential time". It is defined
to be the set of "problems in NP that any problem in NP can be reduced to in
polynomial time". It is known how to solve an NPC problem in exponential
time; it is not known whether they can be solved in subexponential or
polynomial time.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Help break SNAPPY
Date: 29 May 2000 10:02:47 -0700
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> I started my cryptanalysis of Snappy.. I began by analyzing
> repeated usage of the sbox as in
>
> t = sbox[t]
>
> Or just repeated substitution as it seems the best place to
> start. Under this model and 7 substitutions the best diff char
> I found was [...]
Why do you think this is the right model for studying
differential cryptanalysis of Snappy?
------------------------------
** 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
******************************
