Cryptography-Digest Digest #144, Volume #13 Sun, 12 Nov 00 06:13:00 EST
Contents:
Re: voting through pgp ("John A. Malley")
Re: hardness of monoid word problem? (MikeAt1140)
Re: Legal reqiurements for CCTV watermarking ([EMAIL PROTECTED])
Technical articles on cryptography (Guy Macon)
Re: Algorithm with minimum RAM usage? (Guy Macon)
Re: voting through pgp (David Wagner)
Re: Integer encoding on a stream (Mikael Lundqvist)
Re: Updated XOR Software Utility (freeware) Version 1.1 from Ciphile Software (Tim
Tyler)
Re: Q: Rotor machines (Mok-Kong Shen)
Re: Updated XOR Software Utility (freeware) Version 1.1 from Ciphile Software (Tim
Tyler)
Re: Integer encoding on a stream (Mok-Kong Shen)
Re: "Secrets and Lies" at 50% off (Richard Heathfield)
Re: Q: Rotor machines (John Savard)
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: voting through pgp
Date: Sat, 11 Nov 2000 21:52:20 -0800
David Wagner wrote:
>
> John A. Malley wrote:
> >Making the act of voting public introduces a distributed, collective
> >witnessing/authentication to the genuineness of the vote cast.
>
> I don't see it yet. If we're talking about Internet voting, making the
> fact that someone has voted does not say anything about the genuineness
> of the vote cast -- you can't tell whether or not the vote cast was the
> one the legitimate user wanted to be cast.
The witnesses must authenticate the voter, and the voter must
authenticate the witnesses while the voter casts the vote. The vote
remains secret to all. Witnessing the act of voting prevents any
individual voter from voting again. Some witness of the previous act can
detect the next fraudulent attempt and flag it as suspicious. A
"genuine" voting act as used in this context is the one, true voting act
with the casting of a decision allowed the individual. A second attempt
at voting, or voting without authorization, are examples of fraudulent,
non-genuine voting acts.
The decision made by the voter, as a "thing-in-itself", is created at
the moment of decision, the decision value must be public and
tamper-proof (non-malleable) and independent of the identity of the
creator (impossible to trace back to the citizen who cast it) and must
bear the identities of the witnesses (and the voter - maybe) who saw the
act of its creation. The marking of the decision by the witnesses must
also be non-malleable and irrefutable. The more witnesses who saw its
creation the harder it is to pin on any individual witness.
Witnesses remember the number of acts of voting - all witnesses
gathered together would produce a memory of all actual acts of voting -
and the number of acts of voting must equal the number of decisions made
in the election. Disagreement indicates fraud.
No single witness remembers everything. The set of all witnesses who
participated can be regenerated from all of the decisions (as
"things-in-themselves", like ballots signed by witnesses for example.)
The set of all witnesses can be regenerated from the witnesses
themselves who remembered (in some way) who they saw vote. These
regenerated sets must agree - disagreement indicates fraud.
>In a physical voting situation,
> this issue does not arise, because one has a trusted path to a mechanism
> trusted to accurately record the user's wishes, but there is no basis for
> such trust when one is talking about voting on one's home PC.
I agree.
> Nor do I
> think that this is an issue that can be easily solved with clever
> cryptographic algorithms.
Perhaps a protocol could be constructed that is "identical" to the
physical voting in polling places covering aspects like the witnessing
of the act of voting by others, the anonymous, non-malleable ballot ( a
punched hole cannot be undone!), the voter registration card with
physical signature, etc.
BUT, as the number of operations and steps, challenges and responses,
time marks and secure hashes, secure PRNGs, signatures, symmetric and
public key encipherments and even key sizes increase to ensure a secure
election,
one must wonder,
why not just use the paper and punch/ink system we use today? :-)
Binary information is by nature easy to copy, move, manipulate. Look at
all the hoops we must jump through to give bits the same characteristics
of permanence as marks on stone (recall the ostracon?) or ink on paper.
I'd prefer to stick to ink and paper ballots that I mark with a pen or
poke with a stylus. Let's not change just for change's sake.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (MikeAt1140)
Date: 12 Nov 2000 06:55:37 GMT
Subject: Re: hardness of monoid word problem?
<< Subject: hardness of monoid word problem?
From: David A Molnar [EMAIL PROTECTED]
Date: Fri, Nov 10, 2000 10:02 PM
Message-id: <8uics0$b0m$[EMAIL PROTECTED]>
Hi,
Does anyone have pointers to using the following problem for cryptography:
Given: A finitely presented monoid M (say by generators and relations) and
some string S.
Question1 : Can S be derived by composing elements of M ("is S an element
of M?")?
Question2 : If S is an element of M, what is an explicit derivation of
S from a set of generators of M ?
I think that this is either called or closely related to the "word
problem" for a monoid M.
I am aware of the Anshel-Goldfeld scheme for encryption based on the word
problem in a particular group. I am wondering if something similar may be
constructed for a monoid. I also vaguely remember something in A.
Salomaa's book _Public-Key Cryptography_ along these lines regarding
syntactic monoids of automata -- does anyone have results on the security
of that scheme?
I know there exist finitely presented monoids in which the word problem is
undecidable. It seems to me that a "bounded derivation" version of the
word problem in such monoids is then likely to be NP-hard. Not that this
tells us anything about difficulty in practice, of course. :-)
Thanks much,
-David Molnar
David
There really is quite alot of scattered material
concerning encryption based on monoids. Salomaa's text includes a description
of a cryptosystem based on iterated morphisms.
See also the text by R.V.Book and F.Otto,
"String Rewriting Systems" Springer 1993
for security protocols.
The list below may be of some interest. Let me know of this has been of help.-
Michael Anshel
1985:
N.R.Wagner and M.R.Magyarik,
"A public key cryptosystem based on the word problem",
Advances in Cryptology: Proceedings of Crypto 84,ed.G.R.Blakely and D.Chaum,
LNCS,196 Springer Verlag (1985) 19-36
(detailed discussion in W.Patterson,"Mathematical Cryptology" Rowman and
Littlefield
(1987) including a discussion of word problems).
1988
Do Long van,AJeyanthi,R.Siromoney and K.G.Subramanian,
"Public key cryptosystems based on word problems"
ICOMIDC Sym.Math.of Computation,Ho Chi Minh City April (1988)
( a monograph by N.Koblitz, "Algebraic Aspects of
Cryptography" Springer 1998)
1991
M.Garzon and Y.Zalcstein,
"The complexity of Grigorchuk groups with applications to cryptography",
Theoretical Computer Science 88:1(1991) 83-98
(additional discussion may be found in M.Garzon, "Models of Massive
Parallelism"
Springer-Verlag (1995))
1993
I. Anshel and M. Anshel,
"From the Post-Markov Theorem through Decision Problems to Public-Key
Cryptography", American Mathematical Monthly Vol.100, No. 9 (November 1993)
835-845.
1994
V.M.Sidel'nikov,M.A.Cherepenev and V,V Yashichenko,
"Systems of open distribution of keys on the basis of noncommutative
semigroups",
Russian. Acad. Sci. Dokl. Math. Vol.48 No.2 (1994) 384-386
1997
Rabi, Muhammad, and Alan T. Sherman,
``An observation on associative one-way functions in complexity theory,''
Information Processing Letters 64 (2) (1997) 239-244
1999
I. Anshel,M. Anshel,and D. Goldfeld,
"An Algebraic Method for Public-Key Cryptography",
Mathematical Research Letters 6 (1999) 1-5
2000
K.H.Ko,S.J.Lee,J.H.Chean,J.W.Han,J.S.Kang,C.Park,
"New Public-Key Cryptosystem Using Braid Groups" manuscript 2/10/2000
(presented at Crypto 2000)
Also see:
[Gar] Paul Garrett, "Making,Breaking Codes:An Introduction to Cryptology",
Prentice Hall (2001) pp.183-187
and at http://www.math.umn.edu/~garrett/crypto/arithm.html
*****************************************
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Legal reqiurements for CCTV watermarking
Date: Sun, 12 Nov 2000 08:47:51 GMT
In article <[EMAIL PROTECTED]>,
Andrew Cogger <[EMAIL PROTECTED]> wrote:
> Greetings.....
>
> (Appologies if this is way way way OT)
>
> >
> My question...does anyone have any idea what the requirements
> for digital watermarks/signatures are in order for them to be
> used in court? I realise that this is locale specific, but any legal
> precedents or examples would be greatly appreciated.
>
Not law, but some of the issues were addressed in the United Kingdom
House of Lords Select Committee on Science and Technology Fifth Report
http://www.parliament.the-stationery-
office.co.uk/pa/ld199798/ldselect/ldsctech/064v/st0502.htm
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Technical articles on cryptography
Date: 12 Nov 2000 09:30:45 GMT
I found a nice collection of papers on crypto at:
http://citeseer.nj.nec.com/Security/Encryption/
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Algorithm with minimum RAM usage?
Date: 12 Nov 2000 09:46:02 GMT
Dido Sevilla wrote:
>
>
>Tom St Denis wrote:
>>
>> Perhaps in the 2001' CHES proceedings you will find your answer
>> (hehehe). For now... consider using a variant of Twofish or Rijndael
>> where the scheduled key is stored in a ROM/EEPROM. This will lower the
>> key agility but also lower the RAM requirement.
>>
>
>A reasonable implementation of Rijndael on the 8051 microcontroller
>requires 54 bytes of scratch RAM if the key schedule is generated on the
>fly as the subkeys are needed. Serpent would need 56 with the same
>constraints. Twofish needs 52. RC6 needs 77. Don't even think about
>implementing MARS on a small embedded processor... If key agility is a
>concern, on the fly key expansion can be performed instead of burning
>the expanded key in ROM. These RAM usage figures are from a paper
>"Evaluation of Serpent, one of the AES finalists, on 8-bit
>microcontrollers", by Vincent Journot, available as part of the Serpent
>8051 implementation tarball.
>
I found a paper that covers minimum ram crypto on smartcards. It's
Performance Comparison of the AES Submissions
B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson
http://www.counterpane.com/aes-performance.pdf
http://citeseer.nj.nec.com/schneier-performance.html
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: voting through pgp
Date: 12 Nov 2000 09:57:42 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Ok, I see. Witnessing helps with authenticating voters. But it doesn't
help me if my computer has been silently infected with an "Election Day"
virus which secretly changes my vote. (Crypto can't help if one of the
endpoints is not trustworthy.) So it's not a silver bullet, but it still
seems like it could be useful. Right?
>why not just use the paper and punch/ink system we use today? :-)
Good question!
>Let's not change just for change's sake.
I agree.
------------------------------
From: Mikael Lundqvist <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Integer encoding on a stream
Date: Sun, 12 Nov 2000 10:06:25 GMT
If I had to solve something like this, I would be interested in how wide
the range of integers is, i.e. how many integers are there? I would also
be interested in the behavior of the integers. Can prediction be used?
If prediction is not of any help, then the task should be simple.
Storing a number on a bitstream should not be of any importance for the
compression part. As almost always, the more information you can extract
from the integers the better compression you will get.
I hope that these 2c were no slugs though.
Regards,
--
Mikael Lundqvist
mailto:[EMAIL PROTECTED]
http://hem.spray.se/mikael.lundqvist/
Who said:
"If a solution is simple, then it's probably correct!"?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Crossposted-To: alt.freespeech,talk.politics.misc,talk.politics.crypto
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Updated XOR Software Utility (freeware) Version 1.1 from Ciphile
Software
Reply-To: [EMAIL PROTECTED]
Date: Sun, 12 Nov 2000 10:27:52 GMT
In sci.crypt Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
[program size]
: You know why it is as large as it is. Don't complain to me. This
: is the nature of the modern GUI interface. [...]
It is not really. Java indicates that GUI interfaces can be
distributed in a very compact form - assuming all the libraries
that come with the JVM are already present.
: Why do you need it open source? It does what it is intended to do
: and what it is claimed to do and does no more than it is supposed
: to do and you can prove this by using it [...]
No, in fact, that would be impossible.
: You are not getting the source code. I thought of it and engineered
: it and I am not going to just give it to you all. Yes, it's simple
: but as most of you should realize by now with all the posturing and
: pretending in these news groups that all this cannot be too easy
: because almost none of you are thinking of new ideas or innovations
: or even producing the simplest of software and making it available
: to the public. Your lack of creativity and imagination has been
: demonstrated by your deciding that your place in these news groups
: is as pseudo consumer advocate. But you have merely become trivial
: clowns.
Great. Alienate most of your audience, why don't you?
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Rotor machines
Date: Sun, 12 Nov 2000 11:35:42 +0100
Steve Portly wrote:
>
> Mok-Kong Shen wrote:
>
> > John Savard wrote:
..........
[snip]
> As you pointed out these systems would be secure for even short messags.
> Perhaps we need to set more parameters to answer this question?
> I was hoping we could gently explore the possible implications of modern
> computers that don't use binary digits.
It is not very clear what you meant. All modern digital
computers employ bits with which all kinds of informations
can be efficiently processed. Any operations that can be
done in another (conceptual) computation system can be mapped
to the binaray system. It seems unlikely that there will
be alternative more efficient technology of computation, at
least in the foreseeable future.
M. K. Shen
------------------------------
Crossposted-To: alt.freespeech,talk.politics.misc,talk.politics.crypto
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Updated XOR Software Utility (freeware) Version 1.1 from Ciphile
Software
Reply-To: [EMAIL PROTECTED]
Date: Sun, 12 Nov 2000 10:32:06 GMT
In sci.crypt Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
: Scott Craver wrote:
:> Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
:> >Why do you need it open source? It does what it is intended to do
:> >and what it is claimed to do and does no more than it is supposed
:> >to do and you can prove this by using it
:>
:> NO. While I trust that you are not providing an evil
:> trojan horse (or accidentally distributing a 70KB binary
:> with 230KB of viruses attached,) it is NOT EVER the case
:> that merely using the program proves it works as
:> specified.
: You know all the facts?
: We don't think so. After all, how could you?
: So what exactly are you trying to prove?
: You've proved it: you're not very smart to think we are not as
: smart as you.
Use of the royal "we" will distract few from the fact that while you are
being given obviously sensible advice, you appear intent on ignoring it.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Integer encoding on a stream
Date: Sun, 12 Nov 2000 11:47:32 +0100
Benjamin Goldberg schrieb:
>
> A while back, I asked a few questions about how one should store an
> integer on a bit stream in a way that uses few bits. I found this
> method in Knuth (volume 3), for a method which had the additional
> requirements for being prefix free, and having larger integers be
> lexicographically greater than smaller integers.
I suppose it is not very clear what your requirement is.
If you want to put out wholly arbitrarily numbers in the
range [0, 2^n-1], then I can't yet understand that there
could be any scheme that in the average performs better
than using n bits to represent a number in the usual way.
If the numbers are correlated or some sizes of numbers
are more frequent than the others, then I think that
certain economy could eventually be realized. Could you
please explain a bit about the issue?
M. K. Shen
------------------------------
Date: Sun, 12 Nov 2000 10:49:09 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Re: "Secrets and Lies" at 50% off
Stuart Krivis wrote:
>
> On 16 Sep 2000 16:55:54 GMT, Bill Unruh <[EMAIL PROTECTED]> wrote:
> >In <[EMAIL PROTECTED]> [EMAIL PROTECTED]
>(SCOTT19U.ZIP_GUY) writes:
> >
> >> I think I get derision because I don't worshop Mr. BS
> >>and think people vastly overrate is abilitues.
> >
> >Actually, it is for your spelling.
>
> I asked a random sample of the people in my office if they would want to
> read comments by Bruce. They said yes. I then asked if they wanted to read
> comments by David Scott, and they all asked, "Who the fsck is he, and why
> would I care what he has to say?"
>
> I vote that David A Scott be henceforth banned from Usenet. He's as bad as
> that Sternlight guy that hangs around the encryption groups and has a
> woodie about pgp.
Far be it from me to stick up for a pariah, but I can't let this pass.
1) People's participation in Usenet is not subject to democracy, but it
is subject to law.
If you feel Mr Scott has violated his ISP's terms and conditions, you
could complain to them. If you're not prepared to take this step (and it
is a serious step, usually best reserved for spammers IMHO), then either
killfile him or put up with him.
2) Mr Scott and I have crossed swords on a couple of occasions.
Nevertheless, he is helpful on occasion, and has very gently pointed out
one or two flaws in my own algorithm and the implementation thereof,
without resorting to foul-mouthed ravings (well, not as much, anyway).
3) At least he isn't, IMHO, a snake oil merchant. I know his code is
unreadable, and therefore his algorithm is undecipherable(!), but it's
not as if he rams scott19u down people's throats. More recently, he
seems to be plugging Matt Timmermanns' (sp?) code, rather than his own -
and apparently with some justification.
If you don't like the guy, plonk him. But let's not start voting on the
merits of individuals. We all know from bitter experience that neither
human beings nor computers can be trusted with an election process - we
can't even trust them to count correctly, let alone vote correctly.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Q: Rotor machines
Date: Sun, 12 Nov 2000 10:53:59 GMT
On Sun, 12 Nov 2000 11:35:42 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Steve Portly wrote:
>> I was hoping we could gently explore the possible implications of modern
>> computers that don't use binary digits.
>It is not very clear what you meant. All modern digital
>computers employ bits with which all kinds of informations
>can be efficiently processed. Any operations that can be
>done in another (conceptual) computation system can be mapped
>to the binaray system.
True. Of course, when he said:
>>Perhaps it would depend on whether we used Asci WHITE or ultraviolet?
in another part of this thread, then he was really hard to understand.
After all, there are others in this newsgroup, advocating using
arithmetic in another base than binary - carried out, to be sure, on a
binary computer, even with some loss in efficiency - for cipher
purposes.
A conversion between bases will cause individual digits in one system
to lose their identity, and be broken up into parts that are hard to
follow. But an S-box also does that.
While we won't see computers that do base-26 arithmetic, base-10
arithmetic would make it easier to debug core dumps. But even that is
highly unlikely; ASCII being designed for binary, any computer with
decimal storage would use a nonstandard character code.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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
******************************
