Fine-Grained Cryptography: A New Frontier?

Gina Bari Kolata

Daniel Apon

In this dissertation, we explore the frontiers of theory of cryptography along two lines. In the first direction, we explore Lattice Cryptography, which is the primary sub-area of post-quantum cryptographic research. Our first contribution is the construction of a deniable attribute-based encryption scheme from lattices. A deniable encryption scheme is secure against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. An attribute-based encryption scheme allows ``fine-grained'' access to ciphertexts, allowing for a decryption access policy to be embedded in ciphertexts and keys. We achieve both properties simultaneously for the first time from lattices. Our second contribution is the construction of a digital signature scheme that enjoys both short signatures and a completely tight security reduction from lattices. As a matter of independent interest, we give an improved method of randomized inversion of the G gadget matrix, which reduces the noise growth rate in homomorphic evaluations performed in a large number of lattice-based cryptographic schemes, without incurring the high cost of sampling discrete Gaussians. In the second direction, we explore Cryptographic Program Obfuscation. A program obfuscator is a type of cryptographic software compiler that outputs executable code with the guarantee that ``whatever can be hidden about the internal workings of program code, is hidden.'' Indeed, program obfuscation can be viewed as a ``universal and cryptographically-complete'' tool. Our third contribution is the first, full-scale implementation of secure program obfuscation in software. Our toolchain takes code written in a C-like programming language, specialized for cryptography, and produces secure, obfuscated software. Our fourth contribution is a new cryptanalytic attack against a variety of ``early'' program obfuscation candidates. We provide a general, efficiently-testable property for any two branching programs, called partial inequivalence, which we show is sufficient for launching an ``annihilation attack'' against several obfuscation candidates based on Garg-Gentry-Halevi multilinear maps.

Yuxing Chen, Hangxuan Cui, Jun Ting Lin +1 more

This brief presents a novel class of hard-decision algorithms for decoding low density parity check codes. The new algorithms, named fine-grained bit-flipping (FBF) algorithms, employ a detailed classification of each bit, by introducing the XOR value of its estimated and received value as a subdividing criterion. The fine-grained classification allows the algorithms to strengthen the information utilization during each iteration. Simulation results show that the FBF algorithms can achieve up to 5 times better decoding performance than the state-of-the-art bit-flipping algorithms over the binary symmetric channel. Additionally, a well-optimized hardware architecture is developed for implementing FBF algorithms. Compared to other decoders, implementation results demonstrate that the FBF decoders achieve higher throughput and area efficiency.

Dongsheng Wang

Regarding the strange properties of quantum entropy and entanglement, e.g., the negative quantum conditional entropy, we revisited the foundations of quantum entropy, namely, von Neumann entropy, and raised the new method of quantum fine-grained entropy. With the applications in entanglement theory, quantum information processing, and quantum thermodynamics, we demonstrated the capability of quantum fine-grained entropy to resolve some notable confusions and problems, including the measure of entanglement and quantumness, the additivity conjecture of entanglement of formation etc, and the definition of temperature for single quantum system.

Joe Kilian