Aarhus University Seal

Sub-linear, Secure Comparison With Two Non-Colluding Parties

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Tomas Toft, Denmark
  • Department of Computer Science
The classic problem in the field of secure computation is
Yao’s millionaires’ problem; we consider two new protocols solving a
variation of this: a number of parties, P1, . . . , Pn, securely hold two -
bit values, x and y – e.g. x and y could be encrypted or secret shared.
They wish to obtain a bit stating whether x is greater than y using only
secure arithmetic; this should be done without revealing any information,
even the output should remain secret. The present setting is special in
the sense that it is assumed that two specific parties, referred to as
Alice and Bob, are non-colluding. Though this assumption is not satisfied
in general, it clearly is for the main example of this work: two-party
computation based on Paillier encryption.
The first solution requires O(log()(κ + loglog())) secure arithmetic
operations in O(log()) rounds, where κ is a correctness parameter. The
second solution requires only a constant number of rounds, but increases
complexity to O(√(κ + log())) arithmetic operations.
For the motivating setting, each arithmetic operation requires a constant
number of Paillier encryptions to be exchanged between Alice and
Bob. This implies that both solutions require only a sub-linear number
of invocations (in the bit-length, ) of the cryptographic primitives. This
does not imply sub-linear communication, though,
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)174-191
Number of pages18
Publication statusPublished - 2011
EventPublic Key Cryptography -
Duration: 17 Dec 2010 → …


ConferencePublic Key Cryptography
Period17/12/2010 → …

Bibliographical note

Title of the vol.: Public Key Cryptography - PKC 2011. Proceedings / Dario Catalano, Nelly Fazio, Rosario Gennaro and Antonio Nicolosi (eds.)
ISBN: 978-3-642-19378-1

See relations at Aarhus University Citationformats

ID: 40342593