NDLI: Optimal Randomizer Efficiency in the Bounded-Storage Model

Please wait, while we are loading the content...

Optimal Randomizer Efficiency in the Bounded-Storage Model

Content Provider	Springer Nature Link
Author	Dziembowski, Stefan Maurer, Ueli
Copyright Year	2003
Abstract	In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary’s storage capacity is bounded, say by $s$ bits, even if her computational power is unlimited. Assume that a random $t$ -bit string $R$ is either publicly available (e.g., the signal of a deep-space radio source) or broadcast by one of the legitimate parties. If $s < t$ , the adversary can store only partial information about $R$ . The legitimate sender Alice and receiver Bob, sharing a short secret key $K$ initially, can therefore potentially generate a very long $n$ -bit one-time pad $X$ with $n\gg\|K\|$ about which the adversary has essentially no information. All \looseness = –1 previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key $K$ had to be longer than the derived one-time pad ( $n < \|K\|$ ), or $t$ had to be extremely large ( $t > ns$ ), or the adversary was assumed to be able to store only $s$ actual bits of $R$ rather than arbitrary $s$ bits of information about $R$ , or the adversary received a non-negligible amount of information about $X$ . In this paper we prove the first non-restricted security result in the bounded-storage model: $K$ is short, $X$ is very long, and $t$ needs to be only moderately larger than $s + n$ . In fact, $s/t$ can be arbitrarily close to $1$ and hence the storage bound is essentially optimal. The security can be proved also if $R$ is not uniformly random, provided that the min-entropy of $R$ is sufficiently greater than $s$ .
Starting Page	5
Ending Page	26
Page Count	22
File Format	PDF
ISSN	09332790
Journal	Journal of Cryptology
Volume Number	17
Issue Number	1
e-ISSN	14321378
Language	English
Publisher	Springer-Verlag
Publisher Date	2003-11-26
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model

Encryption against Storage-Bounded Adversaries from On-Line Strong Extractors

Non-interactive Timestamping in the Bounded-Storage Model

Constant-Round Oblivious Transfer in the Bounded Storage Model

Bounded Degree Interval Sandwich Problems

Isomorphism for Graphs of Bounded Distance Width

Molecular Computing, Bounded Nondeterminism, and Efficient Recursion

Dynamic Algorithms for Graphs of Bounded Treewidth

Optimal dividend strategy in compound binomial model with bounded dividend rates

Optimal Randomizer Efficiency in the Bounded-Storage Model

Similar Documents

Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model

Encryption against Storage-Bounded Adversaries from On-Line Strong Extractors

Non-interactive Timestamping in the Bounded-Storage Model

Constant-Round Oblivious Transfer in the Bounded Storage Model

Bounded Degree Interval Sandwich Problems

Isomorphism for Graphs of Bounded Distance Width

Molecular Computing, Bounded Nondeterminism, and Efficient Recursion

Dynamic Algorithms for Graphs of Bounded Treewidth

Optimal dividend strategy in compound binomial model with bounded dividend rates

Optimal Randomizer Efficiency in the Bounded-Storage Model