Jorge F. Chávez, Roberto F. Iunes, Hector Conroy, Johanna Ramos · 7 authors
This evaluation examines the IDB's Country Program with Colombia for the 2007-2011 period. The evaluation found social investment and decentralization as two areas in which the IDB maintained presence and relevance during this period. In social investment, the IDB was consolidated as a stable partner to Colombia in the creation and operation of a long-term social safety net. In regards to decentralization, cooperation was crosscutting, as the IDB worked with subnational institutions in diverse sectors, such as transportation, business development, housing, and modernization of the State. The IDB also continued its long-term work with Colombia to modernize and improve the efficiency of oversight agencies and the judicial branch, helping the country to obtain sizeable savings. To continue to improve the strategy with Colombia, OVE recommends that the IDB should: (i) increase its efforts to lower the transaction costs of IDB's cooperation with the country; (ii) improve the evaluability, monitoring and evaluation of the Country Strategy and the projects financed by the IDB; (iii) identify and strengthen the IDB's capacity in the areas and sectors in which the country will concentrate its demand for financial cooperation; and (iv) identify international development experiences that have been successful and present them to Colombia.
According to a contemporary Pole, Ukraine is a country which, having broken out of the clutches of communism, makes its way towards Europe, the place it has always belonged to. The proof of that are the Ukrainians’ European aspirations—to become a member of the EU or NATO, as well as the events of the Orange Revolution, which proved that Ukrainians are mature enough to break free from Russia for the sake of democratization of the country, following the example of Western European countries. However, Ukrainians themselves are no longer so unanimous. A careful look at the country of our neighbours makes it evident that both in the sphere of politics as well as culture the Ukrainian nation is strongly divided. This was demonstrated by the Orange Revolution, which made the West realise that in Ukraine a fight is taking place, where the choice of an eastern or western variant is at stake. Ukrainians are also divided as far as their identity is concerned, both cultural and national, for whose roots they are still searching, both in Russia and Western Europe. We may say that as far as the matter of their place on earth is concerned, Ukrainians are almost in exactly the same place as they were eighty years ago.
Self configuring VLSI technology architectures offer a new environment for creating novel security functions. Two such functions for physical security architectures are proposed to be generated autonomously as unknown/secret internal functions. A cell-based FPGA technology architecture is deployed for generating two classes of self-constructed one-way physical secret functions, one representing a hash function and the other a ciphering function. The Hash function is a non-invertible mapping, where the cipher function should be invertible. The two sample architectures of the functions are inspired from the programmable cell structure of the selected FPGA technology. As the functions are internally created, their mapping structures can be kept completely secret and even unknown to anybody. Such units could be efficiently deployed for a novel physical security even when nothing is known about their exact architecture and mapping functions. Several new attractive application scenarios are demonstrated including a type of zero-knowledge proof of identity and clone-resistant physical units as well as secured dependency functions. It is also shown that such security mechanisms can be kept operational for some useful applications even if the secret-unknown functions are allowed to evolve and develop additional time-dependent and individual properties. Such security functions became recently possible after self-configuring VLSI architectures are available as a part of real microelectronic systems. Keywords-Identification; secret unknown hardware functions; clone-resitant units; secret-unknown physicalcipher, secret unknown hash-functions. 1.
2 source records
Physical Unclonable Functions (PUFs) and Hardware Security
Abstract. There is a broad literature on distributed card games over communications networks, collectively known as mental poker. Likein any distributed protocol, avoiding the need for a Trusted Third Party (TTP) in mental poker is highly desirable, because really trusted TTPs are not always available and seldom free. This paper deals with the player dropout problem in mental poker without a TTP. A solution based on zero-knowledge proofs is proposed. While staying TTP-free, our proposal allows the game to continue after player dropout.
Abstract. In undeniable signature schemes, zero-knowledgeness and non-transferability have been identified so far. In this paper, by separating these two notions, we show the first 3-move confirmation and disavowal protocols for Chaum’s undeniable signature scheme which is secure against active and concurrent attacks. Our main observation is that while the signer has one public key and one secret key, there exist two witnesses in the confirmation and disavowal proofs of Chaum’s scheme.
Abstract. Micali, Rabin, and Kilian [9] recently introduced zero-knowledge sets and databases, in which a prover sets up a database by publishing a commitment, and then gives proofs about particular values. While an elegant and useful primitive, zero-knowledge databases do not offer any good way to perform updates. We explore the issue of updating zero-knowledge databases. We define and discuss transparent updates, which (1) allow holders of proofs that are still valid to update their proofs, but (2) otherwise maintain secrecy about the update. We give rigorous definitions for transparently updatable zero-knowledge databases, and give a practical construction based on the Chase et al [2] construction, assuming that verifiable random functions exist and that mercurial commitments exist, in the random oracle model. We also investigate the idea of updatable commitments, an attempt to make simple commitments transparently updatable. We define this new primitive and give a simple secure construction.
Abstract. Most prior designated confirmer signature schemes either prove security in the random oracle model (ROM) or use general zeroknowledge proofs for NP statements (making them impractical). By slightly modifying the definition of designated confirmer signatures, Goldwasser and Waisbard presented an approach in which the Confirm and ConfirmedSign protocols could be implemented without appealing to general zero-knowledge proofs for NP statements (their Disavow protocol still requires them). The Goldwasser-Waisbard approach could be instantiated using Cramer-Shoup, GMR, or Gennaro-Halevi-Rabin signatures. In this paper, we provide an alternate generic transformation to convert any signature scheme into a designated confirmer signature scheme, without adding random oracles. Our key technique involves the use of a signature on a commitment and a separate encryption of the random string used for commitment. By adding this “layer of indirection, ” the underlying protocols in our schemes admit efficient instantiations (i.e., we can avoid appealing to general zero-knowledge proofs for NP statements) and furthermore the performance of these protocols is not tied to the choice of underlying signature scheme. We illustrate this using the Camenisch-Shoup variation on Paillier’s cryptosystem and Pedersen commitments. The confirm protocol in our resulting scheme requires 10 modular exponentiations (compared to 320 for Goldwasser-Waisbard) and our disavow protocol requires 41 modular exponentiations (compared to using a general zero-knowledge proof for Goldwasser-Waisbard). Previous schemes use the encryption of a signature paradigm, and thus run into problems when trying to implement the confirm and disavow protocols efficiently. 1
Abstract. We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the nonerasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the singleinconsistent-player UC model, which guarantees arbitrary composition as long as all protocols are executed by the same players. As an application, we propose a fully UC threshold Schnorr signature scheme. Our results are based on a new adaptively-secure Feldman VSS scheme. Although adaptive security was already addressed by Feldman in the original paper, the scheme requires secure communication, secure erasure, and either a linear number of rounds or digital signatures to resolve disputes. Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction on the corruption behavior of the adversary, which however disappears in some applications including our new DLKG protocol. We also propose several new adaptively-secure protocols, which may find other applications, like a sender non-committing encryption scheme, a distributed trapdoor-key generation protocol for Pedersen’s commitment scheme, or distributed-verifier proofs for proving relations among commitments or even any NP relations in general. 1
The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting.<br /> <br />We propose new techniques for building <em>quantum</em> zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK.<br /> <br />As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks.<br /> <br />Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, <em>non-oblivious verifier</em> QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.
Abstract. A commitment multiplication proof, CMP for short, allows a player who is committed to secrets s, s ′ and s ′ ′ = s · s ′ , to prove, without revealing s, s ′ or s ′ ′ , that indeed s ′ ′ = ss ′. CMP is an important building block for secure general multi-party computation as well as threshold cryptography. In the standard cryptographic model, a CMP is typically done interactively using zero-knowledge protocols. In the random oracle model it can be done non-interactively by removing interaction using the Fiat-Shamir heuristic. An alternative non-interactive solution in the distributed setting, where at most a certain fraction of the verifiers are malicious, was presented in [1] for Pedersen’s discrete log based commitment scheme. This CMP essentially consists ofa few invocations ofPedersen’s verifiable secret sharing scheme (VSS) and is secure in the standard model. In the first part ofthis paper, we improve that CMP by arguing that a building block used in its construction in fact already constitutes a CMP. This not only leads to a simplified exposition, but also saves on the required number ofinvocations ofPedersen’s VSS. Next we show how to construct non-interactive proofs of partial knowledge [8] in this distributed setting. This allows for instance to prove non-interactively the knowledge of ℓ out of m given secrets, without revealing which ones. We also show how to construct efficient non-interactive zero-knowledge proofs for circuit satisfiability in the distributed setting. In the second part, we investigate generalizations to other homomorphic commitment schemes, and show that on the negative side, Pedersen’s VSS cannot be generalized to arbitrary (black-box) homomorphic commitment schemes, while on the positive side, commitment schemes based on q-one-way-group-homomorphism [7], which cover wide range ofcurrently used schemes, suffice. 1
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano · 5 authors
. Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last decade and has been used throughout modern cryptography in several essential ways. For example, NIZK plays a central role in building provably secure public-key cryptosystems based on general complexity-theoretic assumptions that achieve security against chosen ciphertext attacks. In essence, in a multi-party setting, given a fixed common random string of polynomial size which is visible to all parties, NIZK allows an arbitrary polynomial number of Provers to send messages to polynomially many Verifiers, where each message constitutes an NIZK proof for an arbitrary polynomial-size NP statement. In this paper, we take a closer look at NIZK in the multi-party setting. First, we consider non-malleable NIZK, and generalizing and substantially strengthening the results of Sahai, we give the first construction of NIZK which remains non-malleable after polynomially-many NIZK proofs. Second, we turn to the definition of standard NIZK itself, and propose a strengthening of it. In particular, one of the concerns in the technical definition of NIZK (as well as non-malleable NIZK) is that the so-called &quot;simulator&quot; of the Zero-Knowledge property is allowed to pick a different &quot;common random string&quot; from the one that Provers must actually use to prove NIZK statements in real executions. In this paper, we propose a new definition for NIZK that eliminates this shortcoming, and where Provers and the simulator use the same common random string. Furthermore, we show that both standard and non-malleable NIZK (as well as NIZK Proofs of Knowledge) can be constructed achieving this stronger definition. We call...
Abstract. In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of “self-enforcing ” strategies making each player’s strategy an optimal response to the other player’s strategy. It is known that for many games the expected equilibrium payoffs can be much higher when a trusted third party (a “mediator”) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism that eliminates the need for the mediator yet allows the players to maintain the high payoffs offered by mediator-assisted strategies. We answer this question affirmatively provided the players are computationally bounded and can have free communication (so-called “cheap talk”) prior to playing the game. The main building block of our solution is an efficient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. Both Alice and Bob know a list of pairs (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games. 1
The Curry–Howard correspondence states the equivalence between the constructions implicit in intuitionistic logic and those described in the simplytyped lambda-calculus. It is an insight of great importance in theoretical computer science, and is fundamental in modern approaches to constructive type theory. The possibility of a similar formulae-as-types correspondence for classical logic looks to be a seminal development in this area, but whilst promising results have been achieved, there does not appear to be much agreement of what is at stake in claiming that such a correspondence exists. Consequently much work in this area suffers from several weaknesses; in particular the status of the new rules needed to describe the distinctively classical inferences is unclear. We show how to situate the formulae-as-types correspondence within the proof-theoretic account of logical semantics arising from the work of Michael Dummett andDag Prawitz, and demonstrate that the admissibility of Prawitz’s inversion principle, which we argue should be strengthened, is essential to the good behaviour of intuitionistic logic. By regarding the rules which determine the deductive strength of classical logic as structural rules, as opposed to the logical rules associated with specific logical connectives, we extend Prawitz’s inversion principle to classical propositional logic, formulated in a theory of Parigot’s lambda-mu calculus with eta expansions. We then provide a classical analogue of a subsystem of Martin-Lof’s type theory corresponding to Peano Arithmetic and show its soundness, appealing to an extension of Tait’s reducibility method. Our treatment is the first treatment of induction in classical arithmetic that truly falls under the aegis of the formulae-as-types correspondence, as it is the first that is consistent with the intensional reading of propositional equality.
. 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.