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

Dennis Hofheinz

##### Abstract

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)
Category
Public-key cryptography
Publication info
Keywords
Partitioning argumentstight security proofsdigital signaturespublic-key encryption
Contact author(s)
Dennis Hofheinz @ kit edu
History
2015-10-12: revised
See all versions
Short URL
https://ia.cr/2015/499

CC BY

BibTeX

@misc{cryptoeprint:2015/499,
author = {Dennis Hofheinz},
title = {Algebraic partitioning: Fully compact and (almost) tightly secure cryptography},
howpublished = {Cryptology ePrint Archive, Paper 2015/499},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/499}},
url = {https://eprint.iacr.org/2015/499}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.