Research

Our current projects focus on developing (provably secure) cryptographic systems for privacy, accountability, and trust.

Project Topics.


Anonymous Communication Protocols and Analysis

The onion routing (OR) network Tor is undoubtedly the most widely employed technology for anonymous web access. It however still lacks efficiency, and requires a few seconds to answer a simple http request. We observed that identity-based cryptography (IBC) can mitigate the scalability and efficiency challenges with the existing Tor protocol, and designed two pairing-based onion routing (PB-OR) circuit constructions in an identity-based setting. [4,5,6]

Further, a comprehensive analysis of OR protocol security guarantees is lacking. This has resulted in a significant gap between research work on OR protocols and existing OR anonymity analyses. In a recent work, we are addressing both issues with onion routing by defining a provably secure OR protocol in the universal composability (UC) framework. [2,3] While our OR protocol is practical for deployment in the next generation Tor network, our UC definition greatly simplifies the process of analyzing OR anonymity metrics. In ongoing efforts, we are defining a framework motivated from differential privacy for analyzing anonymous communication protocols [1].

The field of anonymous web browsing is still full of open problems. Tor does not provide any accountability guarantee, and it is employed to safeguard network addresses during criminal activities. This presents an interesting cryptographic and systems challenge of defining an accountable OR protocol that makes anonymous users accountable for their behavior. Moreover, the existing node discovery mechanism in Tor is not considered scalable enough for tomorrow's anonymous traffic and a scalable solution will be required in the future. We look forward tackling some of these issues.

  1. AnoA: A Framework For Analyzing Anonymous Communication Protocols.
    Michael Backes, Aniket Kate, Praveen Manoharan, Esfandiar Mohammadi, and Sebastian Meiser. To appear at IEEE CSF 2013 (June 2013) and HotPETS 2013 (July 2013).
    Available as a techreport , August 2012.
  2. An Efficient Key-Exchange Protocol for Onion Routing.
    Michael Backes, Aniket Kate, and Esfandiar Mohammadi. ACM WPES 2012, October 2012.
    Available as a techreport , August 2012.
  3. Provably Secure and Practical Onion Routing.
    Michael Backes, Ian Goldberg, Aniket Kate, and Esfandiar Mohammadi. IEEE CSF 2012, June 2012.
    Available as Cryptology ePrint Archive: Report 2011/308, June 2011.
  4. Pairing-Based Onion Routing with Improved Forward Secrecy.
    Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. ACM TISSec Vol. 13 Iss. 4 (29), December 2010.
    Also available as Cryptology ePrint Archive, Report 2008/080. (slightly older version)
  5. Using Sphinx to Improve Onion Routing Circuit Construction (Extended Abstract).
    Aniket Kate and Ian Goldberg. FC 2010, January 2010.
    The full version is available as CACR Technical Report (CACR 2009-33).
  6. Pairing-Based Onion Routing.
    Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. PETS 2007, June 2007.
    An extended version available as CACR Technical Report (CACR 2007-08).

Privacy with Accountability in the Emerging Scenarios

Privacy Preserving Advertising
Online behavioral advertising (OBA) involves the tracking of web users' activities in order to deliver tailored advertisements. OBA is typically conducted by third-party data analytics firms (brokers), which track user behaviors across web-sessions using mechanisms such as persistent cookies. This practice raises significant privacy concerns among users and privacy advocates alike.

We recently proposed ObliviAd, a provably secure architecture for privacy preserving OBA. [1] The distinguishing features of our approach are the usage of secure hardware-based private information retrieval (PIR) for distributing advertisements and high-latency mixing of electronic tokens for billing advertisers without disclosing any information about user profiles to brokers. ObliviAd does not assume any trusted party and provides brokers an economical alternative that preserves the privacy of users without hampering the precision of ads selection.

Anonymity in Delay-Tolerant Networks

In 2007, we developed an anonymous key agreement scheme in an identity-based infrastructure and used that to propose the first secure anonymous communication system for delay-tolerant networks (DTNs) [4]. Our system achieves privacy along with confidentiality and integrity for communication over these ad-hoc networks under minimal trust assumptions.

  1. ObliviAd: Provably Secure and Practical Online Behavioral Advertising
    Michael Backes, Aniket Kate, Matteo Maffei, and Kim Pecina. 33rd IEEE Symposium on Security & Privacy (Oakland 2012), May 2012.
  2. Adding Query Privacy to Robust DHTs
    Michael Backes, Ian Goldberg, Aniket Kate, and Tomas Toft. ACM ASIACCS 2012, May 2012.
    Also available as CoRR arXiv:1107.1072v2, April 2012.
  3. Generalizing Cryptosystems Based on the Subset Sum Problem
    Aniket Kate and Ian Goldberg. International Journal of Information Security (IJIS) Vol. 10 (3), Pages 189-199, May 2011.
    Also available as CACR Technical Report (CACR 2007-26) (.pdf).
  4. Anonymity and Security in Delay Tolerant Networks
    Aniket Kate, Gregory M. Zaverucha, and Urs Hengartner. SecureComm 2007, Sept 2007.
    Also available as CACR Technical Report (CACR 2007-12).

Distributed Trust

A trusted authority, in some form, is essential for many secure systems. However, this requirement always leads to the liveness-related issue of single point of failure and sometimes to the more undesirable security issue of key escrow. Resolving these two issues is of paramount importance while designing secure systems for use over the Internet where denial-of-service attacks and malicious entities are widespread. Although distributed cryptography has emerged as a natural choice to mitigate these problems, the cryptography literature largely has failed to provide protocols suitable for the Internet. Namely, the aspects related to the practicality of these protocols have been largely ignored and usable implementations for most of the distributed cryptographic primitives are not yet available.

Distributed key generation (DKG) is a fundamental building block of distributed cryptography and distributed trust. We have designed, implemented and analyzed a practical DKG protocol for use over the Internet [1,3,6]. See our DKG webpage for more details. In continued work, we have also presented its applications towards a few cryptographic and distributed systems scenarios:

  • Identity-Based Cryptography [4],
  • Distributed Hash Tables (DHTs) [2,5], and
  • Pairing-Based Onion Routing [7].
  1. Distributed Key Generation in the Wild
    Aniket Kate, Yizhou Huang and Ian Goldberg. Under Submission.
    Available as Cryptology ePrint Archive: Report 2012/377, June 2012.
  2. Towards Practical Communication in Byzantine-Resistant DHTs
    Maxwell Young, Aniket Kate, Ian Goldberg, and Martin Karsten. IEEE/ACM ToN 21(1): 190-203, March 2012.
    Local copy [PDF]
  3. Distributed Key Generation and Its Applications
    Aniket Pundlik Kate. PhD Thesis, University of Waterloo, June 2010.
    [Thesis page]
  4. Distributed Private-Key Generators for Identity-Based Cryptography
    Aniket Kate and Ian Goldberg. SCN 2010, September 2010.
    An extended version is available as Cryptology ePrint Archive, Report 2009/355.
  5. Practical Robust Communication in DHTs Tolerating a Byzantine Adversary
    Maxwell Young, Aniket Kate, Ian Goldberg and Martin Karsten. IEEE ICDCS 2010, June 2010.
    An extended version is available as CACR Technical Report (CACR 2009-31).
  6. Distributed Key Generation for the Internet
    Aniket Kate and Ian Goldberg. IEEE ICDCS 2009, June 2009.
    An extended version is as CACR Technical Report (CACR 2008-25).
  7. Pairing-Based Onion Routing.
    Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. PETS 2007, June 2007.
    An extended version available as CACR Technical Report (CACR 2007-08).

Minimal Trusted Hardware

A broad trusted hardware assumption can solve almost all security problems in a trivial and uninteresting manner. However, relying entirely on hardware assumptions to achieve security goals of a system (a) can be impractical given the limited memory, bandwidth and CPU capabilities of available hardware modules, and (b) makes the designed system vulnerable to even a tiny overlooked or undiscovered flaw/side-channel of the employed module. Thus, the key challenge while designing a trusted hardware-based system is to determine a minimal hardware assumption required to achieve the system's goals, and justify the assumption for an available hardware module.

Using a minimal trusted hardware such a trusted counter (TrInc), we have broken the well-known resiliency (or replication) lower-bounds for multiparty computation (MPC) and distributed computing primitives [2,3]. We are currently designing efficient MPC and distributed computing protocols for the same, and implementing those using the prevalent TPM standard. Our ObliviAd architecture for privacy preserving advertising also presents an interesting example of minimal trusted hardware, where the PIR problem is solved using the confidentiality (but not storage) assumption on the hardware.

  1. ObliviAd: Provably Secure and Practical Online Behavioral Advertising
    Michael Backes, Aniket Kate, Matteo Maffei, and Kim Pecina. 33rd IEEE Symposium on Security & Privacy (Oakland 2012), May 2012.
  2. On the (Limited) Power of Non-Equivocation.
    Allen Clement, Flavio Junqueira, Aniket Kate, and Rodrigo Rodrigues. ACM PODC 2012, July 2012.
  3. Brief Announcement: Distributed Cryptography using TrInc
    Michael Backes, Fabian Bendun, and Aniket Kate. ACM PODC 2012, July 2012.

Computational Verifiable Secret Sharing (VSS)

Non-homomorphic Commitments
In the computational complexity setting, the feasibility of VSS schemes based on commitments was established over two decades ago. However, all known computational VSS schemes relied on the homomorphic nature of these commitments or achieve weaker guarantees. As homomorphism is not inherent to commitments or to the computational setting in general, a closer look at its utility to VSS was called for. We have demonstrated that homomorphism of commitments is not a necessity for computational VSS in the synchronous or in the asynchronous communication setting [2].

VSS Round Complexity
In the same work [2], we also analyzed a crucial interactive complexity measure of round complexity for computational VSS in the synchronous setting. Most interestingly, our efforts resulted in a new two-round VSS scheme using homomorphic commitments that has the same communication complexity as the well-known three-round Feldman and Pedersen VSS schemes.

Polynomial Commitments
A polynomial commitment scheme allows a committer to commit to a polynomial with a short string that can be used by a verifier to confirm claimed evaluations of the committed polynomial. We introduced and formally defined polynomial commitment schemes, and provide two efficient constructions [3]. Although the commitment schemes such as discrete logarithm commitments or Pedersen commitments used in the VSS literature achieve this goal, the sizes of their commitments are linear in the degree of the committed polynomial. On the other hand, polynomial commitments in our schemes are of constant size (single elements), and the overhead of opening a commitment is also constant. Therefore, our schemes are useful tools to reduce the communication cost in VSS [1, 3]. The schemes have also been used in other verification primitives such as zero knowledge (ZK) sets.

  1. Asynchronous Verifiable Secret Sharing with Optimal Communication Complexity
    Michael Backes, Amit Datta, and Aniket Kate. CT-RSA 2013, February 2013.
    Available as Cryptology ePrint Archive: Report 2012/619, November 2012.
  2. Computational Verifiable Secret Sharing Revisited
    Michael Backes, Aniket Kate and Arpita Patra. ASIACRYPT 2011, December 2011.
    Available as Cryptology ePrint Archive: Report 2011/281, May 2011.
  3. Constant-Size Commitments to Polynomials and Their Applications
    Aniket Kate, Gregory M. Zaverucha and Ian Goldberg. ASIACRYPT 2010, December 2010.
    An extended version is available as CACR Technical Report (CACR 2010-10) (.pdf).
A detailed research report for our work on distributed cryptography is available