Cryptography-Digest Digest #691, Volume #10 Mon, 6 Dec 99 12:13:02 EST
Contents:
Re: NP-hard Problems (Safuat Hamdy)
Re: The leading university of cryptography (Anton Stiglic)
Re: smartcard idea? ([EMAIL PROTECTED])
Re: cookies (Anton Stiglic)
Re: NP-hard Problems (Anton Stiglic)
Re: NP-hard Problems (Anton Stiglic)
Re: Noise Encryption (Guy Macon)
Re: NP-hard Problems (Anton Stiglic)
Re: Encrypting short blocks (Anton Stiglic)
Re: Encrypting short blocks (Anton Stiglic)
Re: High Speed (1GBit/s) 3DES Processor (David Kessner)
Data Encryption in Applet? ([EMAIL PROTECTED])
Re: Noise Encryption ("Tim Wood")
Re: Noise Encryption ("Tim Wood")
Re: NP-hard Problems ([EMAIL PROTECTED])
Re: NSA should do a cryptoanalysis of AES (Kenneth Almquist)
Re: The leading university of cryptography (Keith A Monahan)
Re: "The message is still the same." (Was Re: NSA should do ...) (John Savard)
Re: NP-hard Problems ("Dr. Yongge Wang")
----------------------------------------------------------------------------
From: Safuat Hamdy <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: 06 Dec 1999 16:09:57 +0100
[EMAIL PROTECTED] (Bill Unruh) writes:
> In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (James Pate Williams,
>Jr.) writes:
>
> >What are some problems that are NP-hard but not NP-complete? I know
>
> Well, it is not known if there are any NP hard problems. But assuming
> that say factoring is NP hard, I believe it is not NP complete.
Sorry, but this is *gross* nonsense. Really.
Any NP-complete problem is NP-hard by definition, and yes, the former
exists. SAT (satisfiability of ordinary boolean expressions) is
NP-complete, and so is the travelling salesman problem, the knapsack
problem, ... a whole lot of interesting problems were proven to be
NP-complete, see Garey/Johnson for a more complete listing. And yes, there
are NP-hard problems which are not NP-complete. Assuming that NP != PSPACE,
take QBF (satisfiability of boolean expressions with an unlimited number of
universal and existential quantors) for instance. QBF is PSPACE-complete,
and obviously any NP-problem can be reduced to it. But it is widely
believed that there is no NP-problem to which QBF can be reduced to.
--
S. Hamdy | All primes are odd except 2,
[EMAIL PROTECTED] | which is the oddest of all.
|
unsolicited commercial e-mail | D.E. Knuth
is strictly not welcome |
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: The leading university of cryptography
Date: Mon, 06 Dec 1999 10:32:49 -0500
[EMAIL PROTECTED] wrote:
> Which university, in the US or elsewhere, is by your opinion the best
> when it comes to cryptography. I know Alfred Menezes and Doug Stinson
> both works for the University of Waterloo, Ontario, Canada. Is The
> Massachusetts Institute of Technology (MIT) any good when it comes to
> cryptography - In Europe MIT is often mentioned as one of the best
> engineering universities.
Waterloo and MIT are both great.
To that, I would probably add the Catholic University of Louvain (UCL)
and
in my own city :) Universite de Montreal/McGill University.
For more applied, data security stuff, there would be Princeton and
Berkeley.
There are certainly others that are also great... It depends what you
like
to work on.
Anton
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: smartcard idea?
Date: Mon, 06 Dec 1999 15:38:02 GMT
Hello all,
ELVA has developed and patented a new concept of smartcard named
VocaliD. This smartcard , compliant with ISO7816 standards, also has an
embedded acoustic interface that allows the use of a telephone or a
microphone as a reader for access to online services. An identification
sequence made up of an identification number and a cryptogram is
readable either via the ISO contacts or the acoustic interface. This
cryptogram is a function of the one previously emitted, forming a
linking protocol. This method is much less expensive than OTP.
For more information, please visit our web site : http://www.elva.fr
Jean-Pierre Fortune
ELVA
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: cookies
Date: Mon, 06 Dec 1999 10:56:32 -0500
==============132C5A166902866BEB5E05F6
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
A cookie is a file that is placed on your computer machine when
you go to some web sites. The cookie file contains information
that the web site could read if you ever go back to it. Some web
servers get together and share the information they get from the
cookies they place, this is a way for them to track you on the
Internet. The information these web servers can get from you
is amazing, and worth allot of money. To get an idea, imagine you
going to a mall, as soon as you enter a store, they scan your shoulder
for a serial number, then go to a computer and get all past information
about you. They know, for example, that you just came from the
pet shop store, that you rent allot of movies, that you smoke and
you buy magazines about health issues. They know that you probably
have children since you buy toys at the local toy store and that
your wife wears kinky under clothing, hmmm, anyways, you get
the picture... The worst thing of all is that most people are unaware
of this tracking. You see, in real life, you should be able to go to
a local grocery store and just by a carton of milk, without the store
clerks knowing all your past history of identity, you *should* have
the same right on the Internet. In real life, you are often
pseudonymous,
people might recognize your face, but they don't always know your
true identity or past history. For example, a bus driver has no need
of knowing your true identity when you just want to take a bus to go
to work.
There is a computer software that lets you know what is going into
your cookies, and let you be pseudonymous on the Internet. Hmmm,
let me think, I think it comes from a company called Zero-Knowledge
Systems, the software system is called Freedom :). You can check it
out at
http://www.freedom.net
This URL is not only for people who want to buy nyms and use the
Freedom system, it's also a place to get educated about privacy issues.
Anton
E-mail wrote:
> Many web sites are pretty insistent about taking cookies. Why?
>
> I am suspicious about it because I see it as violation of privacy
> and possibly a means of breaking into data not mentioned in the
> reasons they give.
>
> Jim
> [EMAIL PROTECTED]
==============132C5A166902866BEB5E05F6
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<br>A cookie is a file that is placed on your computer machine
when
<br>you go to some web sites. The cookie file contains information
<br>that the web site could read if you ever go back to it. Some
web
<br>servers get together and share the information they get from the
<br>cookies they place, this is a way for them to track you on the
<br>Internet. The information these web servers can get from you
<br>is amazing, and worth allot of money. To get an idea, imagine
you
<br>going to a mall, as soon as you enter a store, they scan your shoulder
<br>for a serial number, then go to a computer and get all past information
<br>about you. They know, for example, that you just came from the
<br>pet shop store, that you rent allot of movies, that you smoke and
<br>you buy magazines about health issues. They know that you probably
<br>have children since you buy toys at the local toy store and that
<br>your wife wears kinky under clothing, hmmm, anyways, you get
<br>the picture... The worst thing of all is that most people are
unaware
<br>of this tracking. You see, in real life, you should be able to
go to
<br>a local grocery store and just by a carton of milk, without the store
<br>clerks knowing all your past history of identity, you *should* have
<br>the same right on the Internet. In real life, you are often pseudonymous,
<br>people might recognize your face, but they don't always know your
<br>true identity or past history. For example, a bus driver
has no need
<br>of knowing your true identity when you just want to take a bus to go
<br>to work.
<br>There is a computer software that lets you know what is going into
<br>your cookies, and let you be pseudonymous on the Internet. Hmmm,
<br>let me think, I think it comes from a company called Zero-Knowledge
<br>Systems, the software system is called Freedom :). You can check
it
<br>out at
<br><a href="http://www.freedom.net">http://www.freedom.net</a>
<br>This URL is not only for people who want to buy nyms and use the
<br>Freedom system, it's also a place to get educated about privacy issues.
<p>Anton
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<p>E-mail wrote:
<blockquote TYPE=CITE>Many web sites are pretty insistent about taking
cookies. Why?
<p>I am suspicious about it because I see it as violation of privacy
<br>and possibly a means of breaking into data not mentioned in the
<br>reasons they give.
<p>Jim
<br>[EMAIL PROTECTED]</blockquote>
<pre></pre>
</html>
==============132C5A166902866BEB5E05F6==
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: Mon, 06 Dec 1999 11:02:05 -0500
>
>
> Better example: the halting problem.
>
> This is obviously NP-hard, because for any problem in NP, you can
> obviously construct a problem that will halt iff the string is in
> the language.
That's a bad exemple, we are talking about a complexity class, the NP-hard
problem is not even solvable, so it would be odd to fit it in a complexity
class.
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: Mon, 06 Dec 1999 11:06:12 -0500
David A Molnar wrote:
> Bill Unruh <[EMAIL PROTECTED]> wrote:
> > In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (James Pate
>Williams, Jr.) writes:
>
> >>What are some problems that are NP-hard but not NP-complete? I know
>
> > Well, it is not known if there are any NP hard problems. But assuming
> > that say factoring is NP hard, I believe it is not NP complete.
>
> This does not match my understanding of NP hard problems at all. :-(
> As in "head explodes at reading previous two posts" out of joint
> with what I know. Let me write what I think and hopefully we can resolve
> this.
>
> From what I understand :
>
> When we say that a problem P is "NP-hard", we mean that
>
> a) we have a decision problem P defined with respect to some language of
>
No, that is false. An NP-hard problem is not restricted to only decision
problems. That's a basic fact that makes a distinction between NP-Hard
and NP-Complete (NP-Complete problems are necessarily decisional
problems).
The big green book (Applied Cryptography), for example, clearly states
this. See section 2.3.3.
> strings L. That is, we have an alphabet $\Sigma$ and a string
> $s \in \Sigma^*$ -- a string $s$ consisting of some concatenation
> of symbols in the alphabet and of unbounded length -- and we are
> asking the question "Is the string s in the language L??"
[...]
Anton.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Noise Encryption
Date: 06 Dec 1999 11:09:50 EST
In article <82g2km$dck$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim Wood) wrote:
>>The real problem with
>>OTP is to transport the key by a secure media.
>
>This is not always a problem. For instance it is easy for two ships in the
>same dock to transfer key material bettween the but not two ships that have
>sailed to opposite sides of the world!
>
>If they had exchanged key material they would be able to exchange perfectly
>secure material.
Question: Is there a method of sending encrypted messages that does
not at some point require passing secret data (usually a key) between
the sender and the reciever?
If something has to be passed from one to the other, why not a CD-R
full of random data? (I can think of one answer to this: a key that
can be memorized has many advantages over a CD-R).
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: Mon, 06 Dec 1999 11:10:26 -0500
[EMAIL PROTECTED] wrote:
> James Pate Williams, Jr. asked:
> > What are some problems that are NP-hard but not NP-complete? I know
> > circuit-satisfiability is both NP-hard and NP-complete. In a textbook
> > I have r.e.-hard and r.e.-complete are defined where r.e. =
> > recursively enumerable. Are r.e.-hard and r.e.-complete the same as
> > NP-hard and NP-complete? MP (membership problem) and HP (halting
> > problem) are both r.e.-hard and r.e.-complete.
>
> A problem X is NP-Hard if and only if there exists
> a polynomial-time reduction from an NP-complete
> problem to X. The definition of NP-hard is not as
> well established as NP-complete, and references
> differ as to whether it is a set of languages (in
> which case only decision problems are NP-hard) or
> a set of general computational problems.
>
I haven't seen a definition of NP-Hard that would contradict the
fact that it does not need to be a decisional problem.
If an polynomial timed algorith exists for a problem in NP-Complete,
then NP = P. The definition of an NP-hard problem is that if there
exists a polynomial timed algorithm for one of it's problems, then
NP = P. So as you can see, there is not much difference, except for
the fact that NP-hard problems are not limited to decisional problems.
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Encrypting short blocks
Date: Mon, 06 Dec 1999 11:13:18 -0500
wtshaw wrote:
> In article <[EMAIL PROTECTED]>, Anton Stiglic <[EMAIL PROTECTED]> wrote:
>
> > wtshaw wrote:
> >
> >
> > > Pick a block length, pick a usable keylength, design a good algorithm,
> > > case closed.
> > > --
> >
> > Sure, just re-design everything. Analyse it, give it to others to check
> > it out, wait about two years to make sure it seems secure, no problem!
>
> I *thought* the humor would be self-evident. Two years might have little
> to do with such an appraisal, time being non-contributary to insight
> except in postgame evaluations of sports where you learn how dumb those
> that CAN play might be.
>
> Sometimes a redesign is like changing to the correct train that has a
> better chance of reaching a desired destination.
>From reading all sorts of posts here, I don't know anymore if someone is
joking or telling the truth. Some people would have taken the suggestion
seriously, believe me I have seen it here.
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Encrypting short blocks
Date: Mon, 06 Dec 1999 11:15:22 -0500
"Douglas A. Gwyn" wrote:
> Anton Stiglic wrote:
> > "Douglas A. Gwyn" wrote:
> > > Markus Peuhkuri wrote:
> > > > Is there an encyprion algorithm that can be used for short
> > > > blocks (variable from ~10 to 24 bits) _and_ the result is same
> > > > length as original data.
> > > Yes, most binary-oriented stream ciphers have that property.
> > A stream cipher is not a block cipher.
>
> And a cat is not a dog. So what? He didn't ask for a block cipher,
> and why should he?
Very funny, what a sens of humour. He was talking about blocks, so
I tought he wanted a block cipher, why else would he be talking about
blocks, information doesn't usualy come in blocks unless me make them
come in blocks...
------------------------------
From: David Kessner <[EMAIL PROTECTED]>
Crossposted-To: comp.dcom.vpn,comp.security.firewalls
Subject: Re: High Speed (1GBit/s) 3DES Processor
Date: Mon, 06 Dec 1999 09:12:24 -0700
Reply-To: [EMAIL PROTECTED]
Paul Koning wrote:
>
> David Kessner wrote:
> > You can download a DES core for your FPGA from http://www.free-ip.com.
>
> > Twelve of these cores can fit into the largest Xilinx Virtex-E FPGA,
> > achieving a single-DES performance of 44.4 gigabits/second. Of
> > course, you can wire them up serially to get 3DES at 1/3rd the
> > performance-- or a "sluggish" 14.8 gigabits/second. All on a
> > single chip!
>
> Twelve? I can see how 16 cores would help if that lets you do the
> 16 rounds in a pipeline rather than iteratively. Or did you do that
> already? If so, additional parallellism doesn't gain you anything
> for single stream throughput because you can't parallelize CBC
> encryption...
The Free-DES core comes in two flavors: Fast and Small. The fast core
has the 16 rounds pipelined, while the small core has a single "stage"
that does all 16 iterations. As expected, the small core is also
slower,
while the fast core is a lot bigger.
With the largest FPGA on the market you can fit 12 of the fast cores
into the chip.
You're right that CBC mode causes problems with this type of DES core.
There are several ways around this, but none of them are what I would
call "elegant". The easiest is probably interleaving the "chains"
(also mentioned by Volker). The other methods are useful for multi-
channel applications where a single DES chip does the encrypting for
many port (I.E., ethernet ports, T1/E1/OC3 ports, etc).
One thing that I should point out about the Free-DES core is that
it is able to switch keys on each 64-bit block without any performance
penalty. This greatly aids in processing multiple streams and helps
with all that CBC mode stuff...
David Kessner
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To:
comp.lang.java.security,microsoft.public.java.security,comp.lang.java.programmer
Subject: Data Encryption in Applet?
Date: Tue, 07 Dec 1999 00:18:28 +0800
Hi
I am looking for a way to encrypt data through an applet using symmetric
(or asymmetric) encryption. I thought of sending an applet containing a
symmetric key to a client. This is key is to perform encryption on some
data on the client side. Anybody has any idea how to do this in Java or
has any source codes in Java?
Thanks in advance
Greg
------------------------------
From: "Tim Wood" <[EMAIL PROTECTED]>
Subject: Re: Noise Encryption
Date: Mon, 6 Dec 1999 16:29:28 -0000
Guy Macon wrote in message <82gn4e$[EMAIL PROTECTED]>...
>In article <82g2km$dck$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim
Wood) wrote:
>
>
>>>The real problem with
>>>OTP is to transport the key by a secure media.
>>
>>This is not always a problem. For instance it is easy for two ships in the
>>same dock to transfer key material bettween the but not two ships that
have
>>sailed to opposite sides of the world!
>>
>>If they had exchanged key material they would be able to exchange
perfectly
>>secure material.
>
>Question: Is there a method of sending encrypted messages that does
>not at some point require passing secret data (usually a key) between
>the sender and the reciever?
Yes. Public key cryptography enables this, RSA being a popular algorithm.
PGP uses public key encryption (in some combination), as do many other
messaging systems.
>If something has to be passed from one to the other, why not a CD-R
>full of random data? (I can think of one answer to this: a key that
>can be memorized has many advantages over a CD-R).
>
That is what I was suggesting in this case, One Time Pads are well known and
used.
tim
------------------------------
From: "Tim Wood" <[EMAIL PROTECTED]>
Subject: Re: Noise Encryption
Date: Mon, 6 Dec 1999 16:31:54 -0000
Mattias Wecksten wrote in message <[EMAIL PROTECTED]>...
>
>
>Tim Wood wrote:
>
>> Mattias Wecksten wrote in message <[EMAIL PROTECTED]>...
>> >
>> >Assumption:
>> >
>> > * Algorithm is known.
>>
>> This should include the method of key generation. This is where the
>> potential weakness of a non random source comes in.
>>
>
>I think this is the center of all disagreements. What if you use a non
>algorithmic random generator. There is still not true randomness, but still
>there is no way of "guessing" the data.
I think that this is invalid. Please give an example of a non-algorithmic
generator (one that cannot be reduced to an algorithm) that does not produce
true random data.
I think however that a OTP has to use _true_ random data.
tim
>
>Sincerely
>
>M WxX
>
*Sorry I sent this to the author by accident, I have now posted it here.*
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: NP-hard Problems
Date: 6 Dec 1999 16:32:04 GMT
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> I haven't seen a definition of NP-Hard that would contradict the
> fact that it does not need to be a decisional problem.
> If an polynomial timed algorith exists for a problem in NP-Complete,
> then NP = P. The definition of an NP-hard problem is that if there
> exists a polynomial timed algorithm for one of it's problems, then
> NP = P. So as you can see, there is not much difference, except for
> the fact that NP-hard problems are not limited to decisional problems.
No, there is a much more fundamental difference than that. NP-hard
problems are not restricted to the class NP, so while most people will
allow non-decision problems to be called NP-hard, NP-hard problems can
in fact be *much* harder decision problems than those in the class NP.
For example, take a decision problem A that is complete NTIME(2^n).
We know by the various time hierarchy results that such an A exists
and is not in the class NP, so is strictly harder than the problems in
NP. Furthermore, since NP is a subset of NTIME(2^n), you know that
everything in NP is reducible to A. Therefore A is NP-hard, but
cannot possibly be NP-complete, even though it is a decision problem.
So we know that there are (decision) problems that are NP-hard and not
NP-complete, so there exist provably intractible NP-hard problems.
However, we don't know if there are any NP-complete problems that
aren't in P, so there *aren't* any provably intractible NP-complete
problems (well... there may be "provably" intractible NP-complete
problems, but we don't know of any such proofs at this time!). So
there is a *huge* difference between NP-hard and NP-complete, and it's
definitely not restricted to "the fact that NP-hard problems are not
limited to decisional problems".
--
Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
University of North Texas | or better,' so I installed Linux."
Denton, TX 76201 |
------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: NSA should do a cryptoanalysis of AES
Date: 6 Dec 1999 16:43:30 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> Kenneth Almquist <[EMAIL PROTECTED]> wrote:
>: My guess is that the information from the NSA which influences the
>: AES selection will be made public, because as you point out, keeping
>: the information secret would be difficult.
>
> Keeping information secret is part of the NSA's job.
Exactly. That's why I expect them to summarize their evaluation of the
AES candidates in a way which protects any NSA secrets. I would not
expect the NSA to rely on NIST to protect the NSA's secrets, particularly
since (according to Bruce) some lawyers believe that any documents used
by NIST in its evaluation of the AES candidtates are covered by the
Freedom of Information Act.
>: [...] if the NSA breaks one of the finalists, the fact that
>: the encryption algorithm had been broken would rule it out of
>: consideration.
>
> It is not clear whether this is true. What does the number 56 mean
> to you?
It's the key length of DES. It's also a good measure of the strength
of DES, because the NSA worked with IBM to make DES resistant to
differential attacks. When DES was standardized, some people suggested
that the NSA might have hidden a trap door in the algorithm. It is
now clear that the NSA did not do this. As a result, we have some
reason to have confidence in subsequent NSA work on encryption standards.
Kenneth Almquist
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: The leading university of cryptography
Date: 6 Dec 1999 16:50:21 GMT
On a side note, check out those links, I've noticed people here
don't look ANYTHING like I expected them to.
Keith
Yukta Mookhey ([EMAIL PROTECTED]) wrote:
: �� �ޭz�[EMAIL PROTECTED] (David A Molnar)�n���ʨ��G
: [del]
: > You might try looking at a list of cryptographers (David Wagner has one
: > on his site, so does Kevin McCurley) and picking out those whose work you
: > admire. Then see where they are located. That will probably tell you more
: > than I can about which universities are strongest in the kind of crypto
: > you like.
: [del]
: Here are they:
: David's: http://www.cs.berkeley.edu/~daw/people/crypto.html
: Kevin's: http://www.swcp.com/~mccurley/cryptographers/cryptographers.html
: Enjoy them. :)
: --
: [1;32m�� Origin: [37m<Terry.Dragon2.Net> [m
: [1;31m�� From: [36mterry.dorm8.nctu.edu.tw[m
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "The message is still the same." (Was Re: NSA should do ...)
Date: Mon, 06 Dec 1999 16:31:10 GMT
On Sun, 05 Dec 1999 20:25:36 -0700, Sundial Services
<[EMAIL PROTECTED]> wrote:
>For all the tax-money that NSA slurps up each year, and for the enormous
>number of people who (like it or not, acknowledge it or not) depend upon
>their cryptographic expertise to ensure that another Nazi Germany does
>not appear again on this earth, I sincerely hope that they can break
>most commercial systems -- and that they keep their mouths tightly shut,
>as they do, about what they can and cannot do.
>I still remember a poster that I saw in a hallway outside the National
>Cryptography Museum. It was a WW2 poster, "Loose Lips Sink Ships," and
>beneath it was printed, simply, "The message is still the same."
>The grim truth of human nature is that evil people -will- use guns to
>kill people by the millions given the chance to do so... and that the
>best way to prevent them from doing so is by never being caught by
>surprise.
Although this is true as far as it goes, and doubtless they can break
some things we do not imagine they could, I fear that the
circumstances are not still the same.
In warfare, some inventions permanently changed the rules. The firearm
changed the balance between the offence and the defense, and other
weapons at other times in history had major impacts as well.
The microprocessor has had an important effect on the battle of codes
and ciphers. Because of traffic analysis, and other things, the NSA
may well be able to justify its existence. But if it is necessary to
unscramble the contents of an encrypted E-mail, not merely to find the
sender and recipient, or apply other investigative methods, to prevent
a terrorist attack or other tragedy, it may well be beyond their
power.
I am not trying to say that terrorist attacks in which hundreds or
more people are killed are "part of the price we pay for freedom".
Obviously, human lives are far more important than a rigid or
doctrinare approach to civil liberties. However, the circumstances
have changed from World War II; it is no longer the case that major
governments are limited to electromechanical devices, and the rest of
us to pencil and paper. The increase in computing power also benefits
the cryptanalyst, but to a much lesser extent. Only in a world of
enforceable mandatory key escrow would there be the assurance of
breaking the codes that need to be broken; and this doesn't involve a
minor breach of civil liberties; ultimately, it would end up involving
a ban on the private use of computers.
Other technologies on the horizon may put more destructive power into
the hands of the ordinary individual than before, just as the gasoline
in the family car has already done. There are no easy answers to this
dilemma.
------------------------------
From: "Dr. Yongge Wang" <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: 6 Dec 1999 17:04:25 GMT
Bill Unruh <[EMAIL PROTECTED]> wrote:
: In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (James Pate Williams,
:Jr.) writes:
:>What are some problems that are NP-hard but not NP-complete? I know
: Well, it is not known if there are any NP hard problems. But assuming
: that say factoring is NP hard, I believe it is not NP complete.
A
:))))))))))
There are many problems that are NP-hard:) and many problems are NP-complete:)
NP-hard problems are not necessarily in NP, but NP-complete problems
must lie in NP:) E.g., SATisfiability is in NP and is NP-hard,
so it is NP-complete. Again, e.g., Turing machine halting problem
is NP-hard, but it is not in NP, so not NP-complete:)
A
A
--
======================================================.
Yongge Wang | |
Dept. of EE & CS | |
Univ. of Wisconsin--Milwaukee | |
P.O.Box 784 |Yongge Wang |
Milwaukee, WI 53201 |2545 N.Frederick Ave. |
|Apt. 104 |
Tel: (414)229-5731 |Milwaukee, WI 53211 |
Fax: (414)229-2769 | |
[EMAIL PROTECTED] |Tel: (414)3324794 |
http://www.cs.uwm.edu/~wang |Fax: (414)3324794 |
======================================================'
------------------------------
** 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
******************************
