Enormous amounts of data are collected by hospitals, social networking systems, government agencies, and other organizations. There are huge social benefits in analyzing this data, but we must protect the privacy of the individuals in the data. The current standard definition of data privacy is differential privacy [22, 19]. In this thesis, we introduce new definitions of data privacy that can be better than differential privacy in certain ways. We first argue that differential privacy might not be strong enough in social network settings. We then introduce a zero-knowledge based definition of privacy called zero-knowledge privacy, which is strictly stronger than differential privacy and is particularly attractive when modeling privacy in social networks. Both differential privacy and zero-knowledge privacy provide strong privacy guarantees. However, for certain tasks, mechanisms satisfying these privacy definitions have to add a lot of "noise", thus lowering the utility of the released data. Thus, we introduce a new definition of privacy called crowd-blending privacy that strictly relaxes the notion of differential privacy. We demonstrate crowd-blending private mechanisms for histograms and for releasing synthetic data points, achieving strictly better utility than what is possible using differentially private mechanisms. Differential privacy guarantees the same level of privacy protection for all individuals. However, we demonstrate that some individuals may need more privacy than others. Thus, we introduce a generalization of differential privacy called tai- lored differential privacy, where an individual's privacy parameter is "tailored" for the individual based on the individual's data and the data set. We focus on a natural instance of tailored differential privacy, which we call outlier privacy: an individual's privacy parameter is determined by how much of an "outlier " the individual is. In this thesis, we also study the problem of strategy-proof voting, which is plagued by impossibility results. We take a bounded-rationality approach to this problem and consider a setting where voters have "coarse" beliefs (a notion that has gained popularity in the behavioral economics literature). In particular, we construct good voting rules that satisfy a notion of strategy-proofness with respect to coarse i.i.d. beliefs, thus circumventing the existing impossibility results.
Introduction This paper surveys some aspects of the theory of abelian varieties relevant to the Pila–Zannier proof of the Manin–Mumford conjecture and to the André– Oort conjecture. An abelian variety is a complete algebraic variety with a group law. The geometry of abelian varieties is tightly constrained and well-behaved, and they are important tools in algebraic geometry. Abelian varieties defined over number fields pose interesting arithmetic problems, for example concerning their rational points and associated Galois representations. The paper is in three parts: (1) an introduction to abelian varieties; (2) an outline of moduli spaces of principally polarised abelian varieties, which are the fundamental examples of Shimura varieties; (3) a detailed proof of the Ax–Lindemann–Weierstrass theorem for abelian varieties, following amethod using o-minimal geometry due to Pila, Ullmo and Yafaev. The first part assumes only an elementary knowledge of algebraic varieties and complex analytic geometry. The second part makes heavier use of algebraic geometry, but still at the level of varieties, and a little algebraic number theory. Like the first part, the algebraic geometry in the third part is elementary; the third part also assumes familiarity with the concept of semialgebraic sets, and uses cell decomposition for semialgebraic sets and the Pila–Wilkie theorem as black boxes. The second and third parts are independent of each other, so the reader interested primarily in the Ax–Lindemann–Weierstrass theorem may skip the second part (sections 4 to 6). In the first part of the paper (sections 2 and 3), we introduce abelian varieties over fields of characteristic zero, and especially over the complex numbers. The theory of abelian varieties over fields of positive characteristic introduces additional complications which we will not discuss. Our choice of topics is driven by Pila and Zannier's proof of the Manin–Mumford conjecture using o-minimal geometry. We will not discuss the Manin–Mumford conjecture or its proofs directly in this paper; aspects of the proof, and its generalisation to Shimura varieties, are discussed in other papers in this volume.
Stuart H. Rubin, Thouraya Bouabana‐Tebibel, Yasmine Hoadjli, Kadaouia Habib · 5 authors
The solution of NP-hard problems requires the use of one or more explicit or implicit heuristics as a practical measure. Quantum computers promise to make this practical for O (2n) problems or less, but have yet to deliver a solution to a single NP-hard problem. The question addressed by this paper is whether domain transference and reuse of problem-solving knowledge can be mediated through the reuse of heuristics, and, if so, the extent to which such transference may occur in the solution of NP-hard problems. Neural networks have zero domain transference on account of their inability to represent modus ponens. Similarly, CBR, deep learning, EP, GAs, SVMs, the predicate calculus, learning via conventional expert systems, and all other machine learning technologies are unable to theoretically or practically mediate domain transference because they don't respect randomization as the core underpinning technology. The paper offers a constructive proof of the unbounded density of knowledge in support of the Semantic Randomization Theorem (SRT). It details this result and its potential impact on the machine learning community.
Ring signatures enable a user to sign a message so that a ring of possible signers is identified, without revealing exactly which member of that ring actually generated the signature. In some situations, however, an actual signer may possibly want to expose himself, for instance, if doing so, he will acquire an enormous benefit. In this paper, a signature scheme with designated verifiability based on Schnorr ring signature is proposed. The scheme provides a confirmation procedure, in which the real signer is able to convince a designated party that he is the one who generates the signature. The confirming procedure involves an interactive Zero-Knowledge proof protocol, which is non-transferable, and it only can be triggered by the signer. Based on the intractability of Discrete Logarithm Problem (DLP), the scheme is existentially unforgeable under adaptive-chosen message attack in the random oracle model.
Authentication is primary process by which you can verify that someone is legitimate user or not. The identification of an entity or person is based on the username and password provided to that entity. In security systems, authentication is playing an important role by which it provides access to the system to an entity based on their identity. Authentication only ensures that the entity who is claims to be, but do not passes any information about the access rights of the entity. The zero- knowledge protocol used to provide data security and zero-knowledge transfer during authentication. The proposed model for node authentication using zero - knowledge proof for secure login is much faster than existing model in terms of execution time, CPU usage, time complexity and performance. It also provides security features likes confidentiality, integrity, authentication and non-repudiation.
The I-710 and CA-60 highways are key transportation corridors in the Southern California region that are heavily used on a daily basis by heavy duty drayage trucks that transport the cargo from the ports to the inland transportation terminals. These terminals, which include store/warehouses, inland-railways, are anywhere from 5 to 50 miles in distance from the ports. The concentrated operation of these drayage vehicles in these corridors has had and will continue to have a significant impact on the air quality in this region whereby significantly impacting the quality of life in the communities surrounding these corridors. To reduce these negative impacts it is critical that zero and near-zero emission technologies be developed and deployed in the region. A potential local market size of up to 46,000 trucks exists in the South Coast Air Basin, based on near- dock drayage trucks and trucks operating on the I-710 freeway. The South Coast Air Quality Management District (SCAQMD), California Air Resources Board (CARB) and Southern California Association of Governments (SCAG) — the agencies responsible for preparing the State Implementation Plan required under the federal Clean Air Act — have stated that to attain federal air quality standards the region will need to transition to broad use of zero and near zero emission energy sources in cars, trucks and other equipment (Southern California Association of Governments et al, 2011). SCAQMD partnered with Volvo Trucks to develop, build and demonstrate a prototype Class 8 heavy-duty plug-in hybrid drayage truck with significantly reduced emissions and fuel use. Volvo’s approach leveraged the group’s global knowledge and experience in designing and deploying electromobility products. The proprietary hybrid driveline selected for this proof of concept was integrated with multiple enhancements to the complete vehicle in order to maximize the emission and energy impact of electrification. A detailed review of all technologies included in the demonstrator is presented in this report. The project was completed in July 2015 with a final demonstration of the concept vehicle on a simulated drayage route around Volvo’s North American headquarters in Greensboro, NC. The route included all traffic conditions typical of drayage operation in Southern California as well as geofences defined to showcase the zero emission capabilities of the truck. The demonstrator successfully completed four consecutive trips with a gross combined vehicle weight of 44,000 lb., covering approximately 2 miles out of a total distance of 9 miles per trip in the Zero Emission (ZE) geofence. This vehicle is expected to use approximately 30% less fuel than a typical drayage truck in daily operation, and it is designed to allow full electric operation whenever operating in a marine terminal in the ports of Los Angeles / Long Beach. A paper study on the feasibility of expanding the capabilities of the plug-in hybrid concept developed as part of this project was also delivered as an addendum to the regular progress reports.
Ring signatures enable a user to anonymously sign a message on behalf of group of users. In this study, the authors propose the first ring signature scheme whose size is O (log 2 N ), where N is the number of users in the ring. They achieve this result by improving Chandran et al .’s ring signature scheme presented at the International Colloquium on Automata, Languages and Programming 2007. Their scheme uses a common reference string and non‐interactive zero‐knowledge proofs. The security of their scheme is proven without requiring random oracles.
A homomorphic public key crypto-scheme based on the Boolean Satisfiability Problem is proposed. The public key is a SAT formula satisfied by the private key. Probabilistic encryption generates functions implied to be false by the public key XOR the message bits. A zero-knowledge proof is used to provide signatures.
Gurchetan S. Grewal, Mark Ryan, Liqun Chen, Michael R. Clarkson
Du-Vote is a new remote electronic voting protocol that eliminates the often-required assumption that voters trust general-purpose computers. Trust is distributed in Du-Vote between a simple hardware token issued to the voter, the voter's computer, and a server run by election authorities. Verifiability is guaranteed with high probability even if all these machines are controlled by the adversary, and privacy is guaranteed as long as at least either the voter's computer, or the server and the hardware token, are not controlled by the adversary. The design of the Du-Vote protocol is presented in this paper. A new non-interactive zero-knowledge proof is employed to verify the server's computations. Du-Vote is a step towards tackling the problem of internet voting on user machines that are likely to have malware. We anticipate that the methods of Du-Vote can be used in other applications to find ways of achieving malware tolerance, that is, ways of securely using platforms that are known or suspected to have malware.
Zero-knowledge (ZK) proofs have become a central building block for a variety of modern security protocols. Modern ZK constructions, such as the Groth-Sahai proof system, offer novel types of cryptographic flexibility: a participant is able to re-randomize existing ZK proofs to achieve, for instance, message unlink ability in anonymity protocols, she can hide public parts of a ZK proof statement to meet her specific privacy requirements, and she can logically compose ZK proofs in order to construct new proof statements. ZK proof systems that permit these transformations are called malleable. However, since these transformations are accessible also to the adversary, analyzing the security of these protocols requires one to cope with a much more comprehensive attacker model -- a challenge that automated protocol analysis thus far has not been capable of dealing with. In this work, we introduce the first symbolic abstraction of malleable ZK proofs. We further prove the computational soundness of our abstraction with respect to observational equivalence, which enables the computationally sound verification of privacy properties. Finally, we show that our symbolic abstraction is suitable for ProVerif, a state-of-the-art cryptographic protocol verifier, by verifying an improved version of the anonymous webs of trust protocol.
In this chapter we will look at two different applications of information-theoretic multiparty computation (MPC), a practical application and a theoretical application. The example of a practical application is the use of MPC to clear a commodity derivative market. The focus will be on the algorithmic tricks used to implement the auction efficiently. The theoretical application is the use of MPC to realize so-called zero-knowledge proofs. A zero-knowledge proof is a way for a prover to convince a verifier about the validity of a statement without leaking any information on why the statement is true. This can be seen as an MPC problem with n = 2 parties. However, since the minimal requirement for information-theoretic MPC is that fewer than n /2 parties are corrupted, information-theoretic MPC does not seem to help in constructing zero-knowledge proofs. However, as we shall see, a technique sometimes called MPC in the head can be used to turn an efficient, secure MPC for a given relation into an efficient zero-knowledge proof for the same relation. A Double Auction In this section we look at a concrete application of MPC, with a main focus on the algorithmic tricks needed to efficiently do a secure auction. Along the way, we will look at how to efficiently and securely compare two integers secret shared among the parties. 9.1.1 Introduction The algorithmic techniques we will look at are fairly general, but it is instructive to view them in a practical context. We will look at how they have been used to clear the Danish market for contracts on sugar beets from 2008 and until the time of this writing. This was the first industrial application of MPC. More historical details on this can be found later and in the Notes section at the end of this chapter. In the economic field of mechanism design, the concept of a trusted third party has been a central assumption since the 1970s. The field has grown in momentum since it was initiated and has turned into a truly cross-disciplinary field. Today, many practical mechanisms require a trusted third party.
The idea of Zero Knowledge Proof (ZKP) was first proposed by Goldwasser, Micali and Racko [S. Goldwasser, et al. 1989.] in 1989. It is a mutual protocol to solve the problem: the prover demonstrates to the verifier that he has some secret information, but after that the verifier doesn’t know what the secret information is. In the verification process, the prover lets out zero information about the secret to the verifier. ZKP can be divided into two basic kinds: interactive and non-interactive zero knowledge proof . Zero knowledge proof protocols are used extensively in the field of information security, such as identity authentication, fair exchange, key agreement, electronic voting and electronic payment system, etc.
Daniel Cabarcas, Denise Demirel, Florian Göpfert, Jean Lancrenon · 5 authors
Abstract. Commitment schemes are among cryptography’s most im-portant building blocks. Besides their basic properties, hidingness and bindingness, for many applications it is important that the schemes ap-plied support proofs of knowledge. However, all existing solutions which have been proven to provide these protocols are only computationally hiding or are not resistant against quantum adversaries. This is not suitable for long-lived systems, such as long-term archives, where com-mitments have to provide security also in the long run. Thus, in this work we present a new post-quantum unconditionally hiding commit-ment scheme that supports (statistical) zero-knowledge protocols and allows to refreshes the binding property over time. The bindingness of our construction relies on the approximate shortest vector problem, a lattice problem which is conjectured to be hard for polynomial approxi-mation factors, even for a quantum adversary. Furthermore, we provide a protocol that allows the committer to prolong the bindingness prop-erty of a given commitment while showing in zero-knowledge fashion that the value committed to did not change. In addition, our construc-tion yields two more interesting features: one is the ability to “convert” a Pedersen commitment into a lattice-based one, and the other one is the construction of a hybrid approach whose bindingness relies on the discrete logarithm and approximate shortest vector problems.
Unlink ability and accountability are conflicting yet critical requirements for on-line transactions that need to be addressed in order to preserve users' privacy as well as to protect service providers in today identity ecosystems. In this poster paper we introduce a pseudonymous identity management system in which users can carry out unlink able on-line transactions without having to disclose their actual identity to the service providers. At the same time, the service providers have strong assurance about the authenticity of the identity and credentials. In our approach, users' identity is cryptographically encoded in pseudonymous identity tokens issued by trusted identity providers. Our system includes a lightweight policy language which enables users and service providers to express their requirements pertaining to pseudonymous identity verification and a suite of protocols based on zero-knowledge-proofs which enables the fulfillment of these requirements.
Abstract. Pedersen commitments are important cryptographic primi-tives. They allow a prover to commit to a certain value without revealing any information about it and without the prover being able to change its mind later on. Since the first property holds unconditionally this is an essential primitive for many schemes providing long-term confidential-ity. However, the second property only holds computationally. Hence, in the long run bindingness is lost, making the primitive improper for long-lived systems. Thus in this paper, we describe a protocol that, in a sense, prolongs the bindingness of a given Pedersen commitment. More precisely, we demonstrate how to prove in perfect zero-knowledge that a new Pedersen commitment- generated with a larger security param-eter- and a corresponding old commitment both commit to the same value. We stress that this is a non-trivial procedure. Up until now the only known perfect zero-knowledge proof techniques for proving mes-sage equivalence of two commitments work when both commitments use isomorphic message spaces. However, as we will show in this work, to prolong the security of Pedersen commitments we cannot tolerate this restriction. Our prolonging technique works for non-isomorphic message spaces, is efficient, can be repeated an arbitrary number of times, main-tains unconditional confidentiality, and allows to preserve the format of the Pedersen commitments. This makes the construction presented here an important contribution to long-lived systems. Finally, we illustrate this by discussing how commitments with prolongable bindingness can be used to allow for archiving solutions that provide not only integrity but also confidentiality in the long-term.
본 논문에서는 미리 알려진 임의의 다항식과 암호화된 다항식의 곱셈을 수행한 후, 해당 곱셈이 정당하게 수행되었음을 보이기 위해 증명자 (Prover)와 검증자 (Verifier)간의 다항식 상등성 영지식증명 (Zero-knowledge Proof) 프로토콜을 일반화할 수 있는 방법을 다룬다. 이를 위하여 다항식의 상등성을 증명하는 일반화된 프로토콜을 제시하고 랜덤오라클 (Random Oracle) 모델에서 안전성을 증명한다. 이러한 기법은 안전한 집합연산 기법을 포함하여 다항식에 기반한 다자간 연산기법 (Secure Multi-party Computation)에 적용될 수 있다. In this paper, we are interested in a generalization of zero-knowledge interactive protocols between prover and verifier, especially to show that the product of an encrypted polynomial and a random polynomial, but published by a secure commitment scheme was correctly computed by the prover. To this end, we provide a generalized protocol for proving that the resulting polynomial is correctly computed by an encrypted polynomial and another committed polynomial. Further we show that the protocol is also secure in the random oracle model. We expect that our generalized protocol can play a role of building blocks in implementing secure multi-party computation including private set operations.
This habilitation thesis deals with cryptographic primitives that preserve the algebraic structure of underlying objects (messages, keys, etc) and their applications to the design of non-interactive zero-knowledge proofs and privacy-enhancing cryptographic primitives.In 2008, Groth and Sahai showed how to make these proof systems relatively efficient in abelian groups endowed with a bilinear map. These techniques, however, require to work with lower-level primitives where handled objects all live in a cyclic abelian group. Among other things, we need to sign messages without destroying their algebraic structure (in particular, without hashing them first) so as to be able to efficiently prove properties about hidden signed messages. The first part of this thesis describes a structure-preserving signature scheme which was the first efficient realization under previously studied algorithmic assumptions. These tools are also utilized in the design of a novel revocation mechanism for group signatures, which allow users to anonymously sign messages on behalf of a population they belong to. The second part of this thesis considers structure-preserving signatures endowed with homomorphic properties. We show how to use them in the design of non-malleable cryptographic primitives. Using linearly homomorphic structurepreserving signatures, we notably obtain non-malleable commitments to group elements and non-interactive zero-knowledge proofs, as well as public-key encryption schemes that resist chosen-ciphertext attacks.
In this paper we consider the mathematical model of thermo- and photo-acoustic tomography for the recovery of the initial condition of a wave field from knowledge of its boundary values. Unlike the free-space setting, we consider the wave problem in a region enclosed by a surface where an impedance boundary condition is imposed. This condition models the presence of physical boundaries such as interfaces or acoustic mirrors which reflect some of the wave energy back into the enclosed domain. By recognizing that the inverse problem is equivalent to a statement of boundary observability, we use control operators to prove the unique and stable recovery of the initial wave profile from knowledge of boundary measurements. Since our proof is constructive, we explicitly derive a solvable equation for the unknown initial condition. This equation can be solved numerically using the conjugate gradient method. We also propose an alternative approach based on the stabilization of waves. This leads to an exponentially and uniformly convergent Neumann series reconstruction when the impedance coefficient is not identically zero. In both cases, if well-known geometrical conditions are satisfied, our approaches are naturally suited for variable wave speed and for measurements on a subset of the boundary.
Chinyang Henry Tseng, Shiau-Huey Wang, Woei-Jiunn Tsaur
As our aging population significantly grows, personal health monitoring is becoming an emerging service and can be accomplished by large-scale, low-power sensor networks, such as Zigbee networks. However, collected medical data may reveal patient privacy, and should be well protected. We propose a Hierarchical and Dynamic Elliptic Curve Cryptosystem based self-certified public key scheme (HiDE) for medical data protection. To serve a large amount of sensors, HiDE provides a hierarchical cluster-based framework consisting of a Backbone Cluster and several Area Clusters. In an Area Cluster, a Secure Access Point (SAP) collects medical data from Secure Sensors (SSs) in the sensor network, and transmits the aggregated data to a Root SAP located in the Backbone Cluster. Therefore, the Root SAP can serve a considerable number of SSs without establishing separate secure sessions with each SS individually. To provide dynamic secure sessions for mobile SSs connecting SAP, HiDE introduces the Elliptic Curve Cryptosystem based Self-certified Public key scheme (ESP) for establishing secure sessions between each pair of Cluster Head (CH) and Cluster Member (CM). In ESP, the CH can issue a public key to a CM, and computes a Shared Session Key (SSK) with that CM without knowing the CM's secrete key. This concept satisfies the Zero Knowledge Proof so CHs can dynamically build secure sessions with CMs without managing a CM's secrete keys. Our experiments in realistic implementations and Network Simulation demonstrate that ESP requires less computation and network overhead than the Rivest-Shamir-Adleman (RSA)-based public key scheme. In addition, security analysis shows keys in ESP are well protected. Thus, HiDE can protect the confidentiality of sensitive medical data with low computation overhead, and keep appropriate network performance for wireless sensor networks.
The article proposes a novel construction of sign-cryption scheme with provable security which is most suited to be implement on smart card. It is secure in random oracle model and the security relies on Decisional Bilinear Diffie-Hellmann Problem. The proposed scheme is secure against adaptive chosen ciphertext attack (indistiguishbility) and adaptive chosen message attack (unforgeability). The scheme have the security properties anonymity and forward security. Also it is inspired by zero-knowledge proof and is publicly verifiable. The scheme has applied for mutual authentication to authenticate identity of smart card's user and reader via Application protocol Data units. This can be achieved by the verification of the signature of the proposed scheme. Also the sensitive information are stored in the form of ciphertext in Read Only Memory of smart cards. These functions are performed in one logical step at a low computational cost.
본 논문에서는 미리 알려진 임의의 다항식과 암호화된 다항식의 곱셈을 수행한 후, 해당 곱셈이 정당하게 수행되었음을 보이기 위해 증명자 (Prover)와 검증자 (Verifier)간의 다항식 상등성 영지식증명 (Zero-knowledge Proof) 프로토콜을 일반화할 수 있는 방법을 다룬다. 이를 위하여 다항식의 상등성을 증명하는 일반화된 프로토콜을 제시하고 랜덤오라클 (Random Oracle) 모델에서 안전성을 증명한다. 이러한 기법은 안전한 집합연산 기법을 포함하여 다항식에 기반한 다자간 연산기법 (Secure Multi-party Computation)에 적용될 수 있다.