Unfortunately, there is nothing called "truely random". Functions or programs that generate these are pseudorandom functions (or pseudorandom generators PRG) which generate sequences of numbers "statistically indistinguishable" from turly random sequences.
The main problem is if you are using a PRG to generate random numbers, it is cannot be proven
A) A PRG is definitely pseudorandom B) A PRG will behave well for all given seeds.
Infact it is not known if PRGs exist (if it is proved that PRGs exist its a one line proof to prove P not equals NP ). Hence schemes that directly use PRGs to encrypt are suspect.
The only reliable way is to generate random numbers for one time pads is by - schemes like shuffling a deck of cards and picking one at random. Then these pads can be exchanged through public key encryption (RSA or DH key exchange). And then the pads can be used to encrypt.
This is a well known technique - the only problem is generating one time pads. If the company does away with generating one time pads by exchanging programs or by exchanging seeds it is bull.
Because then - the scheme is only as secure as Public Key and the PRG used to generate pseudo random numbers (whichever is lower).
The crux - true randomness does not exist unless you shuffle a deck of cards. I dont think that prescient employs thousands of card shufflers who would shuffle cards and securely tell you the one time pads:). All other schemes that generate one time pads using PRG, seed exchage for PRG is already known and is regarded to be weak.
No - Counter intuitive as it may seem, picking a pseudo random function at random to generate random numbers is only as secure as picking a random seed for *a* defined pseudorandom function and generating random numbers. This and more fascinating crypto stuff in "Foundations of Cryptography" - Some portions of it are also accessible here http://theory.lcs.mit.edu/~oded/ln89.html .
Godel's Proof is applicable to all Axiomatic systems. ie Systems that build upon a few basic assumptions whose validity cannot be questioned or proved. Our current system of mathematics and logic is an example. ie - using our system of mathematics and logic as we know of today - we cannot describe accurately (without contadictions) all problems, leave alone solve them. Tis quite depressing to know that the number of such problems are uncountably infinite.
Somehow our thinking is also tied to logic. We think logically based on certain premises, assumptions and propositions. So our thought process itself as of today comes under the purview of Godel's proof. So as of today there will always be things we cannot understand or reason about
Is our brain a turing machine (an axiomatic system ?) well people are up with cudgels regarding this. Quite franky - people dont know. Also people donot know how to construct a non-axiomatic system - ie a system without a few basic assumptions.
I want to clear up this confusion about Godel's proof being applicable to only recursive and self referential systems. Basically an axiomatic system is a superset of self referential and recursive system. (A hand waving explanation would be - you have these basic axioms, then build a complex system of proofs and results out of these axioms and then try to prove the axioms with these results and proofs. Now that is cheating as it amounts to circular reasoning. This is a recursive and self referential system - but then axiomatic systems are much more than that) So the final verdict is
1. Using the current system of math, logic and reasoning - there are uncountably infinite number problems that cannot be tackled.
2. This limitation applies to _ALL_ fancy axiomatic systems we can come up with.
3. It is as yet unclear if it is possible to build a non axiomatic system.
Dr Felton,
In the cryptography community it is a well estabilshed fact that "security by obscurity of the securing process" is not only weak but also dangerous, giving a false sense of security. In this context I would like to pose two questions
1. What do you think will be the future of effective cryptography research in this context ?
2. Do you, in your personal opinion, think that organizations like SDMI are playing a double game by inviting review but preventing publication ? Do you think this unhealthy precedent will affect cryptography researchers ?
Slashdot Mirror
Unfortunately, there is nothing called "truely random". Functions or programs that generate these are pseudorandom functions (or pseudorandom generators PRG) which generate sequences of numbers "statistically indistinguishable" from turly random sequences.
:). All other schemes that generate one time pads using PRG, seed exchage for PRG is already known and is regarded to be weak.
The main problem is if you are using a PRG to generate random numbers, it is cannot be proven
A) A PRG is definitely pseudorandom
B) A PRG will behave well for all given seeds.
Infact it is not known if PRGs exist (if it is proved that PRGs exist its a one line proof to prove P not equals NP ). Hence schemes that directly use PRGs to encrypt are suspect.
The only reliable way is to generate random numbers for one time pads is by - schemes like shuffling a deck of cards and picking one at random. Then these pads can be exchanged through public key encryption (RSA or DH key exchange). And then the pads can be used to encrypt.
This is a well known technique - the only problem is generating one time pads. If the company does away with generating one time pads by exchanging programs or by exchanging seeds it is bull.
Because then - the scheme is only as secure as Public Key and the PRG used to generate pseudo random numbers (whichever is lower).
The crux - true randomness does not exist unless you shuffle a deck of cards. I dont think that prescient employs thousands of card shufflers who would shuffle cards and securely tell you the one time pads
-Dracken
No - Counter intuitive as it may seem, picking a pseudo random function at random to generate random numbers is only as secure as picking a random seed for *a* defined pseudorandom function and generating random numbers. This and more fascinating crypto stuff in "Foundations of Cryptography" - Some portions of it are also accessible here http://theory.lcs.mit.edu/~oded/ln89.html .
-Dracken
Godel's Proof is applicable to all Axiomatic systems. ie Systems that build upon a few basic assumptions whose validity cannot be questioned or proved. Our current system of mathematics and logic is an example. ie - using our system of mathematics and logic as we know of today - we cannot describe accurately (without contadictions) all problems, leave alone solve them. Tis quite depressing to know that the number of such problems are uncountably infinite.
Somehow our thinking is also tied to logic. We think logically based on certain premises, assumptions and propositions. So our thought process itself as of today comes under the purview of Godel's proof. So as of today there will always be things we cannot understand or reason about
Is our brain a turing machine (an axiomatic system ?) well people are up with cudgels regarding this. Quite franky - people dont know. Also people donot know how to construct a non-axiomatic system - ie a system without a few basic assumptions.
I want to clear up this confusion about Godel's proof being applicable to only recursive and self referential systems. Basically an axiomatic system is a superset of self referential and recursive system. (A hand waving explanation would be - you have these basic axioms, then build a complex system of proofs and results out of these axioms and then try to prove the axioms with these results and proofs. Now that is cheating as it amounts to circular reasoning. This is a recursive and self referential system - but then axiomatic systems are much more than that) So the final verdict is
1. Using the current system of math, logic and reasoning - there are uncountably infinite number problems that cannot be tackled.
2. This limitation applies to _ALL_ fancy axiomatic systems we can come up with.
3. It is as yet unclear if it is possible to build a non axiomatic system.
Dr Felton,
In the cryptography community it is a well estabilshed fact that "security by obscurity of the securing process" is not only weak but also dangerous, giving a false sense of security. In this context I would like to pose two questions
1. What do you think will be the future of effective cryptography research in this context ?
2. Do you, in your personal opinion, think that organizations like SDMI are playing a double game by inviting review but preventing publication ? Do you think this unhealthy precedent will affect cryptography researchers ?
So 4 million $ was spent and the cat was rigged and during the demo time - a van mysteriously runs over the cat! Cat works, the van was the villian!
Kinda remids me about my semester project that worked but sadly during the demo time my machine crashed and formatted the disk.