Efficient cryptographic protocol design based on distributed El gamal encryption

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

36 Scopus citations

Abstract

We propose a set of primitives based on El Gamal encryption that can be used to construct efficient multiparty computation protocols for certain low-complexity functions. In particular, we show how to privately count the number of true Boolean disjunctions of literals and pairwise exclusive disjunctions of literals. Applications include efficient two-party protocols for computing the Hamming distance of two bitstrings and the greater-than function. The resulting protocols only require 6 rounds of interaction (in the random oracle model) and their communication complexity is script O sign(kQ) where k is the length of bit-strings and Q is a security parameter. The protocols are secure against active adversaries but do not provide fairness. Security relies on the decisional Diffie-Hellman assumption and error probability is negligible in Q.

Original languageEnglish
Title of host publicationInformation Security and Cryptology, ICISC 2005 - 8th International Conference, Revised Selected Papers
PublisherSpringer Verlag
Pages32-47
Number of pages16
ISBN (Print)3540333541, 9783540333548
DOIs
StatePublished - 2006
Externally publishedYes
Event8th International Conference on Information Security and Cryptology, ICISC 2005 - Seoul, Korea, Republic of
Duration: 1 Dec 20052 Dec 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3935 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Information Security and Cryptology, ICISC 2005
Country/TerritoryKorea, Republic of
CitySeoul
Period1/12/052/12/05

Fingerprint

Dive into the research topics of 'Efficient cryptographic protocol design based on distributed El gamal encryption'. Together they form a unique fingerprint.

Cite this