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.
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.
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.
Anonymity in Bitcoin, a peer-to-peer electronic currency system, is a complicated issue. Within the system, users are identified by public-keys only. An attacker wishing to de-anonymize its users will attempt to construct the one-to-many mapping between users and public-keys and associate information external to the system with the users. Bitcoin tries to prevent this attack by storing the mapping of a user to his or her public-keys on that user's node only and by allowing each user to generate as many public-keys as required. In this chapter we consider the topological structure of two networks derived from Bitcoin's public transaction history. We show that the two networks have a non-trivial topological structure, provide complementary views of the Bitcoin system and have implications for anonymity. We combine these structures with external information and techniques such as context discovery and flow analysis to investigate an alleged theft of Bitcoins, which, at the time of the theft, had a market value of approximately half a million U.S. dollars.
In this paper, we study methods for improving the utility and privacy of\nreputation scores for online auctions, such as used in eBay, so as to reduce\nthe effectiveness of feedback extortion. The main ideas behind our techniques\nare to use randomization and various schemes to escrow reputations scores until\nappropriate external events occur. Depending on the degree of utility and\nprivacy needed, these external techniques could depend on the number and type\nof reputation scores collected. Moreover, if additional privacy protection is\nneeded, then random sampling can be used with respect reputation scores in such\na way that reputation aggregates remain useful, but individual reputation\nscores are probabilistically hidden from users. Finally, we show that if\nprivacy is also desired with respect to the the reputation aggregator, then we\ncan use zero-knowledge proofs for reputation comparisons.\n
In this paper, we study methods for improving the utility and privacy of reputation scores for online auctions, such as used in eBay, so as to reduce the effectiveness of feedback extortion. The main ideas behind our techniques are to use randomization and various schemes to escrow reputations scores until appropriate external events occur. Depending on the degree of utility and privacy needed, these external techniques could depend on the number and type of reputation scores collected. Moreover, if additional privacy protection is needed, then random sampling can be used with respect reputation scores in such a way that reputation aggregates remain useful, but individual reputation scores are probabilistically hidden from users. Finally, we show that if privacy is also desired with respect to the the reputation aggregator, then we can use zero-knowledge proofs for reputation comparisons.
We propose a coin-flip protocol which yields a string of strong, random coins and is fully simulatable against poly-sized quantum adversaries on both sides. It can be implemented with quantum-computational security without any set-up assumptions, since our construction only assumes mixed commitment schemes which we show how to construct in the given setting. We then show that the interactive generation of random coins at the beginning or during outer protocols allows for quantum-secure realizations of classical schemes, again without any set-up assumptions. As example applications we discuss quantum zero-knowledge proofs of knowledge and quantum-secure two-party function evaluation. Both applications assume only fully simulatable coin-flipping and mixed commitments. Since our framework allows to construct fully simulatable coin-flipping from mixed commitments, this in particular shows that mixed commitments are complete for quantum-secure two-party function evaluation. This seems to be the first completeness result for quantum-secure two-party function evaluation from a generic assumption.
David Bernhard, Véronique Cortier, Olivier Pereira, Ben Smyth · 5 authors
Abstract. Recent results show that the current implementation of He-lios, a practical e-voting protocol, does not ensure independence of the cast votes, and demonstrate the impact of this lack of independence on vote privacy. Some simple fixes seem to be available and security of the revised scheme has been studied with respect to symbolic models. In this paper we study the security of Helios using computational models. Our first contribution is a model for the property known as ballot privacy that generalizes and extends several existing ones. Using this model, we investigate an abstract voting scheme (of which the revised Helios is an instantiation) built from an arbitrary encryp-tion scheme with certain functional properties. We prove, generically, that whenever this encryption scheme falls in the class of voting-friendly schemes that we define, the resulting voting scheme provably satisfies ballot privacy. We explain how our general result yields cryptographic security guaran-tees for the revised version of Helios (albeit from non-standard assump-tions). Furthermore, we show (by giving two distinct constructions) that it is possible to construct voting-friendly encryption, and therefore voting schemes, using only standard cryptographic tools. We detail an instan-tiation based on ElGamal encryption and Fiat-Shamir non-interactive zero-knowledge proofs that closely resembles Helios and which provably satisfies ballot privacy. 1
Matteo Maffei, Giulio Malavolta, Manuel Reinert, Dominique Schröder
The existing (election) voting systems, e.g., representative democracy, have many limitations and often fail to serve the best interest of the people in collective decision making. To address this issue, the concept of liquid democracy has been emerging as an alternative decision-making model to make better use of "the wisdom of crowds". Very recently, a few liquid democracy implementations, e.g. Google Votes and Decentralized Autonomous Organization (DAO), are released; however, those systems only focus on the functionality aspect, as no privacy/anonymity is considered. In this work, we, for the first time, provide a rigorous study of liquid democracy under the Universal Composability (UC) frame- work. In the literature, liquid democracy was achieved via two separate stages -- delegation and voting. We propose an efficient liquid democracy e-voting scheme that uni es these two stages. At the core of our design is a new voting concept called statement voting, which can be viewed as a natural extension of the conventional voting approaches. We remark that our statement voting can be extended to enable more complex voting and generic ledger-based non-interactive multi-party computation. We believe that the statement voting concept opens a door for constructing a new class of e-voting schemes.
Digital signatures are fundamental cryptographic primitives. They are useful as a stand-alone application and building blocks of complex cryptographic systems. Accumulators are another useful cryptographic primitive which provide a way to combine a set of values into one short value. They are useful in improving efficiency of cryptographic systems. In particular, these two primitives are key components in privacy-preserving cryptographic systems. In this thesis, we study the use of digital signatures and accumulators in cryptographic applications. We design digital signature schemes and accumulators with different features that are suitable for a wide range of applications. We are interested in privacy-preserving cryptographic applications including anonymous electronic cash systems, anonymous authentication schemes and anonymous credential systems. We construct three different digital signature schemes, each with distinctive features. We also propose two novel constructions of accumulators. Based on our signature schemes and accumulators, we design two compact electronic cash schemes and a divisible electronic cash scheme. All our schemes are truly anonymous, meaning that privacy of the users is well-protected. We also explore other applications of our newly proposed signatures and accumulators. Specifically, we give a construction of k-times anonymous authentication schemes and attribute-based anonymous credential systems. During the course of the development of the thesis, we generalise existing techniques of zero-knowledge proof-of-knowledge protocol of double-discrete logarithms into zero-knowledge proof-of-knowledge protocol of representation of a committed value. Our protocol is compatible with existing zero-knowledge proof-of-knowledge protocols that demonstrate relationship amongst discrete logarithms. We believe that this protocol, together with the newly introduced primitives, are of independent interest.
Rafael Pass, Wei-Lung Dustin Tseng, Douglas Wikström
We show that only languages in BPP have public-coin black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any setup) and in the bare public key model (where the prover and the verifier have registered public keys). We complement this result by constructing a public-coin black-box zero-knowledge proof based on one-way functions that remains secure under any a priori bounded number of concurrent executions. A key step (of independent interest) in the analysis of our lower bound shows that any public-coin protocol, when repeated sufficiently in parallel, satisfies a notion of “resettable soundness” if the verifier picks its random coins using a pseudorandom function.
Rafael Pass, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam
Few techniques for obtaining concurrent zero-knowledge exist; all require a complex and subtle analysis. We provide an arguably simpler and more general analysis of the oblivious simulation technique of Kilian and Petrank (STOC’01) while achieving the same bounds as Prabhakaran, Rosen and Sahai (FOCS’02). Using this analysis, and relying on tools recently developed by Ong and Vadhan (Eurocrypt’07, TCC’08) we are able to establish the following unconditional results: • every language inNP which has a ZK proof (resp. ZK argument, statistical ZK argument) also has a black-box concurrent ZK proof (resp. ZK argument, statistical ZK argument). • every languge which has a statistical ZK proof also has an ω(log n)-round black-box con-current statistical ZK proof.
Η διατριβή αυτή ασχολείται με την προδιαγραφή και υλοποίηση πρωτοκόλλων ασφάλειας με απαιτήσεις διασφάλισης ιδιωτικότητας, όπως για παράδειγμα τα πρωτόκολλα ηλεκτρονικών μετρητών, ηλεκτρονικής ψηφοφορίας και επιλεκτικής αποκάλυψης δεδομένων. Ο στόχος, όσον αφορά την προδιαγραφή τους, είναι αυτή να γίνει με τυπική μέθοδο (formal method), και, όσον αφορά την υλοποίησή τους, να βασίζεται στην προδιαγραφή τους και να διασφαλίζει τις περί ιδιωτικότητας απαιτήσεις. Το υπάρχον ερευνητικό έργο στη διεθνή βιβλιογραφία σε τυπικές μεθόδους δεν καλύπτει επαρκώς τα πρωτόκολλα ασφάλειας με απαιτήσεις διασφάλισης ιδιωτικότητας όσο άλλων ειδών πρωτόκολλα ασφάλειας, όπως τα πρωτόκολλα αυθεντικοποίησης. Στην παρούσα διατριβή υποστηρίζεται ότι οι λόγοι για αυτή την ανεπάρκεια μελέτης είναι οι εξής: Πρώτον, ότι τα πρωτόκολλα με απαιτήσεις διασφάλισης ιδιωτικότητας βασίζονται σε πιο εξειδικευμένη κρυπτογραφία, όπως η δέσμευση (commitment), η τυφλή υπογραφή (blind signature), η απόδειξη μηδενικής γνώσης (zero-knowledge proof), η ομομορφική κρυπτογραφία (homomorphic encryption), το mix του Chaum και το onion routing. Δεύτερον, ότι είναι απαραίτητη η διαφοροποίηση στη μοντελοποίηση της κλασικής κρυπτογραφίας (συμμετρική και ασύμμετρη κρυπτογράφηση και ψηφιακές υπογραφές) που τα πρωτόκολλα αυτά χρησιμοποιούν από κοινού με τα υπόλοιπα πρωτόκολλα. Η διατριβή αυτή χρησιμοποιεί ως βάση τη γλώσσα προδιαγραφής πρωτοκόλλων Typed MSR [14, 15], καθώς και την προηγούμενη εργασία μας στην ίδια [10, 7, 9, 8, 6] ερευνητική κατεύθυνση και στοχεύει με τροποποιήσεις και προσθήκες να την μετατρέψει σε κατάλληλη, αφενός για την προδιαγραφή πρωτοκόλλων με απαιτήσεις διασφάλισης ιδιωτικότητας, αφετέρου για την προδιαγραφή ενός κατά Dolev-Yao επιτιθέμενου [19] σχεδιασμένου για επίθεση σε πρωτόκολλα τέτοιου είδους. Επιπλέον, χρησιμοποιεί ως βάση τη γλώσσα Jif [30, 31, 29], καθώς και την προηγούμενη εργασία μας [6] στην ίδια ερευνητική κατεύθυνση και στοχεύει να επιδείξει πως η γλώσσα αυτή, που διαθέτει σύστημα τύπων για απαιτήσεις ασφάλειας, μπορεί να χρησιμοποιηθεί με τέτοιον τρόπο ώστε οι αδυναμίες στην υλοποίηση πρωτοκόλλων ασφαλείας όσον αφορά τη συνδεσιμότητα (linkability) να μπορούν να ανιχνευτούν με ένα συνδυασμό στατικών και δυναμικών (runtime) ελέγχων. Τα βασικά συμπεράσματα της διατριβής αυτής είναι τα ακόλουθα: 1. Προκειμένου η Typed MSR να είναι κατάλληλη για την προδιαγραφή πρωτοκόλλων ασφάλειας με απαιτήσεις ιδιωτικότητας, δεν θα πρέπει να μοντελοποιεί τη συμμετρική και την ασύμμετρη κρυπτογράφηση ως αιτιοκρατική. Μια τέτοια απλούστευση μπορεί να μη δημιουργεί προβλήματα στη μοντελοποίηση άλλων πρωτοκόλλων, αλλά οδηγεί σε ανύπαρκτες αδυναμίες διασύνδεσης στα πρωτόκολλα που μελετούμε στην παρούσα διατριβή. 2. Μπορούμε να κατασκευάσουμε υψηλού επιπέδου μοντελοποιήσεις για κρυπτογραφία πιο σύνθετη από την κλασική, όπως είναι η δέσμευση, η τυφλή υπογραφή, η απόδειξη μηδενικής γνώσης και η ομομορφική κρυπτογραφία. 3. Η χρήση μη διαδραστικών μοντελοποιήσεων για τις αποδείξεις μηδενικής γνώσης οδηγεί στην απλοποίηση τόσο της προδιαγραφής των πρωτοκόλλων, όσο και της μετατροπής αυτής σε υλοποίησή τους. 4. Με βάση τις προαναφερθείσες αλλαγές και προσθήκες, η Typed MSR γίνεται κατάλληλη για την προδιαγραφή πρωτοκόλλων ασφάλειας με απαιτήσεις ιδιωτικότητας, όπως δείχνει η προδιαγραφή των δύο πρωτοκόλλων ηλεκτρονικής ψηφοφορίας που περιέχονται στην παρούσα διατριβή. 5. Ένα απλό σύστημα τύπων, που χρησιμοποιείται παράλληλα με το σύστημα τύπων της Typed MSR, αποτρέπει συγκεκριμένες εσφαλμένες χρήσεις της κρυπτογραφίας που μπορεί να οδηγήσουν σε αδυναμίες συνδεσιμότητας, καθώς και να παρακολουθήσει την απειλή συνδεσιμότητας που προκύπτει από κάθε πιθανή χρήση της κρυπτογραφίας. 6. Είναι απαραίτητη η ενημέρωση του εκφρασμένου σε Typed MSR μοντέλου του κατά Dolev-Yao επιτιθέμενου με βάση τα παραπάνω, ώστε να μπορεί πλέον να επιτεθεί στα πρωτόκολλα τα οποία μελετάμε. 7. Η ενημερωμένη αυτή έκδοση του κατά Dolev-Yao επιτιθέμενου δημιουργεί ένα τυπικό (formal) περιβάλλον, στο οποίο μπορούν να εκφραστούν αδυναμίες διασύνδεσης των πρωτοκόλλων. 8. Τα παραπάνω μπορούν να αποτελέσουν τη βάση για τη χρήση της γλώσσας Jif με τέτοιο τρόπο, ώστε οι αδυναμίες στην υλοποίηση πρωτοκόλλων ασφαλείας όσον αφορά τη συνδεσιμότητα να μπορούν να ανιχνευτούν με ένα συνδυασμό στατικών και δυναμικών ελέγχων. 9. Η συνδεσιμότητα δεν είναι δυνατό να ελεγχθεί στατικά στη γενική περίπτωση, αλλά μπορεί να ελέγχεται δυναμικά κατά την εκτέλεση των πρωτοκόλλων. 10. Οι κανόνες της Typed MSR με τους οποίους παράγονται τα καινούρια μηνύματα τα οποία μπορεί να σχηματίσει ο κατά Dolev-Yao επιτιθέμενος από ένα σύνολο γνωστών μηνυμάτων χωρίζονται σε δύο κατηγορίες, ανάλογα με το αν χρησιμοποιούνται στη φάση αποδόμησης των γνωστών μηνυμάτων ή στη φάση κατασκευής των καινούριων. Συγκεκριμένα μηνύματα που βασίζονται στην κρυπτογραφία της διατριβής αυτής δεν μπορούν όμως να χωριστούν σε μία από τις δύο κατηγορίες, καθώς είναι ωφέλιμη η χρήση τους και στις δύο αυτές φάσεις.