Cryptography-Digest Digest #376, Volume #11 Tue, 21 Mar 00 05:13:02 EST
Contents:
Re: unknown verifier designated verifier proofs (David Hopwood)
Re: Download Random Number Generator from Ciphile Software (Anthony Stephen Szopa)
Re: Download Random Number Generator from Ciphile Software (Anthony Stephen Szopa)
Non-doublespending offline digital money? ("matt")
Re: Card shuffling (Mok-Kong Shen)
Re: hardware errors (Mok-Kong Shen)
----------------------------------------------------------------------------
Date: Tue, 21 Mar 2000 07:38:38 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: unknown verifier designated verifier proofs
=====BEGIN PGP SIGNED MESSAGE=====
David A Molnar wrote:
> This is another idea I'm trying to work out. It may be (even) less
> comprehensible than the previous posts on "encrypting to unknown
> public key", for which I apologize in advance.
No, I think I've got the hang of what you're trying to achieve now.
> In 1996, Jakobsson, Impagliazzo, and Sako introduced the notion of a
> "designated verifier proof."
(in [JSI96])
> This is a proof of the form
>
> Either a secret S is true
> OR
> I know the secret key of the party V
>
> The party V is called a "designated verifier." The idea is that you can
> use these to build proofs of knowledge which are both non-interactive
> *and* non-transferable. The way this works is as follows :
>
> Say I build a proof of the above form. I show it to V. Then V either
> believes that S is true, or that I've compromised his secret key.
> We'll assume that V believes his secret key is safe. Now he must
> believe S.
>
> If V tries to show the proof to anyone else...well...in most settings V
> knows his own secret key. So there is no reason for anyone else to
> believe that S is true. The proof is therefore non-transferable.
It's worth pointing out that there are alternative ways to achieve this
than the type of designated confirmer proofs described in [JSI96] (neat
as those proofs are).
As it happens, I thought about this some time ago in the context of
signatures without a non-repudiation property (since non-repudiation
is not always required or desirable, and IMHO applications that send
messages on behalf of users should give the user a choice of whether
to make the signature non-repudiable or not - provided of course that
the recipient is able to distinguish the two types of signature).
Here's a motivating story - any resemblance to recent events in the
news, especially
<http://news.bbc.co.uk/hi/english/uk/newsid%5F668000/668663.stm> and
<http://www.the-times.co.uk/news/pages/sti/2000/03/19/stinwenws01040.html>
is coincidental, and names have been chosen *entirely* at random :-)
Let's say that Winston, a whistle-blower, wants to communicate with
Julie, a journalist. Julie is deeply concerned about the erosion of
civil liberties in her native country, Airstrip One (capital London).
She is particularly concerned about a new bill being rushed through
parliament, that will allow the secret police and intelligence services
(of which Winston is an ex-member) to demand private keys, on pain of
2 years imprisonment, and to impose secrecy orders that would prevent
her from reporting this abuse of power on the rather excellent
satirical television program that she is a researcher for.
She also believes strongly in the principle of anonymity of journalistic
sources, for which the authorities of Airstrip One have shown scant
regard in recent times.
So, Julie and Winston agree to use a cryptographic protocol (in
conjunction with an anonymous remailer network) that will not allow
Winston's identity to be proven despite the fact that all of their
communications are intercepted, and even if Julie's private key is
seized, or she is tortured by the secret police. Also, ideally the
communications should be untraceable in both directions, so that if
the intelligence services turn out to be monitoring the ciphertext
of Winston's communications but do not know about Julie, it should
be a complete surprise to them when she publishes her story. If the
private keys are not revealed then all messages should be private and
authenticated, so that impersonation and man-in-the-middle attacks
are not possible, but there should be no way for the secret police
to *prove* that any particular message was sent between Winston and
Julie, or what they said to each other. I.e. it should be equally
possible that the secret police faked any purported proof, and
Winston and/or Julie should be able to produce their own version
that is equally convincing (whether true or not).
> This is an insanely cool tool. There's only one minor drawback - in
> the constructions I know about, you need to know a chameleon
> commitment scheme for which V posesses the secret information required
> to forge decommits. This generally means you need to know the identity
> of V. This is kind of annoying if you want to apply these proofs in an
> anonymous protocol.
> The question : can you create a designated verifier proof for V without
> knowing the identity of V ?
It is possible if you combine the authentication with encryption.
[JSI96] points this out:
# This attack [co-operating verifiers] shows that designation of messages
# is a necessary tool for authentication of private messages. A well-known
# way of doing this is for the sender of a message to encrypt it using a
# secret key that only he and the receiver knows, but this only applies
# to plain messages and not to proofs. Still, it is a form of verifier
# designation, as it allows the receiver of a message to simulate identical
# transcripts, thereby making it impossible to prove that the transcript
# indeed originated with the claimed sender.
I.e. as long as we only require untransferable authentication of messages,
rather than fully general untransferable proofs of knowledge, it's quite
possible to have a recipient-hiding encryption scheme that also provides
authentication, where the recipient is the designated verifier.
[...]
> The problems [with using a blind recipient hiding scheme as the public
> key algorithm in a designated verifier proof]:
> Designated verifier proofs can not be recipient hiding.
> The whole "designated verifier" property depends on
> everyone being able to tell that the commitments can
> be forged by V. If the commit doesn't reveal V's
> identity, then V can simply keep quiet about his
> ability to forge the commit and it's all over.
If the message is encrypted, then V, or someone who gets hold of V's
private key (e.g. the secret police in our story) would have to reveal
sufficient information to decrypt the message, and we can arrange for
this information to allow forging a transcript of the authentication
proof. This is not automatic for any encryption and authentication
scheme, though. For example, conventional, non-repudiable signing
followed by public key encryption won't work, because it is possible
for the session key (or whatever nonce is used to make the encryption
scheme non-deterministic) to be revealed - even though the private key
has not been - and this plus the encrypted signed message is a
transferable proof of authentication.
I have some ideas for how to fix that, but it's a bit early in the
morning here to be doing protocol design, so I'll check it more
thoroughly first.
[JSI96] Markus Jakobsson, Kazue Sako, Russel Impagliazzo,
"Designated Verifier Proofs and Their Applications,"
Advances in Cryptology - EUROCRYPT '96,
Volume 1070 of Lecture Notes in Computer Science (Ueli Maurer, ed.),
Springer Verlag, 1996.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBONcmXjkCAxeYt5gVAQHEGgf/bGLSX8I1a0CQJZAWJb+Y7CuPF6JINtTR
kOc6PERAgfwZUXMnXug6RgtfX0hZe79etZZqOnFioue394wX2zvJwowBhVZYTE7I
ybrRpxOq+pEIQ2EAATjU2b5DIuzOk9ldjBd78WZ6nmWclE//aBKRlRXVENfN6BPA
wORaULz+hgM7EGNORcri5IlX1gwfJgLLSJa6z28Lws+QjjQrw+JTTOirojmLLegC
TIkLA1vCgwh46HA1Vy4EoHD77DqkwHrLeStssHnc6kFdLPJ6Y77rhjePeyy4n0eV
eQDAducb4HLdBj1/bwzNFzWzO+mF/cuUgcxj/kocR0mSjORE+ZmjiQ==
=R8F/
=====END PGP SIGNATURE=====
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Download Random Number Generator from Ciphile Software
Date: Tue, 21 Mar 2000 00:08:13 -0800
Taneli Huuskonen wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
>
> In <NjoB4.48416$[EMAIL PROTECTED]> "Tom St Denis"
> <[EMAIL PROTECTED]> writes:
>
> >What is the period of the generator?
>
> If I understand the documentation right, it's of the order of (10!)^2,
> which should be large enough for most purposes. However, there is a
> flaw in the algorithm that makes it definitely unsuitable for serious
> cryptographic purposes and might affect its use for large-scale
> simulation too. Basically, the generator first initializes three arrays
> of 10! permutations of 0..9 each. Denote the i'th permutations in these
> arrays by a_i, b_i and c_i, respectively. Then, on round i, the
> generator produces the number c_i (b_i (c_i (a_i (i mod 10)))), when
> 0 <= i < 10! . When k * 10! <= i < (k+1) * 10!, the permutations
> a_{(i+k) mod 10!}, b_{i mod 10!} and c_{i mod 10!} are used instead.
> If one had access to the raw digit stream, there would be a rather
> trivial way to break the code, given maybe a couple hundred million
> known digits - the only thing that changes between round i and
> round i+10! is the permutation a_i. However, these digits are
> transformed into a stream of bytes by grouping them into triplets,
> dividing by 3 and discarding anything exceeding 255. This makes it more
> difficult to attack the cipher, possibly preventing an amateur such as
> myself from breaking it.
>
> Taneli Huuskonen
>
> -----BEGIN PGP SIGNATURE-----
> Version: 2.6.3i
> Charset: noconv
>
> iQB1AwUBONavAQUw3ir1nvhZAQF7aAL8C5E9CiPZ2+R09U36x/0/KeQguoUqFnqZ
> 7Dj1Tee71DYpgpf+VwczxnlHuIPWH2wfzc4hlywCxbRVHvZUTXFHjm39LrlMlNw2
> 7OqJrJUtv1by6PlIELUbGAKmpBzNH9fi
> =nq2d
> -----END PGP SIGNATURE-----
> --
> I don't | All messages will be PGP signed, | Fight for your right to
> speak for | encrypted mail preferred. Keys: | use sealed envelopes.
> the Uni. | http://www.helsinki.fi/~huuskone/ | http://www.gilc.org/
Let me add in reply to Mr. Taneli Huuskonen: I am pleased to see
you have taken the time to attempt to understand the software
theory. You are correct in stating that the random number stream
as implemented is 10!^2. But this should be qualified as follows:
for any single set of three unique sequences of the 10! permutations
of the digits 0 - 9, you can generate 10!^2 digits. You can change
each set according to the Sterling Approximation providing
approximately 1E66,000,000 unique sets thus generating more random
digits. Furthermore, you are correct in that with a sufficient
number of raw random digits it may be possible to determine the set
sequences and you are correct that since about 25% of the raw random
digits are discarded that this task will be more difficult. But
please note: these raw random digits and the subsequent triplets
(less about 25% discarded) are not used as the final OTPs. These
raw triplets are further processed using as many as 10 different
methods to alter these triplet sequences (see Help File Processes 1
and Processes 2). Once these raw triplets are processed further
and extensively, do you think it is reasonably possible to determine
the original set of three MixFile sequences even if I provide you
with the entire reprocessed 3.36 trillion (approximately) triplets
contained in the final OTPs?
Finally, let me add, that in a coming implementation I will be able
to generate approximately 1.7E32 (minimum) random digits for a single
set of MixFiles. This is significantly more than 10!^2 = 1.3E13.
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Download Random Number Generator from Ciphile Software
Date: Tue, 21 Mar 2000 00:07:42 -0800
Tom St Denis wrote:
>
> What is the period of the generator?
>
> Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Download Random Number Generator from Ciphile Software
> >
> > http://www.ciphile.com
> >
> > see Downloads Currently Available web page
> >
> > OARL3_41.zip (588KB)
> >
> > The intended purpose of the OAR-L3: Original Absolutely Random - Level3
> > Random Number Generation Software Package is to generate or provide
> > random digits or numbers for statistical modeling and computer
> > simulations.
> >
> > The OAR-L3 random number generation software is exactly the same
> > software as OAP-L3: Original Absolute Privacy - Level3 encryption
> > software except there is absolutely NO encryption or decryption
> > capability.
> >
> > Not only have the encryption and decryption GUI forms, menus, buttons,
> > etc. been deleted, but also, the encryption and decryption source code
> > has been deleted, then the entire package recompiled. So there is no
> > way to enable any encryption or decryption methods or capabilities using
> > OAR-L3.
> >
> > The Help files included with OAR-L3 are the exact same help files
> > included with OAP-L3 encryption software. Any references to encryption
> > or decryption in these help files are for informational purposes only.
> > These options are only available with OAP-L3.
> >
> > Again, OAR-L3 random number generation software is only intended to
> > generate random digits or numbers for statistical modeling and computer
> > simulations.
(Please Note: I had some trouble posting this reply and had to
cancel several attempts until I got it right. Sorry for any
inconvenience.)
It is most correct to say that the period, for all practicable
purposes, approaches infinity.
The software is designed to allow the user to continue to generate
random digits indefinitely.
All that need be done is to subsequently process the MixFiles
(randomly ordered sequences of the permutations of the digits
0 - 9 created from random user input) that are used in the random
number generator.
See the Help web page entitled, Sterling Approximation.
Then follow all the processes described to generate the final OTPs
in the web pages entitled, Processes 1 and Processes 2.
Even when you have exhausted all the possible sequences of the
permutations of the digits 0 - 9 for the three MixFiles, you still
have, essentially, an infinite ability to process these random
number files further, generating more random digits.
Let me add in reply to Mr. Taneli Huuskonen: I am pleased to see
you have taken the time to attempt to understand the software
theory. You are correct in stating that the random number stream
as implemented is 10!^2. But this should be qualified as follows:
for any single set of three unique sequences of the 10! permutations
of the digits 0 - 9, you can generate 10!^2 digits. You can change
each set according to the Sterling Approximation providing
approximately 1E66,000,000 unique sets thus generating more random
digits. Furthermore, you are correct in that with a sufficient
number of raw random digits it may be possible to determine the set
sequences and you are correct that since about 25% of the raw random
digits are discarded that this task will be more difficult. But
please note: these raw random digits and the subsequent triplets
(less about 25% discarded) are not used as the final OTPs. These
raw triplets are further processed using as many as 10 different
methods to alter these triplet sequences (see Help File Processes 1
and Processes 2). Once these raw triplets are processed further
and extensively, do you think it is reasonably possible to determine
the original set of three MixFile sequences even if I provide you
with the entire reprocessed 3.36 trillion (approximately) triplets
contained in the final OTPs?
Finally, let me add, that in a coming implementation I will be able
to generate approximately 1.7E32 (minimum) random digits for a single
set of MixFiles. This is significantly more than 10!^2 = 1.3E13.
This reply also would have been forthcoming by reading the entire Help
File Theory and Processes sections.
The thorough Help Files included with the software will most
probably answer any questions you may possibly have: including
the one you just asked.
Yet, I may be willing to answer or clarify additional thoughtful
questions about the random number generator.
If anyone has further interest and or questions, you might want to
first try downloading the OAR-L3: Original Absolutely Random -
Level3 Random Number Generation Software Package at
http://www.ciphile.com
Thank you.
------------------------------
From: "matt" <[EMAIL PROTECTED]>
Subject: Non-doublespending offline digital money?
Date: Tue, 21 Mar 2000 17:29:50 +0800
Hi all.
Could anyone tell me if it is theoretically/physically possible to
have a digital cash system which is offline, and prevents double
spending?
Just thinking about it, it seems impossible. But maybe someone knows
some really tricky maths etc...?
Thanks,
Matt.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Tue, 21 Mar 2000 10:49:53 +0100
Scott Nelson wrote:
>
> Another measure of quality is how many cards stick together
> after the final shuffle. For instance, order a deck and
> shuffle it four times, then examine it. You will probably
> notice that several of the cards are still in sequence.
> (If the deck was completely random, more than 3 in sequence
> would be extremely unlikely.) This "stickyness" has actually
> been used by some bridge players to make educated guesses
> as to the position of certain cards. I.e. if you hold
> the King of hearts, and you remember that the King was
> followed by the Ace last hand, then there's a good chance
> the Ace of hearts is to your left. (Assuming of course
> that the deck wasn't shuffled enough.)
I think the most general situation could be described thus: You give
a person a deck. He does something to it without your observation
and gives it back to you. Now what you see is only a certain
permutation of the original deck. My original post was effectively
asking whether it is sensible (and, if yes, how) to a assign
a numerical value to that permutation characterizing how well the
person has destroyed the order of the deck you gave him. Do you
think that such a measure could be well defined, at least to the
satisfaction of the players?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardware errors
Date: Tue, 21 Mar 2000 10:49:42 +0100
Joseph Ashwood wrote:
>
> Well my level of knowledge of hardware isn't as high as
> some, but I do know how they check. The process actually
> begins with analyzing the design to determine which sets of
> input will exercise which lines internal to the device, then
> a set of inputs which exercise all the lines is determines.
> This set of inputs is then run and the outputs checked. With
> extremely high probability if the outputs are all correct,
> then all input sets will generate the correct outputs. (Yes
> I know I'm over-simplifying a little, but since we're not
> dealing with QA here it's close enough)
What you described is the check in the design process, which
as the history shows is not very perfect despite the availability
of sophisticated software packages for that. On the other hand,
assuming that the design is correct, the chips that are produced
can have defects due to inperfections in the production process. I
have yet no idea how the checks at the end of the production line
are done in practice. Certainly, like other industrial products,
a small sample is taken and tested. But it seems to me to be
quite difficult to test a single chip that has so many functionalities
within a reasonably short time period.
M. K. Shen
M. K. Shen
------------------------------
** 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
******************************
