We specify OCH, the first authenticated encryption with associated data scheme built to provide 128-bit multi-user AE security, 128-bit context commitment security, and 256-bit nonces with optional nonce privacy. It therefore addresses pressing limitations of currently widely-deployed schemes. We construct and formally analyze the security of OCH in a modular fashion, with transforms that are of broader applicability. On Intel Raptor Lake CPUs, OCH using the Areion permutation family has a peak encryption speed of 0.62 cycles per byte (cpb), not far off from AES128-GCM (0.38cpb) and outperforming both ChaCha20/Poly1305 (1.63cpb) and TurboSHAKE128-Wrap (3.52cpb).

Abstract A two-input function is a dual PRF if it is a PRF when keyed by either of its inputs. Dual PRFs are assumed in the design and analysis of numerous primitives and protocols including HMAC, AMAC, TLS 1.3 and MLS. But, not only do we not know whether particular functions on which the assumption is made really are dual PRFs; we do not know if dual PRFs even exist. What if the goal is impossible? This paper addresses this with a foundational treatment of dual PRFs, giving constructions based on standard assumptions. This provides what we call a generic validation of the dual PRF assumption. Our approach is to introduce and construct symmetric PRFs, which imply dual PRFs and may be of independent interest. We give a general construction of a symmetric PRF based on a function having a weak form of collision resistance coupled with a leakage hardcore function, a strengthening of the usual notion of hardcore functions we introduce. We instantiate this general construction in two ways to obtain two specific symmetric and dual PRFs, the first assuming any collision-resistant hash function and the second assuming any one-way permutation. A construction based on any one-way function evades us and is left as an intriguing open problem.

Aiming to strengthen classical secret-sharing to make it a more directly useful primitive for human endusers, we develop definitions, theorems, and efficient constructions for what we call adept secret-sharing. Our primary concerns are the properties we call privacy, authenticity, and error correction. Privacy strengthens the classical requirement by ensuring maximal confidentiality even if the dealer does not employ fresh, uniformly random coins with each sharing. That might happen either intentionally—to enable reproducible secretsharing— or unintentionally, when an entropy source fails. Authenticity is a shareholder’s guarantee that a secret recovered using his or her share will coincide with the value the dealer committed to at the time the secret was shared. Error correction is the guarantee that recovery of a secret will succeed, also identifying the valid shares, exactly when there is a unique explanation as to which shares implicate what secret. These concerns arise organically from a desire to create general-purpose libraries and apps for secret sharing that can withstand both strong adversaries and routine operational errors.

Towards advancing the use of big keys as a practical defense against key exfiltration, this paper provides efficiency improvements for cryptographic schemes in the bounded retrieval model (BRM). We identify probe complexity (the number of scheme accesses to the slow storage medium storing the big key) as the dominant cost. Our main technical contribution is what we call the large-alphabet subkey prediction lemma. It gives good bounds on the predictability under leakage of a random sequence of blocks of the big key, as a function of the block size. We use it to significantly reduce the probe complexity required to attain a given level of security. Together with other techniques, this yields security-preserving performance improvements for BRM symmetric encryption schemes and BRM public-key identification schemes.

We introduce identity-based format-preserving encryption (IB-FPE) as a way to localize and limit the damage to format-preserving encryption (FPE) from key exposure. We give definitions, relations between them, generic attacks and two transforms of FPE schemes to IB-FPE schemes. As a special case, we introduce and cover identity-based tweakable blockciphers. We apply all this to analyze DFF, an FPE scheme proposed to NIST for standardization.

The MD transform that underlies the MD and SHA families iterates a compression function h to get a hash function H. The question we ask is, what property X of h guarantees collision resistance (CR) of H? The classical answer is that X itself be CR. We show that weaker conditions X, in particular forms of what we call constrained-CR, suffice. This reduces demands on compression functions, to the benefit of security, and also, forensically, explains why collision-finding attacks on compression functions have not, historically, lead to immediate breaks of the corresponding hash functions. We obtain our results via a definitional framework called RS security, and a parameterized treatment of MD, that also serve to unify prior work and variants of the transform.

We give attacks on Feistel-based format-preserving encryption (FPE) schemes that succeed in message recovery (not merely distinguishing scheme outputs from random) when the message space is small. For $4$-bit messages, the attacks fully recover the target message using $2^{21}$ examples for the FF3 NIST standard and $2^{25}$ examples for the FF1 NIST standard. The examples include only three messages per tweak, which is what makes the attacks non-trivial even though the total number of examples exceeds the size of the domain. The attacks are rigorously analyzed in a new definitional framework of message-recovery security. The attacks are easily put out of reach by increasing the number of Feistel rounds in the standards.

We present new algorithm-substitution attacks (ASAs) on symmetric encryption that improve over prior ones in two ways. First, while prior attacks only broke a sub-class of randomized schemes having a property called coin injectivity, our attacks break ALL randomized schemes. Second, while prior attacks are stateful, ours are stateless, achieving a notion of strong undetectability that we formalize. Together this shows that ASAs are an even more dangerous and powerful mass surveillance method than previously thought. Our work serves to increase awareness about what is possible with ASAs and to spur the search for deterrents and counter-measures.

We advocate schemes based on fixed-key AES as the best route to highly efficient circuit-garbling. We provide such schemes making only one AES call per garbled-gate evaluation. On the theoretical side, we justify the security of these methods in the random-permutation model, where parties have access to a public random permutation. On the practical side, we provide the Just Garble system, which implements our schemes. Just Garble evaluates moderate-sized garbled-circuits at an amortized cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.

Garbled circuits, a classical idea rooted in the work of Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a provable-security treatment for garbling schemes, endowing them with a versatile syntax and multiple security definitions. The most basic of these, privacy, suffices for two-party secure function evaluation (SFE) and private function evaluation (PFE). Starting from a PRF, we provide an efficient garbling scheme achieving privacy and we analyze its concrete security. We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. We extend our scheme to achieve these ends. We provide highly efficient blockcipher-based instantiations of both schemes. Our treatment of garbling schemes presages more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.

In response to needs of disk encryption standardization bodies, we provide the first tweakable ciphers that are proven to securely encipher their own keys. We provide both a narrowblock design StE and a wideblock design EtE. Our proofs assume only standard PRP-CCA security of the underlying tweakable ciphers.

The authors show how the Fiat–Shamir transform can be used to convert three-move identification protocols into two-tier signature schemes (a primitive that they define) with a proof of security that makes a standard assumption on the hash function rather than modelling it as a random oracle. The result requires security of the starting protocol against concurrent attacks. It is also shown that numerous protocols have the required properties, and thus numerous efficient two-tier schemes are obtained. The first application is an efficient transform of any unforgeable signature scheme into a strongly unforgeable one. (This extends the work of Boneh, Shen and Waters whose transform only applies to a limited class of schemes.) The second application is the new one-time signature schemes that, compared with the one-way function-based ones of the same computational cost, have smaller key and signature sizes.

The Fiat-Shamir paradigm for transforming identification schemes into signature schemes has been popular since its introduction because it yields efficient signature schemes, and has been receiving renewed interest of late as the main tool in deriving forward-secure signature schemes. In this paper, minimal (meaning necessary and sufficient) conditions on the identification scheme to ensure security of the signature scheme in the random oracle model are determined, both in the usual and in the forward-secure cases. Specifically, it is shown that the signature scheme is secure (respectively, forward-secure) against chosen-message attacks in the random oracle modelifandonlyifthe underlying identification scheme is secure (respectively, forward-secure) against impersonation underpassive(i.e., eavesdropping only) attacks, and has its commitments drawn at random from a large space. An extension is proven incorporating a random seed into the Fiat-Shamir transform so that the commitment space assumption may be removed.

We give a unified account of classical secret-sharing goals from a modern cryptographic vantage. Our treatment encompasses perfect, statistical, and computational secret sharing; static and dynamic adversaries; schemes with or without robustness; schemes where a participant recovers the secret and those where an external party does so. We then show that Krawczyk's 1993 protocol for robust computational secret sharing (RCSS) need not be secure, even in the random-oracle model and for threshold schemes, if the encryption primitive it uses satisfies only one-query indistinguishability (ind1), the only notion Krawczyk defines. Nonetheless, we show that the protocol is secure (in the random-oracle model, for threshold schemes) if the encryption scheme also satisfies one-query key-unrecoverability (key1). Since practical encryption schemes are ind1+key1 secure, our result effectively shows that Krawczyk's RCSS protocol is sound (in the random-oracle model, for threshold schemes). Finally, we prove the security for a variant of Krawczyk's protocol, in the standard model and for arbitrary access structures, assuming ind1 encryption and a statistically-hiding, weakly-binding commitment scheme.

This paper proposes several new schemes which allow a sender to send encrypted messages to multiple recipients more efficiently (in terms of bandwidth and computation) than by using a standard encryption scheme. Most of the proposed schemes explore a new natural technique called randomness reuse. In order to analyze security of our constructions, we introduce a new notion of multirecipient encryption schemes (MRESs) and provide definitions of security for them. We finally show a way to avoid ad hoc analyses by providing a general test that can be applied to a standard encryption scheme to determine whether the associated randomness reusing MRES is secure. The results and applications cover both asymmetric and symmetric encryption.

We show how to significantly speed-up the encryption portion of some public-key cryptosystems by the simple expedient of allowing a sender to maintain state that is re-used across different encryptions.In particular we present stateful versions of the DHIES and Kurosawa-Desmedt schemes that each use only 1 exponentiation to encrypt, as opposed to 2 and 3 respectively in the original schemes, yielding the fastest discrete-log based public-key encryption schemes known in the random-oracle and standard models respectively. The schemes are proven to meet an appropriate extension of the standard definition of IND-CCA security that takes into account novel types of attacks possible in the stateful setting.

A multi-signature scheme enables a group of signers to produce a compact, joint signature on a common document, and has many potential uses. However, existing schemes impose key setup or PKI requirements that make them impractical, such as requiring a dedicated, distributed key generation protocol amongst potential signers, or assuming strong, concurrent zero-knowledge proofs of knowledge of secret keys done to the CA at key registration. These requirements limit the use of the schemes. We provide a new scheme that is proven secure in the plain public-key model, meaning requires nothing more than that each signer has a (certified) public key. Furthermore, the important simplification in key management achieved is not at the cost of efficiency or assurance: our scheme matches or surpasses known ones in terms of signing time, verification time and signature size, and is proven secure in the random-oracle model under a standard (not bilinear map related) assumption. The proof is based on a simplified and general Forking Lemma that may be of independent interest.

We present novel realizations of the transitive signature primitive introduced by Micali and Rivest, enlarging the set of assumptions on which this primitive can be based, and also providing performance improvements over existing schemes. More specifically, we propose new schemes based on factoring, the hardness of the one-more discrete logarithm problem, and gap Diffie-Hellman (DH) groups. All these schemes are proven transitively unforgeable under adaptive chosen-message attack in the standard (not random-oracle) model. We also provide an answer to an open question raised by Micali and Rivest regarding the security of their Rivest-Shamir-Adleman (RSA)-based scheme, showing that it is transitively unforgeable under adaptive chosen-message attack assuming the security of RSA under one-more inversion. We then present hash-based modifications of the RSA, factoring, and gap Diffie-Hellman based schemes that eliminate the need for "node certificates" and thereby yield shorter signatures. These modifications remain provably secure under the same assumptions as the starting scheme, in the random oracle model.

The secure shell (SSH) protocol is one of the most popular cryptographic protocols on the Internet. Unfortunately, the current SSH authenticated encryption mechanism is insecure. In this paper, we propose several fixes to the SSH protocol and, using techniques from modern cryptography, we prove that our modified versions of SSH meet strong new chosen-ciphertext privacy and integrity requirements. Furthermore, our proposed fixes will require relatively little modification to the SSH protocol and to SSH implementations. We believe that our new notions of privacy and integrity for encryption schemes with stateful decryption algorithms will be of independent interest.

We describe a parallelizable block-cipher mode of operation that simultaneously provides privacy and authenticity. OCB encrypts-and-authenticates a nonempty string M ∈ {0, 1}* using ⌈| M |/ n ⌉ + 2 block-cipher invocations, where n is the block length of the underlying block cipher. Additional overhead is small. OCB refines a scheme, IAPM, suggested by Charanjit Jutla. Desirable properties of OCB include the ability to encrypt a bit string of arbitrary length into a ciphertext of minimal length, cheap offset calculations, cheap key setup, a single underlying cryptographic key, no extended-precision addition, a nearly optimal number of block-cipher calls, and no requirement for a random IV. We prove OCB secure, quantifying the adversary's ability to violate the mode's privacy or authenticity in terms of the quality of its block cipher as a pseudorandom permutation (PRP) or as a strong PRP, respectively.

The Secure Shell (SSH) protocol is one of the most popular cryptographic protocols on the Internet. Unfortunately, the current SSH authenticated encryption mechanism is insecure. In this paper we propose several fixes to the SSH protocol and, using techniques from modern cryptography, we prove that our modified versions of SSH meet strong new chosen-ciphertext privacy and integrity requirements. Furthermore, our proposed fixes will require relatively little modification to the SSH protocol or to SSH implementations. We believe that our new notions of privacy and integrity for encryption schemes with stateful decryption algorithms will be of independent interest.

We describe a parallelizable block-cipher mode of operation that simultaneously provides privacy and authenticity. OCB encrypts-and-authenticates a nonempty string M ε {0,1}• using \lceil |M|/n\rceil + 2 block-cipher invocations, where n is the block length of the underlying block cipher. Additional overhead is small. OCB refines a scheme, IAPM, suggested by Charanjit Jutla. Desirable properties of OCB include: the ability to encrypt a bit string of arbitrary length into a ciphertext of minimal length; cheap offset calculations; cheap session setup; a single underlying cryptographic key; no extended-precision addition; a nearly optimal number of block-cipher calls; and no requirement for a random IV. We prove OCB secure, quantifying the adversary's ability to violate the mode's privacy or authenticity in terms of the quality of its block cipher as a pseudorandom permutation (PRP) or as a strong PRP, respectively.

This paper discusses the design, implementation, and deployment of a secure and practical payment system for electronic commerce on the Internet. The system is based on the iKP family of protocols-(i=1,2,3)-developed at IBM Research. The protocols implement credit card-based transactions between buyers and merchants while the existing financial network is used for payment clearing and authorization. The protocols are extensible and can be readily applied to other account-based payment models, such as debit cards. They are based on careful and minimal use of public-key cryptography, and can be implemented in either software or hardware. Individual protocols differ in both complexity and degree of security. In addition to being both a precursor and a direct ancestor of the well-known SET standard, iKP-based payment systems have been in continuous operation on the Internet since mid-1996. This longevity-as well as the security and relative simplicity of the underlying mechanisms-makes the iKP experience unique. For this reason, this paper also reports on, and addresses, a number of practical issues arising in the course of implementation and real-world deployment of a secure payment system.

We prcscnt a general framework for constructing and analyzing authentication protocols in realistic models of communication networks.This framework provides a sound formalization for the authentication problem and suggests simple and attractive design principles for general authentication and key exchange protocols.The key element in our appronch io a modular treatment of the authentication problem in cryptographic protocols; thii applies to the definition of accurity, to the design of the protocols, and to their analysis.In particulnr, following this modular approach, we show how to systematically transform solutions that work in a model of idaalizcd authenticated communications into solutions that are secure in the realistic setting of communication channels controlled by an active adversary.Using these principles we construct and prove the security of simple and practical authentication and key-exchange protocols.In particular, we provide a security analysis of aomo well-known key exchange protocols (e.g.authenticated Dlfllc-Hcllman key exchange), and of some of the techniques underlying the design of several authentication protocols that are currently being deployed on a large scale for the Intornot Protocol and other applications.

This paper continues the investigation of the connection between probabilistically checkable proofs (PCPs) and the approximability of NP-optimization problems. The emphasis is on proving tight nonapproximability results via consideration of measures such as the "free-bit complexity" and the "amortized free-bit complexity" of proof systems. The first part of the paper presents a collection of new proof systems based on a new error-correcting code called the long code. We provide a proof system that has amortized free-bit complexity of $2 + \epsilon$, implying that approximating MaxClique within $N^{\frac13-\e}$, and approximating the Chromatic Number within $N^{\frac15-\e}$, are hard, assuming $\NP\neq\coRP$, for any e > 0. We also derive the first explicit and reasonable constant hardness factors for Min Vertex Cover, $\MSAT{2}$, and Max Cut, and we improve the hardness factor for $\MSAT{3}$. We note that our nonapproximability factors for $\maxsnp$ problems are appreciably close to the values known to be achievable by polynomial-time algorithms. Finally, we note a general approach to the derivation of strong nonapproximability results under which the problem reduces to the construction of certain "gadgets." The increasing strength of nonapproximability results obtained via the PCP connection motivates us to ask how far this can go and whether PCPs are inherent in any way. The second part of the paper addresses this. The main result is a "reversal" of the connection due to Feige et al. (FGLSS connection) [J. ACM, 43 (1996), pp. 268--292]: where the latter had shown how to translate proof systems for NP into NP-hardness of approximation results for MaxClique, we show how any NP-hardness of approximation result for MaxClique yields a proof system for NP. Roughly, our result says that for any constant f, if MaxClique is NP-hard to approximate within N 1(1+f) , then $\NP\subseteq \overline{\fpcp}[\log,f]$, the latter being the class of languages possessing proofs of logarithmic randomness and amortized free-bit complexity f. This suggests that PCPs are inherent to obtaining nonapproximability results. Furthermore, the tight relation suggests that reducing the amortized free-bit complexity is necessary for improving the nonapproximability results for MaxClique. The third part of our paper initiates a systematic investigation of the properties of PCP and FPCP (free PCP) as a function of the following various parameters: randomness, query complexity, free-bit complexity, amortized free-bit complexity, proof size, etc. We are particularly interested in triviality results, which indicate which classes are not powerful enough to capture NP. We also distill the role of randomized reductions in this area and provide a variety of useful transformations between proof checking complexity classes.

One of the main objections to existing proposals for key escrow is that the individual's privacy relies on too high a level of trust in the law enforcement agencies.In particular, even if the government is trustworthy today, it may be replaced by an un-trustworthy government tomorrow which could immediately and suddenly recover the secret keys of all users."Partial key escrow" was suggested to address this concern, in the context of DES keys.Only some part of a user key is escrowed, so that the authority must make a computational effort to find the rest.We extend this idea and provide schemes to perform partial key escrow in a verifiable manner in a public-key encryption setting.We uncover some subtle issues which must be addressed for any partial key escrow scheme to be secure, the most important of which is the danger of early recovery.We show that other proposals for verifiable partial key escrow suffer from the early recovery problem, and thus do not in fact offer an advantage over standard key-escrow schemes.Our verifiable partial key escrow scheme for the Diffie-Hellman cryptosystem does not suffer from early recovery.Political debate will not make the user versus lawenforcement conflict on privacy vanish.Today we are seeing corporations, pushed by their business needs, ready to accept some form of key escrow.The realistic and urgent question is to find the form which guarantees the most privacy.Our schemes are candidates.

We study notions and schemes for symmetric (ie. private key) encryption in a concrete security framework. We give four different notions of security against chosen plaintext attack and analyze the concrete complexity of reductions among them, providing both upper and lower bounds, and obtaining tight relations. In this way we classify notions (even though polynomially reducible to each other) as stronger or weaker in terms of concrete security. Next we provide concrete security analyses of methods to encrypt using a block cipher, including the most popular encryption method, CBC. We establish tight bounds (meaning matching upper bounds and attacks) on the success of adversaries as a function of their resources.

Whether or not parallel repetition lowers the error has been a fundamental question in the theory of protocols, with applications in many different areas. It is well known that parallel repetition reduces the error at an exponential rate in interactive proofs and Arthur-Merlin games. It seems to have been taken for granted that the same is true in arguments, or other proofs where the soundness only holds with respect to computationally bounded parties. We show that this is not the case. Surprisingly, parallel repetition can actually fail in this setting. We present four-round protocols whose error does not decrease under parallel repetition. This holds for any (polynomial) number of repetitions. These protocols exploit non-malleable encryption and can be based on any trapdoor permutation. On the other hand we show that for three-round protocols the error does go down exponentially fast. The question of parallel error reduction is particularly important when the protocol is used in cryptographic settings like identification, and the error represents the probability that an intruder succeeds.

Pseudorandom function families are a powerful cryptographic primitive, yielding, in particular simple solutions for the main problems in private key cryptography. Their existence based on general assumptions (namely the existence of one-way functions) has been established. The authors investigate new ways of designing pseudorandom function families. The goal is to find constructions that are both efficient and secure, and thus eventually to bring the benefits of pseudorandom functions to practice. The basic building blocks in the design are certain limited versions of pseudorandom function families, called finite length input pseudorandom function families, for which very efficient realizations exist impractical cryptography. Thus rather than starting from one-way functions, they propose constructions of "full-fledged" pseudorandom function families from these limited ones. In particular they propose the cascade construction, and provide a concrete security analysis which relates the strength of the cascade to that of the underlying finite pseudorandom function family in a precise and quantitative way.

A shared coin is one which n players "simultaneously" hold and can later reveal, but no sufficiently small coalition can influence or `a priori predict the outcome. Such coins are expensive to produce, yet many distributed protocols (including broadcast and Byzantine agreement) need them in bulk. We introduce a new paradigm for obtaining shared coins. We suggest distributed, pseudorandom bit generators (D-PRBGs). Analogous to a pseudo-random bit generator, which is an efficient algorithm to expand a short random seed into a long random looking sequence, a DPRBG is a protocol which "expands" a "distributed seed," consisting of shared coins, into a longer "sequence" of shared coins, at low amortized cost per coin produced. Our main result is the construction of a D-PRBG in which this amortized cost (computation and communication) is significantly lower than the cost of any "from-scratch" shared coin generation protocol. Furthermore, for applications which are executed repeatedly, we sugg...

Let Dist(f,g)=Pr/sub u/[f(u)/spl ne/g(u)] denote the relative distance between functions f,g mapping from a group G to a group H, and let Dist(f) denote the minimum, over all linear functions (homomorphisms) g, of Dist(f,g). Given a function f:G/spl rarr/H we let Err(f)=Pr/sub u,/spl upsi//[f(u)+f(/spl upsi/)/spl ne/f(u+/spl upsi/)] denote the rejection probability of the Blum-Luby-Rubinfeld (1993) linearity test. Linearity testing is the study of the relationship between Err(f) and Dist(f), and in particular lower bounds on Err(f) in terms of Dist(f). We discuss when the underlying groups are G=GF(2)/sup n/ and H=GF(2). In this case, the collection of linear functions describe a Hadamard code of block length 2/sup n/ and for an arbitrary function f mapping GF(2)/sup n/ to GF(2) the distance Dist(l) measures its distance to a Hadamard code. Err(f) is a parameter that is "easy to measure" and linearity testing studies the relationship of this parameter to the distance of f. The code and corresponding test are used in the construction of efficient probabilistically checkable proofs and thence in the derivation of hardness of approximation. Improved analyses translate into better nonapproximability results. We present a description of the relationship between Err(f) and Dist(f) which is nearly complete in all its aspects, and entirely complete in some. We present functions L,U:[0,1]/spl rarr/[0,1] such that for all x /spl isin/ [0,1] we have L(x)/spl les/Err(f)/spl les/U(x) whenever Dist(f)=x, with the upper bound being tight on the whole range, and the lower bound tight on a large part of the range and close on the rest. Part of our strengthening is obtained by showing a new connection between linearity testing and Fourier analysis.

Let Dist(f,g)=Pr/sub u/ [f(u)/spl ne/g(u)] denote the relative distance between functions f,g mapping from a group G to a group H, and let Dist(f) denote the minimum, over all linear functions (homomorphisms) g, of Dist(f,g). Given a function f:G/spl rarr/H we let Err(f)=Pr/sub u/,v[f(u)+f(v)/spl ne/f(u+v)] denote the rejection probability of the BLR (Blum-Luby-Rubinfeld) linearity test. Linearity testing is the study of the relationship between Err(f) and Dist(f), and in particular the study of lower bounds on Err(f) in terms of Dist(f). The case we are interested in is when the underlying groups are G=GF(2)/sup n/ and H=GF(2). The corresponding test is used in the construction of efficient PCPs and thence in the derivation of hardness of approximation results, and, in this context, improved analyses translate into better non-approximability results. However, while several analyses of the relation of Err(f) to Dist(f) are known, none is tight. We present a description of the relationship between Err(f) and Dist(f) which is nearly complete in all its aspects, and entirely complete (i.e. tight) in some. In particular we present functions L,U:[0,1]/spl rarr/[0,1] such that for all x/spl isin/[0,1] we have L(x)

The first part of this paper presents new proof systems and improved non-approximability results. In particular we present a proof system for NP using logarithmic randomness and two amortized free bits, so that Max clique is hard within N/sup 1/3/ and chromatic number within N/sup 1/5/. We also show hardness of 38/37 for Max-3-SAT, 27/26 for vertex cover, 82/81 for Max-cut, and 94/93 for Max-2-SAT. The second part of this paper presents a "reverse" of the FGLSS connection by showing that an NP-hardness result for the approximation of Max clique to within a factor of N/sup 1/(g+1/) would imply a probabilistic verifier for NP with logarithmic randomness and amortized free-bit complexity g. We also show that "existing techniques" won't yield proof systems of less than two bits in amortized free bit complexity. Finally, we initiate a comprehensive study of PCP and FPCP parameters, proving several triviality results and providing several useful transformations.

Article Knowledge on the average—perfect, statistical and logarithmic Share on Authors: William Aiello Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJ Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJView Profile , Mihir Bellare IBM T.J. Watson Research Center, PO Box 704, Yorktown Heights, NY IBM T.J. Watson Research Center, PO Box 704, Yorktown Heights, NYView Profile , Ramarathnam Venkatesan Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJ Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 469–478https://doi.org/10.1145/225058.225186Published:29 May 1995 6citation264DownloadsMetricsTotal Citations6Total Downloads264Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The goal of incremental cryptography is to design cryptographic algorithms with the property that having applied the algorithm to a document, it is possible to quickly update the result of the algorithm for a modified document, rather than having to re-compute it from scratch. In settings where cryptographic algorithms such as encryption or signatures are frequently applied to changing documents, dramatic efficiency improvements can be achieved. One such setting is the use of authentication tags for virus protection. We consider documents that can be modified by powerful (and realistic) document modification operations such as insertion and deletion of character-strings (or equivalently cut and paste of text). We provide efficient incremental signature and message authentication schemes supporting the above document modification operations. They meet a strong notion of tamper-proof security which is appropriate for the virus protection setting. We initiate a study of incremental encryp...

We study session key distribution in the ting of Needham and Schroeder.(This is three-party setthe trust model assumed by the popular Kerberos "authentication system. ) Such protocols are basic building blocks for contemporary distributed systems-yet the underlying problem has, up until now, lacked a definition or provably-good solution, One consequence is that incorrect protocols have proliferated.This paper provides the first treatment of this problem in the complexity-theoretic framework of modern cryptography.We present a definition, protocol, and a proof that the protocol satisfies the definition, assuming the (minimal) assumption of a pseudorandom function.When this assumption is appropriately instantiated, our protocols are simple and efficient.

We introduce a natural notion of obliviousness of a sampling procedure, and construct a randomness-efficient oblivious sampler. Our sampler uses O(l+log /spl delta//sup -1//spl middot/log l) coins to output m=poly(/spl epsiv//sup -1/, log /spl delta//sup -1/, log l) sample points x/sub 1/, ..., x/sub m/, /spl isin/ {0, 1}/sup 1/ such that Pr[|1/m/spl Sigma//sub i=1//sup m/f(x/sub i/)-E[f]|>

No abstract available.

We indicate strong non-approximability factors for central problems: N 1=4 for Max Clique; N 1=10 for Chromatic Number; and 66=65 for Max 3SAT. Underlying the Max Clique result is a proof system in which the verifier examines only three "free bits" to attain an error of 1=2. Underlying the Chromatic Number result is a reduction from Max Clique which is more efficient than previous ones. Advanced Networking Laboratory, IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA. e-mail: [email protected]. y Research Division, IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, USA. e-mail: [email protected]. 1 Introduction Max Clique is amongst the most important combinatorial optimization problems. Unfortunately it is NP-hard [16], and attention since this discovery has thus focused on approximation algorithms. Yet the best known ones can approximate the max clique size of an N node graph only to within a factor of N 1\\Gamma...

A basic question about NP is whether or not search reduces in polynomial time to decision. This paper indicates that the answer is negative: Under a complexity assumption (that deterministic and nondeterministic double-exponential time are unequal) a language in NP for which search does not reduce to decision is constructed. These ideas extend in a natural way to interactive proofs and program checking. Under similar assumptions, the authors present languages in NP for which it is harder to prove membership interactively than it is to decide this membership, and languages in NP that are not checkable.

We argue that the random oracle model—where all parties have access to a public random oracle—provides a bridge between cryptographic theory and cryptographic practice. In the paradigm we suggest, a practical protocol P is produced by first devising and proving correct a protocol PR for the random oracle model, and then replacing oracle accesses by the computation of an “appropriately chosen” function h. This paradigm yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. We illustrate these gains for problems including encryption, signatures, and zero-knowledge proofs.

Article Free Access Share on Efficient probabilistically checkable proofs and applications to approximations Authors: M. Bellare View Profile , S. Goldwasser View Profile , C. Lund View Profile , A. Russell View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 294–304https://doi.org/10.1145/167088.167174Published:01 June 1993Publication History 182citation659DownloadsMetricsTotal Citations182Total Downloads659Last 12 Months70Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a general technique to upper bound the spectral norm of an arbitrary function. At the heart of our technique is a theorem which shows how to obtain an upper bound on the spectral norm of a decision tree given the spectral norms of the functions in the nodes of this tree. The theorem applies to trees whose nodes may compute any boolean functions. Applications are to the design of efficient learning algorithms and the construction of small depth threshold circuits (or neural nets). In particular, we present polynomial time algorithms for learning O(log n) clause DNF formulas and various classes of decision trees, all under the uniform distribution with membership queries.

We look at the question of how powerful a prover must be to give a zero-knowledge proof.We present the first unconditional bounds on the complexity of a statistical ZK prover.The result is that if a language possesses a statistical zero-knowledge then it also possesses a statistical zero-knowledge proof in which the prover runs in probabilistic, polynomial time with an NP oracle.Previously this was only known given the existence of one-way permutations.Extending these techniques to protocols of knowledge complexity k(n) >0, we derive bounds on the time complexity of languages of "small" knowledge complexity.Underlying these results is a technique for efficiently generating an "almost" random element of a set S E P.Namely, we construct a probabilistic machine with an NP oracle which, on input 1" and 6 > 0 runs in time polynomial in n and lg 6-1, and outputs a random string from a distribution within distance 6 of the uniform distribution on S n {O, l}~.

A digital signature scheme is presented, which is based on the existence of any trapdoor permutation. The scheme is secure in the strongest possible natural sense: namely, it is secure against existential forgery under adaptive chosen message attack.

A basic question about NP is whether or not search reduces in polynomial time to decision. We indicate that the answer is negative: under a complexity assumption (that deterministic and nondeterministic doubleexponential time are unequal) we construct a language in NP for which search does not reduce to decision. These ideas extend in a natural way to interactive proofs and program checking. Under similar assumptions we present languages in NP for which it is harder to prove membership interactively than it is to decide this membership. Similarly we present languages where checking is harder than computing membership. Each of the following properties --- checkability, random-self-reducibility, reduction from search to decision, and interactive proofs in which the prover's power is limited to deciding membership in the language itself --- implies coherence, one of the weakest forms of self-reducibility. Under assumptions about triple-exponential time, we construct incoherent sets in NP....

The quantitative aspects of randomness in interactive proof systems are studied. The result is a randomness-efficient error-reduction technique: given an Arthur-Merlin proof system (error probability

Quadratic residuosity and graph isomorphism are classic problems and the canonical examples of zero-knowledge languages.However, despite much research effort, all previous zero-knowledge proofs for them required either unproven complexity assumptions or an unbounded number of rounds of message exchange.For both (and similar) languages, we exhibit zeroknowledge proofs that require 5 rounds and no unproven assumptions.Our solution is essentially optimal, in this setting, due to a recent lower bound argument of Goldreich and Krawczyk.

Article The (true) complexity of statistical zero knowledge Share on Authors: M. Bellare MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MAView Profile , S. Micali MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MAView Profile , R. Ostrovsky MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MAView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990 Pages 494–502https://doi.org/10.1145/100216.100285Online:01 April 1990Publication History 40citation347DownloadsMetricsTotal Citations40Total Downloads347Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a digital signature scheme which combines high security with the property of being based on a very general assumption: the existence of trapdoor permutations. Previous signature schemes with comparable levels of security were based on assumptions of the computational hardness of particular algebraic problems such as factoring. Our contribution is to free this important cryptographic primitive from the fortunes of any specific algebraic problem by establishing a truly general signature scheme.