Paper 2015/499

Algebraic partitioning: Fully compact and (almost) tightly secure cryptography

Dennis Hofheinz


We describe a new technique for conducting ``partitioning arguments''. Partitioning arguments are a popular way to prove the security of a cryptographic scheme. For instance, to prove the security of a signature scheme, a partitioning argument could divide the set of messages into ``signable'' messages for which a signature can be simulated during the proof, and ``unsignable'' ones for which any signature would allow to solve a computational problem. During the security proof, we would then hope that an adversary only requests signatures for signable messages, and later forges a signature for an unsignable one. 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).

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCC 2016
Partitioning argumentstight security proofsdigital signaturespublic-key encryption
Contact author(s)
Dennis Hofheinz @ kit edu
2015-10-12: revised
2015-05-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dennis Hofheinz},
      title = {Algebraic partitioning: Fully compact and (almost) tightly secure cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2015/499},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.