In this work, we develop a new class of partitioning arguments from simple assumptions. Unlike previous partitioning strategies, ours is based upon an algebraic property of the partitioned elements (e.g., the signed messages), and not on their bit structure. This allows to perform the partitioning efficiently in a ``hidden'' way, such that already a single ``slot'' for a partitioning operation in the scheme can be used to implement many different partitionings sequentially, one after the other. As a consequence, we can construct complex partitionings out of simple basic (but algebraic) partitionings in a very space-efficient way.
As a demonstration of our technique, we provide the first signature and public-key encryption schemes that achieve the following properties simultaneously: they are (almost) tightly secure under a simple assumption, and they are fully compact (in the sense that parameters, keys, and signatures, resp.~ciphertexts only comprise a constant number of group elements).Category / Keywords: public-key cryptography / Partitioning arguments, tight security proofs, digital signatures, public-key encryption Original Publication (in the same form): IACR-TCC-2016 Date: received 26 May 2015, last revised 12 Oct 2015 Contact author: Dennis Hofheinz at kit edu Available format(s): PDF | BibTeX Citation Version: 20151012:150454 (All versions of this report) Short URL: ia.cr/2015/499 Discussion forum: Show discussion | Start new discussion