Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Some aspects of cryptographic protocols: with applications in electronic voting and digital watermarking
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Cryptographic protocols are widely used on the internet, from relatively simple tasks such as key-agreement and authentication to much more complex problems like digital cash and electronic voting. Electronic voting in particular is a problem we investigate in this thesis.

In a typical election, the main goals are to ensure that the votes are counted correctly and that the voters remain anonymous, i.e. that nobody, not even the election authorities, can trace a particular vote back to the voter. There are several ways to achieve these properties, the most general being a mix-net with a proof of a shuffle to ensure correctness. We propose a new, conceptually simple, proof of a shuffle. We also investigate a mix-net which omits the proof of a shuffle in favor of a faster, heuristically secure verification. We demonstrate that this mix-net is susceptible to both attacks on correctness and anonymity. A version of this mix-net was tested in the 2011 elections in Norway.

We also look at a simple and widely used proof of knowledge of a discrete logarithm in groups of prime order. While the requirement of prime order is well known, we give a precise characterization of what the protocol proves in a group of composite order. Furthermore, we present attacks against a class of protocols of the same form, which shows that the protocol cannot easily be extended to groups where the order is composite or unknown.

We finally look at the problem of music and video piracy. Using a buyer-seller watermark to embed a unique watermark in each sold copy has been proposed as a deterrent since it allows a seller who discovers a pirated copy to extract the watermark and find out which buyer released it. Existing buyer-seller watermarking schemes assume that all copies are downloaded directly from the seller. In practice, however, the seller wants to save bandwidth by allowing a paying customer to download most of the content from other buyers. We introduce this as an interesting open research problem and present a proof-of-concept protocol which allows transfer of content between buyers while keeping the seller's communication proportional to the size of the watermark rather than the size of the content.

Abstract [sv]

Kryptografiska protokoll används i stor omfattning på internet, för att lösa allt från enkla uppgifter som nyckelutbyte och autentisering till komplexa problem som digitala pengar och elektroniska val. I den här avhandlingen är elektroniska val av speciellt intresse.

I ett typiskt valsystem är målen att garantera att rösterna räknas korrekt och att ingen, inte ens valförrättaren, kan spåra en röst tillbaka till den röstande. Det finns flera metoder för att åstadkomma detta, men den mest generella är mixnät med ett så kallat ``proof of a shuffle'' för att garantera korrekthet. Vi föreslår i avhandlingen ett nytt, konceptuellt enkelt, ``proof of a shuffle''. Vi undersöker också ett mixnät som använder ett snabbt heuristiskt argument för korrekthet istället för ett ``proof of a shuffle''. Vi demonstrerar att både korrekthet och anonymitet kan angripas i det mixnätet. En version av samma mixnät användes i valet 2011 i Norge.

Vi undersöker också ett enkelt bevis av kunskap om en diskret logaritm i en grupp. Det är sedan länge välkänt att just det protokollet kräver att gruppen har primtalsordning, men vi ger en karaktärisering av vad som händer i en grupp av sammansatt ordning. Vidare presenterar vi attacker mot en klass av protokoll med samma struktur, vilket visar att protokollet inte enkelt kan utvidgas till grupper av okänd eller sammansatt ordning.

Slutligen studerar vi problemet med piratkopiering av film och musik. Det har föreslagits att vattenmärkning kan användas för att bädda in ett unikt vattenmärke i varje såld kopia. En säljare som upptäcker en piratkopia kan extrahera vattenmärket och därmed avslöja vilken köpare som läckte kopian. Existerande vattenmärkningssystem förutsätter att alla kopior laddas ner direkt från säljaren, men i praktiken vill säljaren ofta reducera mängden datatrafik genom att låta en ny betalande kund ladda ner kopian från tidigare köpare. Vi introducerar detta som ett intressant öppet problem och presenterar ett protokoll som tillåter överföring av data mellan köpare och som bara kräver att säljaren kommunicerar data proportionellt mot storleken på vattenmärket istället för mot storleken på filen.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2015. , ix, 67 p.
Series
TRITA-CSC-A, ISSN 1653-5723 ; 2015:08
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-165436ISBN: 978-91-7595-545-2 (print)OAI: oai:DiVA.org:kth-165436DiVA: diva2:808396
Public defence
2015-05-22, Kollegiesalen, Valhallavägen 79, KTH, STOCKHOLM, 14:00 (English)
Opponent
Supervisors
Note

QC 20150428

Available from: 2015-04-28 Created: 2015-04-28 Last updated: 2015-04-28Bibliographically approved
List of papers
1. Efficiency limitations of Σ-protocols for group homomorphisms revisited
Open this publication in new window or tab >>Efficiency limitations of Σ-protocols for group homomorphisms revisited
2012 (English)In: Security and Cryptography for Networks, Springer Berlin/Heidelberg, 2012, 461-476 p.Conference paper, Published paper (Refereed)
Abstract [en]

We study the problem of constructing efficient proofs of knowledge of preimages of general group homomorphisms. We simplify and extend the recent negative results of Bangerter et al. (TCC 2010) to constant round (from three-message) generic protocols over concrete (instead of generic) groups, i.e., we prove lower bounds on both the soundness error and the knowledge error of such protocols. We also give a precise characterization of what can be extracted from the prover in the direct (common) generalization of the Guillou-Quisquater and Schnorr protocols to the setting of general group homomorphisms. Then we consider some settings in which these bounds can be circumvented. For groups with no subgroups of small order we present: (1) a three-move honest verifier zero-knowledge argument under some set-up assumptions and the standard discrete logarithm assumption, and (2) a Σ-proof of both the order of the group and the preimage. The former may be viewed as an offline/online protocol, where all slow cut-andchoose protocols can be moved to an offline phase.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2012
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7485 LNCS
Keyword
Discrete logarithms, Efficiency limitations, Lower bounds, Offline, Preimages, Zero knowledge, Cryptography, Algebra
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-105313 (URN)10.1007/978-3-642-32928-9_26 (DOI)2-s2.0-84866706029 (Scopus ID)978-364232927-2 (ISBN)
Conference
8th International Conference on Security and Cryptography for Networks, SCN 2012, 5 September 2012 through 7 September 2012, Amalfi
Funder
ICT - The Next Generation
Note

QC 20121120

Available from: 2012-11-20 Created: 2012-11-20 Last updated: 2015-04-28Bibliographically approved
2. Proofs of Restricted Shuffles
Open this publication in new window or tab >>Proofs of Restricted Shuffles
2010 (English)In: PROGRESS IN CRYPTOLOGY - AFRICACRYPT 2010 / [ed] Bernstein DJ; Lange T, 2010, Vol. 6055, 100-113 p.Conference paper, Published paper (Refereed)
Abstract [en]

A proof of a shuffle is a zero-knowledge proof that one list of ciphertexts is a permutation and re-encryption of another list of ciphertexts. We call a shuffle restricted if the permutation is chosen from a public subset of all permutations. In this paper, we introduce a general technique for constructing proofs of shuffles which restrict the permutation to a group that is characterized by a public polynomial. This generalizes previous work by Reiter and Wang [22], and de Hoogh et al. [7]. Our approach also gives a new efficient proof of an unrestricted shuffle that we think is conceptually simpler and allow a simpler analysis than all previous proofs of shuffles.

Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6055
Keyword
cryptographic protocols, election schemes, mix-nets, proof of a shuffle
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-29680 (URN)000279247600007 ()2-s2.0-77953515197 (Scopus ID)978-3-642-12677-2 (ISBN)
Conference
3rd International Conference on Cryptology in Africa
Note
QC 20110218Available from: 2011-02-18 Created: 2011-02-11 Last updated: 2015-04-28Bibliographically approved
3. Cryptanalysis of a Universally Verifiable Efficient Re-encryption Mixnet
Open this publication in new window or tab >>Cryptanalysis of a Universally Verifiable Efficient Re-encryption Mixnet
2012 (English)Manuscript (preprint) (Other academic)
Abstract [en]

We study the heuristically secure mix-net proposed by Puiggal´ı and Guasch (EVOTE2010). We present practical attacks on both correctness and privacy for some sets of parametersof the scheme. Although our attacks only allow us to replace a few inputs, or tobreak the privacy of a few voters, this shows that the scheme can not be proven secure.

National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-112831 (URN)
Note

QC 20130220

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2017-04-04Bibliographically approved
4. Towards transferable watermarks in buyer-seller watermarking protocols
Open this publication in new window or tab >>Towards transferable watermarks in buyer-seller watermarking protocols
2013 (English)In: Proceedings of the 2013 IEEE International Workshop on Information Forensics and Security, WIFS 2013, IEEE conference proceedings, 2013, 197-202 p.Conference paper, Published paper (Refereed)
Abstract [en]

Buyer-seller watermarking protocols are protocols that let a seller embed a watermark which uniquely identifies the buyer of each sold copy of some work without allowing the seller to learn the watermark. The purpose of such protocols is to deter buyers from illegally redistributing the work while protecting the buyer from being framed by dishonest sellers. Existing buyer-seller watermarking schemes require that every buyer receives his or her copy directly from the seller. We consider the problem of extending buyer-seller watermarking to allow (controlled) redistribution between buyers while maintaining a watermark that uniquely identifies each recipient. An efficient and secure protocol of this type could allow distribution of digital content in peer-to-peer networks while protecting the owner's copyright. We give a proof-of-concept protocol which only requires limited interaction with the original seller to change the watermark.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2013
National Category
Other Computer and Information Science
Identifiers
urn:nbn:se:kth:diva-147493 (URN)10.1109/WIFS.2013.6707818 (DOI)000346136700034 ()2-s2.0-84894129214 (Scopus ID)978-146735593-3 (ISBN)
Conference
2013 5th IEEE International Workshop on Information Forensics and Security, WIFS 2013, 18 November 2013 through 21 November 2013, Guangzhou, China
Note

QC 20140627

Available from: 2014-06-27 Created: 2014-06-27 Last updated: 2015-12-03Bibliographically approved

Open Access in DiVA

Thesis(1735 kB)225 downloads
File information
File name FULLTEXT01.pdfFile size 1735 kBChecksum SHA-512
21a613b9195ba8947835effb58a9bca944ef08302d434deb34e7d949c86e7cf717fc4467c2c9eea113e0c3f33996b91564350198955ab2b67af9d1cefc1c3fec
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Terelius, Björn
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 225 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 476 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf