Cryptography-Digest Digest #8, Volume #9 Sat, 30 Jan 99 19:13:03 EST
Contents:
Re: Fialka Punch Card Speculation (Frode Weierud)
NP=coNP (rosi)
Re: Who will win in AES contest ?? ([EMAIL PROTECTED])
Re: Encryption for my little java-mail-server (user)
Re: Random numbers from a sound card? (R. Knauer)
Re: hardRandNumbGen (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Frode Weierud)
Subject: Re: Fialka Punch Card Speculation
Date: 30 Jan 1999 19:24:17 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] () writes:
>Yes, you are correct. That I realized. The number 26 comes from dividing
>80 by 3.
>My speculation concerns how to map a 30 x 30 crossbar matrix to the
>standard 80-column card. Each of the 80 columns contains 12 holes, so
>three columns have 36 holes. If we use 30 holes from three columns, we
>have six holes left. If they are allocated to the 12, 11, and 0 punches of
>two columns, they can be punched independently of a single punch in the 1
>to 9 rows, forming the code for a letter.
Ah, I see what you mean. However, the Fialka did not use normal Hollerith
punched cards. The cards were of a special design which to my knowledge was
used for only this very special purpose. You will find that Russian
equipment often are using quite different solutions than what we are used
to. I have seen that in their electronic equipment. There is often used
quite ingenious mechanical solutions instead of relying entirely on
electrical or pure electronic solutions. The Agat cipher machine is an
almost purely mechanical machine which is in stark contrast to other
one-time-tape machines of the same epoch.
Frode
--
Frode Weierud Phone : +41 22 7674794
CERN, SL, CH-1211 Geneva 23, Fax : +41 22 7679185
Switzerland E-mail : [EMAIL PROTECTED]
WWW : wwwcn.cern.ch/~frode
------------------------------
From: rosi <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: NP=coNP
Date: Sat, 30 Jan 1999 14:17:47 -0800
The following was posted a few weeks back. In case anybody is
interested.
I corrected a couple of typos and removed the postscript addressing
Tim
Bass, but the rest remains intact.
One note: The M and M' in M" are an 'oracle' (which is used in a
slightly loose sense, as M' corresponds to the complexity of M). I
guess, not using the term 'oracle' is a great waste. :)
Thank you.
--- (My Signature)
============================================================================
NP = coNP Made Easier?
(Inefficient but finite and thanks for your patience. It is advised to
first read the first two paragraphs of NOTE [2] and the note of
Brassard's
[1]. Then you have my gratitude, happy reading or happy not reading)
Definition --- Any two automata are output equivalent if
they, on identical input, always write identical, finite
output on their respective output tapes after some finite
time. (Finite trivial output counts as well).
Assumption --- Two automata are equivalent in computing power
(or are computationally equivalent) if they are output
equivalent.
Definition --- A (formalizable) Non-Halting Problem Solving
Machine (NHPSM) M is one that, on some input i and with
some starting configuration (or initial state of M),
eventually within finite time writes an answer of finite
size on its output tape, but may or may not halt. M never
writes anything else (on the output tape) except the answer
if there is one.
A note on the definition seems necessary. We should not be bothered
with
the flavor of a perpetual machine, since whether it is or is not
perpetual
is not of our real concern. We can actually think in exactly the same way
about it as, for example, about the infinite tape of a Turing Machine. Of
ourse, the reader is reminded again of the 'promise' of informal
treatment
here. To be concrete, it is made implicit that the 'acceptor' of the
answer
is 'disconnected' from the NHPSM. Think about it this way: A human puts
a
question q to a computer C (any formalizable device that 'computes') with
C configured in some sort way before the input, or with C in a certain
state before seeing the input. The human is never interested in whether C
halts or not. The human is only interested in looking at the output
media,
which is finite, at a certain time after the start of C to obtain a
satisfactory answer.
Argument (informal sketch only): coNP = NP for output equivalent non-
deterministic automata.
Since elements in the NP-complete set are mutually reducible, we can
pick any one for the purpose of our argument. Let us pick the subset sum
problem SS (defined as: given a set S of integers and another integer i,
determine whether i is or is not the sum of a subset of S). If we can
show that SS is also in coNP, we have established coNP=NP. To show SS is
in coNP, we need only show that when NO is the answer, it can be answered
non-deterministically in polynomial time. To show this, we only need to
show there is an ND computing device for it. (Please remember output
equivalence).
Let the NDTM for answering the YES part of the question be M. We
construct M" which has two TM's (M and M') as its components. At the
start on the input, M" calculates y, where y=f(n) which we will define
shortly, and stores y on one of its internal tapes as the input for M'.
M" then handles control over to M and M' to let them run in parallel.
Of course, M still gets the original input (the problem). M' is actually
a down-counter. It decrements y (one by one). When y becomes zero (or
negtive if that is more convenient), M' writes NEG (or the NEG symbol)
on its output tape and halts. M behaves as usual. If it obtains an answer
(always a positive one of course), it writes POS (or the POS symbol) on
its output tape and halts. M" is a NHPSM and does not halt if and only if
M does not and if and only if the answer to the SS question is negative.
Without being too much concerned about details, we assume M and M' are
perfectly synchronized. When the 'acceptor' looks at the output at any
time, he would see three, and only three, sets of outputs: 1. The places
for POS and NEG are both 'blank'. 2. POS is written on the tape where it
should be written and NEG is also written on the tape where it should be
written. 3. NEG is written on the tape where it should be written but the
place for POS is still `blank'. It is obvious that the latter two can be
seen in polynomial time, indicating that both the answer YES and NO can
be
correctly answered in polynomial time (if y can be calculated and written
on the internal tape in polynomial time as well).
We will not go to details about why y can be calculated and written to
the internal tape in polynomial time. It should not be too difficult from
the definition of f which we give next.
f is a polynomial upper bound function for the polynomial time for
solving SS _positively_ non-deterministically. Since we have cornered
ourselves into accepting that there is a NDTM for SS for the positive
part of the question, we are availed with a bit of luxury. For otherwise,
if we believe there is no such NDTM, the possibility of P=NP is in smoke
and worse still, the definition of NP is in shambles and there is no NP
and no coNP. Then what could be our concerns? As such a NDTM exists (or
is assumed to exist), the SS can be answered in polynomial time when the
answer is YES. Therefore, such an f must exist. Since f is a polynomial
bound function, f is of the form:
a[0]n^k + a[1]n^(k-1) + ... + a[k]n^0
where a[i] for 0<=i<=k are reals with a[0] positive and k is a positive
integer constant. If one is really meticulous, one can use (double)
induction on b and k, for f <= g where g=b*n^(k+1) and b=ceiling(a[0]).
One other thing implicit here is that either n, the size of the
problem,
is part of the input, or n can be extracted in polynomial time from the
input.
We have used the non-deterministic automaton version of NP (NPNP). Now
a brief consideration for the certificate version of NP (CPNP). We have
to adopt the non-deterministic concept, for otherwise the next complexity
measure above P would be E. Certainly, all those CPNP problems can be
answered both positively and negatively in E time, making our questions
non-questions. If we allow the ND concept, there exist TM's (or more
precisely NDTM's) that solve NP problems in polynomial time. Therefore we
are done, as we can either use null/trivial certificates, or use the
input
as a certificate which, by the Argument, can be used to verify.
I know, not all feel comfortable with the assumption of 'output
equivalence' nor with the non-halting sensation, either for fear of one
actually inventing a real perpetual machine after all or for not seeing
a formal justification. This has been with us all the time. We tend to
shrug it off. But it clings on. The real problem is not the fact that we
try to shrug it off; it is we do so or try to do so whenever we feel
'convenient'. If it were Mr. Turing who gave the sensation, we just feel
so bloody good. :)
Some may feel better if we are as powerful as we feel: everything
under
control. I am not so confident. With deterministicity, I am 'almost' sure
that formalizability implies controllability, thus halting. With non-
deterministicity I just do not know and can not pretend to know. How much
can we control things in some kind of 'weird' formalism, should there be
one? For all I dare to guess, we may not be able to exercise any control
in any other formalism apart from the equivalence of a Turing Machine, or
we may only be able to exercise partial and limited control there. To be
FRANK, I do not know. This leads to the ultimate question of formalism
and
its representation --- formal language.
If we believe that whatever we can formalize we can control, then we
can ease some of our pain. M" can halt M (or the human can, by
figuratively
unplugging the power to M) and thus halts itself when M' halts (or when y
becomes zero). --- Oh, sure! Choose a sensible f and the 'acceptor' may
have to, of course, look harder and longer.
There are many, many ways to think about this particular issue, just
as there are for the larger picture, I believe. The problem of coNP?=NP
is an interesting one, no doubt. But I wonder if the ultimate proof or
disproof has much impact on anything (and let us agree to disagree).
==========================================================================
NOTES:
[1] Gilles Brassard, "A Note on the Complexity of Cryptography", IEEE
Transactions on Information Theory, 25, (1979), pp. 232-233.
[2] (This note should serve as a lengthy introduction). This piece is
entirely mine and is informal but is believed to be able to have formal
details filled in. There has been no correspondence or consultation with
any expert in related fields. (I have a sense that the "theory of
reachability" is 'faulty'). Therefore, any errors are mine and any that
are mine are mine alone. Critiques and comments are welcome, either as
posts in the news groups or as private e-mail. Due to my lack of
mathematical training, I won't be able to answer questions I might get.
In that case, please try to obtain answers from authorities in the
related discipline(s) and I apologize in advance.
By 'ease' (am referring to the title of the post), I do not mean it is
because of the discovery of Brassard's 'leap' [1] from being 'hard' to
NP-complete. I am referring to my avoiding the difficulty of a proof by
using the notion of 'output equivalence'. Although I can not provide a
formal proof of my assumption concerning 'output equivalent' automata
(which can only come after a full formalization of NDTM, --- or never
come), it is my strong belief that, for all practical problem-solving
purposes, output equivalent automata are equivalent in computing power.
This piece concerning coNP is noted down from my private,
brainstorming
sessions, the earliest of which contained mainly an old, quite beaten-up,
cryptographic idea which by now is almost entirely abandoned. With this
old idea as a basis, mixed with understanding and misunderstanding of the
underlying complexity issue(s), I kind of developed a problem (only a
problem) for cryptographic applications. This problem is quite unique. It
can be based on for encryption and allows quite some flexibility. It (the
problem) is 'everywhere as hard' and can be proven to be AT LEAST
NP-complete. What is more interesting about the problem is that if the
problem is no harder than NP (equivalently no harder than NP-complete),
then NP=coNP CAN BE PROVEN (totally without the need for the non-halting
annoyance). It also goes without saying that, as always, all are
dependent
on NP and coNP BEING WELL-DEFINED.
One other important point in all this is the totally unsupported
assumption, which is implicit throughout. By unsupported I mean I did not
consult the reader first about it. The assumption is the reader's full
faith and trust in Church's Thesis.
While the fuller brainstorming on this issue has several additional
notes about some obvious points concerning [1]. One I particularly feel
like mentioning. It is the linguistic semantics subtlety of the
conclusion [1] draws. We notice that the hardness of a proof of
cryptographic complexity is not in if-and-only-if relationship with the
hardness of establishing coNP=NP (or coNP!=NP for that matter).
(We should not be so serious all the time. Let the heavy stuff give
way
to a lighter treat :))
Some readers may remember my posts concerning the same issue earlier,
in which I basically said the same thing as the 'jump' in [1]. Well,
basically. I was (and remain) a coward. The difference between mine and
that of [1] is that I perhaps explicitly hesitated on the question: Is
there a (non-trivial) classification between P and NP. But I do not think
things could have been any different had I claimed without justification
that there was no such in-between classification. I said either there was
such an in-between classification (but nobody seemed yet to know the
definition for) or such a 'jump' (as in [1]) must be true. [1] says the
'jump' is true; I say the 'jump' is true or else the 'in-between' must be
true. People believe [1], not mine. Therefore, if A is true, then (A or
B)
is definitely false. I seem to see that when people extremely
knowledgeable
about complexity lecture, logic vanishes into Dilbert Space --- Spelling
Checker? Grammar Improver? Semantics De-abberationer? --- joke in the
virtual sense of it.
Do we see the forever so amusing movie that broken twigs blown off a
tree are consistently, insistently and repeatedly presented to Tarski
seemingly with the sincerest hope that Tarski will one day use one of
them as the final nail for the coffin? :)
Another question I had, but of course did not put down, is the
following:
:) :) Why all this ado since P != NP was already, already proven? It
is
my unfaltering belief that when a proof is given, leading complexity
gurus
will lead the charge at anyone questioning the soundness of the proof. I
am
not kidding. Remove the disbelief by reading one of the posts in reply to
one of my earlier ones.
If I end up here in such a light tone, I might give the impression
that
I am not serious. But I said just now to not have heavy stuff any more
here
this time. As a compromise, let us talk about a serious matter in a joke
and be happily off-topic and off the topic.
When P?=NP is finally settled, the naked ape may find himself bored
with
the direction he has taken in evolution. Another cataclysm may take
place.
Of course, the ape wouldn't go back to trod on all fours, bored with
walking
upright as he is. He might find himself running about on his head.
So seriously, when the world is turned upside down, which would be
what
he sees instead of the other way round, he would catch a glimpse of a
streamer:
:) Nothing in NP-complete is in P _AND_ P equals NP (:
Thank you very much.
--- (My Signature)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Who will win in AES contest ??
Date: Sat, 30 Jan 1999 22:53:25 GMT
In article <78v7p6$3lk$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Thomas Pornin) wrote:
> According to <[EMAIL PROTECTED]>:
> > If I write a DJGPP C ASM combination code for one of the
> > AES candidates can I make my source available
>
> You may not:
> -- write some code into US/Canada and then export it out of US/Canada
> -- write some code and make it freely available if the algorithm is
> protected by some license or patent. Some AES candidates have been
> put by their respective authors into public domain. Others have not.
>
> When the real AES will be chosen, it will be usable for open source and
> all those things. I do not know what will be the US import/export rules
> though (neither do I know this for my own country, as things are moving
> real fast in this field these days).
>
> It is still possible that NSA agents come at your home at night and shoot
> you, but this would not be legal.
>
> --Thomas Pornin
>
If they choose to do what your proposing they would use some mad
dog of an English man so that they could claim plasable deniability.
Besides if the twinky defense worked in court just think how good
the mad cow defense would work. I already recieve enough threatning
mail from some crazy Englishmen. But I don't wish to make enemies
out of all of them I think Paul Onions is a nice guy I really wonder
why he has not left for a better country. I guess I have'nt made to
many enemies in France yet. But that could have something to do with
not speaking French.
But if I spoke German maybe since I'm a heavy beer drinker I could
fit in over there with out making to many enemies.
David Scott
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (user)
Subject: Re: Encryption for my little java-mail-server
Date: Sun, 31 Jan 1999 00:03:09 GMT
On Sat, 30 Jan 1999 23:41:12 GMT, Dominik Werder <[EMAIL PROTECTED]> wrote:
>Hi All!
>
>I need any good and fast encryption for my little java chat server. I
>tried RSA, but its too slow. Has anybody DES or IDEA for Java or
>Pseudocode or a realy good docu for these algorithms?
>Then please mail me: [EMAIL PROTECTED]
JCA http://java.sun.com/products/jdk/1.2/
JCE http://java.sun.com/products/jdk/1.2/jce/
Cryptix http://www.systemics.com/software/cryptix-java/
IAIK http://wwwjce.iaik.tu-graz.ac.at/
JCP http://www.jcp.co.uk/index.htm
Above links from the book Java Cryptography.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random numbers from a sound card?
Date: Sun, 31 Jan 1999 00:06:40 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 30 Jan 1999 14:31:17 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>> How come you state that Champernowne's number has an "excess of ones
>> over zeros"?
>Because all the leading zeros are suppressed.
Can you elaborate with an example.
Bob Knauer
"I place economy among the first and most important virtues and
public debt as the greatest dangers to be feared. We must not
let our rulers load us with perpetual debt."
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Sun, 31 Jan 1999 00:08:31 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 30 Jan 1999 17:15:11 GMT, [EMAIL PROTECTED] (Kurt Wismer)
wrote:
>i don't
>see any foolproof method of verifying that the trng is indeed a trng,
>however...
I believe that a radioactive decay TRNG can be verified to within a
known level of precision.
Bob Knauer
"I place economy among the first and most important virtues and
public debt as the greatest dangers to be feared. We must not
let our rulers load us with perpetual debt."
--Thomas Jefferson
------------------------------
** 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
******************************
