In security proofs of cryptographic schemes, various kinds of assumptions have been used.Among those assumptions, the hardness of the factoring problem, called the factoring assumption, is one of the most reliable assumptions.In this dissertation, we study constructions of factoring-based cryptographic schemes.First we study a cryptographic primitive called a self-bilinear map.We define a relaxed version of a self-bilinear map, which we call a self-bilinear maps with auxiliary information (AI-SBM).We construct an AI-SBM based on the factoring assumption and the existence of indistinguishability obfuscation (iO).We also show that AI-SBM can be used for constructing cryptographic schemes including multiparty key exchange, broadcast encryption, attribute-based encryption and homomorphic signatures.As a side result, we construct a somewhat homomorphic encryption for NC 1 circuits based on the Φ-hiding assumption and the existence of iO.Second we study a cryptographic primitive called lossy trapdoor function (LTDF).We define a relaxed version of an LTDF which we call an adversary-dependent lossy trapdoor functions (ad-LTDF).Then we show that in many applications of LTDFs, we can replace LTDFs with ad-LTDFs.Moreover, we give a construction of ad-LTDFs based on the factoring assumption w.r.t.semi-smooth RSA subgroup moduli (SS moduli), which is a special type of RSA moduli introduced by Groth.As a result, we almost automatically obtain new constructions of a collision resistant hash function, CPA secure PKE scheme and DPKE scheme based on the same assumption.Especially, our DPKE scheme is the first scheme that satisfies the security notion called the PRIV security for block sources proposed by Boldyreva et al. solely based on the factoring assumption.Besides direct applications of ad-LTDFs, we construct a CCA secure PKE scheme based on the factoring assumption w.r.t.SS moduli whose ciphertext overhead is the shortest among schemes based on the same assumption.
In security proofs of cryptographic schemes, various kinds of assumptions have been used.Among those assumptions, the hardness of the factoring problem, called the factoring assumption, is one of the most reliable assumptions.In this dissertation, we study constructions of factoring-based cryptographic schemes.First we study a cryptographic primitive called a self-bilinear map.We define a relaxed version of a self-bilinear map, which we call a self-bilinear maps with auxiliary information (AI-SBM).We construct an AI-SBM based on the factoring assumption and the existence of indistinguishability obfuscation (iO).We also show that AI-SBM can be used for constructing cryptographic schemes including multiparty key exchange, broadcast encryption, attribute-based encryption and homomorphic signatures.As a side result, we construct a somewhat homomorphic encryption for NC 1 circuits based on the Φ-hiding assumption and the existence of iO.Second we study a cryptographic primitive called lossy trapdoor function (LTDF).We define a relaxed version of an LTDF which we call an adversary-dependent lossy trapdoor functions (ad-LTDF).Then we show that in many applications of LTDFs, we can replace LTDFs with ad-LTDFs.Moreover, we give a construction of ad-LTDFs based on the factoring assumption w.r.t.semi-smooth RSA subgroup moduli (SS moduli), which is a special type of RSA moduli introduced by Groth.As a result, we almost automatically obtain new constructions of a collision resistant hash function, CPA secure PKE scheme and DPKE scheme based on the same assumption.Especially, our DPKE scheme is the first scheme that satisfies the security notion called the PRIV security for block sources proposed by Boldyreva et al. solely based on the factoring assumption.Besides direct applications of ad-LTDFs, we construct a CCA secure PKE scheme based on the factoring assumption w.r.t.SS moduli whose ciphertext overhead is the shortest among schemes based on the same assumption.
We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and we use it to develop new approaches for constructing several important cryptographic tools, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box. We realize lossy TDFs based on a variety of cryptographic assumptions, including the hardness of the decisional Diffie–Hellman (DDH) problem and the hardness of the “learning with errors” problem (which is implied by the worst-case hardness of various lattice problems). Taken together, our results resolve some long-standing open problems in cryptography. They give the first injective TDFs based on problems not directly related to integer factorization and provide the first chosen ciphertext-secure cryptosystem based solely on worst-case complexity assumptions.
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.
Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a “central hub” for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. However, constructions based on indistinguishability obfuscation almost always rely on non-black-box techniques, and thus the extent to which it can be used as a building block has been completely unexplored so far. We present a framework for proving meaningful negative results on the power of indistinguishability obfuscation. By considering indistinguishability obfuscation for oracle-aided circuits, we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters [A. Sahai and B. Waters, How to use indistinguishability obfuscation: Deniable encryption, and more, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 475--484] and its variants, as well as subexponential security assumptions. Within our framework we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows: (1) There is no fully black-box construction of a collision-resistant function family from an indistinguishability obfuscator for oracle-aided circuits. (2) There is no fully black-box construction of a key-agreement protocol with perfect completeness from a private-key functional encryption scheme for oracle-aided circuits. Specifically, we prove that any such potential constructions must suffer from an exponential security loss, and thus our results cannot be circumvented using subexponential security assumptions. Our framework captures constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme itself is used in a black-box manner.
Digital signatures and key exchange protocols are the two most important public key cryptographic primitives used in the electronic transmission of data. The goal of key exchange is to preserve the secrecy of the communication, while the goal of digital signatures is to guarantee the authenticity of the exchanged messages. Constructions of digital signature schemes based on classical mathematical assumptions appeared shortly following the invention of public key cryptography in the late 1970s. And just like with key exchange, the most efficient variants are based on number-theoretic problems that are believed to be (sub)-exponentially hard for classical machines, but are solved in polynomial time by Shor’s algorithm on a powerful-enough quantum computer. Also, like for key exchange, the most efficient constructions that we believe to be quantum safe are based on the presumed hardness of lattice problems over polynomial rings. One interesting difference between key exchange and digital signatures is that key exchange appears to inherently require that some mathematical problem be computationally hard. Digital signatures, on the other hand, can be generically constructed from any one-way function [1,2]. So even though they certainly fall into the category of public key primitives based on their usage, their existence requires much weaker assumptions. Additionally, the transformation from a one-way function to a digital signature is not too inefficient. For example, the total parameter size (public key + signature) of the SPHINCS+ scheme [3] is around 40 kB. While these sizes are larger, and signing times considerably longer, than those of signatures based on factoring or discrete log, it is still a usable scheme for many applications. And being only based on symmetric assumptions (e.g. one wayness and collision resistance of cryptographic hash functions), its security is very attractive. In order to be considered an interesting alternative to the above-mentioned signature, a scheme based on a mathematical assumption would need to have significant performance advantages. Schemes based on factoring and the discrete logarithm problem were significantly shorter and faster, and so the generic approach lay dormant for over four decades. The new quantum-safe schemes will need to have similar performance advantages if they are to be used in lieu of this safe approach. Below, we describe two techniques for constructing lattice-based digital signatures with output sizes being just a few kilobytes. On a very high level, lattice-based signature constructions follow the two known approaches for constructing classical signatures. In the first approach, the signer outputs a function f and an image y = f(x) as his public key and keeps x as his secret key. To sign a message μ, he gives a non-interactive zero-knowledge proof that he knows an x satisfying y = f(x), using the message μ to create the ‘challenge’ H(μ) for the proof (where H is a public function that maps μ to something ‘random looking’). If the function f is one way then the verifier should be convinced that the proof could have only been created by the entity who knows x. A classic example of this type of scheme is the Schnorr signature scheme [4] based on the hardness of the discrete logarithm problem. The second approach is to create a function f together with a trapdoor f−1, output f as the public key and keep f−1 as the secret key. A message μ is signed by using the secret trapdoor to create a pre-image x such that f(x) = H(μ). Again, if the function f is one way then only someone in possession of a trapdoor should be able to invert it. An example of such a construction based on a ‘factoring-like’ assumption is the RSA signature scheme [5]. The high-level ideas for lattice-based signatures follow the above blueprints, but the technical details are significantly more involved. The main reason for the complications is the different algebraic structure of the hard one-way function underlying lattice cryptography. While the domain of the function in discrete log and RSA-based one-way functions are groups, the domains in lattice-based signatures are sets that are not closed under any operation—in particular, they are elements in a group that have small norms. This crucial small norm requirement precludes us from using uniformly random masking as in Schnorr signatures or having a trapdoor for a bijective one-way function as in RSA signatures. These barriers have, nevertheless, been overcome and the resulting digital signatures are quite practical. In 2017, the US National Institute of Standards and Technology (NIST) began a ‘competition’ for a quantum-safe key exchange and digital signatures standard. At the time of this writing, this process is in the third round and there are two lattice-based signatures remaining—each following one of the above high-level designs. The CRYSTALS-Dilithium [6] scheme follows the Schnorr framework, but adds a crucial rejection-sampling step to keep the size of the coefficients small. The FALCON scheme [7] utilizes a randomized trapdoor sampling technique that uses a secret trapdoor for f−1 to produce random pre-images from a particular distribution. Because there is no longer a bijection, it is crucial to also have the property that the distribution of the outputted pre-images does not leak information about the trapdoor. Both schemes are relatively fast and their parameters (public key + signature size) are the shortest of all quantum-safe signature schemes. While both schemes are based on lattices, they have rather different characteristics. FALCON has very short parameters (see Table 1), but entails a rather complicated procedure for signature generation. In particular, it uses (an optimized version of) the GPV sampler [8], which requires floating-point arithmetic with approximately 64 bits of precision. Requiring such high precision means that subtle implementation errors may not get detected even with rigorous testing. Dilithium, on the other hand, has larger parameters but a very simple implementation where all the sampling in the signing is done in a power-of-2 range; it is thus much less prone to implementation errors. It is quite possible that in the future both schemes will be used for different applications. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Conflict of interest statement. None declared.
Abstract. Key establishment protocols based on hardness assumptions, such as the discrete logarithm problem and the integer factorization problem, are vulnerable to quantum computer attacks, whereas the protocols based on other hardness assumptions, such as the conjugacy search problem and the decomposition search problem, can resist such attacks. The existing protocols based on the hardness assumptions which can resist quantum computer attacks are only passively secure. Compilers are used to convert a passively secure protocol to an actively secure protocol. Compilers involve some tools such as a signature scheme and a collision-resistant hash function. If there are only passively secure protocols but not a signature scheme based on the same assumption, then the application of existing compilers requires the use of such tools based on different assumptions. But the introduction of new tools, based on different assumptions, makes the new actively secure protocol rely on more than one hardness assumption. We offer an approach to derive an actively secure two-party protocol from a passively secure two-party protocol without introducing further hardness assumptions. This serves as a useful formal tool to transform any basic algebraic method of public key cryptography to the real world applicable cryptographic scheme.