FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 | 4 | 5 |   ...   | 9 |

«Limits of Provable Security From Standard Assumptions Rafael Pass∗ Cornell University rafael April 2, 2011 Abstract We show that the ...»

-- [ Page 1 ] --

Limits of Provable Security From Standard Assumptions

Rafael Pass∗

Cornell University


April 2, 2011


We show that the security of some well-known cryptographic protocols, primitives and assumptions (e.g., the Schnorr identification scheme, commitments secure under adaptive selectivedecommitment, the “one-more” discrete logarithm assumption) cannot be based on any standard

assumption using a Turing (i.e., black-box) reduction. These results follow from a general result showing that Turing reductions cannot be used to prove security of constant-round sequentially witness-hiding special-sound protocols for unique witness relations, based on standard assumptions; we emphasize that this result holds even if the protocol makes non-black-box use of the underlying assumption.

∗ First version from November 4, 2010. This revision contains new results on blind signatures (Section 9). Pass is supported in part by a Alfred P. Sloan Fellowship, Microsoft New Faculty Fellowship, NSF CAREER Award CCF-0746990, AFOSR Award FA9550-08-1-0197, BSF Grant 2006317.

Contents 1 Introduction 2

1.1 Our Results......................................... 3

1.2 Other Related Work.................................... 5

1.3 Proof Techniques...................................... 6

1.4 On Non-black-box Reductions............................... 8

1.5 Overview.......................................... 8 2 Preliminaries 8

2.1 Notation........................................... 8

2.2 Basic Definitions...................................... 9

2.3 Black-box reductions........

–  –  –

1 Introduction Modern Cryptography relies on the principle that cryptographic schemes are proven secure based on mathematically precise assumptions; these can be general —such as the existence of one-way functions—or specific—such as the hardness of factoring products of large primes. The security proof is a reduction that transforms any attacker A of the scheme into a machine that breaks the underlying assumption (e.g., inverts an alleged one-way function). This study has been extremely successful, and during the past four decades many cryptographic tasks have been put under rigorous treatment and numerous constructions realizing these tasks have been proposed under a number of well-studied complexity-theoretic intractability assumptions. But there are some well-known protocols, primitives, and assumptions, that have resisted security reductions under well-studied intractability assumptions.

The Schnorr identification scheme Schnorr’s identification [Sch91] scheme is one of the most well-known and commonly-used identification schemes. For instance, recent usage includes the BlackBerry Router protocol. Schnorr showed security of this scheme under a passive (eavesdropper) attack based on the discrete logarithm assumption. But what about active (malicious) attacks? In particular, can security under active—even just sequential—attacks be based on the discrete logarithm assumption, or any other “standard” intractability assumption?1 The adaptive selective decommitment problem Assume a polynomial-time adversary receives a number of commitments and may then adaptively request openings of, say, half of them. Do the unopened commitments still remain hiding? This problem was first formalized by Dwork, Naor, Reingold and Stockmeyer [DNRS03] but according to them it arouse over 25 years ago in the context of distributed computing.2 As noted by Dwork et al, random-oraclebased commitment schemes easily satisfy this property. Can we construct non-interactive (or even two-round) commitment schemes that provably satisfy this property based on any standard intractability assumption?3 One-more inversion assumptions Can a polynomial-time algorithm A, given a prime-order group G and a generator g for G, find the discrete logarithm (w.r.t to the generator g) to “target” points y1,..., y ∈ G if it may make − 1 queries to a discrete logarithm oracle (for the group G and generator g)? The “one-more” discrete-logarithm assumption states that no such algorithm exists. Assumptions of this “one-more inversion” type were introduced by Bellare, Namprempre, Pointcheval and Semanko [BNPS03] and have been used to prove the security of a number of practical schemes; for instance, Bellare and Palacio [BP02] have shown active security of Schnorr’s identification scheme under the one-more discrete logarithm assumption. But can the security of these type of one-more inversion assumptions be based on more standard-type assumptions?

Unique Blind Signatures In 1982, Chaum [Cha82] introduced the concept of a “blind signature”— roughly speaking, a signature scheme where a user may ask a signer S to sign a message m As we shall discuss shortly, Bellare and Palacio [BP02] have demonstrated that Schnorr’s scheme is secure under active attacks under a new type of “one-more inversion” assumption.

We remark that DNRS focused their treatment on a non-adaptive version of this game where the adversary must select all the commitments to be opened up in a single shot; the general adaptive version is considered in Remark

7.1 in [DNRS03].

Interestingly, the related question of constructing encryption schemes secure under selective decryption based on “standard-type assumptions” has recently been solved [BHY09].

while keeping the content of m secret from S—and provided its first implementation. His scheme is non-interactive (just as traditional signature schemes) and has the desirable property that for every message there is a unique valid signature. Can the security of his scheme, or more generally, any “unique non-interactive blind signature” (i.e., non-interactive blind signature schemes with unique signatures), be based on standard assumptions?

Witness hiding of parallelized versions of classical zero-knowledge protocols It is well-known that parallelized versions of the classic three-round zero-knowledge protocols of [GMR89, GMW91, Blu86] are witness indistinguishable [FS90]. As shown by Feige and Shamir [FS90], for certain languages with multiple witnesses, they are also witness hiding under sequential (and even concurrent) composition. Can we prove that these protocols also are witness hiding under sequential composition for languages with unique witnesses based on any standard assumption?

In this paper, we present negative answers to the above questions for a very liberal definition of “standard intractability assumptions”, if we restrict to Turing (i.e., black-box) reductions—that is, reductions that use the alleged attacker A as a black-box.

More precisely, following Naor [Nao03] (see also [DOP05, HH09, RV10]), we model an intractability assumption as an arbitrary game between a (potentially) unbounded challenger C, and an attacker A.4 A is said to break the assumption C with respect to the threshold t if it can make C output 1 with probability non-negligibly higher than the threshold t. The only restriction we put on C is that it communicates with A in an a priori fixed polynomial number of rounds; we refer to such assumptions as polynomial-round intractability assumptions. All traditional cryptographic hardness assumptions (e.g., the hardness of factoring, the hardness of the discrete logarithm problem, the decisional Diffie-Hellman problem etc.) can be modeled as 2-round challengers C with the threshold t being either 0 (in case of the factoring or discrete logarithm problems) or 1/2 (in case of the decisional Deffie-Hellman problem). But also the “one-more discrete logarithm assumption” for a fixed polynomial l, or the assumption that a specific protocol (P, V ) is witness-hiding under a single, or even an a priori bounded number of, interactions can be modeled as polynomial-round challengers C (with the threshold t = 0).

1.1 Our Results Our main result shows that it is impossible to (Turing) reduce any polynomial-round intractability assumption to the witness hiding under sequential composition property of certain types of constantround arguments of knowledge protocols—called “computationally special-sound” protocols—for languages with unique witnesses. All our specific lower-bounds follow as corollaries of this result.

Recall that a three-round public-coin interactive proof is said to be special-sound [CDS94], if a valid witness to the statement x can be efficiently computed from any two accepting prooftranscripts of x which have the same first message but different second messages. We consider a relaxation of this notion—which we simply call computational special-soundness—where a) the number of communication rounds is any constant (instead of just three), b) the extractor may need a polynomial number of accepting transcripts (instead of just two), and c) extraction need only succeed if the transcripts are generated by communicating with a computationally-bounded prover. All traditional constant-round public-coin proofs of knowledge protocols (such as [GMR89, In contrast to [Nao03], we do not insist that the challenger is efficient; since our aim is to prove lower bounds, this only strengthens our results.

GMW91, Blu86, Sch91], as well as instantiations of [GMW91, Blu86] using statistically-hiding commitments) satisfy this property, and continue to do so also under parallel repetition.

Theorem 1 (Main Theorem - Informally stated). Let (P, V ) be a constant-round computationally special-sound interactive argument with super logarithmic-length verifier messages for the language L with unique witnesses. Assume there exists a polynomial-time Turing reduction R such that RA breaks the r(·)-round assumption C (where r is a polynomial) w.r.t. the threshold t for every A that breaks sequential witness hiding of (P, V ). Then C with respect to the threshold t can be broken in polynomial-time.

Our main theorem is most closely related to the work of Haitner, Rosen and Shaltiel [HRS09].

As we explain in more detail in Section 1.2, [HRS09] also present lower bounds for using Turing reductions to demonstrate witnes hiding for constant-round public-coin protocols. They consider a more general class of protocols than we do, and they present a lower-bound for “stand-alone” (as opposed to sequential) witness hiding. However, their lower bound only applies to restricted classes of Turing reductions, whereas our lower bound applies to arbitrary Turing reductions.

Our main theorem directly rules out using Turing reductions for demonstrating sequential witness hiding of parallelized versions of classical zero-knowledge protocols for languages with unique witnesses based on polynomial-round intractability assumptions. We next show that all the previously mentioned questions can be restated in the language of “sequential witness hiding for unique witness languages”, and we can thus use our main theorem to provide negative answers also to those questions.

Schnorr’s identification scheme: To rule out Turing reductions for proving security of the Schnorr identification scheme, note that Schnorr’s protocol is a special-sound proof for a unique witness language. Next, if Schnorr’s protocol is not sequentially witness hiding, then it cannot be a secure identification scheme: The witness in this proof is the identifier’s secretkey, so if an attacker can recover it after hearing polynomially many proofs, we can trivially violate the security of the identification scheme. (We mention that, on the other hand, the related scheme by Okamoto’s scheme [Oka92], can be proven secure based on the discrete logarithm assumption. However, the language considered in Okamoto’s protocol does not have a unique witnesses.) Adaptive selective decommitment: To rule out solutions to the selective-decommitment problem, we extend one of the results from [DNRS03] to show that if implementing the commitment scheme in GMW’s Graph 3-Coloring protocol with non-interactive (or two-round) commitments that are secure under adaptive selective decommitment, then the resulting protocol is sequentially witness hiding for any efficiently samplable hard language with unique witnesses;5 so assuming the existence of an efficiently samplable hard language with unique witnesses, Turing reductions cannot be employed to reduce adaptive selective-decommitment security of such commitments to any polynomial-round intractability assumption.

One more inversion assumptions: As mentioned, Bellare and Palacio [BP02] have shown that the security of the Schnorr scheme can be based on the “one-more discrete log” assumption, so by their work, we directly get that polynomial-round intractability assumptions cannot be Turing-reduced to the one-more discrete log assumption. By directly constructing appropriate Dwork, Naor, Reingold and Stockmeyer [DNRS03] show that the GMW protocol instantiated with “plain” (i.e., non-adaptive) selective-decommitment secure commitment satisfies some weak notions of zero-knowledge which, in particular, imply single-instance witness-hiding for unique witness relations.

special-sound protocols, we can generalize this result to rule out even weaker types of “manymore” discrete logarithm assumptions (where we require that it is hard to find inverses when having access to only inverses, where 0.) Using the same approach, we get that polynomial-round intractability assumptions cannot be Turing reduced to many-more variants of the RSA problem either (and more generally, any family of certified permutations that is additive homomorphic).

Unique blind signatures: The notion of unforgeability for blind signature schemes [PS00] requires that no attacker having requested signatures (where is an arbitrary polynomial) can come up with +1 signatures. We show that the existence of a unique non-interactive blind signatures implies that for every polynomial, there exists a computationally special-sound protocol for a unique witness language that is witness hiding under sequential repetitions;

this suffices for applying our main theorem to rule out using Turing reductions for basing the security of such blind signature schemes on polynomial-round intractability assumptions.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 9 |

Similar works:

«MR012013.4 OPERATOR MANUAL MERLIN® HANDCART COMPRESSED AIR FOAM SYSTEM (CAFS) Multi-Purpose, Portable Compressed Air Foam System for Fire Suppression, Decontamination & Spill Response This document contains Intelagard proprietary information intended for use solely by the purchaser of this Intelagard system. Reproduction is not authorized without the expressed written consent of Intelagard. 1 MR012013.4 2 MR012013.4 TABLE OF CONTENTS TABLE OF CONTENTS MERLIN QUICK START SECTION 1 – FRONT...»

«EVID Ceiling Speaker Systems An Application Guide THE CEILING SPEAKER SYSTEMS – AN OVERVIEW VALUE OF PREMIUM PERFORMANCE: A Unique Solution to an Age Old Problem THE EVID SOLUTION – WHY IS IT DIFFERENT? The EVID C8.2HC – Wide spectrum Pattern Control in a Compact Package. 3 The EVID 4.2 and 8.2 – Full Range Models with Punch The 10.1 Finally a Compact True Ceiling Subwoofer THE BASICS SELECTING & POSITIONING CEILING LOUDSPEAKERS Ceiling Systems – Size vs. Coverage SPL Requirements –...»

«Reluctant Meister How Germany's past is shaping its European future By Lord Stephen Green, Member of the House of Lords It is a great honour for me to stand here today, amongst friends from former times when I was a banker in a competing house, as well as other friends from my time as Trade and Investment Minister of the British Government. Both roles brought me often to Germany a country I have loved and found fascinating ever since my schooldays. To start with, it was the German language...»

«La Famille Chabrier dit Vadeboncoeur The Ancestors and Descendants of Jean Chabrier dit Vadeboncoeur United States Canada Quebec France Volume II The Family Tree Compiled by: Roger & Nancy Verboncoeur La Famille Chabrier dit VADEBONCOEUR As of: 12/24/2014 For additions or corrections please contact: Roger Verboncoeur 720 Simmons Trail Green Cove Springs FL 32043-9567 U.S.A. e-mail: R.Verboncoeur@Comcast.net Copyright © 2001 – 2013 Roger & Nancy Verboncoeur. All rights reserved. Record...»

«Note: The following table appears in the printed Annual Report on the facing page of the Chairman's Letter and is referred to in that letter. Berkshire’s Corporate Performance vs. the S&P 500 Annual Percentage Change in Per-Share in S&P 500 Book Value of with Dividends Relative Berkshire Included Results Year (1) (2) (1)-(2) 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998...»

«NIU’s Haunted Physics Laboratory Teacher’s Guide  Content  2005  Cover  2008  Notes  2009    NIU’s Spooky Science Saturday started out as NIU’s Haunted Physics Laboratory in  the fall of 2003 as a way to draw families to a physics department outreach event  on campus.  It has been an overwhelming success, growing from several  interactive displays in two labs visited by 250 people that first year to nearly 100 ...»

«Załącznik 3 do wniosku o wszczęcie postepowania habilitacyjnego Piotr J. Flatau Attachement 3 for “habilitacja” application – Piotr J. Flatau Self-evaluation by Piotr J. Flatau November 2011 1. Table of contents 1. Table of contents 2. Curriculum Vitae 3. Scientific Publications in Science Citation index 4. Scientific contributions overview Major thesis topic – exact single and multiple scattering methods 5. 5.1. Single scattering by non-spherical particles in discrete dipole...»

«Indian Journal of Fundamental and Applied Life Sciences ISSN: 2231– 6345 (Online) An Open Access, Online International Journal Available at www.cibtech.org/sp.ed/jls/2015/01/jls.htm 2015 Vol.5 (S1), pp. 4722-4731/Talebi and Ansari Research Article ANALYZING THE FACTORS AFFECTING THE NON-REPAYMENT OF LOANS AND CREDITS RECEIVED BY CUSTOMERS (CASE STUDY OF MASKAN BANK IN KOHKILOYEH-BOYER AHMAD) Hossein Talebi and *Yaghob Ansari 1 Department of Management, Yasouj Branch, Islamic Azad University,...»

«BEFORE THE AUTHORITY FOR ADVANCE RULINGS (INCOME TAX) NEW DELHI 26th Day of July, 2011 A.A.R. Nos. 858-861 of 2009 PRESENT Mr Justice. P.K. Balasubramanyan (Chairman) Mr. V.K. Shridhar (Member) Name & address of the applicant LS Cable Limited, (12-16F) LS Tower, 1026-6, Hogye-dong Gyeonggi-do, 431-080 Korea Commissioner Concerned Director of Income-tax-I (International Taxation) New Delhi Present for the Applicant Mr.N.Venkataraman, Sr.Advocate Mr. Taranpreet Singh, FCA Mr.Satish Aggarwal, FCA...»

«BDOHP Biographical Details and Interview Index EASTWOOD, Basil (Stephen Talbot) (born 4 March 1944) Career (with, on right, relevant pages in interview) Entry to FO (Arabian Department), 1966 pp 2-5 Middle East Centre for Arab Studies, 1967 pp 5-6 Jedda, 1968 pp 6-7 Colombo, 1969 pp 7-11 Cairo, 1972 pp 11-17 Cabinet Office (assessments Staff), 1976 pp 17-19 FCO (Personnel Operations Department), 1978 pp 20-21 Bonn, 1980 pp 21-26 Head of Chancery, Khartoum, 1984 pp 26-32 Counsellor...»

«LISTENING TO BIKE LANES a case study in one-eyed prophecy by Jeffrey A. Hiles B.A. Wright State University 1990 presented in partial fulfillment of the requirements for the degree of Master of Science The University of Montana 1996 Hiles, Jeffrey A., M.S., September 1996 Listening to Bike Lanes: a case study in one-eyed prophecy One group of bicycle advocates insists that cities need special facilities to separate bicyclists from motor traffic and make cycling less intimidating. Another group...»

«Our School Newsletter Greenwich Public School Partnership and Opportunity Excellence and Success A Greenwich Road Campus: 72a Greenwich Road, Greenwich NSW 2065 T (02) 9436 3731 F (02) 9906 4120 A Kingslangley Road Campus: 32 Kingslangley Road, Greenwich NSW 2065 T (02) 9436 3217 F (02) 9906 6437 E: greenwich-p.school@det.nsw.edu.au W www.greenwich-p.schools.nsw.edu.au Issue 28 Term 3 Week 8 2 September 2015 Principal’s Message Megan Lockery Principal’s Message Senior Choir sings at Opera...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.