In this paper we put forward the Bounded Player Model for secure computation. In this new model, the number of players that will ever be involved in secure computations is bounded, but the number of computations has no a priori bound. Indeed, while the number of devices and people on this planet can be realistically estimated and bounded, the number of computations these devices will run can not be realistically bounded. We stress that in the Bounded Player model, in addition to no a priori bound on the number of sessions, there is no synchronization barrier, no trusted party, and simulation must be performed in polynomial time. In this setting, we achieve concurrent Zero Knowledge (cZK) with sub-logarithmic round complexity. Our security proof is (necessarily) non-black-box, our simulator is “straight-line” and works as long as the number of rounds is ω(1). We further show that unlike previously studied relaxations of the standard model (e.g., bounded number of sessions, timing assumptions, super-polynomial simulation), concurrent-secure computation is still impossible to achieve in the Bounded Player model. This gives evidence that our model is “closer” to the standard model than previously studied models, and study of this model might shed light on constructing round efficient concurrent zero-knowledge in the standard model as well.
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
Malleability for cryptography is not necessarily an opportunity for attack, but in many cases a potentially useful feature that can be exploited. In this work, we examine notions of malleability for non-interactive zero-knowledge (NIZK) proofs. We start by defining a malleable proof system, and then consider ways to meaningfully control the malleability of the proof system, as in many settings we would like to guarantee that only certain types of transformations can be performed. We also define notions for the cases in which we do not necessarily want a user to know that a proof has been obtained by applying a particular transformation; these are analogous to function/circuit privacy for encryption. As our motivating application, we consider a shorter proof for verifiable shuffles. Our controlled-malleable proofs allow us for the first time to use one compact proof to prove the correctness of an entire multi-step shuffle. Each authority takes as input a set of encrypted votes and a controlled-malleable NIZK proof that these are a shuffle of the original encrypted votes submitted by the voters; it then permutes and re-randomizes these votes and updates the proof by exploiting its controlled malleability. As another application, we generically use controlled-malleable proofs to realize a strong notion of encryption security. Finally, we examine malleability in existing proof systems and observe that Groth-Sahai proofs are malleable. We then go beyond this observation by characterizing all the ways in which they are malleable, and use them to efficiently instantiate our generic constructions from above; this means we can instantiate our proofs and all their applications using only the Decision Linear (DLIN) assumption. Work done as an intern at Microsoft Research Redmond
José Bacelar Almeida, Manuel Barbosa, Endre Bangerter, Gilles Barthe · 6 authors
Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from having to implement cryptography on their own by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is risky as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper, we present ZKCrypt, an optimizing cryptographic compiler that achieves an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt tightly integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage in the pipeline, ZKCrypt provides assurance that the implementation it outputs securely realizes the high-level proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system.
In this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all N P. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zeroknowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO 1989). Although it is widely believed that there exist constant-round zero-knowledge proofs of knowledge for all N P, to the best of our knowledge, no proof of this fact has been published. 1
Networks and entity groupings requires entity authentication while preserving the privacy of the entity being authenticated. Zero-Knowledge Proof (ZKP) plays an important role in authentication without revealing secret information. Diffie–Hellman (D-H) key exchange algorithm was developed to exchange secret keys through unprotected channels. This paper discusses zero-knowledge protocols and Diffie– Hellman algorithm and analyzes their vulnerability against known attacks. Also it presents a proposed protocol based on modification of Diffie–Hellman algorithm into an interactive zero-knowledge proof protocol. The proposed protocol is designed and developed to satisfy the zero-knowledge proof properties and resists the known attacks
We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by Krzakala et al. \cite{KrzakalaEtAl}, message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of non-zero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate $δ$ exceeds the (upper) Rényi information dimension of the signal, $\uRenyi(p_X)$. More precisely, for a sequence of signals of diverging dimension $n$ whose empirical distribution converges to $p_X$, reconstruction is with high probability successful from $\uRenyi(p_X)\, n+o(n)$ measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension $n$ and $k(n)$ non-zero entries, this implies reconstruction from $k(n)+o(n)$ measurements. For `discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from $o(n)$ measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal $p_X$.
Open access
2 source records
Sparse and Compressive Sensing Techniques
Microwave Imaging and Scattering Analysis
Distributed Sensor Networks and Detection Algorithms
In this paper we present a new 5-pass identification scheme with asymptotic\ncheating probability 1/2 based on the syndrome decoding problem. Our protocol\nis related to the Stern identification scheme but has a reduced communication\ncost compared to previous code-based zero-knowledge schemes, moreover our\nscheme permits to obtain a very low size of public key and secret key. The\ncontribution of this paper is twofold, first we propose a variation on the\nStern authentication scheme which permits to decrease asymptotically the\ncheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice)\nbut with less communication. Our solution is based on deriving new challenges\nfrom the secret key through cyclic shifts of the initial public key syndrome; a\nnew proof of soundness for this case is given Secondly we propose a new way to\ndeal with hashed commitments in zero-knowledge schemes based on Stern's scheme,\nso that in terms of communication, on the average, only one hash value is sent\nrather than two or three. Overall our new scheme has the good features of\nhaving a zero-knowledge security proof based on well known hard problem of\ncoding theory, a small size of secret and public key (a few hundred bits), a\nsmall calculation complexity, for an overall communication cost of 19kb for\nauthentication (for a $2^{16}$ security) and a signature of size of 93kb\n(11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous\nschemes based on coding theory.\n
Rosemberg Silva, Pierre-Louis Cayrel, Richard Lindner
In this paper we propose a new 5-pass zero-knowledge identification scheme with soundness error close to 1/2. We use the hardness of the Inhomogeneous Small Integer Solution problem as security basis. Our protocol achieves lower communication costs compared with previous lattice-based zeroknowledge identification schemes. Besides, our construction allows smaller public and secret keys by applying the use of ideal lattices. We allow the prover to possess several pairs of secret and public keys, and choose randomly which pair is to be used in a given round of execution. We also dealt with nonces in zero-knowledge schemes in a new way, lowering the number of values exchanged between the prover and the verifier. Hence, our scheme has the good features of having a zero-knowledge security proof based on a well known hard problem of lattice theory, with worst to average-case reduction, and small size of secret and public keys.
Sebastian Ries, Marc Fischlin, Leonardo A. Martucci, Max Muuhlhauser
The topics of trust and privacy are more relevant to users of online communities than ever before. Trust models provide excellent means for supporting users in their decision making process. However, those models require an exchange of information between users, which can pose a threat to the users' privacy. In this paper, we present a novel approach for a privacy preserving computation of trust. Besides preserving the privacy of the recommenders by exchanging and aggregating recommendations under encryption, the proposed approach is the first that enables the trusting entities to learn about the trustworthiness of their recommenders at the same time. This is achieved by linking the minimum amount of information that is required for the learning process to the actual recommendation and by using zero-knowledge proofs for assuring the correctness of this additional information.
Experts predict that in the next 10 to 100 years scientists will succeed in creating human-level artificial general intelligence. While it is most likely that this task will be accomplished by a government agency or a large corporation, the possibility remains that it will be done by a single inventor or a small team of researchers. In this paper, we address the question of safeguarding a discovery which could without hesitation be said to be worth trillions of dollars. Specifically, we propose a method based on the combination of zero knowledge proofs and provably AI-complete CAPTCHA problems to show that a superintelligent system has been constructed without having to reveal the system itself.
Raluca Ada Popa, Andrew J. Blumberg, Hari Balakrishnan, Frank H. Li
A significant and growing class of location-based mobile applications aggregate position data from individual devices at a server and compute aggregate statistics over these position streams. Because these devices can be linked to the movement of individuals, there is significant danger that the aggregate computation will violate the location privacy of individuals. This paper develops and evaluates PrivStats, a system for computing aggregate statistics over location data that simultaneously achieves two properties: first, provable guarantees on location privacy even in the face of any side information about users known to the server, and second, privacy-preserving accountability (i.e., protection against abusive clients uploading large amounts of spurious data). PrivStats achieves these properties using a new protocol for uploading and aggregating data anonymously as well as an efficient zero-knowledge proof of knowledge protocol we developed from scratch for accountability. We implemented our system on Nexus One smartphones and commodity servers. Our experimental results demonstrate that PrivStats is a practical system: computing a common aggregate (e.g., count) over the data of 10,000 clients takes less than 0.46 s at the server and the protocol has modest latency (0.6 s) to upload data from a Nexus phone. We also validated our protocols on real driver traces from the CarTel project.
In this paper we present a new 5-pass identification scheme with asymptotic cheating probability 1/2 based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced communication cost compared to previous code-based zero-knowledge schemes, moreover our scheme permits to obtain a very low size of public key and secret key. The contribution of this paper is twofold, first we propose a variation on the Stern authentication scheme which permits to decrease asymptotically the cheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice) but with less communication. Our solution is based on deriving new challenges from the secret key through cyclic shifts of the initial public key syndrome; a new proof of soundness for this case is given Secondly we propose a new way to deal with hashed commitments in zero-knowledge schemes based on Stern's scheme, so that in terms of communication, on the average, only one hash value is sent rather than two or three. Overall our new scheme has the good features of having a zero-knowledge security proof based on well known hard problem of coding theory, a small size of secret and public key (a few hundred bits), a small calculation complexity, for an overall communication cost of 19kb for authentication (for a $2^{16}$ security) and a signature of size of 93kb (11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous schemes based on coding theory.
Vote validity proof and verification is an efficiency bottleneck and privacy drawback in homomorphic e-voting. The existing vote validity proof technique is inefficient and only achieves honest-verifier zero knowledge. In this paper, an efficient proof and verification technique is proposed to guarantee vote validity in homomorphic e-voting. The new proof technique is mainly based on hash function operations that only need a very small number of costly public key cryptographic operations. It can handle untrusted verifiers and achieve stronger zero knowledge privacy. As a result, the efficiency and privacy of homomorphic e-voting applications will be significantly improved.
For anyone interested in the philosophy of risk–benefit analysis, a two-part paper in this issue makes stimulating reading [1, 2]. The authors describe an effect of antidepressants on fetal neuronal development. Maternal exposure to both tricyclic antidepressants and selective serotonin reuptake inhibitors (SSRIs) during pregnancy was associated with a 10-fold increase in laxative use in children. The findings illustrate how safety issues can remain undetected late in the life cycle of a drug, despite millions of patients being exposed for decades. Clinical pharmacology research, as with any science, needs to define questions that summarize the hypotheses to be tested. The efficacy of medicines can be defined by questions that are easy to formulate and are addressed by clinical trials. Even so, the efficacy of antidepressant medication is contentious, given the high placebo response, failure to prevent suicide and selective reporting of results [3, 4]. For safety issues, the key questions are usually not known until the data are collected. With myriad potential safety questions, it is important that all the available basic pharmacology is reviewed and that this knowledge is used to direct a search for specific clinical safety signals. The Groningen group have adopted this approach with a detailed literature review to form a hypothesis that maternal antidepressant use might influence fetal enteric nervous system development [1]. In a second study, they use epidemiology to assess paediatric laxative use as a potential marker of a specific teratogenic signal associated with the maternal use of antidepressants [2]. The starting point for this work was the linking of a small signal of infantile hypertrophic pyloric stenosis cases to the maternal use of fluoxetine in a northern Netherlands birth defect registry. This association is rational, because fluoxetine crosses the blood–brain barrier and serotonin contributes to the development of enteric neurons. A serotonin-based mechanism could also explain an increased use of laxatives by the children of mothers who had taken an SSRI. When a drug first comes to market, the assessment of the risk-to-benefit ratio is an educated guess. Efficacy can be defined by objective clinical trials, where predefined end-points are quantified. That the efficacy data are invariably adequate at the time of marketing is supported by the rarity of withdrawals of medicines because of later proof of a lack of efficacy. But safety cannot usually be quantified objectively; thus, many parameters might show a signal which can neither be confirmed or ignored [5]. To define fully the safety profile of a medicine at the time of marketing would be so expensive that new drug development would halt if this were a requirement. As a compromise, the subjective assessment of safety data is based on international guidance on minimal requirements, summarized by the International Conference on Harmonisation's guideline, ICHE1 [6]. This sets a reasonable minimal exposure for medicines for non-life-threatening diseases of about 1500 people, of whom some 300–600 should be exposed for 6 months and at least 100 are exposed for 1 year. Though a reasonable requirement for drug development, the limitations of ICHE1 and the importance of postmarketing data are highlighted by the number of drugs that are withdrawn from the market for previously undetected safety problems. The ICHE1 safety population may prove inadequate to detect major concerns. Sometimes major safety concerns are only evident with larger and longer population exposure, for example, clofibrate. Here an early data set, considerably larger than the ICHE1 requirement, initially showed a favourable risk–benefit ratio [7]. But eventually, a clinical trial of some 200 000 patient-years showed a significant increase in mortality [8]. But not all important safety signals require large numbers of patients treated for many years. A safety signal might occur in only a small subpopulation, which at the time of licensing has either not been studied or has been studied in limited numbers. Ever since the thalidomide disaster revolutionized medicines regulation, the prime subpopulation of concern has been the fetus. The number of pregnancies exposed to a new drug at the time of licensing is invariably small or zero. When the drug is likely to be worth the risk of prescribing in pregnancy, it may take decades before the risks are quantified, for example, with anti-epileptic therapy [9]. With the increasing use of antidepressants during pregnancy in recent years, now about 2% of all pregnant women in some countries, it is time to consider how safe such prescribing might be. The labelling information of antidepressants has numerous safety warnings and always recommends caution in pregnancy, but statements that ‘neonates should be observed’ raises the question of what form this observation should take. Without control groups, it is often impossible to separate the risk of the disease, the risk of the therapy and the background incidence of developmental abnormality. Some adverse events only become apparent indirectly through the presence of a cofactor, a proxy or a challenge test. Supressing eosinophils may seem safe until a parasitic infection is encountered; grapefruit juice seems innocuous until a drug solely metabolized by CYP3A4 is co-administered. In the present study, the group used a pharmacy prescription database to detect the use of diarrhoea and constipation medication as a marker of enteric nervous system development. What is commendable in this approach is that basic pharmacology has been reviewed to develop a hypothesis that is then tested with epidemiology. Antidepressants can modify monoamine synaptic transmission of serotonin, noradrenaline or dopamine. The pharmacology of noradrenaline and dopamine is well established. Serotonin may affect anger, aggression, arousal, body temperature, mood, sleep, vomiting, sexuality and appetite and may even modify social decision making [10]. The pharmacology of serotonin has been sufficiently studied that it is possible to define safety questions that need to be answered in clinical studies of a new molecule that affects serotoninergic pathways. These include whether there is an effect on the following parameters: pulmonary hypertension; pulmonary hypertension in the fetus; heart valve abnormalities; chronotropic/inotropic effects via receptors in atria or ventricles; mood changes or suicidality; platelet aggregation; vasoconstriction; QT effects similar to cisapride; the incidence of serotonin syndrome alone or in combination; and bone resorption [11]. But there is more to the monoamines than neurotransmission. Knockout mouse models show the importance of the serotonin re-uptake transporter (SERT) and the noradrenaline transporter (NET) in neuronal development. SERT-deficient mice are susceptible to both diarrhoea and constipation in adult life. A careful review of the literature by the Groningen authors discusses evidence that modification of 5-HT2B receptors, SERT and NET may each adversely affect enteric nervous system development [1]. The safety analysis of medicines is more complex than the assessment of efficacy. Though antidepressants are taken by about 10% of Americans (they are the most commonly used prescription drug class in the USA), they continue to come up with surprises. If proved, the current findings are a major concern. Antidepressants have to cross the blood–brain barrier and affect neuronal function in order to work. This makes them likely to cross the placenta and access the neural crest and neural tube. If these commonly used drugs affect enteric nervous system development, then it is difficult to guarantee the safe development of other tissues. We cannot yet be reassured about potential central nervous system effects on children who have been exposed in utero, nor is there much certainty about long-term effects on the increasing number of children and adolescents exposed to antidepressants during their youth [12, 13]. The approach by the Groningen group, of using pharmacology to define an appropriate safety question, is exemplary. Only when such questions are formulated can sense be made of much of the mass of postmarketing pharmacovigilance data. Finding signals in these huge databases is like searching for a needle in a haystack. Defining a question based on the pharmacology to probe the data and using co-medication usage as a marker is analogous to using a magnet to search for such a valuable needle. The author is a pharmaceutical industry consultant and advises a range of companies on pharmaceutical development. The content of this article does not promote a particular commercial interest.
Open access
Pharmacological Effects and Toxicity Studies
Intestinal Malrotation and Obstruction Disorders
Maternal Mental Health During Pregnancy and Postpartum
Abstract Distributed applications are difficult to program reliably and securely. Dependently typed functional languages promise to prevent broad classes of errors and vulnerabilities, and to enable program verification to proceed side-by-side with development. However, as recursion, effects, and rich libraries are added, using types to reason about programs, specifications, and proofs becomes challenging. We present F*, a full-fledged design and implementation of a new dependently typed language for secure distributed programming. Our language provides arbitrary recursion while maintaining a logically consistent core; it enables modular reasoning about state and other effects using affine types; and it supports proofs of refinement properties using a mixture of cryptographic evidence and logical proof terms. The key mechanism is a new kind system that tracks several sub-languages within F* and controls their interaction. F* subsumes two previous languages, F7 and Fine. We prove type soundness (with proofs mechanized in Coq) and logical consistency for F*. We have implemented a compiler that translates F* to .NET bytecode, based on a prototype for Fine. F* provides access to libraries for concurrency, networking, cryptography, and interoperability with C#, F#, and the other .NET languages. The compiler produces verifiable binaries with 60% code size overhead for proofs and types, as much as a 45x improvement over the Fine compiler, while still enabling efficient bytecode verification. We have programmed and verified nearly 50,000 lines of F* including new schemes for multi-party sessions; a zero-knowledge privacy-preserving payment protocol; a provenance-aware curated database; a suite of web-browser extensions verified for authorization properties; a cloud-hosted multi-tier web application with a verified reference monitor; the core F* typechecker itself; and programs translated to F* from other languages such as F7 and JavaScript.
For the general problem of minimizing a convex function over a compact convex domain, we will investigate a simple iterative approximation algorithm based on the method by Frank & Wolfe 1956, that does not need projection steps in order to stay inside the optimization domain. Instead of a projection step, the linearized problem defined by a current subgradient is solved, which gives a step direction that will naturally stay in the domain. Our framework generalizes the sparse greedy algorithm of Frank & Wolfe and its primal-dual analysis by Clarkson 2010 (and the low-rank SDP approach by Hazan 2008) to arbitrary convex domains. We give a convergence proof guaranteeing ε-small duality gap after O(1/ε) iterations. The method allows us to understand the sparsity of approximate solutions for any l1-regularized convex optimization problem (and for optimization over the simplex), expressed as a function of the approximation quality. We obtain matching upper and lower bounds of Θ(1/ε) for the sparsity for l1-problems. The same bounds apply to low-rank semidefinite optimization with bounded trace, showing that rank O(1/ε) is best possible here as well. As another application, we obtain sparse matrices of O(1/ε) non-zero entries as ε-approximate solutions when optimizing any convex function over a class of diagonally dominant symmetric matrices. We show that our proposed first-order method also applies to nuclear norm and max-norm matrix optimization problems. For nuclear norm regularized optimization, such as matrix completion and low-rank recovery, we demonstrate the practical efficiency and scalability of our algorithm for large matrix problems, as e.g. the Netflix dataset. For general convex optimization over bounded matrix max-norm, our algorithm is the first with a convergence guarantee, to the best of our knowledge.
The canonical model of primary visual cortex (V1) is that it forms a linear generative model of the image stimulus presented to the eyes. Thus, for a given image with pixel values Xj, the representation Xj*=∑ibiψij is formed by multiplying the activity of each neuron (bi) by the feature that neuron encodes (ψij), and summing over all neurons. We call this a cooperative representation, since it involves all of the neurons collectively forming a single representation. Over time, the network is thought to adapt so as to minimize, on average, the mean-squared error between the representation X* and the input X, ||X-X*||2. Performing gradient descent on this error function yields the usual learning rule Δψij= α bi(Xj- ∑ibiψij ), where α is some small positive constant called the learning rate. Typically, the features ψij are interpreted as the receptive fields (RF’s; features to which a neuron responds) of the neurons; indeed, there is strong evidence [1] that the feature encoded by a neuron is very similar to its RF. In that case, the value ψij can be thought of as the strength of the synaptic connection between input pixel value Xj, and neuron i. With that interpretation in mind, it is clear that the canonical learning rule Δψij= α bi(Xj- ∑ibiψij ), used by most previous work in this field [1,2], fails to be biologically realistic because the rule for updating one synaptic strength ψij requires knowledge of the strengths of many synaptic connections, all on different neurons (with indices i), and it is not clear that such information is available to each individual synapse in the brain.
We consider instead a Hebbian learning rule that respects synaptic locality, Δψij= α bi(Xj- biψij ) [3]. In this case, the information required to change the strength of synapse ψij consists solely of the pre-synaptic activity Xj, the post-synaptic activity bi, and the current strength of the synaptic connection ψij. While this rule respects the locality of synaptic information, it does not appear to perform gradient descent on the desired error function ||Xj- ∑ibiψij||2. Instead, our local rule can be seen as gradient descent on the error function ∑i||Xj- biψij ||2, which is the sum over all neurons of the error between each neuron’s own internal representation of the input, biψij, and the input image. In other words, a network that follows Oja’s [3] local learning rule is a solipsistic one: each neuron makes its own individual representation of the input, and learning optimizes each of those representations individually.
We have proven that, if neuronal activities {bi} are uncorrelated, and sufficiently sparse (the majority of the bi’s are zero for any given image), the local and non-local learning rules are approximately equal, when averaged over many image presentations: = α ≈ α . This suggests a previously undiscovered role for independence and sparseness in visual cortex: these properties allow the neuronal network to (approximately) form the optimal cooperative representation, despite the locality of its learning rules. The same proof applies other neuronal networks that form linear generative models.
We will present the details of our proof, and an example network (similar to that of [4]) of leaky integrate-and-fire neurons that learns a sparse image code using the local learning rule Δψij= α bi(Xj- biψij ). In our network, inhibitory inter-neuronal connections and variable firing thresholds keep the neuronal activities uncorrelated and sparse throughout the learning process. When trained on natural scenes, this network learns the same diversity of receptive fields as do previous non-local algorithms [1,2].
Ioannis Chatzigiannakis, Apostolos Pyrgelis, Paul G. Spirakis, Yannis C. Stamatiou
Elliptic Curve Cryptography (ECC) is an attractive alternative to\nconventional public key cryptography, such as RSA. ECC is an ideal candidate\nfor implementation on constrained devices where the major computational\nresources i.e. speed, memory are limited and low-power wireless communication\nprotocols are employed. That is because it attains the same security levels\nwith traditional cryptosystems using smaller parameter sizes. Moreover, in\nseveral application areas such as person identification and eVoting, it is\nfrequently required of entities to prove knowledge of some fact without\nrevealing this knowledge. Such proofs of knowledge are called Zero Knowledge\nInteractive Proofs (ZKIP) and involve interactions between two communicating\nparties, the Prover and the Verifier. In a ZKIP, the Prover demonstrates the\npossesion of some information (e.g. authentication information) to the Verifier\nwithout disclosing it. In this paper, we focus on the application of ZKIP\nprotocols on resource constrained devices. We study well-established ZKIP\nprotocols based on the discrete logarithm problem and we transform them under\nthe ECC setting. Then, we implement the proposed protocols on Wiselib, a\ngeneric and open source algorithmic library. Finally, we present a thorough\nevaluation of the protocols on two popular hardware platforms equipped with low\nend microcontrollers (Jennic JN5139, TI MSP430) and 802.15.4 RF transceivers,\nin terms of code size, execution time, message size and energy requirements. To\nthe best of our knowledge, this is the first attempt of implementing and\nevaluating ZKIP protocols with emphasis on low-end devices. This work's results\ncan be used from developers who wish to achieve certain levels of security and\nprivacy in their applications.\n
Ioannis Chatzigiannakis, Apostolos Pyrgelis, Paul G. Spirakis, Yannis C. Stamatiou
Elliptic Curve Cryptography (ECC) is an attractive alternative to conventional public key cryptography, such as RSA. ECC is an ideal candidate for implementation on constrained devices where the major computational resources i.e. speed, memory are limited and low-power wireless communication protocols are employed. That is because it attains the same security levels with traditional cryptosystems using smaller parameter sizes. Moreover, in several application areas such as person identification and eVoting, it is frequently required of entities to prove knowledge of some fact without revealing this knowledge. Such proofs of knowledge are called Zero Knowledge Interactive Proofs (ZKIP) and involve interactions between two communicating parties, the Prover and the Verifier. In a ZKIP, the Prover demonstrates the possesion of some information (e.g. authentication information) to the Verifier without disclosing it. In this paper, we focus on the application of ZKIP protocols on resource constrained devices. We study well-established ZKIP protocols based on the discrete logarithm problem and we transform them under the ECC setting. Then, we implement the proposed protocols on Wiselib, a generic and open source algorithmic library. Finally, we present a thorough evaluation of the protocols on two popular hardware platforms equipped with low end microcontrollers (Jennic JN5139, TI MSP430) and 802.15.4 RF transceivers, in terms of code size, execution time, message size and energy requirements. To the best of our knowledge, this is the first attempt of implementing and evaluating ZKIP protocols with emphasis on low-end devices. This work's results can be used from developers who wish to achieve certain levels of security and privacy in their applications.
Shlomi Dolev, Panagiota N. Panagopoulou, Mikaël Rabie, Elad M. Schiller · 5 authors
Players in a game are assumed to be totally rational and absolutely smart. However, in reality all players may act in non-rational ways and may fail to understand and find their best actions. In particular, participants in social interactions, such as lotteries and auctions, cannot be expected to always find by themselves the "best-reply" to any situation. Indeed, agents may consult with others about the possible outcome of their actions. It is then up to the counselee to assure the rationality of the consultant's advice. We present a distributed computer system infrastructure, named rationality authority, that allows safe consultation among (possibly biased) parties. The parties' advices are adapted only after verifying their feasibility and optimality by standard formal proof checkers. The rationality authority design considers computational constraints, as well as privacy and security issues, such as verification methods that do not reveal private preferences. Some of the techniques resembles zero-knowledge proofs. A non-cooperative game is presented by the game inventor along with its (possibly intractable) equilibrium. The game inventor advises playing by this equilibrium and offers a checkable proof for the equilibrium feasibility and optimality. Standard verification procedures, provided by trusted (according to their reputation) verification procedures, are used to verify the proof. Thus, the proposed rationality authority infrastructure facilitates the applications of game theory in several important real-life scenarios by the use of computing systems.
Recent work in the corporate governance literature stresses the need to provide boards of directors (BoDs) with explicit incentives to safeguard shareholder welfare (Bebchuk, Fried, and Walker 2002; Bebchuk and Fried 2004). Jensen (1993) observes that “encouraging outside board members to hold substantial equity interests would provide better incentives.” In a similar spirit, the National Association of Corporate Directors (National Association of Corporate Directors 1995) proposed that “boards should pay directors solely in the form of stock and cash — with equity representing a substantial portion of the total up to 100 percent.” Indeed, equity-based BoD compensation has been on the rise in recent years (Bhagat and Black 2002; Conference Board 2006; Pearl Meyer & Partners 2007).1 The underlying premise is that equity awards help align BoD incentives with shareholder interests and enhance long-term firm value (Byrne 1996; Gabrielle 2001). However, to the extent that directors hold both vested and unvested (restricted) equity-based instruments, their actions are likely influenced by a combination of short-term and long-term incentives. The literature has focused mainly on the beneficial long-term incentive effects of equity awards. However, the effects of accompanying short-term incentives are not clear. Are they non–value adding, or do they in fact affect BoD behavior in a way that benefits shareholders? We address these questions in this paper. In particular, our purpose is to jointly examine the short-term and long-term incentive effects of equity-based BoD compensation on the BoD’s corporate governance (contracting and monitoring) and advisory (consulting) roles.2 The boards’ corporate governance role has been examined extensively.3 However, directors are typically individuals with considerable management experience and expertise and serve as a natural resource for top management in making crucial strategic and operational decisions.4,5 In fact, surveys have indicated that most directors view advising as their primary role (Mace 1972; Demb and Neubauer 1992; Adams 2009). Nevertheless, the BoD’s advisory role has received relatively little attention in the literature. Adams and Ferreira (2007), for example, examine the BoD’s monitoring and advisory role and show that a less independent BoD is sometimes optimal because it is less likely to monitor management, which, in turn, induces management to share information with the BoD, and receive better advice leading to greater investment efficiency.6 If this advisory role is indeed value-enhancing for shareholders, it cannot be ignored when examining the short-term and long-term incentive effects of BoD compensation. We use a simple agency model in which the BoD performs three roles: contracting, monitoring and consulting. The BoD contracts with the manager to supply some productive input that results in firm output. A performance evaluation system that produces an informative signal about firm output, and consequently about managerial effort, is used to contract with the manager. By monitoring, the BoD improves the precision of this information signal. By serving as a consultant, the BoD makes the manager more productive, that in turn means higher expected firm output. The BoD and the manager’s inputs are unobservable and personally costly.7 We assume that board members are themselves rational and self-serving, and must be motivated to provide consulting and monitoring inputs. Consequently, there are two agency problems in our model. The first is between the BoD and the manager, and the second is between the BoD and the shareholders. Both the agency problems arise because the BoD and manager’s respective inputs are unobservable and personally costly. In this respect, our paper adds to the growing literature that models shareholder-manager conflict as arising from a two-tier agency relationship. In our context, a single-tier model that examines shareholder-manager agency conflict stemming from the separation of ownership and control does not permit a role for the BoD. Therefore, by examining a multi-tier agency relationship our paper helps us better understand organizations (Bolton and Scharfstein 1998). In related work, Kumar and Sivaramakrishnan (2008) examine the BoD’s corporate governance role using a double agency model. They focus on the impact of the lack of BoD independence from management on corporate governance, and characterize optimal equity awards to the BoD to create the right BoD incentives. Harris and Raviv (2008) present a model where control of the board can be given to either insiders (the non-independent board) or outsiders (the independent board) — both insiders and outsiders have private payoff-related information. They show that it is sometimes beneficial to give board control to insiders in order to better exploit their information. We begin our analysis by examining a benchmark setting in which the BoD’s inputs are commonly observable. In this benchmark case, it suffices to compensate the BoD for the personal cost of providing consulting and monitoring inputs. When the BoD’s inputs are not observable, explicit BoD incentives become necessary. We show that long-term incentives (i.e., incentives tied to firm output) make the BoD explicitly care about the firm’s output and thereby motivate the BoD to play an active consulting role. Thus, compensating the BoD with restricted stock awards (equity) motivates the BoD to supply consulting input. However, we identify conditions under which long-term incentives alone do not suffice in motivating the BoD’s monitoring input. The is that the BoD’s monitoring input improves the of the performance evaluation system used to managerial and has on firm output. The BoD, does not have incentive to supply monitoring input. the need for short-term incentives. We show that incentives tied to the short-term used to are in this because they provide incentives for the BoD to in We are not of work that has the role of short-term BoD incentives in this short-term BoD a that the manager can these in for private the BoD or We address this by a setting where the manager can the firm’s short-term and show in the use of short-term induces the BoD to monitoring In our results that both long-term and short-term incentives are to that the BoD both corporate governance and consulting equity awards are in the with to equity awards are in motivating In we are to of BoD compensation to BoD The paper as In we the model. In we the BoD’s consulting and monitoring inputs. In we the effects of providing short-term long-term incentives to the BoD. In we the where the manager can firm We provide a and some in where is the of is the manager’s is the manager’s productive effort, and is the cost of productive to the manager. The manager’s productive input is unobservable to the BoD. we assume it is where actions that are in the interests of the shareholders. of we assume that productive is personally to the The output of the by is a from the with The BoD has the expertise to as a to the manager. from simple advice to the manager to providing on and the firm’s and We assume that the manager’s Thus, the BoD’s expertise and the manager a We do not on the of and for the that the BoD’s consulting input can have a more impact on the manager’s when the manager either or productive We assume that the firm’s expected output on productive effort, of the BoD’s consulting is that the productive that We assume that the firm’s output, is not the short-term of the manager. Therefore, the manager cannot be a that a of this output. the manager to be on an and short-term which we by by a performance system in performance can of two where We can of as a short-term of the output. we assume that the manager does not have the to this we this The that the manager cannot be a contract on the long-term output some the manager’s contract can be on long-term the optimal compensation contract would be a of is a of there is that in short-term performance play a role in managerial is literature on managerial or that can be to the to short-term and Bebchuk and (1993) show that focus on short-term performance in model this by the manager’s that a contract on short-term performance is of our model is that the BoD’s consulting and monitoring inputs are unobservable to the manager, as is the manager’s to the BoD. Both the BoD and the manager must be motivated to supply their respective inputs. in the the BoD is with restricted and We assume that restricted equity awards have a that the firm’s output or value observable. Thus, the value of restricted equity awards on the of of compensation we use the restricted equity awards to to BoD compensation on the firm’s output of compensation for of the the value of equity awards on the firm’s short-term which is by awards be as a short-term incentive when there are on as a we use the equity awards to to BoD compensation on The manager’s compensation is on short-term performance — the of the performance the contract to the by the BoD. The BoD’s on the can be on both short-term and long-term and We use to the contract to the BoD by the shareholders. We are in that directors have an that has example, that directors their a of the of the fact that the is for both and that a of their between the of and outside in their is to the Board the of directors on boards is years of directors have for more the is The of is as the BoD a compensation contract to the manager. If the manager the or productive the BoD monitoring and consulting inputs. performance is and are as of that by monitoring input the BoD makes the short-term performance a less signal about the firm’s output Consequently, by monitoring the BoD improves the of about the manager’s productive input and can the manager productive a expected compensation The BoD’s consulting on the the manager’s and firm output, it can for the BoD’s monitoring role. The BoD’s consulting input the of the short-term performance a on it the of consulting can or the of about the manager’s productive on consulting input is more informative on consulting input the is a of the in the can a or a in the manager. an where the BoD’s consulting the manager’s it the that on productive by the manager, making about the manager’s makes it more likely that the manager is for Thus, consulting in this the role of and thereby results in expected compensation the where means that the signal more likely with consulting when the manager productive making about the manager’s more more for the manager. a higher compensation is to the manager to supply productive In the of and which of these two effects and the BoD’s consulting input improves or the of the short-term performance about the manager’s productive input We can the has a on the manager’s performance evaluation by the of the short-term performance about the manager’s productive to consulting and in the of has a on the manager’s performance evaluation by the of the short-term performance about the manager’s productive to consulting and in the of If the of consulting on the of the short-term performance about the manager’s productive to consulting and in the of is is to that we are the of on consulting and consulting input. Thus, consulting the role of monitoring in our model. the consulting has an on the of with to the manager’s productive input. The BoD’s consulting input the manager’s the adds some to the performance evaluation that conditions and are conditions and it is that of In the impact of the BoD’s consulting input on the of and on the manager’s performance is for or effects of BoD consulting makes the model more the that the role the short-term performance and the long-term value play in motivating the BoD the become to We to the effects of the BoD’s consulting and monitoring inputs using the by and in the effects of and in the of and consulting the of about the manager’s productive and the of to which the manager is in Consequently, we can identify a of for which the manager’s by the to the is not us to the effects of consulting and The focus of is on the manager’s expected compensation and on However, in the of or are on the manager’s Therefore, on the us to identify a of that for of monitoring, consulting does not affect the of the of the we focus on the of for which the BoD’s consulting does not affect the of with to the managerial productive input. We begin our analysis by examining a where the BoD’s monitoring and consulting inputs are commonly and the manager productive input (the manager’s productive input is not setting a benchmark which we the benefits from providing short-term and long-term incentives to the BoD when the BoD’s inputs are not observable. In this benchmark explicit incentives are to motivate the BoD to provide these it suffices to compensate the BoD for the of these inputs. Thus, the that the BoD monitoring input the from monitoring — expected compensation cost — the BoD’s cost of the the BoD consulting input they a If consulting has a on the manager’s performance the consulting input from the BoD the from and expected managerial compensation the BoD’s cost of consulting. If on the consulting has a the consulting input from the BoD the from the in expected managerial compensation and the BoD’s cost of consulting. We this in the In the benchmark the the BoD consulting monitoring inputs in the benefits from these inputs the BoD’s cost of monitoring and consulting. We a setting in which these inputs are unobservable to the manager and to outside shareholders. setting us to examine the role of short-term and long-term BoD In BoD compensation vested stock and equity the value of these is by short-term is to examine the role of short-term BoD incentives in motivating their consulting and monitoring we first characterize the BoD’s optimal compensation contract on and on and We examine the optimal contract can the form of a to the BoD on short-term performance and restricted equity stock tied to long-term and the BoD’s and of we to and assume the monitoring and consulting by the BoD. In the benchmark the BoD’s monitoring input the of the short-term performance about the manager’s productive a monitoring the BoD to that in the manager productive a expected compensation However, a BoD contract on long-term performance does not the BoD’s compensation to or the manager’s compensation — monitoring improves the precision of about to is not to compensate the BoD on long-term performance and that it monitoring input in can that the BoD consulting input in The is to the firm’s expected output of the BoD’s and manager’s compensation. The the BoD and the that the BoD consulting input. the that BoD are The to that the BoD monitoring and consulting inputs in using a contract on to the need to compensate the BoD on both short-term and long-term that the BoD’s cost of monitoring input does not affect the BoD’s compensation the cost of monitoring to the cost of consulting is that the firm the BoD consulting input in by the BoD when this the BoD monitoring input. that both monitoring and consulting affect the In this case, that the BoD consulting input does not monitoring input. The BoD has to be explicitly for the cost of monitoring, in to the cost of to supply monitoring and consulting inputs in contract the that are more likely when the BoD monitoring input. monitoring is that the firm must provide incentive for the BoD to supply monitoring input in and which are the two that become more likely when the BoD monitoring input — by monitoring improves the precision of about by the that is when the firm’s long-term performance is that the BoD optimal of the cost of monitoring to the cost of consulting is a of both short-term and long-term Thus, the BoD’s compensation to both short-term and long-term and is to that the BoD consulting and monitoring inputs in We this in the does not a BoD contract on long-term performance that the BoD monitoring input. A BoD contract that is on both long-term and short-term and is to that the BoD consulting and monitoring inputs in The BoD optimal the BoD for of short-term and long-term and we to examine the optimal BoD contract can be a that is on short-term performance and a that is on long-term it the optimal BoD contract can be short-term and long-term We can the which conditions under which the optimal BoD contract can the form of a on the short-term performance and restricted equity stock value is tied to the output The can that the BoD monitoring and consulting input in by the BoD a contract of the form If If We focus on with in which to a of BoD compensation short-term and long-term is to that does not the incentive effects of BoD equity awards. In particular, equity awards and long-term performance incentives as are not because the BoD with equity makes a of the firm’s output — firm output compensation — of Nevertheless, we a more in our analysis and our attention to contracts of the form where a share of the firm given to the BoD, and a a us to to the role of equity awards in the BoD compensation is similar to that in the benchmark for the incentive that the BoD’s monitoring and consulting inputs. equity as in share the BoD to care about the firm’s expected long-term that given a equity the BoD would in the However, as we in restricted equity awards are not in motivating monitoring input. the BoD that the manager has productive effort, it does not by to the of the performance about the manager’s productive has incentive to monitoring that given the the BoD’s consulting input the of about the manager’s productive restricted equity awards provide incentive to the BoD to that the manager productive the as the BoD a portion of that incentive to the BoD to not monitoring If the BoD that the manager has productive effort, it not supply monitoring input to the that and thereby the manager’s expected compensation as is to that the BoD’s incentive to not supply monitoring input does not solely on to the manager’s expected compensation. Therefore, we identify the equity to motivate the consulting the the BoD’s consulting input results in higher expected firm output that the BoD some equity their The must the benefits and with the BoD’s consulting input in and equity to to the BoD. equity is for shareholders, it does not make to have the BoD provide consulting input in The BoD’s incentive to not supply monitoring input some In our it is rational for the BoD to not supply monitoring input there that this example, directors have personal with the manager of the If we to the effects of the BoD’s personal cost of monitoring suffices to that restricted equity awards cannot motivate the BoD to supply monitoring input in The of this is as The is that is of the BoD’s and the We can the The can be by to the that consulting long-term firm value and monitoring has short-term in turn that the BoD’s compensation has to be tied to both short-term and long-term Indeed, that restricted equity awards are to that the BoD consulting and that equity awards are to that the BoD monitoring role. the BoD’s compensation to the long-term performance of the firm — restricted equity awards — is the BoD’s compensation to the firm’s short-term performance does not to be that as we have the BoD, the manager, must be for short-term The If a performance is to it is for setting BoD incentives as The use of short-term performance in setting BoD incentives is with an in that it the BoD to performance by for management — on which there is little — is that is a performance and have the incentive to in a way that on by using their it is the of the to that the and the performance of a firm in a the BoD has a to shareholder Thus, it would that in setting BoD the use of performance that are to managerial incentives does not help this this it is more likely that when the firm’s output is of managerial the analysis we assume that does not a personal cost to the manager does it affect or If it the manager would in or expected from is greater the this cost an it does not affect our analysis is to show that in the manager indeed to productive the BoD has to short-term that is the manager in to or expected BoD monitoring the effects of does not the manager’s incentive to the BoD this behavior by the manager and that or is to or However, results in higher expected compensation because the performance evaluation system is less because it is more for the BoD to the manager’s productive input. The manager the firm’s short-term performance in results in higher expected compensation We examine the BoD’s compensation incentives to monitor the manager in the of performance We first the role of long-term BoD incentives. We that compensating the BoD with an equity share does not give the BoD incentive to supply monitoring input in The is similar to the The is that the BoD’s monitoring input is for the BoD and it improves the of about the manager’s productive the fact that monitoring the of performance by the manager the BoD that the manager productive in the BoD does not by monitoring input. an equity share the BoD not supply monitoring input. the use of the short-term BoD incentives. that on monitoring the of and thereby the of the the of on by the that the BoD that the manager productive in is more likely to means that the the BoD short-term they can that the BoD monitoring input in short-term BoD incentives incentive with to monitoring role in the of performance The of providing corporate boards with long-term incentives equity awards has been by recent corporate governance literature. as a most directors hold both vested and unvested (restricted) equity and their actions are likely influenced by a combination of short-term and long-term incentives. it would that long-term incentives should suffice in that boards to shareholder the effects of short-term incentives are not clear. In this we examine the effects of short-term and long-term incentives on the corporate governance (contracting and monitoring) and management advisory (consulting) of the BoD using a two-tier agency primary is that long-term incentives not suffice and that short-term BoD incentives can play a role in shareholder as restricted equity provide the BoD with the incentive to supply consulting by not motivate the BoD to monitor when monitoring is personally to the BoD. By short-term incentives BoD as or a on short-term can the BoD contracting, and monitoring more short-term serve an incentive role in the of long-term incentives. of our model some we have on a simple to these In particular, the that are be as there is considerable in the agency literature in this If we this and it is that the not the manager to the and not the BoD to the monitoring However, the underlying incentive is the as in our model. in the results of the we the effects of the BoD’s consulting and monitoring inputs on the of the short-term about the manager’s In particular, we conditions that the BoD’s consulting input has or with to the of the short-term when helps the it is not necessary. results and hold when we for of the BoD’s consulting input. We that managerial is a primary BoD Recent corporate governance as the of shareholder and shareholder to directors have this In our monitoring is not a for is because the way can in our model is the manager to supply productive when is expected to supply productive there is in — the manager productive In in our managerial is and monitoring can be as the cost of in where we performance we do not view monitoring as a way to the improves the precision of the performance and the effects of it does not the BoD to If the BoD with some managerial a would that the manager does not in The role of short-term BoD incentives in a setting where the primary is is not clear. be an for is to that shareholder and BoD interests be for can create incentives for directors to provide consulting and monitoring inputs the for directors of is is that directors some benefits personal or have for when be as directors for short-term In this the of boards that directors can serve as and shareholder and not be in the our analysis makes a for providing explicit incentives to align interests and of the BoD, a recent by to a a in the by making corporate boards more and to have been in to recent the of stock by some address this the cost of incentive that we have in this paper. We use and to conditions that the BoD’s consulting input improves or the of about the manager’s productive input. can be that the of to that is and as Thus, We the to We that that Therefore, the of about the manager’s productive input improves when the BoD consulting can be that the of to the as we can that We to identify conditions that the of and for that the BoD’s consulting input does not affect the manager’s expected compensation we the by and to the effects of and we to identify conditions that when the the as an of and the manager’s the is The is to the firm’s expected output of the BoD’s and manager’s compensation. The the BoD and the that the BoD consulting input. the that BoD are The is to the firm’s expected output of the BoD’s and manager’s compensation. The the BoD and the that the BoD monitoring and consulting inputs. the that BoD are that both monitoring and consulting cost affect the optimal The optimal BoD contract that consulting and monitoring inputs in is in the of contract can be a contract of the form The BoD’s monitoring input improves the of the performance about the manager’s productive However, the BoD that the manager productive effort, it has incentive to monitoring equity awards do not the fact that the BoD does not by monitoring effort, personal cost for the BoD that the manager productive effort, it has incentive to monitoring for an The optimal compensation contract that the manager in that and monitoring the of on a the BoD can the manager’s expected compensation by monitoring The manager this behavior by the BoD and does not a contract on monitoring The BoD supply consulting input in The way the BoD can the manager from firm performance is to a compensation the manager productive in A rational BoD this behavior by the manager and the compensation contract to the manager productive and does not that makes productive more for the manager. on and is more likely to the of on and a the BoD higher expected compensation to the manager productive in more to the of in where a similar has been the fact that monitoring the effects of the manager’s the BoD does not have incentive to supply monitoring input it is with an equity share in the The is that monitoring is personally for the BoD and monitoring improves the of the performance about the manager’s productive Thus, the BoD that the manager has productive in it has incentive to supply monitoring We have in that in a setting a combination of short-term and long-term incentives can that the BoD consulting and monitoring inputs in can be to the In the between the and is that the that is when the firm’s output is is in the setting and in the Thus, similar as in the of it can be that a combination of short-term and long-term incentive can that the BoD consulting and monitoring inputs in that the manager’s to firm performance on the compensation