NDLI: Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models

Content Provider	IEEE Xplore Digital Library
Author	Naor, M. Segev, G. Smith, A.
Copyright Year	1963
Abstract	We address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to ldquomanuallyrdquo authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any there exists a -round protocol for authenticating -bit messages, in which only bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of on the required length of the manually authenticated string. The second model we consider is the traditional message authentication model. In this model, the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. We apply the proof technique above to obtain a lower bound of on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (Advances in Cryptology-CRYPTO '93, pp. 355-367, 1993). Finally, we prove that one-way functions are necessary (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting.
Sponsorship	IEEE Information Theory Society
Starting Page	2408
Ending Page	2425
Page Count	18
File Size	448167
File Format	PDF
ISSN	00189448
Volume Number	54
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-06-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Information security Message authentication Cryptographic protocols Computer crime Entropy Cryptography Computer science Gas insulated transmission lines Communication system control Communication channels unconditional security Authentication cryptographic protocols lower bounds
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

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

Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models (2006)

Tight bounds for unconditional authentication protocols in the manual channel and shared key models (2006)

Tight bounds for unconditional authentication protocols in the manual channel and shared key models (2006)

Tight bounds for unconditional authentication protocols in the manual channel and shared key models. Cryptology eprint archive, report 2006/175 (2006).

Using One-Way Chains to Provide Message Authentication without Shared Secrets

Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

Key-exchange authentication using shared secrets

New Monotones and Lower Bounds in Unconditional Two-Party Computation

Unconditional authenticity and privacy from an arbitrarily weak secret (2003)

Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models

Similar Documents

Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models (2006)

Tight bounds for unconditional authentication protocols in the manual channel and shared key models (2006)

Tight bounds for unconditional authentication protocols in the manual channel and shared key models (2006)

Tight bounds for unconditional authentication protocols in the manual channel and shared key models. Cryptology eprint archive, report 2006/175 (2006).

Using One-Way Chains to Provide Message Authentication without Shared Secrets

Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

Key-exchange authentication using shared secrets

New Monotones and Lower Bounds in Unconditional Two-Party Computation

Unconditional authenticity and privacy from an arbitrarily weak secret (2003)

Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models