. An interactive proof system (or argument) (P; V ) is concurrent zero-knowledge if whenever the prover engages in polynomially many concurrent executions of (P; V ), with (possibly distinct) colluding polynomial time bounded veriers V1 ; : : : ; V poly(n) , the entire undertaking is zero-knowledge. Dwork, Naor, and Sahai recently showed the existence of a large class of concurrent zero-knowledge arguments, including arguments for all of NP, under a reasonable assumption on the behavior of clocks of nonfaulty processors. In this paper, we continue the study of concurrent zero-knowledge arguments. After observing that, without recourse to timing, the existence of a trusted center considerably simpli- es the design and proof of many concurrent zero-knowledge arguments (again including arguments for all of NP), we design a preprocessing protocol, making use of timing, to simulate the trusted center for the purposes of achieving concurrent zero-knowledge. Once a particular p...
We present zero-knowledge proofs and arguments for arithmetic circuits over finite prime fields, namely given a circuit, show in zero-knowledge that inputs can be selected leading to a given output. For a field GF(q), where q is an n-bit prime, a<br />circuit of size O(n), and error probability 2^−n, our protocols require communication of O(n^2) bits. This is the same worst-cast complexity as the trivial (non zero-knowledge)<br />interactive proof where the prover just reveals the input values. If the circuit involves n multiplications, the best previously known methods would in general require communication<br />of Omega(n^3 log n) bits.<br />Variations of the technique behind these protocols lead to other interesting applications.<br />We first look at the Boolean Circuit Satisfiability problem and give zero-knowledge proofs and arguments for a circuit of size n and error probability 2^−n in which there is an interactive preprocessing phase requiring communication of O(n^2)<br />bits. In this phase, the statement to be proved later need not be known. Later the prover can non-interactively prove any circuit he wants, i.e. by sending only one message, of size O(n) bits.<br />As a second application, we show that Shamirs (Shens) interactive proof system for the (IP-complete) QBF problem can be transformed to a zero-knowledge proof<br />system with the same asymptotic communication complexity and number of rounds. The security of our protocols can be based on any one-way group homomorphism with a particular set of properties. We give examples of special assumptions sufficient for this, including: the RSA assumption, hardness of discrete log in a prime order group, and polynomial security of Die-Hellman encryption. We note that the constants involved in our asymptotic complexities are small enough for our protocols to be practical with realistic choices of parameters.
A perfect zero-knowledge interactive protocol allows a prover to convince a verifier of the validity of a statement in a way that does not give the verifier any additional information [GMR,GMW]. Such protocols take place by the exchange of messages back and forth between the prover and the verifier. An important measure of efficiency for these protocols is the number of rounds in the interaction. In previously known perfect zero-knowledge protocols for statements concerning NP--complete problems [BCC], at least k rounds were necessary in order to prevent one party from having a probability of undetected cheating greater than 2 \\Gammak . In this paper, we give the first perfect zero-knowledge protocol that offers arbitrarily high security for any statement in NP with a constant number of rounds. The protocol is computationally convincing (rather than statistically convincing as would have been an interactive proof--system in the sense of Goldwasser, Micali and Rackoff) because the ver...
Alain Fonteneau, Alain Gubian, Henri Sterdyniak, Christine Verpeaux
What Prospects for French Social Security ? A. Fonteneau, A. Gubian, H. Sterdyniak, C. Verpeaux In the future, the ageing of the population, increases in health expenditures, the rise of unemployment and the necessity to encourage the birth rate will make the problems of the social security more acute. Is it possible to finance spreading social transfers without undermining economic growth ? Could one reform the social welfare system to avoid the extension of transfers ? To get clearer social choices and to aim at macroeconomic balance, social benefits should be financed only by households. Workers would contribute to the insurance role of social security ; income tax would provide for solidarity. Shifting all contributions on to wage earners and raising wages accordingly would have no short-term impact. However, employers would be assured that gross costs were not to be increased and indeed would remain stable. Replacing employers' contributions by a turnover tax or by VAT would not result in better economic performance. Substituting part of the employers' contributions by a tax on machines would stimulate the saving of capital and employment. A solution of liberal obedience that would separate solidarity financed by the Government from privately financed individual insurance seems neither viable nor desirable. As far as health expenditures are concerned, the development of private insurances would deny the principle of equality of all men in respect of medical care. Insurance companies would be tempted to make a select among their potential clients and to exclude those who present too many risks. Two other ways seem to be more promising, even though they include risks. In the first case a centralized control of the care supply is based on an assessment system of medical techniques. In the second one, coordinated networks of care are based on decentralization.