Secure computation methods include methods that use homomorphic encryption (HE) and those that use secret sharing (SS). Secure computation based on HE can be realized using one server, and the computation process can be made public if the encryption key is kept secure. However, HE generally requires a substantial computation cost. In contrast, SS has the advantage of low computation cost, allowing for high-speed processing; however, all servers must be managed independently. And the process of k or more servers cannot be disclosed. In particular, secret input will be leaked when the same organization manages multiple servers to implement SS. Therefore, a complex model where each server is independently managed is required. Iwamura et al. proposed a secure computation that is information-theoretic secure in n≥k instead of n≥2k−1 by assuming a trusted third party (TTP). In this paper, by making more effective use of a TTP, we demonstrate that secure computation based on SS is possible with only one computing server. Moreover, we show that the entire computation process can be disclosed if the key is managed safely. We realize a method that solves the disadvantages of conventional approaches with a faster computation than those methods.
Secure computation methods include methods that use homomorphic encryption (HE) and those that use secret sharing (SS). Secure computation based on HE can be realized using one server, and the computation process can be made public if the encryption key is kept secure. However, HE generally requires a substantial computation cost. In contrast, SS has the advantage of low computation cost, allowing for high-speed processing; however, all servers must be managed independently. And the process of k or more servers cannot be disclosed. In particular, secret input will be leaked when the same organization manages multiple servers to implement SS. Therefore, a complex model where each server is independently managed is required. Iwamura et al. proposed a secure computation that is information-theoretic secure in n≥k instead of n≥2k−1 by assuming a trusted third party (TTP). In this paper, by making more effective use of a TTP, we demonstrate that secure computation based on SS is possible with only one computing server. Moreover, we show that the entire computation process can be disclosed if the key is managed safely. We realize a method that solves the disadvantages of conventional approaches with a faster computation than those methods.
Nowadays, computation becomes more advanced, and may require more than one parties to participate.Some examples include e-voting system and privacy-preserving data analytics.One of the main concerns here is privacy.Inputs of these systems must be kept secret.To address this concern, we can construct the systems by using secure multi-party protocols, where several parties with their secret inputs perform joint computations in oblivious ways.Many aspects of the protocols can be further improved towards the usage in reallife applications, considering operational requirements and trade-offs.These operational requirements include efficiency, functionality, security, scalability, and verifiability.This thesis consists of three parts; each part focuses on specific improvements.In the first part, we focus on improving security and efficiency.We consider a homomorphic secret sharing scheme, where a secret input from each party is divided into several shares, each share is sent to different computing server, and the servers can perform some computation locally to get shares of the result.It is obvious that homomorphic secret sharing schemes can be used as secure multi-party protocols with small communication.We found that the existing homomorphic secret sharing scheme with public key of Lai et al. (Asiacrypt 2018) is 1-secure, which means if more than one computing servers try to collude, the security of the system will be compromised.They also proposed a t-secure scheme, but it requires solving NP-hard problem.To improve their security level, we use the idea from the secret sharing scheme of Ito et al.Our scheme also supports any number of computing servers without solving NP-hard problem.Using hyper-graph representation of non-access structures, we prove the maximum polynomial degree that our scheme can support.In addition, we prove correctness and security of the scheme, and propose some possible further improvements.In the second part, we focus on improving scalability and efficiency.Most of the secret sharing schemes, including homomorphic secret sharing, require the number of parties to be fixed in advance.This causes an inconvenience if we want to add more parties later in order to change the security setting or improve availability of the system.One existing variant of secret sharing, called evolving secret sharing, allows any number of parties to join the system at any time.However, it is inefficient to perform computation on this kind of secret sharing.To address this problem, we propose the definition of evolving homomorphic secret sharing, which combines evolving and homomorphic properties together.The scheme iii then supports unbounded number of parties, and allows local computation on shares.In addition to the definition, we propose two concrete schemes.The first scheme realizes evolving disjunctive hierarchical access structure supporting multiplication.The second scheme realizes evolving partially disjunctive hierarchical access structure supporting lowdegree polynomial computation.In the third part, we focus on improving functionality, verifiability, and efficiency.We consider the problem of oblivious deterministic finite automata (DFA) evaluation protocol.In this problem, one party holds a secret string, and the other party holds a secret pattern.The goal of this protocol is to output whether the string matches with the pattern of not without revealing both secret inputs.Most of the existing protocols use several communication rounds and require public key primitives, which can be inefficient.As our contribution, we propose an oblivious conditional disclosure of secrets (CDS) scheme for DFA.It is the first CDS scheme that has a functionality of DFA evaluation.We then use the proposed oblivious CDS scheme as a building block to construct an oblivious DFA evaluation protocol, using a multi-client verifiable computation framework.As a result, our protocol is constant-round, verifiable, and does not require any public key primitives.We also propose a standard CDS scheme for DFA as an independent interest.This thesis is expected to be a step of secure multi-party protocols and secret sharing schemes enhancements towards real-life applications.High level ideas for more improvements are also suggested as future prospects.
Advancements in Internet of Things devices allow for the collection and analysis of big data. Moreover, cloud computing has emerged as an ideal platform for big data analysis because it quickly provides computing resources for analysis at scale. However, concerns exist regarding the privacy and security of this information. Secure computation is a technology that enables computation while maintaining data encryption. In this study, we present a new secure computation based on a client-server model, in which a set of servers perform computations using the inputs of multiple clients. We adopt the(k,n)threshold secret sharing approach, where an inputsis divided intonshares and can be recovered from shares with a thresholdk. However, conventional secure computation using(k,n)threshold secret sharing generally requires the conditionn≥2k−1and communication among multiple servers for each multiplication. To the best of our knowledge, no previous study has solved this problem completely. We demonstrate that processes that require communication can be concentrated in the preprocessing phase and propose a secure computation using(k,n)threshold secret sharing that does not require communication during the secure computation phase, even when multiplication is performed. Moreover, we show that the number of communications does not depend on the number of multiplications, unlike in conventional methods. As communication often requires more processing time than the actual secure computation, our method makes it possible to realize faster overall processing than conventional methods. We also present an extensive security analysis and experimental simulation of the proposed method. Our proposed method achieves information-theoretic security against semi-honest adversaries under certain conditions withn<2k−1.
Two-party computation allows two clients to jointly compute an arbitrary function of their inputs without revealing these inputs to each other. In this study, we adopt a server-aided model, in which a set of computing servers performs computation using the inputs of two clients. In the (k, n) threshold secret sharing scheme, input s is divided into n shares and can be recovered from k shares, where k is a threshold. Typically, the multiplication of shares increases the polynomial's degree from (k-1) to (2k-2), thus increasing the number of shares required from k to 2k-1. Because each server typically holds only one share, the number of servers required also increases to 2k-1. Therefore, a set of n servers can compute multiplication securely only if the adversary corrupts at most k-1 <; n/2 servers. In this study, we differentiate N, which is the number of required servers, and n, which is the parameter of the (k, n) threshold secret sharing scheme. We propose a method of multiplication by using only N ≥ k servers. This is implemented by sending two shares of the same input to each server. In a “normal” method, sending multiple shares to one server violates security because k shares can be leaked from k-1 servers. We overcome this by implementing a different functionality, where each share is first encrypted with a different random number (encrypted share) before being sent to a server. Instead of the “normal shares” of ab, our protocol computes the encrypted shares of ab using the encrypted shares of a and b. We show that the proposed method is secure against a non-colluding semi-honest adversary. Moreover, we implement our method in MATLAB and show its efficiency.
Encrypted control systems allow to evaluate feedback laws on external servers without revealing private information about state and input data, the control law, or the plant. While there are a number of encrypted control schemes available for linear feedback laws, only few results exist for the evaluation of more general control laws. Recently, an approach to encrypted polynomial control was presented, relying on two-party secret sharing and an inter-server communication protocol using homomorphic encryption. As homomorphic encryptions are much more computationally demanding than secret sharing, they make up for a tremendous amount of the overall computational demand of this scheme. For this reason, in this paper, we investigate schemes for secure polynomial control based solely on secret sharing. We introduce a novel secure three-party control scheme based on three-party computation. Further, we propose a novel n-party control scheme to securely evaluate polynomial feedback laws of arbitrary degree without inter-server communication. The latter property makes it easier to realize the necessary requirement regarding non-collusion of the servers, with which perfect security can be guaranteed. Simulations suggest that the presented control schemes are many times less computationally demanding than the two-party scheme mentioned above.
It seems to be a generally acknowledged fact that you should never trust a computer and that you should trust the person operating the computer even less. This in particular becomes a problem when the party that you do not trust is one which is separated from you and is one on which you depend, e.g. because that party is the holder of some data or some capability that you need in order to operate correctly. How do you perform a given task involving interaction with other parties while allowing these parties a minimal influence on you and, if privacy is an issue, allowing them to learn as little about you as possible. This is the general problem of secure multiparty computation. The usual way of formalizing the problem is to say that a number of parties who do not trust each other wish to compute some function of their local inputs, while keeping their inputs as secret as possible and guaranteeing the correctness of the output. Both goals should be obtained even if some parties stop participating or some malevolent coalition of the parties start deviating arbitrarily from the agreed protocol. The task is further complicated by the fact that besides their mutual distrust, nor do the parties trust the channels by which they communicate. A general solution to the secure multiparty computation problem is a compiler which given any feasible function describes an efficient protocol which allows the parties to compute the function securely on their local inputs over an open network. Over the past twenty years the secure multiparty computation problem has been the subject of a large body of research, both research into the models of multiparty computation and research aimed at realizing general secure multiparty computation. The main approach to realizing secure multiparty computation has been based on verifiable secret sharing as computation, where each party holds a secret share of each input and during the execution computes secret shares of all intermediate values. This approach allows the parties to keep all inputs and intermediate values secret and to pool the shares of the output values to learn exactly these values. More recently an approach based on joint homomorphic encryption was introduced, allowing for an efficient realization of general multiparty computation secure against an eavesdropper. A joint encryption scheme is an encryption scheme where all parties can encrypt, but where it takes the participation of all parties to open an encryption. The computation then starts by all parties broadcasting encryptions of their inputs and progresses through computing encryptions of the intermediary values using the homomorphic properties of the encryption scheme. The encryptions of the outputs can then be jointly decrypted. In this dissertation we extend this approach by using threshold homomorphic encryption to provide full-fledged security against an active attacker which might control some of the parties and which might take over parties during the course of the protocol execution. As opposed to a joint encryption scheme a threshold encryption scheme only requires that a given number of the parties are operating correctly for decryption to be possible. In this dissertation we show that threshold homomorphic encryption allows to solve the secure general multiparty computation problem more efficiently than previous approaches to the problem. Starting from an open point-to-point network there is a long way to general secure multiparty computation. The dissertation contains contributions at several points along the way. In particular we investigate how to realize secure channels. We also show how threshold signature schemes can be used to efficiently realize a broadcast channel and how threshold cryptography can be used to provide the parties of the network with a source of shared randomness. All three tools are well-known to be extremely powerful resources in a network, and our principle contribution is to provide efficient realizations. The dissertation also contains contributions to the definitional part of the field of multiparty computation. Most significantly we augment the recent model of universally composable security with a formal notion of what it means for a protocol to only realize a given problem under a given restricted input-output behavior of the environment. This e.g. allows us to give the first specification of a universally composable zero-knowledge proof of membership which does not at the same time require the proof system to be a proof of knowledge.
Encrypted control systems allow to evaluate feedback laws on external servers without revealing private information about state and input data, the control law, or the plant. While there are a number of encrypted control schemes available for linear feedback laws, only few results exist for the evaluation of more general control laws. Recently, an approach to encrypted polynomial control was presented, relying on two-party secret sharing and an inter-server communication protocol using homomorphic encryption. As homomorphic encryptions are much more computationally demanding than secret sharing, they make up for a tremendous amount of the overall computational demand of this scheme. For this reason, in this paper, we demonstrate that multi-party computation enables secure polynomial control based solely on secret sharing. We introduce a novel secure three-party control scheme based on three-party computation. Further, we propose a novel n-party control scheme to securely evaluate polynomial feedback laws of arbitrary degree without inter-server communication. The latter property makes it easier to realize the necessary requirement regarding non-collusion of the servers, with which perfect security can be guaranteed. Simulations suggest that the presented control schemes are many times less computationally demanding than the two-party scheme mentioned above.