International Association for Cryptologic Research

International Association
for Cryptologic Research


Kamil Kluczniak


Lockable Obfuscation from Circularly Insecure Fully Homomorphic Encryption 📺
Kamil Kluczniak
In a lockable obfuscation scheme, a party called the obfuscator takes as input a circuit C, a lock value y and, a message m, and outputs an obfuscated circuit. Given the obfuscated circuit, an evaluator can run it on an input x and learn the message if C(x) = y. For security, we require that the obfuscation reveals no information on the circuit as long as the lock y has high entropy even given the circuit C. The only known constructions of lockable obfuscation schemes require indistinguishability obfuscation (iO) or the learning with errors (LWE) assumption. Furthermore, in terms of technique, all known constructions, excluding iO-based, are build from provably secure variations of graph-induced multilinear maps. We show a generic construction of a lockable obfuscation scheme built from a (leveled) fully homomorphic encryption scheme that is circularly insecure. Specifically, we need a fully homomorphic encryption scheme that is secure under chosen-plaintext attack (IND-CPA) but for which there is an efficient cycle tester that can detect encrypted key cycles. Our finding sheds new light on how to construct lockable obfuscation schemes and shows why cycle tester constructions were helpful in the design of lockable obfuscation schemes. One of the many use cases for lockable obfuscation schemes are constructions for IND-CPA secure but circularly insecure encryption schemes. Our work shows that there is a connection in both ways between circular insecure encryption and lockable obfuscation.
Ring Signatures: Logarithmic-Size, No Setup—from Standard Assumptions 📺
Ring signatures allow for creating signatures on behalf of an ad hoc group of signers, hiding the true identity of the signer among the group. A natural goal is to construct a ring signature scheme for which the signature size is short in the number of ring members. Moreover, such a construction should not rely on a trusted setup and be proven secure under falsifiable standard assumptions. Despite many years of research this question is still open.In this paper, we present the first construction of size-optimal ring signatures which do not rely on a trusted setup or the random oracle heuristic. Specifically, our scheme can be instantiated from standard assumptions and the size of signatures grows only logarithmically in the number of ring members.We also extend our techniques to the setting of linkable ring signatures, where signatures created using the same signing key can be linked.
Signatures with Flexible Public Key: Introducing Equivalence Classes for Public Keys
We introduce a new cryptographic primitive called signatures with flexible public key $$(\mathsf{SFPK})$$. We divide the key space into equivalence classes induced by a relation $$\mathcal {R}$$. A signer can efficiently change his or her key pair to a different representatives of the same class, but without a trapdoor it is hard to distinguish if two public keys are related. Our primitive is motivated by structure-preserving signatures on equivalence classes ($$\mathsf{SPS\text {-}EQ}$$), where the partitioning is done on the message space. Therefore, both definitions are complementary and their combination has various applications.We first show how to efficiently construct static group signatures and self-blindable certificates by combining the two primitives. When properly instantiated, the result is a group signature scheme that has a shorter signature size than the current state-of-the-art scheme by Libert, Peters, and Yung from Crypto’15, but is secure in the same setting.In its own right, our primitive has stand-alone applications in the cryptocurrency domain, where it can be seen as a straightforward formalization of so-called stealth addresses. Finally, it can be used to build the first efficient ring signature scheme in the plain model without trusted setup, where signature size depends only sub-linearly on the number of ring members. Thus, we solve an open problem stated by Malavolta and Schröder at ASIACRYPT’2017.