Cryptography-Digest Digest #794, Volume #8 Wed, 23 Dec 98 21:13:04 EST
Contents:
Re: What is Randomness? (Dr. Yongge Wang)
Re: coNP=NP Made Easier? ([EMAIL PROTECTED])
Re: How much of CipherSaber is it OK to post on the web? (was: CS for Dummies)
(fungus)
Re: Encryption Basics (Aman)
Re: Cryptography board game! (was: CipherSaber for Dummies?) (John Curtis)
Re: What is Randomness? (R. Knauer)
Re: coNP=NP Made Easier? ([EMAIL PROTECTED])
test (Madoktor)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Dr. Yongge Wang)
Subject: Re: What is Randomness?
Date: 24 Dec 1998 00:52:55 GMT
R. Knauer ([EMAIL PROTECTED]) wrote:
: On 23 Dec 1998 18:09:08 GMT, [EMAIL PROTECTED] (Dr. Yongge Wang) wrote:
: >I am sorry, there is no Word format, it is only in
: >PostScript and PDF version.
: PDF will work - but I did not see the download link for that.
: What is the exact URL?
http://www.cs.uwm.edu/~wang/
then go to thesis.
Thanks for your interest.
: Bob Knauer
: "Laws to suppress tend to strengthen what they would prohibit.
: This is the fine point on which all the legal professions of
: history have based their job security."
: --Frank Herbert
--
======================================================.
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 |
======================================================'
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Thu, 24 Dec 1998 00:53:46 GMT
In article <[EMAIL PROTECTED]>,
rosi <[EMAIL PROTECTED]> wrote:
> Bryan Olson wrote:
> >
> > rosi wrote:
> > > I think I am not confused and you are NOT ilias.
> > >
> > > I can, at this time, only answer one person, focusing on one set of
> > > questions and getting one thread taken care of.
> >
> > Posts invite follow-ups. E-mail is the appropriate medium for
> > private discussions.
> Put the above two lines more appropriately to that ilias.
>
> Let me just ask you once more: Are you or are you not this ilias?
>
> I am waiting for this ilias to repsond. If you are the same ilias,
> we can continue instead of wondering off to other directions.
Eh, Bryan is Bryan, and I am Ilias, and Rosi is Rosi (sorry I don't know
your first name!). I'm visiting Washington, so my responses are going to
be irregularly timed for the rest of 98.
> > > One other thing, yet very important. Your interpretation and under-
> > > standing of ilias's notions, opinions, statements, etc. are likely
> > > very correct, and it will be appreciated when you try to help people
> > > to explain whatever they mean. However, I need his words. If you had
> > > joined the discussion earlier and given your opinion on 21, I likely
> > > could have found an ally.
> >
> > There's no need to worry about Dr. Kastanas' concept versus Valmari
> > Antti's or Rune Bang Lyngsoe's or mine. They are the same in every
> > important way.
> >
>
> I never worry about any concept of anybody. I just want a clear
> description of whatever concept one adopts, and I want the world to
> see what a clear description of whatever concept one adopts really is.
> I am very curious why you would like to say for other people? Let these
> people speak for themselves. You have your opportunity to make it clear
> to the world in exactly what way 'they are the same in every
> important way'. So while waiting for a reply from this ilias, why don't
> you post your concept, notion, and the exact definition of such an M
> (NDTM? I really do not care in the least. As I said it can be a magic
> piece of rock). Just tell me, us, and the whole world how that works. I
> take whatever you come up and proceed with the discussion. I do not in
> the least believe you would have the courage to shy away from a few
> simple questions. :)
It's good if other people speak too, I should think! They might express
something in a better way.
Eh, you _have_ to care as to ND or not... No, the definition that covers
deterministic TM or deterministic magic rock does NOT also cover N.D.
> > > Would you commit to carrying out this through to the end once
> > > we start? I.e. either we agree my argument is correct, or my
> > > argument is faulty, or one side is shown inconsistent or contradictory
> > > (if some simple questions are answered squarely and directly without
> > > evasion)?
> > >
> > > By the way, ilias perhaps has already seen that whichever notion
> > > he uses, the issue IS settled (if ND is a well defined concept).
> >
> > I cannot commit to carrying through until we agree. The ^^^^^^
>
> ???
> What significant questions? Beneath is an elephant, and beneath is
> a turtle, and beneath are turtles all the way downward? :)
Even worse; there are omega_1 many turtles, and they form a topological
"long-line"...?!
Ilias
P.S. Sorry, I'll have to unfreeze my fingers
before typing anything more.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: fungus <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: How much of CipherSaber is it OK to post on the web? (was: CS for Dummies)
Date: Wed, 23 Dec 1998 22:47:17 -0100
[EMAIL PROTECTED] wrote:
>
> If someone wants to post a complete CipherSaber program on the
> Internet or incorporate CipherSaber in a commercial product, and
> believes they can do so legally where they live, I have no objection.
>
Here we see the stupidity of the laws. I live in a country with
no restrictions on crypto but what are the legalitys of posting
my CipherSaber program to usenet?
If the message ends up in IRAQ then who's responsible?
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (Aman)
Subject: Re: Encryption Basics
Date: 23 Dec 1998 19:11:01 -0600
On Tue, 22 Dec 1998 20:53:15 GMT, A C Wilshere <[EMAIL PROTECTED]>
wrote:
>
>FREE, sounds good already, especially to a Yorkshireman, (no, its not
>true that Yorkshiremen are tight) ;-)
>
It may interest you to know, that the author of the current Scramdisk
system (AMAN) is also a Yorkshireman (me) living but a few miles
from Sheffield. I know how tight we are so I thought I really ought to
make it available for free!
Best wishes for Christmas and a happy new year to all.
Extra special wishes to all Scramdisk users around the world.
Regards,
Aman.
------------------------------
From: [EMAIL PROTECTED] (John Curtis)
Crossposted-To: talk.politics.crypto
Subject: Re: Cryptography board game! (was: CipherSaber for Dummies?)
Date: 23 Dec 1998 22:05:10 GMT
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Paul Rubin) writes:
>In article <75liuo$shs$[EMAIL PROTECTED]>,
>Robert Munyer <[EMAIL PROTECTED]> wrote:
>>I bet you could think of some kind of similar real-world analogy
>>for describing RC4. Try to think about things children do in
>>elementary school. Putting pegs into holes, or marbles on a
>>chinese-checker board, that kind of stuff. Remember those wooden
>>IQ tests (with golf tees) that roadside diners used to have on the
>>tables, to keep people busy while waiting for their food?
>
>It's pretty straightforward to do 52-element RC4 with a deck of cards.
I believe you that it is straightforward. Why don't you
post a quick writeup pointing the way? With perhaps an
estimate of how strong the encryption is? This would be fun
and a very portable demonstration.
ciao,
jcurtis
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is Randomness?
Date: Thu, 24 Dec 1998 01:28:21 GMT
Reply-To: [EMAIL PROTECTED]
On 24 Dec 1998 00:52:55 GMT, [EMAIL PROTECTED] (Dr. Yongge Wang) wrote:
>http://www.cs.uwm.edu/~wang/
>then go to thesis.
I already did that, and got this:
"Randomness and Complexity. 1996. (postscript, 218K)"
Not PDF.
Bob Knauer
"The police of a state should never be stronger or better armed than the citizenry.
An armed citizenry, willing to fight, is the foundation of civil freedom."
--Robert Heinlein
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Thu, 24 Dec 1998 00:11:32 GMT
In article <[EMAIL PROTECTED]>,
rosi <[EMAIL PROTECTED]> wrote:
Greetings from Puget Sound!... I'm sitting at port 868 of the King County
Library System, watching through the window as snow engulfs metropolitan
Seattle. I have next to me Lobel's The Frog and the Toad, Capablanca's Chess
Fundamentals, Ping the Duck, and "Star-Fishing", Green Jello (?) Band. The
reason is, I'm with my daughter, and she's 6. (_She_ is reading Capablan-
ca; I taught her the moves last week. _I_ am reading Frog and Toad).
I'll reply to the extent possible.
> Dear ilias,
>
> Sorry I had terribly busy days and had to pull the thread from archive.
> The archive is attached at the end. Hope I got everything.
>
> From yours I understand you agree to the following:
> 21. The SS problem CAN be answered positively in finite time. To
> be specific, there exists a TM that answers (i.e. halts and
> prints YES# on its output tape) within finite time when
> given i' which IS a subset sum of S (we use the same SS
> problem given in the previous post).
> NOTE: you actually answered my first two questions in one.
Sure; and likewise for NO#. That is, SS is recursive (computable).
"Finite time" says no more and no less than that.
> 22. We will use M as the TM referred to in 1.
> NOTE: this is in response to my third question in the previous
> post.
> 23. It is not possible for the solution time (i.e. time needed to
> solve the SS problem) to be bounded by n^1 for all natural
> numbers n.
> NOTE: this is in response to my fourth question in the
> previous post.
> 24. In addition, if I understand correctly, that you mean M is
> NOT to be run more than once for it to provide the answer.
> NOTE: again here providing the answer is: to halt and to
> print YES# on M's output tape when i' (and S) are input to
> M.
There is no sense in running a det. M "more than once"; it does
the same thing every time.
There is no point in "running" a N.D. M _at all_... not even once --
unless if you use the "guessing" version of NP's definition.
The problem is, you are not making a distinction between N.D. and
D. machines... or so it seems!
> In addition,
> 25. You asked me to be more specific about my assumption (think my
> guess is correct that's what you want). If you really want a
> repetition of the definitions and the assumption, I can include
> in the next post. Please let me know.
> Actually, all I want is that you allow an assumption to be made,
> be it true or false. We will concentrate on the derivation, i.e.
> we first try to establish that there is no problem with the steps
> going from the assumption to coNP=NP (even though the assumption
> might be in error). We will finally deal with the validity of the
> assumption. Is this fine?
Yes, I asked exactly what the assumption is.
> Please accept my apologies and let me know if any of the above
> of my understanding is incorrect or not accurate. I am, in fact,
> particularly concerned with my interpretation of 24. From your previous
> posts I seem to see that you may have adopted a specific notion of
> NDTM's. That is fine, as long as one does not give trouble. As I have
It _is_ the notion of NDTM generally accepted; there is no variability
there. If you have a different one in mind, please do explain!
> been kind of explicity, there are the 'correct guess', the 'by magic',
> and the 'massive, unlimited parallelism' etc. etc. I believe there had
> been considerations, but by the time Brassard's was published, people
> had settled somewhat. I now see that I am wrong. Adopting whichever is
> likely a personal taste kind of thing. However, there may be more to it
> than just that. But I do not think we need to go into it.
>
> Since I sensed something, I think I'd better make it explicit and
> clear so that I do not misunderstand you. To be concrete, I give two
> notions and would like you to pick one that you really mean:
> 26. M will always halt. If YES# is printed on the output tape on
> halt, we know for sure that the integer input to M IS a subset
> sum. However, it may print things (trivial included) other than
> YES#, and we know nothing. In such a case, the input could very
> well be a subset sum, but for the particular run (know you
> do not quite like the word 'run', you may give it a verb to
> denote the execution/processing), no definite answer is provided.
> NOTE: since you seemed to have mentioned 'no multiple run',
> I should not have given this. But I have to make sure.
In fact I described just such a machine... "K". I don't dislike the term
"run"; I pointed out that K, as well as other N.D. machines, have many
feasible "runs" on one and the same input.
> 27. M will halt and print YES# iff the input IS a subset sum of S.
> Otherwise, M's execution is UNDEFINED. UNDEFINE is not specific
> enough. Some people prefer this to be non-halting. For our
> discussion, we can, but not necessarily have to, say that M
> halts (in such cases) only after 'exponential time' to avoid
> later embarrassment.
Again, this is unclear. What do you mean by "M"?? Is it D, or ND?
If it is to be ND, then saying "IFF" above is pointless.
.....
> @ Given S (the set of integers) and i' an integer that IS a subeset
> @ sum of S. (This is the preamble the following refer to)
> @ 1. Is there a mechanism that taking S and i' as input answers YES?
> @ (This seems obvious from my highlight of your text, but let us
> @ confirm).
>
> Yes, there is.
>
> Comment: I suspect your question is _not_ the one you meant to
> ask...
> -------
>
> The trivial mechanism that prints YES# in 1 step, without even _reading_
> S
> or i', satisfies Question 1 !
>
> OK, I'll assume you meant "if i' is a subset sum, M prints YES#,
> _AND_
> if i' is not, M doesn't print YES#"
> Yes, there is such a thing.
>
> @ NOTE: it does not matter what mechanism, an DNTM is fine, and
> @ a piece of magic rock is fine as well, as long as it answers
> @ YES.
>
> Uh-oh... Magic rock is, in fact, fine; but what you want seems
> to be
> "give input S,i'(subset sum), push START, and the mechanism WILL print
> YES#";
> well, the NDTM I described, ("K"), is _not_ guaranteed to do so. It
> is
> _not_ fine!
>
> *****
> K makes a N.D. choice at each member of S, "keep/throw away";
> so it
> "keeps" a subset of S. It sums that subset, and if it gets i', it
> prints YES#.
> That's its "program".
> OK, you push START; K "keeps" some subset. If that doesn't
> happen
> to have sum i', K WILL NOT print YES#.
>
> EVEN SO, K "solves the S-Sum problem"! These words do NOT
> mean
> "WILL print YES#". They are _defined_ to mean "there is a possible
> compu-
> tation that would have printed YES#". This CANNOT be expressed by
> "machine
> runs... and prints YES#"!
>
> _Deterministic_ machines "run...and give answer", yes; but that's
> not
> applicable to N.D. ones.
> *****
>
> On the other hand, it is easy to make a DTM, "J", that _is_
> fine.
> J systematically generates, one after another, _all_ subsets of S and
> checks their sums. J is as you want; it WILL print YES#.
>
> @ 2. If the answer to 1. is positive, (i.e. there is such a
> mechanism
> @ that answers YES), then the mechanims would eventually within
> @ finite time answer YES, do you agree?
>
> Yes...
>
> "To answer" means "to answer in finite time". But again -- I hope you
> don't
> mean "N.D. or D., machines just run and give answer"... "Answer" by an
> N.D.
> machine is defined as above; it's not "by running".
>
> @(We can take your version
> @ where we need to run multiple times, but no matter how many
> times,
> @ the mechanism answers YES within finite time)
>
> Eh, on the contrary, I said that "running multiple times" is of
> _no use_ with N.D. machines (and, of course, pointless for D. ones).
>
> @ 3. Do you object to referring to this mechanism as M? If you do,
> @ please give it a name.
>
> I'll call it (&#$%^(*%$#%^&*(*%$$%. Uh... all right, let's use
> M.
>
> @ 4. Would this finite time referred to in 2. be bounded by some
> @ polynomial function f=n^1? (IMPORTANT: the exponent is a
> constant,
> @ namely 1. We can take your version where we need to run
> multiple
> @ times, but no matter how many times, the mechanism answers YES
> @ within time bounded by f)
>
> (There is no "running multiple times"... An N.D. machine answers
> within time bound f iff for any input of size n, if the correct
> answer
> is "yes", there is a possible computation having at most f(n) steps that
> would print YES#. "Poss. comp." meaning sequence of N.D. choices.)
>
> No, there is no N.D. M with f(n) = n^1 that can do the job;
> there are cases where M has to read the entire input plus do more work,
> and reading the input already takes up n steps. (So, no det. M
> either).
>
> Of course, K works and has time bound much better than f(n) =
> n^3.
>
> (In the sense given; no, you can't expect to plug in some input and
> necessa-
> rily "get the answer" by a single, f(n)-bounded run. Or, for that
> matter,
> _any_ number of such runs. Printing YES# implies "yes!"; not printing
> YES#
> implies nothing. That's how NDTM's are. )
>
> J is a DTM that solves the problem; but it takes exponential
> time.
>
> @ That's all for today (though two more I would like you to answer as
> well
> @in the following). I am patient and we WILL get to the bottom of it.
>
> I suggest the crucial point is in the part between *****'s above.
>
> @ There is one more important thing I woudl like to ask yout first. I
> do not
> @want us spending a huge amount of time and then get stuck on one point,
> if
> @we can avoid it. Please answer: Can I make the assumption I made with
> output
> @equivalence? If you say I can not, I admit that I can not continue and
> we can
> @stop right here.
>
> Could you re-state exactly what it is? Remember, a NDTM on a
> given
> input has a tree of different possible computations (and outputs).
>
> @ I am sorry that you do not see the relevance of Church. But that is
> not
> @important at all to me (with you). All I want is the faith in his
> Thesis;
> @and you said wouldn't want to disagree with Church.
>
> I didn't say Church is irrelevant... or that I doubt his Thesis;
> I said that the matter we were discussing did not involve it. Every set
> in
> NP has by definition an associated pol. t. NDTM; it easily follows it
> is recursive; and so on.
>
> @ As to the questions and points made in the one I am replying to, I
> will
> @answer all of them, if you want, when we first finish the set of
> questions,
> @which when answered will define things that we will use consistently.
> @
> @ Thank you very much.
> @ --- (My Signature)
> @
> @P.S. Showing my argument holds for CPNP is just showing that CPNP is
> nothing
> @ more or less than NPNP. You can not do without NPNP. Even you may
> be
>
> Eh... they are equivalent definitions. It's easy to prove that
> if X satisfies one of them then X satisfies the other.
>
> @ able to verify using DTM, to get the certificate you still need
> NDTM.
> @ That is exactly the reason I call it masterpiece. DTM to get the
> cert.
> @ and DTM to verify, the problem is then in P. The ever chance for
> the
> @ problem to be 'hard' is that DTM alone can not solve.
>
> You don't have to "get a certificate"... from anybody! The
> verifier DTM can check _anything_ submitted in the certificate slot and
> find out that it works as certificate, or that it doesn't -- that's the
> entire story! (I gave an example, K'). Pick S and i; you don't
> need
> any particular "certificate" for them: if you put any subset of S
> (equiv.
> any binary string of length |S|) in the slot, the verifier is indeed
> able
> to check in pol. time that the subset has sum i, or that it doesn't.
> This is a complete proof that S-Sum is in NP -- without any involvement
> of N.D. machines. (Conversely, if the N.D. definition holds, it follows
> a verifier exists, with a polynomial-sized slot).
Ilias
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: - (Madoktor)
Subject: test
Date: Thu, 24 Dec 1998 01:51:00 GMT
test - do not bother
------------------------------
** 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
******************************
