Pseudorandomness and Cryptographic Applications

By: Michael Luby

Write A Review

Paperback | 9 April 1996

At a Glance

Paperback
248 Pages

Dimensions(cm)
25.4 x 19.6 x 254

Paperback

RRP $160.00

$126.75

21%OFF

or 4 interest-free payments of $31.69 with

Ships in 3 to 5 business days

A pseudorandom generator is an easy-to-compute function that stretches a short random string into a much longer string that "looks" just like a random string to any efficient adversary. One immediate application of a pseudorandom generator is the construction of a private key cryptosystem that is secure against chosen plaintext attack.

There do not seem to be natural examples of functions that are pseudorandom generators. On the other hand, there do seem to be a variety of natural examples of another basic primitive: the one-way function. A function is one-way if it is easy to compute but hard for any efficient adversary to invert on average.

The first half of the book shows how to construct a pseudorandom generator from any one-way function. Building on this, the second half of the book shows how to construct other useful cryptographic primitives, such as private key cryptosystems, pseudorandom function generators, pseudorandom permutation generators, digital signature schemes, bit commitment protocols, and zero-knowledge interactive proof systems. The book stresses rigorous definitions and proofs.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Mathematics Applied Mathematics Stochastics Reference, Information & Interdisciplinary Subjects Interdisciplinary Studies General Studies Computing & I.T.Computer Security Data Encryption Computer Science Mathematical Theory of Computation

Mathematical Modelling Science Science in General Maths for Scientists Engineering & Technology Technology in General Maths for Engineers

Overview and Usage Guide	p. ix
Mini-Courses	p. xiii
Acknowledgments	p. xv
Preliminaries 3
Introduction of some basic notation that is used in all subsequent lectures
Review of some computational complexity classes
Description of some useful probability facts
Introduction to private key cryptosystems, pseudorandom generators, One-way functions
Introduction of some specific conjectured One-way functions	p. 13
Discussions of security issues associated with the computing environment of a party, including the security parameter of a protocol
Definition of an adversary, the achievement ratio of an adversary for a protocol, and the security of a protocol
Definitions of One-way functions and One-way permutations, and cryptographic reduction	p. 21
Definition of a weak One-way function
Reduction from a weak Oneway function to a One-way function
More efficient security preserving reductions from a weak One-way permutation to a One-way permutation	p. 35
Proof that the discrete log problem is either a One-way permutation or not even weak One-way permutation via random self-reducibility
Definition of a pseudorandom generator, the next bit test, and the proof that the Two definitions are equivalent
Construction of a pseudorandom generator that stretches by a polynomial amount from a pseudorandom generator that stretches by One bit	p. 49
Introduction of a Two part paradigm for derandornizing probabilistic algorithms
Two problems are used to exemplify this approach: witness sampling and vertex partitioning	p. 56
Definition of inner product bit for a function and what it means to be a hidden bit
Description and proof of the Hidden Bit Theorem that shows the inner product bit is hidden for a One-way function
Definitions of statistical measures of distance between probability distributions and the analogous computational measures
Restatement of the, Hidden Bit Theorem in these terms and application of this theorem to construct a pseudorandom generator from a One-way permutation
Description and proof of the Many Hidden Bits Theorem that shows many inner product bit are hidden for a One-way function
Definitions of various notions of statistical entropy, computational entropy and pseudoentropy generators
Definition of universal hash Functions
Description and proof of the Smoothing Entropy Theorem	p. 79
Reduction from a One-way One-to-One function to a pseudorandom generator using the Smoothing Entropy Theorem and the Hidden Bit Theorem
Reduction from a One-way regular function to a pseudorandom generator using the Smoothing Entropy Theorem and Many Hidden Bits Theorem	p. 88
Definition of a false entropy generator
Construction and proof of a pseudorandom generator from a false entropy generator
Construction and proof of a false entropy generator from any One-way function in the non- uniform sense	p. 95
Definition of a stream private key cryptosystem, definitions of several notions of security, including passive attack and chosen plaintext
attack, and design of a stream private key cryptosystern that is secure against these attacks based on a pseudorandom generator	p. 105
Definitions and motivation for a block cryptosystern and security against chosen plaintext attack
Definition and construction of a pseudorandom function generator from a pseudorandom generator
Construction of a block private key cryptosystern secure against chosen plaintext attack based on a pseudorandom function generator	p. 117
Discussion of the Data Encryption Standard
Definition of a pseudorandom invertible permutation generator and discussion of applications to the construction of a block private key cryptosystern secure against chosen plaintext attack
Construction of a perfect random permutation based on a perfect random function	p. 128
Construction of a pseudorandom invertible permut
Table of Contents provided by Publisher. All Rights Reserved.

Pseudorandomness and Cryptographic Applications

At a Glance

Paperback

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Mathematical Modelling

Univariate Families of Distributions

Univariate Families of Distributions

Speed

How it Explains the World

Everything Is Predictable

How Bayes' Remarkable Theorem Explains the World

Occupancy Estimation and Modeling

Inferring Patterns and Dynamics of Species Occurrence

Guidance and Control of Unmanned Vehicles

Solar Power Forecasting

Using Time Series and Machine Learning

LOVE! VALOUR! EQUATIONS!

Mathematics of the Couple

Artificial Intelligence Techniques in Mathematical Modeling and Optimization

Intelligent Data-Driven Systems and Artificial Intelligence

Mathematical Modelling Techniques

Mathematical Modelling Techniques

Quantitative Biology

Life from the Numbers

Dynamic Characteristics of Layered Structures: Mathematical Modelling, and Numerical Simulations

Mathematical Modelling, and Numerical Simulations

Mathematical Concepts in Single-Neuron Dynamics

The Mathematical Concepts in Science Series

Mathematical Concepts in Single-Neuron Dynamics

The Mathematical Concepts in Science Series

Fuzzy Sets and Triangular Norms

Aggregation in Decision-Aided Intelligent Systems

Invasive Species

Risk Assessment and Management

Family of High-Ordered Integer-Valued Auto-Regressive Models and Applications

Business Process Analytics

Modeling, Simulation and Design

Applied Statistical Modelling for Ecologists

A Practical Guide to Bayesian and Likelihood Inference Using R, JAGS/Nimbl

Implicit-Explicit Methods for Evolutionary Partial Differential Equations

Ordinary Differential Equations and Applied Linear Algebra

Life Lessons from Game Theory

The Art of Thinking Strategically in a Complex World

Foundations of Mathematical Modeling and Analysis in Engineering

This product is categorised by