An Efficient Scheme for Proving a Shuffle

An Efficient Scheme for Proving a Shuffle. Furukawa, J. & Sako, K. 2001.

In this paper, we propose a novel and efficient protocol for proving the correctness of a shuffle, without leaking how the shuffle was performed. Using this protocol, we can prove the correctness of a shuffle of n data with roughly 18n exponentiations, where as the protocol of Sako-Kilian[SK95] required 642n and that of Abe[Ab99] required 22n log n. The length of proof will be only 211 n bits in our protocol, opposed to 218 n bits and 214 n log n bits required by Sako-Kilian and Abe, respectively. The proposed protocol will be a building block of an efficient, universally verifiable mix-net, whose application to voting system is prominent.

@conference {PShuffle,
	title = {An Efficient Scheme for Proving a Shuffle},
	booktitle = {Proceedings of {CRYPTO} 2001},
	year = {2001},
	publisher = {Springer-Verlag, LNCS 2139},
	organization = {Springer-Verlag, LNCS 2139},
	abstract = {In this paper, we propose a novel and efficient protocol for proving the correctness of a shuffle, without leaking how the shuffle was performed. Using this protocol, we can prove the correctness of a shuffle of n data with roughly 18n exponentiations, where as the protocol of Sako-Kilian[SK95] required 642n and that of Abe[Ab99] required 22n log n. The length of proof will be only 211 n bits in our protocol, opposed to 218 n bits and 214 n log n bits required by Sako-Kilian and Abe, respectively. The proposed protocol will be a building block of an efficient, universally verifiable mix-net, whose application to voting system is prominent.},
	isbn = {978-3-540-42456-7},
	doi = {10.1007/3-540-44647-8},
	url = {http://portal.acm.org/citation.cfm?id=704279},
	author = {Jun Furukawa and Kazue Sako},
	editor = {Joe Kilian}
}

Downloads: 0

{"_id":"JhDKbxXspGbRxnJCy","bibbaseid":"furukawa-sako-anefficientschemeforprovingashuffle-2001","downloads":0,"creationDate":"2018-07-03T04:50:29.696Z","title":"An Efficient Scheme for Proving a Shuffle","author_short":["Furukawa, J.","Sako, K."],"year":2001,"bibtype":"conference","biburl":"https://gnunet.org/bibliography/export/bibtex","bibdata":{"bibtype":"conference","type":"conference","title":"An Efficient Scheme for Proving a Shuffle","booktitle":"Proceedings of CRYPTO 2001","year":"2001","publisher":"Springer-Verlag, LNCS 2139","organization":"Springer-Verlag, LNCS 2139","abstract":"In this paper, we propose a novel and efficient protocol for proving the correctness of a shuffle, without leaking how the shuffle was performed. Using this protocol, we can prove the correctness of a shuffle of n data with roughly 18n exponentiations, where as the protocol of Sako-Kilian[SK95] required 642n and that of Abe[Ab99] required 22n log n. The length of proof will be only 211 n bits in our protocol, opposed to 218 n bits and 214 n log n bits required by Sako-Kilian and Abe, respectively. The proposed protocol will be a building block of an efficient, universally verifiable mix-net, whose application to voting system is prominent.","isbn":"978-3-540-42456-7","doi":"10.1007/3-540-44647-8","url":"http://portal.acm.org/citation.cfm?id=704279","author":[{"firstnames":["Jun"],"propositions":[],"lastnames":["Furukawa"],"suffixes":[]},{"firstnames":["Kazue"],"propositions":[],"lastnames":["Sako"],"suffixes":[]}],"editor":[{"firstnames":["Joe"],"propositions":[],"lastnames":["Kilian"],"suffixes":[]}],"bibtex":"@conference {PShuffle,\n\ttitle = {An Efficient Scheme for Proving a Shuffle},\n\tbooktitle = {Proceedings of {CRYPTO} 2001},\n\tyear = {2001},\n\tpublisher = {Springer-Verlag, LNCS 2139},\n\torganization = {Springer-Verlag, LNCS 2139},\n\tabstract = {In this paper, we propose a novel and efficient protocol for proving the correctness of a shuffle, without leaking how the shuffle was performed. Using this protocol, we can prove the correctness of a shuffle of n data with roughly 18n exponentiations, where as the protocol of Sako-Kilian[SK95] required 642n and that of Abe[Ab99] required 22n log n. The length of proof will be only 211 n bits in our protocol, opposed to 218 n bits and 214 n log n bits required by Sako-Kilian and Abe, respectively. The proposed protocol will be a building block of an efficient, universally verifiable mix-net, whose application to voting system is prominent.},\n\tisbn = {978-3-540-42456-7},\n\tdoi = {10.1007/3-540-44647-8},\n\turl = {http://portal.acm.org/citation.cfm?id=704279},\n\tauthor = {Jun Furukawa and Kazue Sako},\n\teditor = {Joe Kilian}\n}\n","author_short":["Furukawa, J.","Sako, K."],"editor_short":["Kilian, J."],"key":"PShuffle","id":"PShuffle","bibbaseid":"furukawa-sako-anefficientschemeforprovingashuffle-2001","role":"author","urls":{"Paper":"http://portal.acm.org/citation.cfm?id=704279"},"downloads":0},"search_terms":["efficient","scheme","proving","shuffle","furukawa","sako"],"keywords":[],"authorIDs":[],"dataSources":["FWsPTwsmjtrBtRS3B"]}