From: pom@anke.imsd.uni-mainz.DE (Prof. Dr. Klaus Pommerening)
Subject: unpredictable random generators (terminology)
Organization: Johannes Gutenberg Universitaet Mainz
Date: Thu, 19 Nov 1992 09:47:48 GMT

In article <1992Nov12.171127.2162@ee.eng.ohio-state.edu>  
butzerd@blanc.eng.ohio-state.edu (Dane C. Butzer) writes:
> >Indeed, I personally avoid the
> >word "random" in the sense you call "cryptographic randomness"; I tend to
> >call it "unpredictable" as contrasted with "random" and mean  
"algorithmically
> >unpredictable" as opposed to "algorithmically random" since we are dealing 
> >with pseudo-randomness in virtually every case where these ideas apply  
anyway.
> Good idea.  I'll do that from now on.  How about trying on a new acronym,
> too: URNG for Unpredicatble Random Number Generator, to distinguish RNGs
> that are designed for cryptography from the typical PRNGs?

In the literature there is a certain confusion as to how call this sort
of (unpredictable) pseudo-random generators. Examples are:
 - secure
 - unpredictable
 - cryptographically strong
 - perfect
I prefer the latter term, because it is so short, and, more
important, the cryptographic strength implies that the generator
passes all efficient statistical tests -- truly perfect, isn't it?
Here is a small bibliography:

S. G. Akl, H. Meijer:                                                        
   A fast pseudo random permutation generator with applications                 
   to cryptology.                                                               
   In CRYPTO '84, 269--275.                                                     
W. Alexi, B. Chor, O. Goldreich, C. P. Schnorr:                              
   RSA and Rabin functions: Certain parts are as hard as the whole.             
   SIAM J. Comput. 17 (1988), 194--209.                                         
L. Blum, M. Blum, M. Shub:                                                   
   A simple unpredictable pseudo-random number generator.                       
   SIAM J. Comput. 15 (1986), 364--383.                                         
M. Blum, S. Micali:                                                          
   How to generate cryptographically strong sequences of                        
   pseudo-random bits.                                                          
   SIAM J. Comput. 13 (1984), 850--864, =                                     
   Proc. 23th IEEE Symp. on Foundations of Computer Science, 1982,              
   112--117.                                                                    
K. J. Edwards:                                                               
   Perfect pseudorandom numbers.                                                
   Bull. Inst. Math. Appl. 24 (1988), 80--81.                                   
O. Goldreich, S. Goldwasser, S. Micali:                                      
   On the cryptographic applications of random functions.                       
   In CRYPTO '84, 276--288.                                                     
E. Kranakis:                                                                 
   Primality and Cryptography.                                           
   Wiley-Teubner Series in Computer Science,                                    
   Teubner, Stuttgart 1986                                                      
H. Krawczyk:
   How to predict congruential generators.
   In: CRYPTO '89, 138--153.
S. Micali, C. P. Schnorr:                                                    
   Efficient, perfect random number generators.                                 
   In CRYPTO '88.                                                           
A. Shamir:                                                                   
   On the generation of cryptographically strong pseudo-random                  
   number sequences.                                                            
   8th International Colloquium on Automata, Languages and                      
   Programming.                                                                 
   Lecture Notes in Computer Science 62,                                        
   Springer-Verlag, Berlin usw. 1982, und                                       
   ACM Trans. Comput. Systems 1 (1983), 38--44.                                 
U. V. Vazirani, V. V. Vazirani:                                              
   Efficient and secure pseudo-random number generation.                        
   Proc. 25th IEEE Symp. on Foundations of Computer Science, 1984,              
   458-463,                                                                     
   and in CRYPTO '84, 193--202.                                                 
A. C. Yao:                                                                   
   Theory and applications of trapdoor functions.                               
   Proc. 23th IEEE Symp. on Foundations of Computer Science, 1982,              
   88--91.                                                                      

Note: CRYPTO 'xx is
   Advances in Cryptology: Proceedings of CRYPTO 'nn.                      
   Proceedings Univ. of California, Santa Barbara 19nn.                         
   Lecture Notes in Computer Science xxx,                                       
   Springer-Verlag, Berlin usw. 19xx.                                           

--
Prof. Dr. Klaus Pommerening
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet
Obere Zahlbacher Strasse 69, W-6500 Mainz, Germany
Newsgroups: sci.crypt