This paper analyzes security strength of Iseki & Hayashi's secure computation which is valid for computation of polynomial as for real numbers, and proposes a new method to improve its security strength. First we derive the fact that Iseki & Hayashi's secure computation is deciphered if the value of single input variables of the computation is known. This implies that the security strength of Iseki & Hayashi's secure computation is bounded by the length of bits which can be inputted to this single variable. To improve this bound to be more secured, we propose a technique to repeat steps of Iseki & Hayashi's secure computation until its security strength becomes sufficiently powerful. A simple relationship about security strength between Iseki & Hayashi's secure computation and our proposal is found, and it shows security strength becomes quickly powerful with the increase of number of repetitions. Finally, numerical examples are demonstrated to show the effectiveness of our proposal.
This paper analyzes security strength of Iseki & Hayashi's secure computation which is valid for computation of polynomial as for real numbers, and proposes a new method to improve its security strength. First we derive the fact that Iseki & Hayashi's secure computation is deciphered if the value of single input variables of the computation is known. This implies that the security strength of Iseki & Hayashi's secure computation is bounded by the length of bits which can be inputted to this single variable. To improve this bound to be more secured, we propose a technique to repeat steps of Iseki & Hayashi's secure computation until its security strength becomes sufficiently powerful. A simple relationship about security strength between Iseki & Hayashi's secure computation and our proposal is found, and it shows security strength becomes quickly powerful with the increase of number of repetitions. Finally, numerical examples are demonstrated to show the effectiveness of our proposal.
Abstract. For many cryptographic protocols, security relies on the assumption that adversarial entities have lim-ited computational power. This type of security degrades progressively over the lifetime of a protocol. However, some cryptographic services, such as timestamping services or digital archives, are long-lived in nature; they are expected to be secure and operational for a very long time (i.e., super-polynomial). In such cases, security cannot be guaranteed in the traditional sense: a computationally secure protocol may become insecure if the attacker has a super-polynomial number of interactions with the protocol. This paper proposes a new paradigm for the analysis of long-lived security protocols. We allow entities to be active for a potentially unbounded amount of real time, provided they perform only a polynomial amount of work per unit of real time. Moreover, the space used by these entities is allocated dynamically and must be polynomially bounded. We propose a new notion of long-term implementation, which is an adaptation of computational indistinguishability to the long-lived setting. We show that long-term implementation is preserved under polynomial parallel composi-tion and exponential sequential composition. We illustrate the use of this new paradigm by analyzing some security properties of the long-lived timestamping protocol of Haber and Kamat. 1
We address the problem of the-security of cryptographic protocols in face of future advances in computing technology and algorithmic research. The problem stems from the fact may be deemed that computations which at a given point in time may be deemed infeasible, can, in the course of years or decades, be made possible with improved hardware and/or breakthroughs in code-breaking algorithms. In such cases, the security of historical , but nonetheless highly confidential data may be in jeopardy. We present a scheme for efficient secure two-party communication with provable everlasting security. The security is guaranteed in face of any future technological advances, given the current state of of the art. Furthermore, the security of the messages is also guaranteed even if the secret encryption/decryption key is revealed in the future, The scheme is based on the bounded storage model and provides information-theoretic security in this model. The bounded storage model postulates an adversary who is computationally unbounded, and is only bounded in the amount of storage (not computation space) available to store the output of his computation. The bound on the storage can be arbitrarily large (e.g., 100 Tbytes), as long as it is fixed. Given this storage bound, our protocols guarantee that even a computationally all powerful adversary gains no information about a message (except with a probability that is exponentially small in the security parameter k). The bound on storage space need only hold at the time of the message transmission. Thereafter, no additional storage space or, computational power can help the adversary in deciphering the message. We present two protocols. The first protocol, which elaborates on the autoregressive (AR) protocol of Aumann and Rabin (see Advances in Cryptology-Crypto '99, p. 65-79, 1999), employs a short secret key whose size is independent of the length of the message, but uses many public random bits. The second protocol uses an optimal number of public random bits, but employs a longer secret key. Our proof of security utilizes a novel linear algebraic technique.
For many cryptographic protocols, security relies on the assumption that adversarial entities have limited computational power. This type of security degrades progressively over the lifetime of a protocol. However, some cryptographic services, such as timestamping services or digital archives, are emph{long-lived} in nature; they are expected to be secure and operational for a very long time (ie super-polynomial). In such cases, security cannot be guaranteed in the traditional sense: a computationally secure protocol may become insecure if the attacker has a super-polynomial number of interactions with the protocol. This paper proposes a new paradigm for the analysis of long-lived security protocols. We allow entities to be active for a potentially unbounded amount of real time, provided they perform only a polynomial amount of work emph{per unit of real time}. Moreover, the space used by these entities is allocated dynamically and must be polynomially bounded. We propose a new notion of emph{long-term implementation}, which is an adaptation of computational indistinguishability to the long-lived setting. We show that long-term implementation is preserved under polynomial parallel composition and exponential sequential composition. We illustrate the use of this new paradigm by analyzing some security properties of the long-lived timestamping protocol of Haber and Kamat.
In order to improve efficiency and solve the security vulnerabilities of the secure set computation protocols in practical applications, two secure two-party protocols for set membership and set intersection were proposed based on discrete logarithm problem and the polynomial representation of sets with which the set operation problem could be transformed into a polynomial evaluation problem. Firstly, a latest efficient secure set membership protocol was analyzed, and a security vulnerability of leaking the privacy of the participants by obtaining the element of participants on the brute attack was found. To overcome the security vulnerability, a new method was introduced by representing sets by polynomials and randomizing the polynomials, which could ensure the security of the participants without any leakage of interactions. Based on the discrete logarithm problem and the new method, a new secure set membership protocol was presented. The protocol could judge set-element membership with high-efficiency, and did not leak any other information about the participants besides the size of the set. Further, a secure set intersection protocol was showed according to the same technique. The security proofs of both protocols were given under the semi-honest model by using the probability polynomial time simulator, which indicated that the simulator views were computationally indistinguishable from the original protocols’ execution views. Finally, the detailed analysis about the protocols’ performance was presented, showing that both protocols were more efficient than other protocols since their communication complexity and computational complexity were smaller.
We consider a minimal scenario for secure computation: Parties A and B have private inputs x and y and a shared random string r. A and B are each allowed to send a single message to a third party C, from which C is to learn the value of f(x, y) for some function f, but nothing else. We show that this model is surprisingly powerful: every function f can be securely computed in this fashion. If the messages are required to be of polynomial size, then we exhibit an efficient protocol for any function f computable in nondeterministic logspace. Using a computational notion of security, we exhibit efficient protocols for any polynomial-time computable function f, assuming the existence of one-way functions. The above results generalize to the case where there are more than two parties with private inputs. The minimalistic nature of our model makes it easy to transform positive results achieved in our model to other more general models of secure computation. It also gives hope for lowerbound proofs. We give an alternative characterization of our model in terms of graph embeddings, and use this to show that for most Boolean functions on {0, 1} n × {0, 1} n, the need to hide just one of the input bits from C requires a communication overhead of n bits. 1
We propose a general method for studying properties of quantum channels acting on an n-partite system, whose action is invariant under permutations of the subsystems. Our main result is that, in order to prove that a certain property holds for an arbitrary input, it is sufficient to consider the case where the input is a particular de Finetti-type state, i.e., a state which consists of n identical and independent copies of an (unknown) state on a single subsystem. Our technique can be applied to the analysis of information-theoretic problems. For example, in quantum cryptography, we get a simple proof for the fact that security of a discrete-variable quantum key distribution protocol against collective attacks implies security of the protocol against the most general attacks. The resulting security bounds are tighter than previously known bounds obtained with help of the exponential de Finetti theorem.