Abstract Almost cryptographic protocols are presented with security arguments. None of them, however, did explain why a protocol should like this, not like that. The reason is that there are short of any principles for designing and analyzing cryptographic protocols. In this paper, we put forth such a principle beyond security, called Less Parameters, which says that the involved parameters should be reduced as less as possible. Actually, the principle ensures a protocol better cost. In different scenarios, the principle is not easy to grasp. Intuitively, we advise to introduce public parameters as less as possible. In the light of the principle, we investigate some signatures. We believe the techniques developed in this paper will be helpful to better some cryptographic protocols.
The design of secure protocols that implement arbitrarily desired functionalities is a major part of modern cryptography. Taking the opposite perspective, the design of any cryptographic scheme may be viewed as the design of a secure protocol for implementing a suitable functionality. Still, we believe that it makes sense to differentiate between basic cryptographic primitives (which involve little interaction) like encryption and signature schemes, on the one hand, and general cryptographic protocols, on the other hand. In this chapter we consider general results concerning secure multi –party computations, where the two –party case is an important special case. In a nutshell, these results assert that one can construct protocols for securely computing any desirable multi–party functionality (see the following terminology). Indeed, what is striking about these results is their generality, and we believe that the wonder is not diminished by the (various alternative) conditions under which these results hold. Our focus on the general study of secure multi–party computation (rather than on protocols for solving specific problems) is natural in the context of the theoretical treatment of the subject matter. We wish to highlight the importance of this general study to practice. Firstly, this study clarifies fundamental issues regarding security in a multi–party environment. Secondly, it draws the lines between what is possible in principle and what is not. Thirdly, it develops general techniques for designing secure protocols. And last, sometimes it may even yield schemes (or modules) that may be incorporated in practical systems.
In this work, we investigate the security of interactive computations. The main emphasis is on the mathematical methodology that is needed to formalise and analyse various security properties. Differently from many classical treatments of secure multi-party computations, we always quantify security in exact terms. Although working with concrete time bounds and success probabilities is technically more demanding, it also has several advantages. As all security guarantees are quantitative, we can always compare different protocol designs. Moreover, these security guarantees also have a clear economical interpretation and it is possible to compare cryptographic and non-cryptographic solutions. The latter is extremely important in practice, since cryptographic techniques are just one possibility to achieve practical security. Also, working with exact bounds makes reasoning errors more apparent, as security proofs are less abstract and it is easier to locate false claims. The choice of topics covered in this thesis was guided by two principles. Firstly, we wanted to give a coherent overview of the secure multi-party computation that is based on exact quantification of security guarantees. Secondly, we focused on topics that emerged from the author's own research. In that sense, the thesis generalises many methodological discoveries made by the author. As surprising as it may seem, security definitions and proofs mostly utilise principles of hypothesis testing and analysis of stochastic algorithms. Thus, we start our treatment with hypothesis testing and its generalisations. In particular, we show how to quantify various security properties, using security games as tools. Next, we review basic proof techniques and explain how to structure complex proofs so they become easily verifiable. In a nutshell, we describe how to represent a proof as a game tree, where each edge corresponds to an elementary proof step. As a result, one can first verify the overall structure of a proof by looking at the syntactic changes in the game tree and only then verify all individual proof steps corresponding to the edges. The remaining part of the thesis is dedicated to various aspects of protocol design. Firstly, we discuss how to formalise various security goals, such as input-privacy, output-consistency and complete security, and how to choose a security goal that is appropriate for a specific setting. Secondly, we also explore alternatives to exact security. More precisely, we analyse connections between exact and asymptotic security models and rigorously formalise a notion of subjective security. Thirdly, we study in which conditions protocols preserve their security guarantees and how to safely combine several protocols. Although composability results are common knowledge, we look at them from a slightly different angle. Namely, it is irrational to design universally composable protocols at any cost; instead, we should design computationally efficient protocols with minimal usage restrictions. Thus, we propose a three-stage design procedure that leads to modular security proofs and minimises usage restrictions.
What does it mean for a cryptographic protocol to be "secure"? Capturing the security requirements of cryptographic tasks in a meaningful way is a slippery business: On the one hand, we want security criteria that prevent "all potential attacks" against a protocol; on the other hand, we want our criteria not to be overly restrictive and accept "reasonable protocols". One of the main reasons for flaws is the often unexpected interactions among different protocol instances that run alongside each other in a composite system.This tutorial studies a general methodology for defining security of cryptographic protocols. The methodology, often dubbed the "trusted party paradigm", allows for defining the security requirements of a large variety of cryptographic tasks in a unified and natural way. We first review more basic formulations that capture security in isolation from other protocol instances. Next we address the security problems associated with protocol composition, and review formulations that guarantee security even in composite systems.
Large quantum computers pose a threat to our public-key cryptographic infrastructure. The possible responses are: \n \nDo nothing; accept the fact that quantum computers might be used to break widely deployed protocols. \nMitigate the threat by switching entirely to symmetric-key protocols. \nMitigate the threat by switching to different public-key protocols. \n \nEach user of public-key cryptography will make one of these choices, and we should not expect consensus. Some users will do nothing---perhaps because they view the threat as being too remote. And some users will find that they never needed public-key cryptography in the first place. \n \nThe work that I present here is for people who need public-key cryptography and want to switch to new protocols. Each of the three articles raises the security estimate of a cryptosystem by showing that some attack is less effective than was previously believed. Each article thereby reduces the cost of using a protocol by letting the user choose smaller (or more efficient) parameters at a fixed level of security. \n \nIn Part 1, I present joint work with Samuel Jaques in which we revise security estimates for the Supersingular Isogeny Key Exchange (SIKE) protocol. We show that known quantum claw-finding algorithms do not outperform classical claw-finding algorithms. This allows us to recommend 434-bit primes for use in SIKE at the same security level that 503-bit primes had previously been recommended. \n \nIn Part 2, I present joint work with Martin Albrecht, Vlad Gheorghiu, and Eamonn Postelthwaite that examines the impact of quantum search on sieving algorithms for the shortest vector problem. Cryptographers commonly assume that the cost of solving the shortest vector problem in dimension
d is
2(0.265ldots+o(1))d quantumly and
2(0.292ldots+o(1))d classically. These are upper bounds based on a near neighbor search algorithm due to Becker--Ducas--Gama--Laarhoven. Naively, one might think that
d must be at least
483(approx128/0.265) to avoid attacks that cost fewer than
2128 operations. Our analysis accounts for terms in the
o(1) that were previously ignored. In a realistic model of quantum computation, we find that applying the Becker--Ducas--Gama--Laarhoven algorithm in dimension
d>376 will cost more than
2128 operations. We also find reason to believe that the classical algorithm will outperform the quantum algorithm in dimensions
d<288. \n \nIn Part 3, I present solo work on a variant of post-quantum RSA. The original pqRSA proposal by Bernstein--Heninger--Lou--Valenta uses terabyte keys of the form
n=p1p2p3p4cdotspicdotsp231 where each
pi is a
4096-bit prime. My variant uses terabyte keys of the form
n=p12p23p35p47cdotspipiicdotsp20044225287 where each
pi is a
4096-bit prime and
pii is the
i-th prime. Prime generation is the most expensive part of post-quantum RSA in practice, so the smaller number of prime factors in my proposal gives a large speedup in key generation. The repeated factors help an attacker identify an element of small order, and thereby allow the attacker to use a small-order variant of Shor's algorithm. I analyze small-order attacks and discuss the cost of the classical pre-computation that they require.