Interactive proof systems are considered in which the best set of possible verifiers is restricted to the class of probabilistic log-space automata. A. Condon (1988) introduced this model and showed that if the protocols are allowed to run for arbitrarily many rounds, exponential-time languages can be proved to a log-space verifier. To better approximate the usual notion of interactive proof systems, a number of researchers have considered a more realistic, further restricted model in which protocols are polynomially bounded, both in the number of rounds of communication and in the number of computational steps allowed to the verifier. A notion of language-recognition zero-knowledge is defined for this model, and it is shown that anything provable in this model can be proved in language-recognition zero-knowledge.>
While the intuition underlying a zero knowledge proof system [GMR85] is that no âknowledgeâ is leaked by the prover to the verifier, researchers are just beginning to analyze such proof systems in terms of formal notions of knowledge. In this paper, we show how interactive proof systems motivate a new notion of practical knowledge, and we capture the definition of an interactive proof system in terms of practical knowledge. Using this notion of knowledge, we formally capture and prove the intuition that the prover does not leak any knowledge of any fact (other than the fact being proven) during a zero knowledge proof. We extend this result to show that the prover does not leak any knowledge of how to compute any information (such as the factorization of a number) during a zero knowledge proof. Finally, we define the notion of a weak interactive proof in which the prover is limited to probabilistic, polynomial-time computations, and we prove analogous security results for such proof systems. We show that, in a precise sense, any nontrivial weak interactive proof must be a proof about the prover's knowledge, and show that, under natural conditions, the notions of interactive proofs of knowledge defined in [TW87] and [FFS87] are instances of weak interactive proofs.
Suppose your netmail is being erratically censored by Captain Yossarian. Whenever you send a message, he censors each bit of the message with probability 1/2, replacing each censored bit by some reserved character. Well versed in such concepts as redundancy, this is no real problem to you. The question is, can it actually be turned around and used to your advantage? We answer this question strongly in the affirmative. We show that this protocol, more commonly known as oblivious transfer, can be used to simulate a more sophisticated protocol, known as oblivious circuit evaluation([Y]). We also show that with such a communication channel, one can have completely noninteractive zero-knowledge proofs of statements in NP. These results do not use any complexity-theoretic assumptions. We can show that they have applications to a variety of models in which oblivious transfer can be done.
Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Widgerson
Quite complex cryptographic machinery has been developed based on the assumption that one-way functions exist, yet we know of only a few possible such candidates. It is important at this time to find alternative foundations to the design of secure cryptography. We introduce a new model of generalized interactive proofs as a step in this direction. We prove that all NP languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions.
Brotowasisto, Oscar Gish, Ridwan Malik, Paramita Sudharto
This paper describes health care financing and expenditures in Indonesia, a developing country spending around $US 9.40 per capita annually for health care (2.6% of GOP). Per capita health care spending has held constant in real terms over the last five years. The public sector accounts for 36.8% of all health care expenditure, or 43.1% if health care spending by state enterprises is included. About 13% of the population, almost all of them government employees and their families, are covered by some form of health insurance. In 1984, 62% of the population was spending privately â at then current exchange rates â an average of $US 2.70 per capita annually for health care, another 30% averaged $US 8.35 each, and the upper 9% $US 31.90. The Government is reviewing various âsocial financingâ mechanisms with a view to expanding health insurance coverage both for those in formal wage employment and the bulk of the population which remains either on the land or is part of the âinformalâ sector. Steps are also being taken to increase the efficient use of resources by, among other things, making greater use of evaluation techniques and economic methodologies. Such efforts are coupled with more decentralized authority being given to the provinces and districts. Particularly important to future health efforts is the further expansion of community-based activities, especially in the form of the Posyandu (integrated health post).
We show that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the first public-key cryptosystem secure against chosen ciphertext attack.
This paper analyzes one method governments employ to circumvent the discipline of a competitive system of fiscal federalism - intergovernmental collusion in the form of intergovernmental grants. Grants, it is argued, serve to encourage the expansion of the public sector by concentrating taxing powers in the hands of the central government and by weakening the fiscal discipline imposed on governments forced to self-finance their expenditures. The results reported suggest that intergovernmental grants do encourage growth in the public sector. The results offer further support for the use of monopoly government assumptions in public sector modeling.
In the current environment of general budget stringency in developing countries it is unrealistic to push for more spending for health services. The answer to this health crisis is to relieve government of much of the responsibility for financing those kinds of health services for which the benefits to society as a whole (as opposed to direct benefits to the users of the service) are low freeing resources to finance those services for which benefits are high. The intent is to relieve government of the burden of spending on health care for the rich freeing resources for more spending for the poor. Individuals with sufficient income should pay for their curative care. The financing and provision of these private health services should be shifted to a combination of the nongovernment sector and a sector reorganized to be more financially self-sufficient. A shift such as this would increase the resources available for those types of health services which are goods and currently are underfunded public health programs such as immunization vector control some prenatal and maternal care sanitary waste disposal and health education. Also such a shift would increase the resources available for simple curative care and referral for the poor who now only have limited access to low quality services of this nature. Government efforts to cover the full costs of health care for everyone from general revenues have contributed to 3 sets of problems in the health systems of many countries: an allocation problem -- insufficient spending on cost-effective health activities; an internal efficiency problem -- inefficient programs; and an equity problem -- inequitable distribution of benefits from health services. 4 policies for health financing are proposed to raise revenues for important health programs increase the efficiency of health services and make the system better serve the poor. These are: charging users of health facilities; providing insurance or other risk coverage; strengthening nongovernmental health activities; and decentralizing government health services. A table summarizes the effects of each of the 4 options for reform in alleviating health sector problems.
Decentralization of public program administration and financing to subnational units of government is examined in the context of hospital and nursing home assistance programs in the United States. Do subnational governments (i.e., states) adapt service utilization controls and tighter program eligibility during periods of fiscal austerity? Are these actions affected by expenditure levels, state budget balances, tax revenues, and the state's proportion of low income persons? Published data covering the period 1978-1982 from each of the 50 U.S. states were analyzed using multiple regression. States with a low proportion of low-income persons and a high per capita tax base were likely to increase minimum income eligibility standards to keep pace with inflation. All other states, regardless of fiscal condition, tended toward more restrictive income standards. States were equally likely to adopt utilization controls for health and long-term care services regardless of state revenue or health expenditures.
This Note proposes such a consistent approach, arguing that courts in international extradition cases should focus on the accused's risk of flight rather than on the presence or absence of specific "special circumstances." Part I briefly discusses the international extradition process and outlines the important societal and individual interests at stake in the bail decision. Part II discusses the origin and evolution of the judicial approaches to bail in international extradition cases and demonstrates the inconsistency in the lower courts' treatment. Part III suggests an approach for making bail decisions in international extradition cases. It argues that the determinative factor in the bail decision should be the accused's risk of flight, not the presence of specific "special circumstances." Part III also shows that the burden of proof in the bail decision is properly on the accused, and it argues that the standard for bail should be more stringent after the accused has been determined extraditable.
Abstract : This volume examines the problems involved in integrating information systems currently in use in a large decentralized international organization. It is divided into three parts. The first part, A Conceptual Model for Integrated Autonomous Processing, highlights the fact that the technical strategy was modulated by three key conflicting organizational forces - autonomy, integration, and evolution. A conceptual system architecture has been developed to provide a technological message-oriented and data-oriented response to meet the organizational needs. The second part, Gaining Strategic Advantage Through Composite Information Systems, identified critical success factors for the successful deployment of Composite Information Systems (CIS) ideas and techniques. For this environment, a data-driven strategy offers the best chances for successful development of a modular and flexible infrastructure suited to the decentralized and highly autonomous structure of the organization. The third part, Integrating Systems for Financial Institutions Services Using Composite Information Systems, analyzes the three key organizational forces in greater detail. Autonomy, for example, is examined in terms of hardware control, operational control, transaction control, software control, data control, and management control. The forces of integration and evolution are also decomposed in a similar vein. The case study reveals that the operations of the organization can be improved by more foresight in certain areas. Keywords: Knowledge Based integrated information systems engineering(KBIISE). (KR)
A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [Ba], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string w is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept w. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject w with small probability. In [GMR] such a protocol was defined to be a zero-knowledge protocol if at the end of the interaction the verifier has learned nothing except that w â L. We study complexity theoretic implications of a language having this property. In particular we prove that if L admits a zeroknowledge proof then L can also be recognized by a two round interactive proof. This complements a result by Fortnow [F] where it is proved that the complement of L has a two round interactive proof protocol. The methods of proof are quite similar to those of Fortnow [F]. As in his case the proof works under the assumption that the original protocol is only zero-knowledge with respect to a specific verifier.
Zero knowledge protocols provide a way of proving that a statement is true without revealing anything other than the correctness of the claim. Zero knowledge protocols have practical applications in cryptography and are used in many applications. While some applications only exist on a specification level, a direction of research has produced real-world applications. Zero knowledge protocols, also referred to as zero knowledge proofs, are a type of protocol in which one party, called the prover, tries to convince the other party, called the verifier, that a given statement is true. Sometimes the statement is that the prover possesses a particular piece of information. This is a special case of zero knowledge protocol called a zero-knowledge proof of knowledge. Formally, a zero-knowledge proof is a type of interactive proof.
The notion of a zero knowledge interactive proof that one party "knows" some secret information is explored. It is shown that any "random self-reducible" problem has a zero knowledge interactive proof of this sort. The zero knowledge interactive proofs for graph isomorphism, quadratic residuosity, and "knowledge" of discrete logarithms all follow as special cases. Based on these results, new zero knowledge interactive proofs are exhibited for "knowledge" of the factorization of an integer, nonmembership in cyclic subgroups of Zp*, and determining whether an element generates Zp*. None of these proofs relies on any unproven assumptions.
In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff. We introduce and classify various definitions of zero-knowledge. Two definitions which are of special interest are auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox simulation zero-knowledge implies auxiliary-input zeroknowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e. were proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2]. We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las vegas zeroknowledge proof system necessarily belongs to R. We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of non-trivial auxiliary-input zero-knowledge proofs. In order to derive most of the results in the paper we make use of the full power of the definition of zero-knowledge: specifically, the requirement that there exist a simulator for any verifier, including "cheating verifiers".
ABSTRACT For a nation composed of independent regions, the effects of local tax competition for business investments are examined. It is first shown that atomistic regional authorities tax only local resources to finance the provision of public services to business. Thus, an efficient interregional equilibrium is induced. Various political/institutional constraints are shown to cause misallocation of the capital stock and an inefficient provision of public services. The characterization of the inefficiency is shown to vary widely, depending upon the constraint under consideration.
ABSTRACT Type/Token Ratios have been extensively used in child language research as an index of lexical diversity. This paper shows that the measure has frequently failed to discriminate between children at widely different stages of language development, and that the ratio may in fact fall as children get older. It is suggested here that such effects are caused by a negative, though non-linear, relationship between sample size (i.e. number of tokens) and Type/Token Ratio. Effects of open and closed class items are considered and an alternative Verbal Diversity measure is examined. Standardization of the number of tokens before computing Type/Token Ratios is recommended.