Cryptology ePrint Archive: Report 2015/833
Efficient Key Authentication Service for Secure End-to-end Communications
Mohammad Etemad and Alptekin Küpçü
Abstract: After four decades of public key cryptography, both the industry and academia seek better solutions for the public key infrastructure. A recent proposal, the certificate transparency concept, tries to enable untrusted servers act as public key servers, such that any key owner can verify that her key is kept properly at those servers. Unfortunately, due to high computation and communication requirements, existing certificate transparency proposals fail to address the problem as a whole.
We propose a new efficient key authentication service (KAS). It uses server-side gossiping as the source of trust, and assumes servers are not all colluding. KAS stores all keys of each user in a separate hash chain, and always shares the last ring of the chain among the servers, ensuring the users that all servers provide the same view about them (i.e., no equivocation takes place). Storing users keys separately reduces the server and client computation and communication dramatically, making our KAS a very efficient way of public key authentication. The KAS handles a key registration/change operation in O(1) time using only O(1) proof size; independent of the number of users. While the previous best proposal, CONIKS, requires the client to download 100 KB of proof per day, our proposal needs less than 1 KB of proof per key lifetime, while obtaining the same probabilistic guarantees as CONIKS.
Category / Keywords: public-key cryptography / Certificate transparency, End-to-end encryption, Key authentication
Original Publication (with major differences): ProvSec 2015
Date: received 27 Aug 2015
Contact author: metemad at ku edu tr
Available format(s): PDF | BibTeX Citation
Version: 20150828:152731 (All versions of this report)
Short URL: ia.cr/2015/833
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]