# Efficient Circuit-Size Independent Public Key Encryption with KDM Security

 1/p-Secure Multiparty Computation without Honest Majority and the Best of Both Worlds 120px Authors Amos Beimel[@: 1] Yehuda Lindell[@: 2] Eran Omri[@: 3] Ilan Orlov[@: 4] Download original

Abstract. A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation, where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair - all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition - ${\displaystyle 1/p}$-secure computation - which guarantees partial fairness. For two parties, they construct${\displaystyle 1/p}$-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study ${\displaystyle 1/p}$-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p${\displaystyle 1/p}$-secure protocols that are resilient against any number of corrupt parties provided that the number of parties is constant and the size of the range of the functionality is at most polynomial (in the security parameter ${\displaystyle n}$). If less than ${\displaystyle 2/3}$ of the parties are corrupt, the size of the domain is constant, and the functionality is deterministic, then our protocols are efficient even when the number of parties is log log ${\displaystyle n}$. On the negative side, we show that when the number of parties is super-constant, ${\displaystyle 1/p}$-secure protocols are not possible when the size of the domain is polynomial. Thus, our feasibility results for 1/p-secure computation are essentially tight. We further motivate our results by constructing protocols with stronger guarantees: If in the execution of the protocol there is a majority of honest parties, then our protocols provide full security. However, if only a minority of the parties are honest, then our protocols are ${\displaystyle 1/p}$-secure. Thus, our protocols provide the best of both worlds, where the ${\displaystyle 1/p}$- security is only a fall-back option if there is no honest majority.

## Introduction

A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation, where parties give their inputs to a trusted party which, in turn, returns the output of the functionality to all parties. This is formalized by requiring that for every adversary in the real world, there is an adversary in the ideal world, called simulator, such that the output of the real-world adversary and the simulator are indistinguishable in polynomial time. Such security can be achieved when there is a majority of honest parties [1]. Secure computation is fair - all parties get the output. Cleve [2] proved that, in general, fairness is not possible without an honest majority.

To overcome the impossibility of [2], Gordon and Katz [3] suggested a relaxed definition - ${\displaystyle 1/p}$-secure computation - which guarantees partial fairness. Informally, a protocol is ${\displaystyle 1/p}$-secure if for every adversary in the real world, there is a simulator running in the ideal world, such that the output of the real-world adversary and the simulator cannot be efficiently distinguished with probability greater than ${\displaystyle 1/p}$. For two parties, Gordon and Katz construct ${\displaystyle 1/p}$-secure protocols for functionalities whose size of either their domain or their range is polynomial (in the security parameter). They also give impossibility results when both the domain and range are super-polynomial. Gordon and Katz ask whether their results can be extended to multiparty protocols. We give positive and negative answers to this question.

Previous Results. Cleve [2] proved that any protocol for coin-tossing without an honest majority cannot be fully secure; specifically, if the protocol has ${\displaystyle r}$ rounds, then it is at most ${\displaystyle 1/r}$-secure. Protocols with partial fairness, under various definitions and assumptions, have been constructed for coin-tossing [2], [4], [5], [6], for contract signing/exchanging secrets [7], [8], [9], [10], [11], [12], and for general functionalities [13], [14], [15], [16], [17], ref name='[12]'>J. A. Garay, P. D. MacKenzie, M. Prabhakaran, and K. Yang. Resource fairness and composability of cryptographic protocols. In TCC 2006, volume 3876 of LNCS, pages 404–428, 2006.</ref>, [3]. We next describe the papers that are most relevant to our paper. Moran, Naor, and Segev [5] construct 2-party protocols for coin tossing that are ${\displaystyle 1/r}$-secure (where ${\displaystyle r}$ is the number of rounds in the protocol). Gordon and Katz [3] define ${\displaystyle 1/p}$-security and construct 2-party ${\displaystyle 1/p}$-secure protocols for every functionality whose size of either the domain or the range of the functionality is polynomial. Finlay, Beimel, Omri, and Orlov [6] construct multiparty protocols for coin tossing that are ${\displaystyle O\left(1/r\right)}$-secure provided that the fraction of corrupt parties is slightly larger than half. In particular, their protocol is ${\displaystyle O\left(1/r\right)}$-secure when the number of parties is constant and the fraction of bad parties is less than ${\displaystyle 2/3}$.

Gordon et al. [18] showed that complete fairness is possible in the two party case for some functions. Gordon and Katz [19] showed similar results for the multiparty case. The characterization of the functions that can be computed with full fairness without honest majority is open. Gordon et al. [20] studied completeness for fair computations. Specifically, they showed a specific function that is complete for fair two-party computation; this function is also complete for ${\displaystyle 1/p}$-secure two-party computation.

Ishai et al. [21] considered “best of two worlds” protocols. Such protocols should provide full security with an honest majority and some (weaker) security if there is only a minority of honest parties. They give positive and negative results for the existence of such protocols. We discuss some of their results below.

### Our Results

We study ${\displaystyle 1/p}$-secure protocols in the multiparty setting. We construct protocols for general functionalities that are ${\displaystyle 1/p}$-secure against any number of corrupt parties provided that the number of parties is constant. Our protocols require that the size of the range of the (possibly randomized) functionality is at most polynomial in the security parameter. That is, we show the following feasibility result.
Theorem (Informal). Let ${\displaystyle F}$ be a (possibly randomized) functionality with a constant number of parties whose size of range is at most polynomial in the security parameter ${\displaystyle n}$. Then, for every polynomial ${\displaystyle p\left(n\right)}$ there is a ${\displaystyle 1/p\left(n\right)}$ -secure protocol for ${\displaystyle F}$ tolerating any number of corrupt parties.

Our results are the first general feasibility results for ${\displaystyle 1/p}$-secure protocols in the multi-party setting, e.g., even for the case that there are 3 parties and two of them might be corrupt. We provide two additional protocols that are ${\displaystyle 1/p}$- secure assuming that the fraction of corrupt parties is less than ${\displaystyle 2/3}$. These two protocols are more efficient than the protocols discussed above. Specifically, one of the protocols is ${\displaystyle 1/p}$-secure even when the number of parties is log log ${\displaystyle n}$ (where ${\displaystyle n}$ is the security parameter) provided that the functionality is deterministic and the size of the domain of inputs is constant.

The definition of ${\displaystyle 1/p}$-security allows that with probability ${\displaystyle 1/p}$ the outputs of the honest parties will be arbitrary, e.g., for a Boolean function the outputs can be non-Boolean. Some of our protocols are always correct, that is, they always return an output of the functionality with the inputs of the honest parties and some inputs for the corrupt parties. This correctness property is essential for the best of both worlds results described below.

We further motivate our results by constructing protocols with best of both worlds guarantees: If in the execution of the protocol there is a majority of honest parties, then our protocols provide full security. However, if only a minority of parties are honest, then our protocols are ${\displaystyle 1/p}$-secure. The protocols succeed although they do not know in advance if there is an honest majority or not. Specifically, we show that
Theorem (Informal). Let ${\displaystyle F}$ be a functionality with a constant number of parties whose size of domain and range is at most polynomial in the security parameter ${\displaystyle n}$. Then, for every polynomial ${\displaystyle p\left(n\right)}$ there is a protocol for ${\displaystyle F}$ tolerating any number of corrupt parties such that
— If there is an honest majority, then the protocol is fully secure.
— If there is no honest majority, then the protocol is ${\displaystyle 1/p\left(n\right)}$ -secure.

Thus, the ${\displaystyle 1/p}$ -security guarantee can be considered as a fall-back option if there is no honest majority. Our protocols provide the best of both worlds, the world of honest majority where the known protocols (e.g., [1]) provide full security if there is an honest majority and provide no security guarantees if no such majority exists and the world of secure computation without honest majority.

In the latter world the security is either security-with-abort or ${\displaystyle 1/p}$-security. These types of security are incomparable. Ishai et al. [21] proved that there is no general protocol which provides full security when there is an honest majority and security-with-abort without an honest majority. Thus, our protocols provide the best possible combination of both worlds.

Katz [22] presented a protocol, for any functionality ${\displaystyle F}$, with full security when there is an honest majority, as well as ${\displaystyle 1/p}$-security with abort for any num¬ber of corrupt parties. This result assumes a non-rushing adversary. In contrast, our protocols achieve a stronger security with a minority of honest parties and can handle the more realistic case of a rushing adversary. However, our protocols only work with a constant number of parties and a polynomial size domain.

To complete the picture, we prove interesting impossibility results. We show that, in general, when the number of parties is super-constant, ${\displaystyle 1/p}$-secure protocols are not possible without honest majority when the size of the domain is polynomial. This impossibility result justifies the fact that in our protocols the number of parties is constant. We also show that, in general, when the number of parties is ${\displaystyle \omega \left(logn\right)}$, ${\displaystyle 1/p}$-secure protocols are not possible without honest majority even when the size of the domain is 2. The proof of the impossibility results is rather simple and follows from an impossibility result of [3]. Nevertheless, they show that our general feasibility results are almost tight.

Our impossibility results should be contrasted with the coin-tossing protocol of [6], which is an efficient ${\displaystyle 1/p}$ - secure protocol even when ${\displaystyle m\left(n\right)}$, the number of parties, is polynomial in the security parameter and the number of bad parties is ${\displaystyle m\left(n\right)+O\left(1\right)}$. Our results show that these parameters are not possible for general ${\displaystyle 1/p}$-secure protocols even when the size of the domain of inputs is 2.

The above mentioned impossibility results do not rule out that the best of two worlds results of Katz [22] can be strengthened by removing the restriction that the adversary is non-rushing. We show that this is impossible, that is, in general, when the number of parties is super-constant and the size of the domain is polynomial, there is no protocol that is fully secure with an honest majority and ${\displaystyle 1/p}$ -secure-with-abort without such a majority.

The ideas behind our protocols. Our protocols use ideas from the protocols of Gordon and Katz [3] and Beimel et al. [6], both of which generalize the protocol of Moran, Naor, and Segev [5]. In addition, our protocols introduce new ideas that are required to overcome challenges that did not occur in previous works, e.g., dealing with inputs (in contrast to the scenario of [6]) and dealing with a dishonest majority even after parties abort (in contrast to the scenario of [3]). In particular, in order to achieve resilience against any number of corrupt parties we introduce new techniques for hiding the round in which parties learn the output of an execution. Specifically, our protocols proceed in rounds, where in each round values are given to subsets of parties. There is a special round ${\displaystyle i*}$ in the protocol. Prior to round ${\displaystyle i*}$, the values given to a subset of parties are values that can be computed from the inputs of the parties in this subset; starting from round ${\displaystyle i*}$ the values are the “correct” output of the functionality. The values given to a subset are secret shared such that only if all parties in the subset cooperate they can reconstruct the value. Similar to the protocols of [5], [3], [6], the adversary can cause harm (e.g., bias the output of the functionality) only if it guesses ${\displaystyle i*}$; we show that in our protocols this probability is small and the protocols are ${\displaystyle 1/p}$-secure.

In our protocols that are ${\displaystyle 1/p}$-secure against a fraction of ${\displaystyle 2/3}$ corrupt parties (which are described in Section 4), if in some round many (corrupt) parties have aborted and there is a majority of honest parties among the active parties, then the set of active parties reconstructs the value given to this set in the previous round. The mechanism to secret share the values in this protocols is similar to [6] , however, there are important differences in this sharing, as the sharing mechanism of [6] is not appropriate for ${\displaystyle 1/p}$-secure computations of functionalities which depend on inputs. The fact that the protocol proceeds until there is an honest majority imposes some restrictions that imply that the protocol can tolerate only a fraction of ${\displaystyle 2/3}$ corrupt parties.

Our protocols that are ${\displaystyle 1/p}$-secure against any number of corrupt parties (which are described in Section 5) take a different route. To describe the ideas of the protocol, we consider only the three-party case, where at most two parties are corrupt. In the protocol if one party aborts, then the remaining two parties execute a two-party protocol for the functionality. Again, this protocol proceeds in rounds, where in each round each party gets a value. If the party in the three- party protocol aborts after round ${\displaystyle i*}$, then all these values are the “correct” output of the functionality. To hide ${\displaystyle i*}$, also prior to ${\displaystyle i*}$, with some probability all these values must be equal. With the remaining probability, a new ${\displaystyle i*}$ is chosen with uniform distribution for the two-party protocol. In other words, in the two- party protocol prior to the original ${\displaystyle i*}$, with some probability, we chose a “fake” value of 1 for the new ${\displaystyle i*}$ of the two-party protocol.

Open Problems. In our impossibility results the size of the range is superpolynomial (in the security parameter). However, in all our protocols the size of the range is polynomial. It is open if there is an efficient ${\displaystyle 1/p}$-secure protocol when the number of parties is not constant and the size of both the domain and range is polynomial. In our protocols, the number of rounds is double-exponential in the number of parties. Our impossibility results do not rule out that this double¬exponential dependency can be improved.

The protocols of [3] are private - the adversary cannot learn any information on the inputs of the honest parties (other than the information that it can learn in the ideal world of computing ${\displaystyle F}$). The adversary can only bias the output. Some of our protocols are provably not private (that is, the adversary can learn extra information). However, for other protocols, we do not know whether they are private. It is open if there are general multiparty ${\displaystyle 1/p}$-secure protocols that are also private.

## Background and the Model of Computation

A multi-party protocol with ${\displaystyle m}$ parties is defined by ${\displaystyle m}$ interactive probabilis¬tic polynomial-time Turing machines ${\displaystyle p_{1},\dots ,p_{m}}$. Each Turning machine, called party, has the security parameter 1n${\displaystyle 1^{n}}$ as a joint input and a private input ${\displaystyle y_{j}}$. The computation proceeds in rounds. In each round, the active parties broadcast and receive messages on a common broadcast channel. The number of rounds in the protocol is expressed as some function ${\displaystyle r\left(n\right)}$ in the security parameter (typically, ${\displaystyle r\left(n\right)}$ is bounded by a polynomial). At the end of the protocol, the (honest) parties should hold a common value ${\displaystyle w}$ (which should be equal to an output of a predefined functionality).

In this work we consider a corrupt, static, computationally-bounded (i.e., non-uniform probabilistic polynomial-time) adversary that controls some subset of parties. That is, before the beginning of the protocol, the adversary corrupts a subset of the parties and may instruct them to deviate from the protocol in an arbitrary way. The adversary has complete access to the internal states of the corrupted parties and fully controls the messages that they broadcast throughout the protocol. The honest parties follow the instructions of the protocol.

The parties communicate via a synchronous network, using only a broadcast channel. The adversary is rushing, that is, in each round the adversary sees the messages broadcast by the honest parties before broadcasting the messages of the corrupted parties for this round (thus, the broadcast messages of the corrupted parties can depend on the messages of the honest parties in the same round).

In this work we consider ${\displaystyle 1/p}$-secure computation. Roughly speaking, we say that a protocol ${\displaystyle n}$ is ${\displaystyle 1/p}$-secure if for every adversary ${\displaystyle A}$ attacking ${\displaystyle n}$ in the real-world there is a simulator ${\displaystyle S}$ running in the ideal-world, such that the global output of the real-world and the ideal-world executions cannot be distinguished with probability greater than ${\displaystyle 1/p}$. The formal definitions of ${\displaystyle 1/p}$-security and security with abort and cheat detection, which is a tool used in this paper, will be given in the full version of the paper.

## Feasibility Results for 1/p-Secure Multiparty Computation

In this section we state our main feasibility results. Our main result asserts that any functionality with a polynomial size range for a constant number of parties can be ${\displaystyle 1/p}$-securely computed in polynomial time tolerating any number of corrupt (malicious) parties. We next formally state this result.

Theorem 1. Let ${\displaystyle F}$ be an ${\displaystyle m}$-party (possibly randomized) functionality. If enhanced trap-door permutations exist, and if ${\displaystyle m}$ is constant and the size of the range ${\displaystyle g\left(n\right)}$ is bounded by a polynomial in the security parameter ${\displaystyle n}$, then for any polynomial ${\displaystyle p\left(n\right)}$ there is an ${\displaystyle r\left(n\right)}$ -round ${\displaystyle 1/p}$ (n) -secure protocol computing ${\displaystyle F}$ tolerating up to ${\displaystyle m-1}$ corrupt parties, where ${\displaystyle r\left(n\right)=\left(p\left(n\right)*g\left(n\right)\right)^{2^{O\left(m\right)}}}$.

The protocol that implies Theorem 1 for general ${\displaystyle m}$ will appear in the full version of this paper. In this extended abstract we present, in Section 5, the 3-party version of this protocol tolerating up to 2 corrupt parties. In addition, for functionalities where the domain size is also bounded by a polynomial, we will present in the full version of this paper a protocol with somewhat stronger security properties. Using these stronger security, we can transform it into a protocol of the best of both worlds type (see Section 6.1 for details).

We give substantially better protocols secure against an adversary that may corrupt strictly less than two-thirds of the parties. Formally, we prove the fol¬lowing theorem.

Theorem 2. Let ${\displaystyle F}$ be an ${\displaystyle m\left(n\right)}$ -party (possibly randomized) functionality. Let ${\displaystyle t\left(n\right)}$ be such that ${\displaystyle m\left(n\right)/2\leq t\left(n\right)<2m\left(n\right)/3}$. If enhanced trap-door permutations exist, then for any polynomial ${\displaystyle p\left(n\right)}$ the following hold:
If m(n) is constant (hence, t = t(n) is constant) and the size of the range g(n) is bounded by a polynomial, then there exists an r(n)-round 1/p(n)- secure protocol computing F tolerating up to t corrupt parties, where r(n) = (2p(n))2+1 • g(n)2.
If F is deterministic and the size of the domain d(n) is bounded by a poly¬nomial, then there exists an r(n)-round 1/p(n)-secure protocol computing F tolerating up to t(n) corrupt parties, where r(n) = p(n) • d(n)m(n)'2 , provided that r(n) is bounded by a polynomial.

The protocols that imply the results of Theorem 2 are presented in Section 4. As implied by the second item of Theorem 2, the round complexity of our protocol when ${\displaystyle F}$ is deterministic has only a linear dependency on ${\displaystyle p\left(n\right)}$. Specifically, this protocol has polynomially many rounds even when the number of parties is 0.5 log log ${\displaystyle n}$ provided that the functionality is deterministic and the size of the domain of inputs is constant.

## Protocols with Less Than Two-Thirds Corrupt Parties

In this section we describe our protocols that are secure when the adversary corrupts strictly less than two thirds of the parties. We start with a protocol that assumes that either the functionality is deterministic and the size of the domain is polynomial, or that the functionality is randomized and both the domain and range of the functionality are polynomial. We then present a modification of the protocol that is ${\displaystyle 1/p}$-secure for (possibly randomized) functionalities if the size of the range is polynomial (even if the size of the domain of ${\displaystyle F}$ is not polynomial). The first protocol is more efficient for deterministic functionalities with polynomial-size domain. Furthermore, the first protocol has full correctness, while in the modified protocol, correctness is only guaranteed with probability ${\displaystyle 1-1/p}$.

Following [5], [6], we present the first protocol in two stages. We first describe in Section 4.1 a protocol with a dealer and then in Section 4.2 present a protocol without this dealer. The goal of presenting the protocol in two stages is to simplify the understanding of the protocol and to enable us to prove the protocol in a modular way. In Section 4.3, we present a modification of the protocol which is ${\displaystyle 1/p}$-secure if the size of the range is polynomial (even if the size of the domain of ${\displaystyle f}$ is not polynomial).

### The Protocol for Polynomial-Size Domain with a Dealer

In this section we assume that there is a special trusted on-line dealer, denoted ${\displaystyle T}$. This dealer interacts with the parties in rounds, sending messages on private channels. We assume that the dealer knows the set of corrupt parties. In Section 4.2, we show how to remove this dealer and construct a protocol without a dealer.

In our protocol the dealer sends in each round values to subsets of parties; the protocol proceeds with the normal execution as long as at least ${\displaystyle t+1}$ of the parties are still active. If in some round ${\displaystyle i}$, there are at most ${\displaystyle t}$ active parties, then the active parties reconstruct the value given to them in round ${\displaystyle i-1}$, output this value, and halt. Following [22], [18], [5], [3], [6], the dealer chooses at random with uniform distribution a special round ${\displaystyle i*}$. Prior to this round the adversary gets no information and if the corrupt parties abort the execution prior to ${\displaystyle i*}$, then they cannot bias the output of the honest parties or cause any harm. After round i*${\displaystyle i*}$, the output of the protocol is fixed, and also in this case the adversary cannot affect the output of the honest parties. The adversary can cause harm only if it guesses ${\displaystyle i*}$ and this happens with small probability.

In this extended abstract, we only give a verbal description of the protocol. This protocol is designed such that the dealer can be removed from it in Section 4.2. At the beginning of the protocol each party sends its input ${\displaystyle y_{j}}$ to the dealer. The corrupted parties may send any values of their choice. Let ${\displaystyle x_{1},\dots ,x_{m}}$ denote the inputs received by the dealer. If a corrupt party ${\displaystyle p_{j}}$ does not send an input, then the dealer sets ${\displaystyle x_{j}}$ to be a random value selected uniformly from the input domain ${\displaystyle X_{n}}$. In a preprocessing phase, the dealer ${\displaystyle T}$ selects uniformly at random a special round ${\displaystyle i*\in \{1,\dots ,r\}}$. The dealer computes ${\displaystyle \omega \leftarrow {f_{n}}\left(x_{1},\dots ,x_{m}\right)}$. Then, for every round ${\displaystyle 1\leqslant i\leqslant r}$ and every ${\displaystyle L\subset \{1,\dots ,m\}}$ such that ${\displaystyle m-t\leqslant |L|\leqslant t}$, the dealer selects an output, denoted ${\displaystyle \sigma _{L}^{i}}$, as follows (this output is returned by the parties in ${\displaystyle Q_{L}=\{p_{j},\dots ,j\in L\}}$ if the protocol terminates in round ${\displaystyle i+1}$ and ${\displaystyle Q_{L}}$ is the set of the active parties):
CASE I: ${\displaystyle 1\leqslant i\leqslant i*}$. For every ${\displaystyle j\in L}$ the dealer sets ${\displaystyle {\hat {x}}_{j}=x_{j}}$ and for every ${\displaystyle j\notin L}$ it chooses ${\displaystyle {\hat {x}}_{j}}$ independently with uniform distribution from the domain ${\displaystyle X_{n}}$; it computes the output ${\displaystyle \sigma _{L}^{i}\leftarrow f_{n}\left({\hat {x}}_{1},\dots ,{\hat {x}}_{m}\right)}$.
CASE II: ${\displaystyle i*\leqslant i\leqslant r}$. The dealer sets ${\displaystyle \sigma _{L}^{i}=\omega }$

The dealer ${\displaystyle T}$ interacts with the parties in rounds, where in round ${\displaystyle i}$, for ${\displaystyle 1\leqslant i\leqslant r}$, there are of three phases:
The peeking phase. The dealer ${\displaystyle T}$ sends to the adversary all the values ${\displaystyle \sigma _{L}^{i}}$ such that all parties in ${\displaystyle Q^{L}}$ are corrupted.
The abort and premature termination phase. The adversary sends to ${\displaystyle T}$ the identities of the parties that abort in the current round. If there are less than ${\displaystyle t+1}$ active parties, then ${\displaystyle T}$ sends ${\displaystyle \sigma _{L}^{i-1}}$ to the active parties, where ${\displaystyle Q_{L}}$ is the set of the active parties, where parties can also abort during this phase. The honest parties return this output and halt.
The main phase. If at least ${\displaystyle t+1}$ parties are active, ${\displaystyle T}$ notifies the active parties that the protocol proceeds normally to the next round.

If after ${\displaystyle r}$ rounds there are at least ${\displaystyle t+1}$ active parties, then ${\displaystyle T}$ sends ${\displaystyle \omega }$ to all active parties and the honest parties output this value.

Example 1. As an example, assume that ${\displaystyle m=5}$ and ${\displaystyle t=3}$. In this case the dealer computes a value ${\displaystyle \sigma _{L}^{i}}$ for every set of size 2 or 3. Consider an execution of the protocol where ${\displaystyle p_{1}}$ aborts in round 4 and ${\displaystyle p_{3}}$ and ${\displaystyle p_{4}}$ abort in round 100. In this case, T${\displaystyle T}$ sends ${\displaystyle \sigma _{\{2.5\}}^{99}}$ to ${\displaystyle p_{2}}$ and ${\displaystyle p_{5}}$, which return this output.

We next hint why for deterministic functionalities, an adversary can cause harm in the above protocol by at most ${\displaystyle {O}{({d^{O\left(r\right)}/r})}}$, where ${\displaystyle d=d\left(n\right)}$ is the size of the domain of the inputs and the number of parties, i.e., ${\displaystyle m}$, is constant. As in the protocols of [5], [3], [6], the adversary can only cause harm by causing the protocol to terminate in round ${\displaystyle i*}$. In our protocol, if in some round there are two values ${\displaystyle \sigma _{L}^{i}}$ and ${\displaystyle \sigma _{L}'^{i}}$ that the adversary can obtain such that ${\displaystyle \sigma _{L}^{i}=\sigma _{L}'^{i}}$, then the adversary can deduce that ${\displaystyle i. Furthermore, the adversary might have some auxiliary information on the inputs of the honest parties, thus, the adversary might be able to deduce that a round is not ${\displaystyle i*}$ even if all the values that it gets are equal. However, there are less than ${\displaystyle 2^{t}}$ values that the adversary can obtain in each round (i.e., the values of subsets of the ${\displaystyle t}$ corrupt parties of size at least ${\displaystyle m-t}$). We will show that for a round ${\displaystyle i}$ such that ${\displaystyle i, the probability that all these values are equal to a fixed value is ${\displaystyle 1/d^{O(1)}}$ for a deterministic function fn (for a randomized functionality this probability also depends on the size of the range). By [3], Lemma 2, this implies that the protocol is ${\displaystyle d^{O(1)}/r}$-secure.

### Eliminating the Dealer of the Protocol

We eliminate the trusted on-line dealer in a few steps using a few layers of secret-sharing schemes. First, we change the on-line dealer, so that, in each round ${\displaystyle i}$, it shares the value ${\displaystyle \sigma _{L}^{i}}$ of each subset ${\displaystyle Q_{L}}$ among the parties of ${\displaystyle Q_{L}}$ using a ${\displaystyle |L|}$-out-of-${\displaystyle |L|}$ secret-sharing scheme - called inner secret-sharing scheme. As in protocol with the dealer (described in Section 4.1), the adversary is able to obtain information on ${\displaystyle \sigma _{L}^{i}}$ only if it controls all the parties in ${\displaystyle Q_{L}}$. On the other hand, the honest parties can reconstruct ${\displaystyle \sigma _{L}^{i-1}}$ (without the dealer), where ${\displaystyle Q_{L}}$ is the set of active parties containing the honest parties. In the reconstruction, if an active (corrupt) party does not give its share, then it is removed from the set of active parties ${\displaystyle Q_{L}}$. This is possible since in the case of a premature termination an honest majority among the active parties is guaranteed (as further explained below).

Next, we convert the on-line dealer to an off-line dealer. That is, we con¬struct a protocol in which the dealer sends only one message to each party in an initialization stage; the parties interact in rounds using a broadcast channel (without the dealer) and in each round ${\displaystyle i}$ each party learns its shares of the ${\displaystyle i}$th round inner secret-sharing schemes. In each round ${\displaystyle i}$, each party ${\displaystyle p_{j}}$ learns a share of ${\displaystyle \sigma _{L}^{i}}$ in a ${\displaystyle |L|}$-out-of-${\displaystyle |L|}$ secret-sharing scheme, for every set ${\displaystyle Q_{L}}$ such that ${\displaystyle j\in L}$ and ${\displaystyle {m-t}\leqslant {|L|}\leqslant {t}}$ (that is, it learns the share of the inner scheme). For this purpose, the dealer computes, in a preprocessing phase, the appropriate shares for the inner secret-sharing scheme. For each round, the shares of each party ${\displaystyle p_{j}}$ are then shared in a 2-out-of-2 secret-sharing scheme, where ${\displaystyle p_{j}}$ gets one of the two shares (this share is a mask, enabling pj to privately reconstruct its shares of the appropriate ${\displaystyle \sigma _{L}^{i}}$ although messages are sent on a broadcast channel). All other parties get shares in a ${\displaystyle t}$-out-of-${\displaystyle \left({m-1}\right)}$ Shamir secret-sharing scheme of the other share of the 2-out-of-2 secret-sharing. We call the resulting secret-sharing scheme the outer ${\displaystyle \left(t+1\right)}$-out-of-${\displaystyle m}$ scheme (since ${\displaystyle t}$ parties and the holder of the mask are needed to reconstruct the secret).

To prevent corrupt parties from cheating, by say, sending false shares and causing reconstruction of wrong secrets, every message that a party should send during the execution of the protocol is signed in the preprocessing phase (together with the appropriate round number and with the party’s index). In addition, the dealer sends a verification key to each of the parties. To conclude, the off-line dealer gives each party the signed shares for the outer secret sharing scheme together with the verification key.

The protocol with the off-line dealer proceeds in rounds. In round ${\displaystyle i}$ of the protocol, all parties broadcast their (signed) shares in the outer ${\displaystyle \left({t+1}\right)}$-out- of-${\displaystyle m}$ secret-sharing scheme. Thereafter, each party can unmask the message it receives (with its share in the appropriate 2-out-of-2 secret-sharing scheme) to obtain its shares in the ${\displaystyle |L|}$-out-of-${\displaystyle |L|}$ inner secret-sharing of the values ${\displaystyle \sigma _{L}^{i}}$ (for the appropriate sets ${\displaystyle Q_{L}}$’s to which the party belongs). If a party stops broadcasting messages or broadcasts improperly signs messages, then all other parties consider it as aborted. If ${\displaystyle m-t}$ or more parties abort, the remaining parties reconstruct the value of the set that contains all of them, i.e., ${\displaystyle \sigma _{L}^{i-1}}$. If the premature termination occurs in the first round, then the remaining active parties engage in a fully secure protocol (with honest majority) to compute ${\displaystyle f_{n}}$.

The use of the outer secret-sharing scheme with threshold ${\displaystyle t+1}$ plays a crucial role in eliminating the on-line dealer. On the one hand, it guarantees that an adversary, corrupting at most ${\displaystyle t}$ parties, cannot reconstruct the shares of round ${\displaystyle i}$ before round i${\displaystyle i}$. On the other hand, at least ${\displaystyle m-t}$ parties must abort to prevent the reconstruction of the outer secret-sharing scheme (this is why we cannot proceed after ${\displaystyle m-t}$ parties aborted). Furthermore, since ${\displaystyle t\leqslant {2m/3}}$, when at least ${\displaystyle m-t}$ corrupt parties aborted, there is an honest majority. To see this, assume that at least ${\displaystyle m-t}$ corrupt parties aborted. Thus, at most ${\displaystyle t-\left(m-t\right)={2t-m}}$ corrupt parties are active. There are ${\displaystyle m-t}$ honest parties (which are obviously active), therefore, as 2t — m < m — t ${\displaystyle 2t-m<{m-t}}$(since ${\displaystyle t<{2m/3}}$), an honest majority is achieved when at least ${\displaystyle m-t}$ parties abort. In this case we can execute a protocol with full security for the reconstruction.

Finally, we replace the off-line dealer by using a secure-with-abort and cheat- detection protocol computing the functionality computed by the dealer. This is done similarly to the preprocessing phase in [6], which in turn use the results of [23], [24]. Obtaining the outputs of this computation, an adversary is unable to infer any information regarding the input of honest parties or the output of the protocol (since it gets ${\displaystyle t}$ shares of a ${\displaystyle \left({t+1}\right)}$-out-of-${\displaystyle m}$ secret-sharing scheme). The adversary, however, can prevent the execution, at the price of at least one corrupt party being detected cheating by all other parties. In such an event, the remaining parties will start over without the detected cheating party. This goes on either until the protocol succeeds or there is an honest majority and a fully secure protocol computing ${\displaystyle f_{n}}$ is executed.

Comparison with the multiparty coin-tossing protocol of [6]. Our protocol combines ideas from the protocols of [3], [6]. However, there are some important differences between our protocol and the protocol of [6]. In the coin-tossing protocol of [6], the bits of are shared using a threshold scheme where the threshold is smaller than the size of the set ${\displaystyle Q_{L}}$. This means that a proper subset of ${\displaystyle Q_{L}}$ containing corrupt parties can reconstruct of. In coin-tossing this is not a prob¬lem since there are no inputs. However, when computing functionalities with inputs, such of might reveal information on the inputs of honest parties in ${\displaystyle Q_{L}}$, and we share of with threshold ${\displaystyle |Q_{L}|}$. As a result, we use more sets ${\displaystyle Q_{L}}$ than in [6] and the bias of the protocol is increased (put differently, to keep the same security, we need to increase the number of rounds in the protocol). For example, the protocol of [6] has small bias when there are polynomially many parties and ${\displaystyle t=m/2}$. Our protocol is efficient only when there are constant number of parties. As explained in Section 7, this difference is inherent as a protocol for general functionalities with polynomially many parties and ${\displaystyle t=m/2}$ cannot have a small bias.

### 1/p-Secure Protocol for Polynomial Range

Using an idea of [3], we modify our protocol so that it will have a small bias when the size of the range of the functionality ${\displaystyle F}$ is polynomially bounded (even if ${\displaystyle F}$ is randomized and has a big domain of inputs). The only modification is the way that each of is chosen prior to round ${\displaystyle i*}$: with probability ${\displaystyle 1/\left(2p\right)}$ we choose of as a random value in the range of fn and with probability ${\displaystyle 1-1/\left(2p\right)}$ we choose it as in Case I described in Section 4.1. More formally, in the protocol with the dealer, in the preprocessing phase we replace Case I with the following step:</br> — For each ${\displaystyle {i}\in \left\{1,\dots ,{i*-1}\right\}}$ and for each ${\displaystyle L\subseteq \left\lceil m\right\rceil }$,</br> • with probability ${\displaystyle 1/\left(2p\right)}$, the dealer selects uniformly at random ${\displaystyle z_{i}^{L}\in Z_{n}}$ and sets ${\displaystyle \sigma _{i}^{L}=z_{i}^{L}}$</br> • with the remaining probability ${\displaystyle 1-1/\left(2p\right)}$, the dealer chooses of as in Case I described in Section 4.1.</br> Similar changes are made in the protocol without the dealer.

The idea why this change improves the protocol is that now the probability that all values held by the adversary are equal prior to round ${\displaystyle i*}$ is larger, thus, the probability that the adversary guesses ${\displaystyle i*}$ is smaller. This modification, however, can cause the honest parties to output a value that is not possible given their inputs, and, in general, we cannot simulate the case (which happens with probability ${\displaystyle 1/\left(2p\right)}$) when the output is chosen with uniform distribution from the range.

## The 3-party Protocol Tolerating Two Corrupt Parties

In this section we describe an ${\displaystyle r}$-round 3-party protocol tolerating two corrupt parties. Unlike Section 4, we directly describe our protocol without any dealer. The formal description of the 3-party protocol, Protocol MPCFor3Protocolr, appears in Figure 1 and Figure 2.

We next sketch the ideas of the protocol. As in all our protocols, we construct a protocol with two phases. The first phase is a preliminary phase in which the parties compute a given functionality (securely-with-abort with cheat detection). The output of this functionality for party ${\displaystyle p_{j}}$ includes the messages that ${\displaystyle p_{j}}$ broadcasts throughout the second phase - called the interaction phase. For simplicity of presentation, in the rest of the paper, we assume that in the interaction phase of the protocol the adversary is a fail-stop adversary. That is, all parties follow the protocol with one exception: the corrupt parties may abort the computation at any time. For our protocols, this assumption is without loss of generality, since in each round there is a small number of messages that each party can send. We have already demonstrated how to limit the adversary to aborts in this case by signing (in the preprocessing phase) any such possible message. Using this assumption, we can omit the discussion regarding signing of the messages.

In the preliminary phase of the protocol, for each round ${\displaystyle i}$ and for each subset ${\displaystyle L\subset \left\{1,2,3\right\}}$ of size one or two a value ${\displaystyle \sigma _{L}^{i}}$ is chosen similarly to the way the values in the protocols in Section 4 are chosen; this value is used by the parties ${\displaystyle \left\{p_{j}:\in L\right\}}$ if the other party/parties abort in round ${\displaystyle i+1}$. Specifically, there is a special round, called ${\displaystyle i*}$, chosen with uniform distribution from {1,..., r}${\displaystyle \left\{1,\dots ,r\right\}}$. Prior to round ${\displaystyle i*}$ with the inputs of the subset and the random inputs for other party/parties. Starting in round ${\displaystyle i*}$, the value of each subset is the output ${\displaystyle \omega f_{n}}$ on the inputs of all parties.

If no party aborts during the protocol, then each party ${\displaystyle p_{j}}$ outputs the value ${\displaystyle \sigma _{\left\{j\right\}}^{r}}$. If two corrupt parties abort in some round ${\displaystyle i}$, then the third party ${\displaystyle p_{j}}$ outputs the value ${\displaystyle \sigma _{\left\{j\right\}}^{i-1}}$. The difficult case is when one party, say ${\displaystyle p_{3}}$, aborts in some round ${\displaystyle p_{1}}$. In this case one of the active parties ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$ might be corrupt. Thus, the parties execute a variant of the two-party ${\displaystyle r}$-round ${\displaystyle O/\left(1/r\right)}$-secure protocol of [3] to compute ${\displaystyle f_{n}}$. Specifically, if ${\displaystyle i>i*}$, then in each round of the two-party protocol the parties get the value ${\displaystyle \omega }$ (thus, an abort of ${\displaystyle p_{3}}$ after round ${\displaystyle i*}$ does not affect the output). If ${\displaystyle i, then we would like to execute the following protocol: (1) a new special round ${\displaystyle {i^{*}}_{\left\{1,2\right\}i}}$ is selected with uniform distribution from ${\displaystyle \left\{1,\dots ,r\right\}}$, and (2) an ${\displaystyle i}$-round protocol is executed, where prior to round ${\displaystyle {i^{*}}_{\left\{1,2\right\}i}}$ each party gets a value that depends only on its input and starting from round ${\displaystyle {i^{*}}_{\left\{1,2\right\}i}}$, each party gets ${\displaystyle \sigma _{\left\{1,2\right\}}^{i-1}}$.

Fig. 1. Functionality ShareGenFor3r.
Fig. 2. The 3-party protocol MPCFor3r for computing F .

The protocol sketched above is flawed: suppose now that ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$ are corrupt. In each round ${\displaystyle i}$ they can simulate the execution of the two-party protocol that they would have executed if ${\displaystyle p3}$ has aborted. The first round ${\displaystyle i}$ in which all the values they get in the simulated protocol are equal is ${\displaystyle i*}$. Thus, they can determine ${\displaystyle i*}$ and bias the output of the protocol with a high probability. To overcome this problem, we modify the way that ${\displaystyle i_{L,i}^{*}}$ is chosen prior to round ${\displaystyle i}$: with probability ${\displaystyle O\left(1/{\sqrt {r}}\right)}$ set ${\displaystyle i_{L,i}^{*}=1}$, and with the remaining probability choose it at random from ${\displaystyle \left\{1,\dots ,r\right\}}$. Notice that the simulated protocol in the case i*L i = 1${\displaystyle i_{L,i}^{*}=1}$ looks like the simulated protocols in rounds starting from ${\displaystyle i*}$, thus, the probability that the corrupted parties guess ${\displaystyle i*}$ is ${\displaystyle O\left({\sqrt {r}}/r\right)=O\left(1/{\sqrt {r}}\right)}$. However, a corrupt ${\displaystyle p_{2}}$ can bias the protocol by guessing ${\displaystyle i_{L,i}^{*}=1}$ and aborting in round 1 of the two-party protocol. This can cause an additional bias of at most ${\displaystyle O\left(1/{\sqrt {r}}\right)}$. All together, the resulting protocol is ${\displaystyle O\left(1/{\sqrt {r}}\right)}$-secure.

We next explain how the two-party protocol is executed. The two-party protocol of [3] has, again, two stages: a preliminary stage and an interaction phase. In our protocol, we have only one preliminary stage, in which all preliminary phases of the two-party protocols are executed simultaneously. That is, in the preliminary phase, for every round ${\displaystyle 1\leqslant i\leqslant r}$ and for every ${\displaystyle L\subset \left\{1,2,3\right\}}$ of size two, the preliminary phase of the two-party protocol of [3] is executed for ${\displaystyle L}$ (using ${\displaystyle \sigma _{L}^{i}}$ and ${\displaystyle i_{L,i}^{*}}$. Let (SlL j )jeL ${\displaystyle \left(S_{L,j}^{i}\right)_{j\in L}}$ be the two outputs of the preliminary phase that should be given to the parties indexed by ${\displaystyle L}$. Each ${\displaystyle S_{L,j}^{i}}$ for ${\displaystyle j\in L}$ is shared using a 3-out-of-3 secret sharing scheme. The output of the preliminary phase of each party includes exactly one of these shares.

Later, in each interaction round ${\displaystyle i}$, for each ${\displaystyle L\subset \left\{1,2,3\right\}}$ of size two and for each ${\displaystyle j\in L}$, the parties ${\displaystyle p_{k}}$, where ${\displaystyle k\neq j}$,execute the two party protocol of round ${\displaystyle i-1}$ using ${\displaystyle S_{\left\{1,2,1\right\},1}^{i-1}}$ and ${\displaystyle S_{\left\{1,2,1\right\},2}^{i-1}}$ respectively.

In the above, we only sketched the protocols. The formal description of the functionality computed by the preliminary phase appears in Figure 1 and the protocol appears in Figure 2. The proof that the protocol is ${\displaystyle 1/p}$-secure will appear in the full version of the paper. To construct a 3-party protocol for functionalities where the size of range is small we use the same trick used in Section 4.3: With some small probability a value given to a set is chosen from the range prior to ${\displaystyle i*}$ in the 3-party interaction and prior to ${\displaystyle i_{L,i}^{*}}$ in the two parties’ protocols. The ${\displaystyle m}$-party protocols tolerating up to ${\displaystyle m-1}$ corrupt parties, uses the same ideas as our 3-party protocols. In a preliminary phase, ${\displaystyle i*}$ and values are chosen as above. If one party aborts in some round ${\displaystyle i}$, then the remaining ${\displaystyle m-1}$ parties execute our ${\displaystyle \left(m-1\right)}$-party protocol, where if ${\displaystyle i>i*}$ then it uses ${\displaystyle i_{L,i}^{*}=1}$, and if ${\displaystyle i then ${\displaystyle i_{L,i}^{*}=1}$ with some probability and ${\displaystyle i_{L,i}^{*}}$ is random otherwise. In this ${\displaystyle \left(m-1\right)}$-party protocol, if a party aborts the remainin ${\displaystyle \left(m-2\right)}$ parties execute our ${\displaystyle \left(m-2\right)}$-party protocol (again with its special round being set to 1 with some probability), and so on.

## Best of Both Worlds — The 1/p Way

We study the question of whether or not it is possible to construct “best of both worlds” protocols, when the fall-back security guarantee is ${\displaystyle 1/p}$-security or ${\displaystyle 1/p}$-security-with-abort. We investigate whether protocols with these weaker notions of security are possible when full privacy cannot be guaranteed. In the full version of the paper, we construct protocols that guarantee full-security whenever less than half of the parties are corrupt, and ${\displaystyle 1/p}$-security-with-abort otherwise. These protocols are simpler and more efficient than the protocols that guarantee fall-back ${\displaystyle 1/p}$-(full)-security, which we describe below.

To construct the protocols that have fall-back ${\displaystyle 1/p}$-(full)-security, we show in Section 6.1 how to transform ${\displaystyle 1/p}$-secure protocols of a certain type into protocols that retain the same security for the case of no honest majority, while guaranteeing full-security whenever less than half of the parties executing the protocol are corrupt. Specifically, we will prove the following theorem.

Theorem 3. Let ${\displaystyle F}$ be an ${\displaystyle m}$-party (possibly randomized) functionality. If enhanced trap-door permutations exist, and if ${\displaystyle m}$ is constant and the size of the domain ${\displaystyle g\left(n\right)}$ and the size of the range ${\displaystyle g\left(n\right)}$ are bounded by a polynomial in the security parameter n, then for any polynomial ${\displaystyle p\left(n\right)}$ there is an ${\displaystyle r\left(n\right)}$-round ${\displaystyle 1/p\left(n\right)}$-secure protocol computing ${\displaystyle F}$ tolerating up to ${\displaystyle m-1}$ corrupt parties and, in addition, guarantees full-security in the presence of an honest majority, where ${\displaystyle r\left(n\right)=2*p\left(n\right)^{2m}*\left(d\left(n\right)*g\left(n\right)\right)^{2^{O\left(m\right)}}}$.

A similar theorem will appear in the full version of the paper for the result of applying the above transformation to the protocol implying the second item of Theorem 2. The resulting protocol has polynomially many rounds even when the number of parties is ${\displaystyle {\frac {1}{2}}}$ log log ${\displaystyle n}$ provided that the functionality is deterministic and the size of the domain of inputs is constant.

### Best of Both Worlds — The 1/p-(full)-Security Variant

In this section we show how to transform ${\displaystyle 1/p}$-secure protocols of a certain type into protocols that retain the security of the original protocol for the case of no honest majority, while guaranteeing full-security whenever less than half of the parties executing the protocol are corrupted. Intuitively, the transformation works if the original protocol has full security against a weaker adversary that can only abort at the beginning of each round (i.e., before seeing the messages of the honest parties for this round). Specifically, this transformation can be applied to all protocols in this paper that have full correctness (namely, the protocols that assume that the sizes of the domain and the range are polynomial). Note that protocols that do not have full correctness (at least for the case of honest majority) do not guarantee full-security for the case of honest majority. At the end of this section, we will hint why the resulting protocols guarantee the desired security notion. The full argument will appear in the full version of the paper.

The basic structure of protocols that can be transformed. For simplicity of presentation we first present our transformation for an (original) protocol with a certain structure. Consider an ${\displaystyle m}$-party protocol for computing a functionality <mathF[/itex] that has the following structure: The interaction starts with a preliminary phase in which the parties execute a secure-with-abort with cheat-detection protocol for computing the messages that the parties are to send in the next ${\displaystyle r}$ interaction rounds; after this phase, each party ${\displaystyle p_{j}}$ holds a (signed) message ${\displaystyle M_{j}^{i}}$ for each round ${\displaystyle 1\leqslant i\leqslant r}$. In each interaction round ${\displaystyle i}$, each party ${\displaystyle p_{j}}$ broadcasts the message ${\displaystyle M_{j}^{i}}$. Any failure of party ${\displaystyle p_{j}}$ to broadcast the signed message as prescribed by the protocol is considered as an abort of ${\displaystyle p_{j}}$. The adversary can cause the protocol to prematurely terminate by instructing some ${\displaystyle t_{A}<\left\lceil {\frac {m}{2}}\right\rceil }$ corrupted parties to abort. Unless premature termination takes place, the protocol proceeds normally (that is, as long as less than ${\displaystyle t_{A}}$ of parties have aborted). In the case of premature termination, the remaining parties engage in a protocol ${\displaystyle \Pi _{TERM}}$ for agreeing on the output of the protocol, based on the view of the parties in the protocol so far. More specifically, the decision upon the output is based on the outputs of the (remaining) parties from the preliminary phase, on the messages broadcast until round ${\displaystyle i-1}$, and on the set of parties that have aborted ${\displaystyle D}$.

Indeed, all our protocols that were described in previous sections have the above structure. For the sake of being concrete, however, in the following we will describe the transformation as applied to the protocol of Section 4.2. In this protocol ${\displaystyle \Pi _{TERM}}$ is a protocol for reconstructing the output that is always executed with a guaranteed honest majority.

The transformation. The core of the change is a mask: we add to the messages of the parties in each round. This mask is shared in a ${\displaystyle \left(\left\lfloor {\frac {m}{2}}\right\rfloor +1\right)}$-out-of-${\displaystyle m}$ secretsharing scheme. Hence, the messages of the parties disclose the original messages if and only if a majority of the parties work together to reconstruct the appropriate masks. Below we explain this change in more detail.

Denote by ${\displaystyle M_{j}^{i}}$ the message that party ${\displaystyle p_{j}}$ is instructed to broadcast in round ${\displaystyle i}$ of the original protocol. That is, the output of party ${\displaystyle p_{j}}$ from the preliminary phase of the original protocol includes the messages ${\displaystyle M_{j}^{1},\dots ,M_{j}^{r}}$. In the preliminary phase of the new protocol a random string ${\displaystyle r_{j}}$ will be selected for each party ${\displaystyle p_{j}}$ and each round ${\displaystyle i}$, and the sequence ${\displaystyle {\hat {M}}_{j}^{1},\dots ,{\hat {M}}_{j}^{r}}$ will be given to party ${\displaystyle p_{j}}$, where ${\displaystyle {\hat {M}}_{j}^{i}={\hat {M}}_{j}^{i}\oplus r_{j}^{i}}$. In addition, each party will also receive a share of ${\displaystyle r_{j}^{i}}$ in a ${\displaystyle \left(\left\lfloor {\frac {m}{2}}\right\rfloor +1\right)}$-out-of- ${\displaystyle m}$ Shamir secret-sharing scheme. The message ${\displaystyle {\hat {M}}_{j}^{1}}$ and the shares of its mask ${\displaystyle r_{j}^{i}}$ are all signed.

Each interaction round of the original protocol is turned into a two-phased round in the new protocol. In the first phase, each party ${\displaystyle p_{j}}$ broadcasts the message ${\displaystyle {\hat {M}}_{j}^{1}}$. In the second phase, the parties reconstruct all masks of round ${\displaystyle i}$ by broadcasting all shares of masks ${\displaystyle r_{j}^{i}}$, for ${\displaystyle 1\leqslant j\leqslant m}$. If both phases are completed, then the parties have the same information as in the original protocol. Any failure of party ${\displaystyle p_{j}}$ to broadcast the signed message as prescribed by the protocol is considered as an abort of ${\displaystyle p_{j}}$ (including messages added by the transformation).

The adversary can cause the protocol to prematurely terminate only by in-structing some ${\displaystyle t_{A}<\left\lfloor {\frac {m}{2}}\right\rfloor }$ corrupted parties to abort. We handle such premature termination in round ${\displaystyle i}$ by instructing the parties to behave as if premature termination has occurred at the beginning or at the end of round ${\displaystyle i}$ (i.e., at the beginning of round ${\displaystyle i+1}$). Specifically, if premature termination takes place before the reconstruction of the masks (in the second phase of round ${\displaystyle i}$) is completed, then the remaining parties will behave as if the original protocol was terminated at the beginning of round ${\displaystyle i}$. That is, they will engage in a protocol ${\displaystyle \Pi _{TERM}}$ for agreeing on the output of the protocol, based on the messages broadcast until round ${\displaystyle i-1}$ and on the set of parties that have aborted ${\displaystyle D}$. Otherwise, if the reconstruction of the masks was completed before the abort, then the remaining parties will behave as if the original protocol was terminated at the beginning of round ${\displaystyle i+1}$.

The security of the new protocol. In the full version of this paper, we argue that applying the above transformation to any of the our protocols that assume that the domain and the range are polynomial, results in a protocol that is (i) fully secure against a malicious adversary that can corrupt any strict minority of the parties, and (ii) ${\displaystyle 1/p}$-secure against a malicious adversary that can corrupt up to ${\displaystyle t}$ parties. Furthermore, we will show that this is true for any protocol that has the structure defined above and, in addition, satisfies a few simple requirements.

We now give some intuition for why this is true if the transformation is applied to the protocol of Section 4.2. We need to consider two cases. In the case that at list half of the parties are malicious, it is quite straightforward to see that the adversary attacking the transformed protocol is not any more powerful than an adversary for the original protocol, since once the adversary sees the messages of the corrupted parties, the masks add no new information.

In the case of an honest majority, the shares of ${\displaystyle r_{j}^{i}}$ that the corrupted parties see, do not reveal anything to the adversary as long as the shares of honest parties are not revealed (these shares are only revealed in the second phase of round ${\displaystyle i}$). Thus, if the adversary causes a premature termination during the first phase of round ${\displaystyle i}$, then it has no more information than is obtained in the original protocol (by an adversary corrupting the same subset of parties) until the beginning of round ${\displaystyle i}$. If it aborts after the first phase, then the honest parties will succeed in reconstructing the masks. Thus, the adversary is no more powerful then an adversary for the original protocol that can only abort at the beginning of each round. However, the security of the original protocol can only be violated if the adversary causes premature termination during round ${\displaystyle i*}$. Finally, the reconstruction is fully secure in the presence of an honest majority.

## Impossibility of 1/p-secure Computation with Non-Constant Number of Parties

For deterministic functions, our protocols are efficient when the number of parties ${\displaystyle m}$ is constant and the size of the domain or range is at most polynomial (in the security parameter ${\displaystyle n}$) or when the number of parties is log log ${\displaystyle n}$ and the size of the domain is constant. We show that, in general, there is no efficient protocol when the number of parties is ${\displaystyle m\left(n\right)=\omega \left(1\right)}$ and the size of the domain is polynomial and when ${\displaystyle m\left(n\right)=\omega \left(logn\right)}$ and the size of the domain of each party is 2. That is, we prove the following two theorems.
Theorem 4. For every ${\displaystyle m\left(n\right)=\omega \left(logn\right)}$, there exists a deterministic ${\displaystyle m\left(n\right)}$ - party functionality ${\displaystyle F'}$ with domain ${\displaystyle \left\{0,1\right\}}$ that cannot be ${\displaystyle 1/p}$-securely computed for ${\displaystyle p\geqslant {2+1}/poly\left(n\right)}$ without an honest majority. Theorem 5. For every ${\displaystyle m\left(n\right)=\omega \left(1\right)}$, there exists a deterministic ${\displaystyle m\left(n\right)}$-party functionality ${\displaystyle F''}$ with domain ${\displaystyle \left\{0,1\right\}^{logn}}$ that cannot be ${\displaystyle 1/p}$-securely computed for ${\displaystyle \geqslant 2+1}$ without an honest majority.

### Impossibility of Achieving “The Best of Both Worlds” for General Functionalities

Above we showed that ${\displaystyle 1/p}$-secure computation is impossible in general when the number of parties is ${\displaystyle m\left(n\right)=\omega \left(1\right)}$ and the size of the domain is polynomial and when ${\displaystyle m\left(n\right)=\omega \left(logn\right)}$ and the size of the domain of each party is 2. Since a “Best of Both Worlds” type protocol with fall-back ${\displaystyle 1/p}$-security is in particular ${\displaystyle 1/p}$- secure, the same impossibility results are implied for protocols of this type (i.e., guaranteeing full-security with an honest majority and ${\displaystyle 1/p}$-security otherwise). We show that such protocols are impossible in general, even when allowing the fall-back security to be the weaker notion of ${\displaystyle 1/p}$-security-with-abort. Hence, we show that the results discussed in Section 6 are somewhat optimal.

We start by showing in that for general functionalities (i.e., where both domains and both ranges may be super-polynomial), it is impossible to construct even 3-party protocols that simultaneously achieve full-security for the case of honest majority (i.e., at most one corrupted party) and ${\displaystyle 1/p}$-security-with-abort with no honest majority. We then use this result to prove general impossibility results, that is, to prove the two following theorems:
Theorem 6. For every ${\displaystyle m\left(n\right)=\omega \left(logn\right)}$, there exists a deterministic ${\displaystyle m\left(n\right)}$ - party functionality ${\displaystyle F'}$ with domain ${\displaystyle \left\{0,1\right\}}$ that cannot be computed simultaneously guaranteeing full-security with an honest majority and ${\displaystyle 1/p}$-security-with-abort for ${\displaystyle p\geqslant {2+1/poly\left(n\right)}}$ against an adversary controlling ${\displaystyle \left\lfloor m\left(n\right)/2\right\rfloor +1}$parties.
Theorem 7. For every ${\displaystyle m\left(n\right)=\omega \left(1\right)}$, there exists a deterministic ${\displaystyle m\left(n\right)}$-party functionality ${\displaystyle F''}$ with domain ${\displaystyle \left\{0,1\right\}^{logn}}$ that cannot be computed simultaneously guaranteeing full-security with an honest majority and ${\displaystyle 1/p}$-security-with-abort for ${\displaystyle p\geqslant {2+1/poly\left(n\right)}}$ against an adversary controlling ${\displaystyle \left\lfloor m\left(n\right)/2\right\rfloor +1}$ parties.

## Authors

1. Dept. of Computer Science, Ben Gurion University
2. Dept. of Computer Science, Bar Ilan University
3. Dept. of Computer Science, Bar Ilan University
4. Dept. of Computer Science, Ben Gurion University

## References

1. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In 19th STOC, pages 218-229, 1987.
2. R. Cleve. Limits on the security of coin flips when half the processors are faulty. In 18th STOC, pages 364-369, 1986.
3. S. D. Gordon and J. Katz. Partial fairness in secure two-party computation. In EUROCRYPT 2010, volume 6110 of LNCS, pages 157-176, 2010.
4. R. Cleve. Controlled gradual disclosure schemes for random bits and their applications. In CRYPTO ’89, volume 435 of LNCS, pages 573-588, 1990.
5. T. Moran, M. Naor, and G. Segev. An optimally fair coin toss. In TCC 2009, pages 1-18, 2009.
6. A. Beimel, E. Omri, and I. Orlov. Protocols for multiparty coin toss with dishonest majority. In CRYPTO 2010, volume 6223 of LNCS, pages 538-557, 2010.
7. M. Blum. How to exchange (secret) keys. ACM Trans. Comput. Syst., 1(2):175– 193, 1983.
8. M. Luby, S. Micali, and C. Rackoﬀ. How to simultaneously exchange a secret bit by ﬂipping a symmetrically-biased coin. In 24th FOCS, pages 11–21, 1983.
9. S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing con-tracts. CACM, 28(6):637–647, 1985.
10. M. Ben-Or, O. Goldreich, S. Micali, and R. Rivest. A fair protocol for signing contracts. In 12th ICALP, pages 43–52, 1985.
11. I. Damg˚ard. Practical and provably secure release of a secret and exchange of signatures. J. of Cryptology, 8(4):201–222, 1995.
12. D. Boneh and M. Naor. Timed commitments. In CRYPTO 2000, volume 1880 of LNCS, pages 236–254, 2000.
13. A. C. Yao. How to generate and exchange secrets. In 27th FOCS, pages 162–167, 1986.
14. Z. Galil, S. Haber, and M. Yung. Cryptographic computation: Secure fault-tolerant protocols and the public-key model. In CRYPTO ’87, volume 293 of LNCS, pages 135–155, 1988.
15. D. Beaver and S. Goldwasser. Multiparty computation with faulty ma jority. In 30th FOCS, pages 468–473, 1989.
16. S. Goldwasser and L. Levin. Fair computation of general functions in presence of immoral ma jority. In CRYPTO ’90, volume 537 of LNCS, pages 77–93, 1991.
17. B. Pinkas. Fair secure two-party computation. In EUROCRYPT 2003, volume 2656 of LNCS, pages 87–105, 2003.
18. S. D. Gordon, C. Hazay, J. Katz, and Y. Lindell. Complete fairness in secure two-party computation. In 40th STOC, pages 413–422, 2008.
19. S. D. Gordon and J. Katz. Complete fairness in multi-party computation without an honest ma jority. In TCC 2009, pages 19–35, Berlin, Heidelberg, 2009.
20. S. D. Gordon, Y. Ishai, T. Moran, R. Ostrovsky, and A. Sahai. On complete primitives for fairness. In TCC 2010, volume 5978 of LNCS, pages 91–108, 2010.
21. Y. Ishai, J. Katz, E. Kushilevitz, Y. Lindell, and E. Petrank. On achieving the “best of both world” in secure multiparty computation. SIAM J. on Computing, 40(1), 2011. Journal version of [20, 21].
22. J. Katz. On achieving the “best of both worlds” in secure multiparty computation. In 39th STOC, pages 11–20, 2007.
23. R. Pass. Bounded-concurrent secure multi-party computation with a dishonest ma jority. In 36th STOC, pages 232–241, 2004.
24. D. Beaver, S. Micali, and P. Rogaway. The round complexity of secure protocols. In 22nd STOC, pages 503–513, 1990.

Annotation. Secure encryption for messages, depending on the key (KDM) is a new area that has attracted many researchers in recent years. Roughly speaking, the safety circuit KDM respect to the set of functions ${\displaystyle ~F}$ provides security, even if the message is encrypted KDM ${\displaystyle ~f(sk)}$ for all ${\displaystyle ~f\in F}$ . We present an effective scheme of construction of public key encryption, which KDM is safe for a wide range of functions ${\displaystyle ~F}$ .Our set of functions includes functions computed by polynomial arithmetic modular chain (MAC); we present a variety of programs like a straight line, compute multivariate polynomials (extended scheme includes all the rational function whose numerator and denominator which are described in the paper). Unlike previous schemes, our is flexible: the size of the ciphertext depends on the degree of polynomials, and so all the parameters of the circuit are completely independent of the size or number of the functions of secret keys (users). We note that although KDM security is the practical application of all previous work with the standard model or have ineffective results in the common set of functions that are valid for a small set of linear functions. The effectiveness of our scheme is much more compared to the previous results.

## Introduction

Working with the public key systems, protected from intruders who have the ability to request cipher text, is a very active area of research at the moment. Initial schemes developed in this area, called "circular"[CL01] Camenisch, J., Lysyanskaya, A.: An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001) </ref>and allows you to encrypt a secret key or a linear function of the secret key; later, it was considered more general functions, and safety of these schemes is called safe for KDM Posts [BRS02] Black, J., Rogaway, P., Shrimpton, T.: Encryption-Scheme Security in the Presence of Key-Dependent Messages. In: Nyberg, K., Heys, H.M. (eds.)SAC 2002. LNCS, vol. 2595, pp. 62–75. Springer, Heidelberg (2003) </ref>. In particular, we say that the scheme is a public key encryption(PKE) KDM [ ${\displaystyle ~F}$ ] Safe (where ${\displaystyle ~F}$ is a class of functions) if it is safe, even in relation to the enemy, having public keys${\displaystyle ~pk_{1},...,pk_{n}}$ and has access to encrypted messages KDM${\displaystyle ~f(sk_{1},...,sk_{n})}$ for adaptively selected functions${\displaystyle ~f\ni F}$ .

Recent studies, initially motivated by the fact that in some systems the keys encrypt other keys (thanks to the scheme itself or misuse of protocols), showed the presence of other reasons for studying KDM security. From a theoretical point of view, KDM security can be used to "reconcile" the two basic approaches to security, security on the basis of equity and indistinguishable Yao safety [AR00] Abadi, M., Rogaway, P.: Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption). In: Watanabe, O.,Hagiya, M., Ito, T., van Leeuwen, J., Mosses, P.D. (eds.) TCS 2000. LNCS,vol. 1872, pp. 3–22. Springer, Heidelberg (2000); J. Cryptology 15(2), 103–127 (2002), J. Cryptology 20(3), 395 (2007) </ref> [ABHS05] Ad˜ao, P., Bana, G., Herzog, J., Scedrov, A.: Soundness of Formal Encryption in the Presence of Key-Cycles. In: di Vimercati, S.d.C., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 374–396.Springer, Heidelberg (2005)</ref> [BPS08] Backes, M., Pfitzmann, B., Scedrov, A.: Key-dependent message security under active attacks - BRSIM/UC-soundness of Dolev-Yao-style encryption with key cycles. In: CSF 2007, pp. 112–124 (2008); Journal of Computer Security 16(5), 497–530 (2008)</ref>. This concept has a wonderful relationship with other fundamental concepts, cryptographic agility[ABBC10] Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic Agility and Its Relation to Circular Encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403–422. Springer, Heidelberg (2010) </ref>,and entanglement [CKVW10] Canetti, R., Tauman Kalai, Y., Varia, M., Wichs, D.: On Symmetric Encryption and Point Obfuscation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 52–71. Springer, Heidelberg (2010) </ref>.From a practical standpoint, KDM security is crucial for the development of some cryptographic protocols. For example, this concept is used in anonymous credential systems [CL01] Camenisch, J., Lysyanskaya, A.: An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001)</ref>Where KDM secure encryption is used to prevent the delegation of powers. Another example is a fully-homomorphic encryption where KDM security is used to achieve an unlimited build [G09] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169–178 (2009)</ref>.

Almost all of the previous work on the KDM security were focused on finding KDM [ ${\displaystyle ~F}$ ] (standard model) secure coding schemes, public key encryption function class${\displaystyle ~F}$ ,that is feasible without paying attention to efficiency. KDM security for the largest variety of functions - all functions Limited Boolean circuit - was reached Barak Haytnerom, Hofheinz and Yishai [BHHI10] Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded Key-Dependent Message Security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS,vol. 6110, pp. 423–444. Springer, Heidelberg (2010)</ref>,Following previous work, such as [BHHO08] Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-Secure Encryption from Decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008) </ref> [BHHO08] Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-Secure Encryption from Decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008)</ref>.Nevertheless, in all these schemes work very inefficient. For example, even the most effective scheme of work </ref> требует вычисления ${\displaystyle ~\Theta (k)}$exponentiation for your group${\displaystyle ~G}$ for each bit of a secret key. Here${\displaystyle ~k}$ is the parameter security. This leads to the presence of${\displaystyle ~\Theta (k^{2})}$ loss compared to a standard El-Gamal encryption, which can be encrypted ${\displaystyle ~k}$bit by doing ${\displaystyle ~\Theta (1)}$ exponentiation. Work Appelbaum, Kesha, Paykerta and Saha [ACPS09] Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems.In: C 2009, pp. 595–618 (2009) </ref> It is the only one in which the efficacy and safety of KDM scheme and proposed scheme is much more effective than the others. Nevertheless, this work is safe only for KDM linear function classes. We discuss previous work in more detail in Section 1.7.

### Our Mission

' Effective encryption with a lot of inquiries. 'In this paper we consider the problem of finding effective KDM safe circuits that allow the enemy to choose from a large variety of functions ${\displaystyle ~F}$ for the secret key. The effectiveness of the scheme should be comparable to El Gamalevym encryption (at least for a permanent set of functions), is a semantically secure encryption (and much better than in previous works ,which requires at least ${\displaystyle ~\Theta (k^{2})}$calculations for El-Gamal case).

Building an effective KDM [${\displaystyle ~F}$] Safe scheme for large${\displaystyle ~F}$ It is a challenge, and techniques from previous works are ineffective for this purpose. Indeed, all previous work in the standard model, or offer inefficient results, or have a noticeable computational overhead [CCS09] Camenisch, J., Chandran, N., Shoup, V.: A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 351–368. Springer, Heidelberg (2009)</ref>BG10] Brakerski, Z., Goldwasser, S.: Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back). In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1–20. Springer, Heidelberg (2010), Full paper is available at eprint 2010/226 </ref>,or apply to a small class of functions, such as linear.

Flexible options. 'Another important factor that has been ignored in the past, that's what we call flexible circuit parameters, dealing with restrictions on the choice of parameters in functions ${\displaystyle ~F}$ ,and when they should be limited (to determine). Consider, for example, the number of ${\displaystyle ~n}$ keys (users) in ${\displaystyle ~f(sk_{1},...,sk_{2})}$. Some schemes (e.g. ) do not allow to freely choose${\displaystyle ~n}$, but rather require the selection of the maximum${\displaystyle ~n}$to generate the keys, and the proof of KDM Security severely limits the scheme. It is obvious that we need a flexible system that allows unlimited choice (freely definable)${\displaystyle ~n}$even after key generation.

To determine the flexibility, we consider the following parameters: the number of key, the circuit size of functions, and the degree of the polynomial. For these parameters, we will find out whether they should be defined (limited) as the entrance for the (1) key generation, (2) encryption, or (3) does remain unlimited. In operation they are listed in order of increasing flexibility.

### Our results

We create such intelligent encryption (e.g., message encryption schemes in blocks rather than bit by bit), which is efficient, flexible and KDM provides security against a large number of functions based on the assumption DCR.   Roughly speaking, our scheme provides security for KDM polynomial and rational functions (ratio of two polynomials) for a set of integers(${\displaystyle ~N}$ in absolute value), which allows an unlimited number of key schemes of unlimited size, compute polynomials of degree limited only by the encryption. This is the first time determined by the flexibility, and the first time for KDM security reached a level of flexibility (without depending on the number of keys without depending on the time of key generation in the circuit in dependence only on the degree, without size, circuitry and time encryption ). We also give general proof with three modes for KDM security, which has been used in previous studies, including ours.

Next, we describe these issues.

### Classes of functions

Function ${\displaystyle ~f}$ It called MAC function (modular arithmetic circuit), if there is a scheme for a multi-dimensional size ${\displaystyle ~f}$,for which outputs are variables${\displaystyle ~X_{1},...,X_{n}}$ and constants of${\displaystyle ~Z_{K}}$ and wherein the run ${\displaystyle ~+,-}$ or ${\displaystyle ~\cdot }$ for a plurality of ${\displaystyle ~Z_{K}}$ . I.e, ${\displaystyle ~f}$ MAC is computable if and only if it can be calculated from the variables and constants${\displaystyle ~Z-{K}}$ , applying${\displaystyle ~+,-}$ and ${\displaystyle ~\cdot }$ modulo ${\displaystyle ~K}$a large number of times (this is also called the length of the program right from the${\displaystyle ~n}$ variables in${\displaystyle ~Z_{K}}$ , which can be considered as processing multidimensional function).

Plenty of features.${\displaystyle ~MAC_{d}[K]}$ It contains functions which overall degree (as a polynomial) does not exceed ${\displaystyle ~d=poly(K)}$ ,and wherein the MAC in computable${\displaystyle ~Z_{K}}$ . Lots of features ${\displaystyle ~Q(MAC_{d}[k])}$ It is a set of functions that can be represented by the ratio (division) of the two MAC computable functions. These are two sets of functions, with respect to which our two schemes (for different ${\displaystyle ~K}$)KDM will be safe, respectively.

' The variety of functional classes . These classes are quite a few. Let's begin with${\displaystyle ~MAC_{d}[K]}$ It includes all the features that are represented by polynomials with a total degree${\displaystyle ~\leq d}$, where the calculation formula (well-formed) is a word from the set of alphabets ${\displaystyle ~\{X_{1},...,X_{n},+,\cdot ,^{m},(,),a|m\in Z,a\in Z_{N^{S-1}}\}}$ . It includes all the features that are represented by the formula, allowing this division that

${\displaystyle ~((2X_{1}+X_{2}+...+X_{n})^{10}+(X_{1}+4)...(X_{n}+4)(X_{2}+4X_{3})^{-1})^{2}+3(X_{3}^{-3}-2X_{2}^{2}X_{1})^{2}modKActually,[itex]~MAC_{d}[K]}$ Class much as these formulas can be interpreted in terms of logarithmic order scheme, while MAC schemes may be multi-dimensional procedure. MAC scheme can be modeled programs straight length with the number of variables such as the order of the scheme (i.e., by simple circuit diagrams in topological order); the result is a polynomial whose degree is only required to limit (maximum${\displaystyle ~d}$). Note that ${\displaystyle ~MAC_{d}[K]}$ may contain polynomials that have an exponential number of terms. The simplest example of such a function is

${\displaystyle ~f(X_{1},...,X_{n})=(X_{1}+...+X_{n})^{d}modK}$ для ${\displaystyle ~n=poly(k),d=poly(k)}$

This feature can be easily computed MAC scheme (with a polynomial number of chains), but it has an exponential number of terms ${\displaystyle ~\{X_{1}^{\xi _{1}}...X_{n}^{\xi _{n}}|\xi _{1}+...+\xi _{n}=d\}}$ during expansion.

On the other hand, by definition, these classes can not figure out the functions that have exponential degree (as we need a polynomial of degree for our Safe build KDM). For example,${\displaystyle ~MAC_{d}[K]}$ contains${\displaystyle ~f(X)=X^{2^{k}}}$ (although ${\displaystyle ~f}$It can be calculated according to a polynomial MAC circuit).

### Properties proposed schemes

We construct two effective intellectual KDM-secure PKE scheme as follows:

'KDM Security:' 'Our scheme will ${\displaystyle ~KDM[MAC_{d}[N^{s-1}]]}$ and ${\displaystyle ~KDM[Q(MAC_{d}[N])]}$secure, respectively, wherein ${\displaystyle ~N}$is the product of two prime numbers,${\displaystyle ~s\geq 2}$.

' Computational cost: 'encryption and decryption of our first scheme requires only${\displaystyle ~2d++4(d+2)}$Exponentiation in${\displaystyle ~Z_{N^{s}}}$ ,when encrypting (decrypting) the encrypted text from${\displaystyle ~f(sk_{1},...,sk_{n})}$ with a degree of${\displaystyle ~d}$. (For our second circuit costs twice as much).

Flexibility parameter:' In our schemes, for the first time, the number of${\displaystyle ~}$ keys for functions${\displaystyle ~f(sk_{1},...,sk_{n})}$, number ${\displaystyle ~l}$ for ${\displaystyle ~+,-,\cdot }$calculations ${\displaystyle ~f}$MAC scheme (that is, the size of the circuit), and the overall degree of ${\displaystyle ~d}$ for ${\displaystyle ~f}$ It can be freely selected by the adversary. In particular, our circuit will KDM safe even if that adversary can arbitrarily select these parameters and adaptively, and when ${\displaystyle ~n,l}$ completely restricted and${\displaystyle ~d}$needed as input to the encryption step. (An obvious upper bound for these parameters is the number of steps of the enemy, which is a polynomial ${\displaystyle ~k}$).It also means that the party that holds the encryption can choose which${\displaystyle ~d}$protect each encryption, depending on the level of sensitivity or risk KDM alleged attack.

Moreover, the effectiveness of our scheme (both in terms of computational cost, and for the length of the ciphertext) are independent of${\displaystyle ~n,l}$ . Our schemes therefore remain effective, even if these parameters are quite large. This is in contrast to the previously proposed schemes, as will be shown below.

### Proof model with three modes

For our proof of security, we give a general framework for evidence KDM safety evidence for a model with three modes, which clarifies its structure and highlights the important parts. In fact, the definition of security KDM includes an opponent who can gain access to the encryption algorithm, encryption for inquiring${\displaystyle ~f(sk_{1},...sk_{n})}$ and receiving a valid dependent encryption key or a random bit encryption; the opponent should not be able to distinguish between these two cases. To prove the safety we need to model the case where the presence of any enemy violates basic assumptions. However, this is problematic, because without the private key is not clear how it is possible to simulate the calculation of the encryption functions, depending on the key, however, with a secret key, these two cases can be distinguished, and the violation of basic assumption gives no contradiction.

Our proof model with three modes solves this problem by preparing a three-game (or "modes") to provide evidence of safety and with a double simulation, where the first secret key is not known, and the second is known. The first and last game within the normal encryption key dependent on a random encryption and, as indicated above. The key idea is to find an intermediate game where encryption is not dependent on the secret key, but that it was not distinguishable from the first game, even when a certain secret key.

The proposed concept combines the techniques of security, as it can be shown that the known standard model KDM safe circuits,as we have a structure suitable for the model with three modes.

### Methods

${\displaystyle ~}$

We informally and did not accurately describe our basic ideas, but try to give a good understanding. We use the following approach.

- Building an effective intellectual KDM-secure PKE scheme in relation to a moderately large and simple sets. - Reduce security KDM PKE with respect to a sufficiently large and complex set up KDM security in relation to, due to the "compression" of the structure MAC scheme in a simple structure.

It is important to choose carefully so that it was not too big or too small. We choose the set of one-dimensional polynomials and construct KDM against the schema, based on a new idea, a cascade of El Pilar and Gamalevoy encryption, and show its compliance with safety KDM.

' KDM scheme for one-dimensional polynomial: 'cascade Pilar El Gamal encryption. We proceed from the previous works (in particular, [BG10]), reached KDM security for linear functions and bits. Converting them into intelligent modular scheme for the private key is carried out follows1. Encryption of messages M in the final scheme [BG10] is a cipher text form, where only A (M) depends on the message (El Gamal encryption); Our starting point was the work [KTY09]. KDM security relies on the fact that when the message is a linear function of the form f (x) = ax + b secret key x, its encryption is indistinguishable from encryption that is independent of (s + b), and only on a, b (such it is possible to perform simulation using the key x). To expand on this property, which is a polynomial f (x) of degree d, we mean, and we can say, as above, that is indistinguishable from the ciphertext. Now right term is independent of the secret key and the left depends, but the degree of the polynomial d-1. Our "cascade Pilar El Gamaleva" scheme thus encrypts left element to receive and apply the same idea to reduce by one degree. We can continue the recursive construction of these pairs, encoding each time the left element of the new coded message. The final ciphertext we derive as a set consisting of all elements of the right and left last.

'The reduction of the MAC schemes to the one-dimensional polynomial.' In order to achieve our common class for most of the keys, we reduce their number by setting the secret keys as the sum of a "secret" key μ and "differences" for μ2.Zatem polynomial MAC computation scheme can be re-interpreted as a one-dimensional for μ. Namely, KDM safety toward reduced to KDM safety with respect to the one-dimensional polynomial. An important point in the above process is that for the coefficients can be calculated in polynomial time, if f is a member of. This fact allows the use of polynomial-time algorithm for the simulation. That's why we use.

' The second scheme: Security MAC for private schemes. 'Ciphertext in our second scheme for the message M is a set, which is encrypted Enc first circuit and R is randomly selected element. Values ​​are the encryption "numerator" and "denominator" for KDM message, and they are evaluated two MAC functions f 'and f ". Here . Obviously, the encryption (C ', C ") KDM message is a random distribution for S. In this regard, we successfully reduce safety KDM KDM second scheme to security cipher of the first scheme. The only problem here is that the denominator can be 0 and therefore in this case can not be determined. But we can overcome this problem by changing a bit the circuit and thoroughly carry out the proof.

### Knitted working and comparison with our schemes

Figure 1 shows a comparison of the previous scheme with ours. There is κ Security Options. Note that all schemes, except for [CCS09] are KDM-CPA secure, while [CCS09] is KDM-CCA2 safe.

Explanations Fig.1 "size" represents the number of tuples in a MAC scheme, calculating function in the case of our schemes. The column "The flexibility of the parameters" describes the flexibility of parameters n, d, for the function. "The limited KeyGen" means that you need to fix the maximum settings before generating keys, KDM security is performed only when the option is less than the maximum, and the effectiveness of the scheme depends on this maximum. "The limited Enc" means that we do not have to fix such highs and KDM security holds for all values ​​of the parameter, but the parameter is required for encryption, and the effectiveness of the scheme depends on its value. "Unlim." It means that the scheme (at all stages) does not depend on the value of this parameter. Column "in the message text encryption" is the ratio between the length and the length of the encryption text messages. We note that we can improve the properties of the known circuit in Figure 1 by the use of known techniques:

- Using the technique of the work [ACPS09], the value of "text to encrypt a message" from the works [BHHO08] and [BG10] can be reduced to O (1). - If the function is limited to polynomials, [BHHI10] can be unlimited in n.

Compare with [ACPS09]: They are only concerned with linear functions in comparison with our large variety of MAC schemes, and they are based on the assumption of LWE, while we work DCR assumption.

Comparison with the [A10, A11]: These schemes reach KDM security in relation to the largest set of functions (more than we), although the scheme is the result obtained from the use of inefficient Safe computing. It is important to know the possibilities of KDM schemes, but they are not comparable with the more effective schemes, regardless of size, as in our case. This is especially important considering the application of such circuits. The size of circuit is limited in [BHHI10, A11], whereas in our model, it is unlimited, and requires only limitation degree d.

Рис.1.Options for our schemes and previous works.

Compare with [BHHO08, BGK09, BG10]: For the first time KDM security has been achieved [BHHO08]. Their scheme has been used as a basis for work [BGK09] and [BG10], which reached KDM security in relation to the set of polynomials of fixed degree for bits of secret keys (as we have said, they can describe and blocks of keys, not bits). Degree polynomials in [BGK09, BG10] should be bounded by a constant (because the length of the text in these encryption schemes grows exponentially with this degree), and thus, the algorithm KeyGen limited. In contrast, in our schemes degree polynomials limited only encryption, a number of terms may also be polynomially. For the scheme [BG10] the number of users is limited algorithm KeyGen, while it indefinitely in our schemes. Finally, the scheme [BGK09, BG10] (and to a lesser extent [BHHO08]) are less effective than our.

Other related work. The concept of security has been defined KDM Black, Hevea and Shrimpton in [BRS02], although Kamenish and Lisyanskaya in [CL01] independently identified similar concept called schematic encrypted earlier. Earlier work on security KDM studied in a model of a random algorithm. In [BDU08] shows that certain OAEP encryption KDM are safe. In [HK07] generalized KDM term security of pseudorandom functions. Building KDM safe circuits in the standard model has long been an open problem. She was partially solved in [HU08] for the case of symmetric encryption keys. First PKE, which is KDM secure in the standard model, was proposed in Bonn, Halevy, Hamburg and Ostrovsky [BHHO08]. First CCA2 and KDM secure PKE was proposed in [CCS09]. Total transformation since KDM secure PKE for a certain class of functions and to a broad class shown in [A11]. Examples PKE, that satisfy the semantic security, but KDM (in particular, 2-stage) security have been independently shown in works [GH10] and [ABBC10]. In [HH09] shows that the security of the encryption scheme for "sufficiently large" can not be proved because the proof of the reduction works with the security function and opponents of both black boxes. The relationship between the adaptive model of Dolev-Yao and generalized version of the KDM security are studied in [BPS08], at the time, subsequent connection KDM agility and safety entanglement shown in [ABBC10] and [CKVW10], respectively. We send the reader to [MTY11] to study the results of KDM Security and their applications.

## Preliminaries

Symbols and Terminology: For integers n, m ≤ n, let [n] and [m..n] be the set {1, ..., n} and {m, .., n}, respectively. For a valid x, [x] denotes the largest integer not exceeding x.

Polynomials and rational functions: polynomial (general) degree is for f. A rational function to be a function that can be written with the help of two polynomials f and g.

Group Piper: Let N be the product of two prime numbers is 1 and T + N. We define three subsets of (sets of quadratic residues, quadratic residues composite, the roots for the sets, namely:

Theorem 1 ([P99, DJ01, KTY09]). There is a polynomial time computable bijective homomorphism satisfying the following property:

Definition 2. (The assumption in the composite residue (DCR) [P99, DJ01]). Let s ≥ 2 will be a number. Then there is a generator Gen for the result N of the two safe primes that the following value for a negligible for any adversary A:

DCR Our assumption is slightly different from the original [P99, DJ01], where g is taken from a first (or second) game, but our initial assumption follows, by erecting g squared.

### KDM security

Public key encryption scheme: In this paper, the public key encryption scheme is a generator Setup to system parameters prm, such as the description of the group, and all users commonly use this parameter as the input for the other three algorithms.

Function Description: As in previous studies, we assume that all functions f have a polynomial size D. (In the case of our circuits, D is a MAC scheme or MAC computes f). After we denote the function corresponding to D.

KDM Security: For public-key encryption scheme and its spaces, secret keys and messages SkSp MeSp, performed

For simplicity, we assume that SkSp MeSp and depend only on the parameters of the system prm. For a positive integer n and the bit b, consider the following game:

In this game A is allowed to make adaptive questions:

- If A makes the i-th every new request, it generates i-th key pair and sends a response. - If A makes a request of i-th (i, D) from where i [n] and D is the description function, the algorithm responds to the following questions C (is a fixed element MeSp and n is the number of keys generated):

We will argue that the scheme is safe, if the next value is negligible for any n and any algorithm A.

You can easily check that this definition does not depend on the choice, if the property meets indistinguishable. Our definition of KDM security stronger than in previous works [BRS02, BHHO08]: it allows the enemy is adaptive to receive a new key, while previous work [BRS02, BHHO08] do not permit. (In other words, using the terminology of Section 1.4, the number of keys n becomes "unlimited"). Some known circuits (e.g., [BG10]) require fixing maximum n to generate keys and security KDM they can only be demonstrated when n is less than a predetermined maximum. Our scheme does not require fixation n and therefore it can be proved property KDM strict security.

### Modular arithmetic circuits

Definition 3 (modular arithmetic circuits (MAC)). Modular arithmetic circuit D (MAC) is a diagram for inputs which are variables and constants, and there are performed operations +, -, • or for longer. (We emphasize that in this case the chain is unlimited). For the MAC-D scheme, the number of transactions in D is dimension D. Note that in our case the MAC scheme equivalent to the length of the programs directly with an unlimited number of registers. It is obvious that the function computed MAC is a polynomial of the scheme. We write as a function f, when the MAC-D scheme computes f. For the natural numbers is the set of all rational functions, which can be calculated using a MAC-D schemes with the size and 3.Zdes n specifies the number of inputs for D.

## KDM safe circuit with respect to the MAC schemes with a limited degree

Cascading Pilar El-Gamal encryption: Our scheme is called a d cascade El Pilar Gamalevoy recursively calculated as follows. First performed "El Pilar Gamaleva" encryption for message M, where T = N + 1 and. Then, the left term is also encrypted cipher text on "Pilar El Gamal" and get to where. Then we ask how. (Please note that most of the encryption does not depend on the message and can be carried out independently with regard to the degree of the border as El Gamaleva scheme, but with much greater capacity). d cascade El Pilar Gamaleva encryption scheme is a set of M

Detailed scheme: Our system uses security settings κ and ξ, and s ≥ 2 and d are positive integers. The scheme is as follows: - Creates N values of the two prime numbers with a bit length. Is randomly selected and displayed. (A T we denote the 1 + N.)

3 - Overall degree polynomials can not be computable from D in polynomial time. But this fact is not a problem in our case, because we can easily calculate the upper limit for the total degree in D.

- Is randomly selected, is calculated and displayed.

- for selected randomly and displayed where

- With the sum as output

Where L is a function defined in Theorem 1.

Security: We prove the following theorem in Section 6.

Theorem 4 (KDM security of our scheme with respect to). For any multidimensional security settings to, the proposed scheme is secure KDM against the assumption under the DCR.

In particular, for any multi-dimensional, and any polynomial-time enemy A, KDM violates the security of our scheme, there is the enemy B, violates DCR assumption and satisfying

Where q is the number of requests for the A, determines the number of computing steps for computers and E represents the total computational cost for. We can show a stronger version of Theorem 4, where the enemy can directly select parameters when making inquiries cipher. (Specifically, d It becomes limited and unlimited, as specified in Section 1.4). Proof of strict level of security similar to the proof of Theorem 4. Therefore, we omit it.

## KDM safe circuit with respect to the private MAC schemes with limited degrees

This section provides a general transformation of the safe scheme a safe scheme where defines a set of polynomials, and the set of all rational functions for. Applying this transformation to our first scheme, we can have a safe scheme. The difficulty in creating safe circuits is that the denominator to be 0 (or may be irreversible): it becomes a problem in the proof security circuit as modeling the proof (which knows sk) can not know, whether reversible or no. Therefore, we must change our scheme and prove its safety, so that you can simulate the state of the enemy, without even knowing reversibility. We take into account the complexity of factorization of K. Then the module is not possible to find a value that is not zero, but also irreversible. (If there is such, it is possible to factor K by calculation). Thus, it can be assumed that the value of either reversibly or equal to 0. Then we define the value of the function as follows, where the 1/0 and 0/0 are special characters. Note that we are not obliged to consider the other case (that is, the case where not equal to 0, but it is irreversible), in accordance with the above discussion. Let there be a public key encryption scheme whose secret keys and reports taken from for some integer K. The transformation of the schemes carried out as follows. - The statements of equals. Here, 1/0 and 0/0 are special characters. - Represents a the same thing as - Is randomly selected and evaluated

Then output

- With breaks on and calculates

After that, it shows 1/0, and if. 0/0 is displayed if. Otherwise, the phone.

Theorem 5. It is assumed complexity of factorization K. Assume the following property: for any function will be part of further security for the safety means for the scheme. Evidence. (approximate) Opponent B for the safety circuit is created from the enemy And for safety circuits as follows. B receives the public parameter prm and a plurality of public keys as input and transmits them to A. When A sends a query pair and descriptions MAC schemes, B randomly selects sets the values ​​of E 'and E "to describe the functions, respectively, sends requests receives responses C ', and C "from the opponent and sends (C', C") back to A as a response to the request. If A takes a bit, then B-bit outputs. Due to the difficulty of factorization of K values ​​will be either reversible or to 0. Thus, we can consider. In this way,

Messages that should be encoded in the following cases, it is, 1/0 and 0/0, respectively. This means that the state of the simulated enemy And B is identical to the present. This proof is difficult doable if factorization To easily administered because A may send a request (D ', D "), which is equal to 0, but irreversible. This means that R can not be equal to Ns-1 s ≥ 3.

## Proof model with three modes

### Short review

This evidence is introduced to overcome the dilemma described in section 1.5. It has three modes, the so-called standard, fake and hidden. Standard mode of the original game, KDM for security. The other two modes are as follows. (See. Figure 2)

Рис. 2.Proof model with three modes.

Fake Mode: This mode allows you to calculate the "fake cipher text" by querying the enemy (i, D), but without the use of secret keys. Counterfeit texts should be indistinguishable from the text of the standard mode under the condition where the simulation known secret keys. This invisibility can not be proved in the absence of secret keys. Instead, we have to prove this property for security encryption chance. This invisibility is an important part of the evidence KDM security.

Stealth mode: This mode allows you to calculate the "hidden text" without the help of requests opponent (i, D) and a secret key. The hidden text should be indistinguishable from the counterfeit, on the assumption that in the simulation unknown secret keys. Note that knowledge of the secret key is not required because the fake and hidden text can be calculated without the use of secret keys. This invisibility can be demonstrated using standard cryptographic security arguments secret keys. Because hidden text does not depend on the request of the enemy D, KDM safety performed well.

### Formal Description

The model with three modes for the scheme represent a couple of false modes and a hidden mode. Inputs and outputs of the algorithm are given as follows. - Adopts open parameters prm, positive integer n as inputs and outputs n pairs of keys. - Accepts the same inputs as the keys and. - It takes as input parameters open prm, a set of public keys, a natural number i, and also the description of D for the functions and displays of C. - Accepts the same inputs, except that D and outputs C. KDM security proof scheme with respect to a plurality of functions performed by the fact that the probability of success for A in the same as in the two games and, but with minor differences.

Where A is allowed to make an adaptive number of requests. He can send as the query string and bit pair. Where i ∈ [n] are integers and D is a description of the functions. From algorithms obtained the following answers:

- Returns created KgFake (in GameFake) or KgHide (in GameHide).

In the final game of the text encryption is no longer dependent on f, requested adversary A. Thus, the following theorem holds. Theorem 6. Assuming that for any polynomial enemy And there is a small function that will be less than the difference between for anyone, then the scheme will be safe. As already noted, the evidence known KDM safe circuits in standard models [BHHO08, ACPS09, BG10] can be interpreted as above.

## The proof of the first security scheme

### Interactive vector lemma>

We see Lemma, which will be used to prove the KDM security of our schemes. Let ${\displaystyle ~Gen(1^{k})}$ is a generator, outputting the value ${\displaystyle ~N}$two safe primes with the same bit length. Let ${\displaystyle ~A}$ is a polynomial adversary,${\displaystyle ~b}$ It means bits, and ${\displaystyle ~s\geq 2}$ integer. define the game ${\displaystyle ~IV_{1}}$ and ${\displaystyle ~IV_{2}}$ in the following way.

• ${\displaystyle ~IV_{1}}$ : ${\displaystyle ~N\gets Gen(1^{k},g\gets ^{\}SCR[N^{S}])}$, ${\displaystyle ~b'\gets A^{O_{b}}(s,N,g)}$, Outputs ${\displaystyle ~b'}$
• ${\displaystyle ~IV_{2}}$ : ${\displaystyle ~N\gets Gen(1^{k}),g,h\gets ^{\}SCR[N^{S}]}$, ${\displaystyle ~b'\gets ^{O_{b}}(s,N,g,h)}$, Outputs ${\displaystyle ~b'}$

In these two games, the opponent ${\displaystyle ~A}$ polynomial allowed to make requests. AT${\displaystyle ~IV_{1}}$ ${\displaystyle ~A}$ can send the item${\displaystyle ~\sigma }$ from ${\displaystyle ~Z_{N^{s-1}}}$ as a query. Then ${\displaystyle ~O_{b}(\sigma )}$randomly selects ${\displaystyle ~r\gets ^{\}[[N/4]]}$and returns

${\displaystyle ~u^{*}\gets {\begin{cases}T^{\sigma }g^{r}modn^{S},&{\mbox{if }}b=1{\mbox{ }}\\g^{r}modN^{s},&{\mbox{if }}b=0{\mbox{ }}\end{cases}}}$

On the other hand,${\displaystyle ~IV_{2}}$ ${\displaystyle ~A}$ can send the item${\displaystyle ~\sigma ,{\bar {\sigma }}}$ from ${\displaystyle ~Z_{N^{s-1}}^{2}}$ as a query. Then${\displaystyle ~{\bar {O_{b}}}(\sigma ,{\bar {\sigma }})}$ randomly selects ${\displaystyle ~r\gets ^{\}[[N/4]]}$ and returns

${\displaystyle ~(u^{*},{\bar {u}}^{*}\gets {\begin{cases}T^{\sigma }g^{r},T^{\bar {\sigma }}h^{r}modN^{s},&{\mbox{if }}b=1{\mbox{ }}\\(g^{r},h^{r})modN^{s},&{\mbox{if }}b=0{\mbox{ }}\end{cases}}}$

For${\displaystyle ~k=1,2}$advantage${\displaystyle ~A}$ in ${\displaystyle ~IV_{K}}$It is defined as

${\displaystyle ~Adv.IV_{K}[A]=|Pr[b'=1|b=1]-Pr[b'=1|b=0]|.}$

Lemma 1 ((DCR) of the lemma for vector Interactive${\displaystyle ~k=1,2,}$ Full version).
For ${\displaystyle ~k=1,2,}$ none polynomial opponent can not be negligible advantage ${\displaystyle ~IV_{K}}$ when DCR assumption.

Our definition of games ${\displaystyle ~IV_{K}}$ a little different from :The original game takes an accident${\displaystyle ~r}$ for ${\displaystyle ~g^{r}}$ not from${\displaystyle ~[N/4]}$, and from${\displaystyle ~T^{2}}$ for some fixed values${\displaystyle ~T\geq N^{S}}$. This difference is not significant, since the accident ${\displaystyle ~r}$ for the original games taken from${\displaystyle ~[T^{2}]}$ in order to ensure the proximity distribution${\displaystyle ~g^{r}}$ a uniform distribution${\displaystyle ~SCR[N^{S}]}$. We can show that the same is true even when the${\displaystyle ~r}$ is selected from ${\displaystyle ~[[N/4]]}$.

### The proof for the case where the number n is equal to 1 Keys

${\displaystyle ~}$

Before proving the safety of our scheme, consider the game${\displaystyle ~GameKDM_{A}^{1}[MAC]}$ for ${\displaystyle ~n=1}$.(Here, we simply write${\displaystyle ~MAC}$ instead ${\displaystyle ~MAC_{n,d,l}[N^{s-1}]}$ ).

Enemy ${\displaystyle ~A}$in this game takes options open${\displaystyle ~prm=(s,N,g)}$ and a public key ${\displaystyle ~pk=h=g^{x}modN^{s}}$ as inputs. Whenever ${\displaystyle ~A}$ It sends a request "description" function ${\displaystyle ~F}$ , called ${\displaystyle ~MAC}$${\displaystyle ~D}$,bidder sends back

${\displaystyle ~C=(u_{d}^{-1},u_{d-1}^{-1}v_{d},...,u_{0}^{-1}v_{1},T^{f_{D}x}v_{0})}$

where ${\displaystyle ~f_{D}}$ It is a function corresponding to${\displaystyle ~D}$ and ${\displaystyle ~(u_{k},v_{k})=(g^{r_{k}},h^{r_{k}})}$ for ${\displaystyle ~r_{k}\gets [N/4]}$ . Since the number of keys is equal to${\displaystyle ~1}$, then ${\displaystyle ~f_{D}}$It can be written as ${\displaystyle ~f_{D}(Y)=\sum {}{}_{j}a_{j}Y^{j}modN^{S}}$ for some ${\displaystyle ~(a_{j})_{j\in [0...d]}}$ . At the end of the bit outputs ${\displaystyle ~b'}$.

Security here is proved on the basis of the evidence for a model with three modes of section 5. Algorithms and KgFake EncFake defined as follows.

• ${\displaystyle ~KgFake(prm)}$ : The same algorithm that${\displaystyle ~Kg}$,except that it establishes${\displaystyle ~aux}$ for the zero line.
• ${\displaystyle ~EncFake(prm,pk,aux,D)}$ : Splits ${\displaystyle ~prm}$ and ${\displaystyle ~pk}$ how ${\displaystyle ~(s,N,g)}$ and ${\displaystyle ~h}$.Take${\displaystyle ~r_{k}\gets ^{\}[N/4]}$ and is calculated ${\displaystyle ~(u_{k},v_{k})\gets (g^{r_{k}},h^{r_{k}})}$ for ${\displaystyle ~k\in [d]}$ .Let ${\displaystyle ~f_{D}(Y)=sum{}{}_{j}a_{j}Y^{j}modN^{s}}$ . Calculates and displays the "fake text"

${\displaystyle ~C_{Fake}=(u_{d}^{-1},T^{a_{d}}u_{d-1}^{-1}v_{d},...,T^{a_{1}}u_{0}^{-1}v_{1},T^{a_{0}}v_{0})}$

We show that the difference ${\displaystyle ~|Pr[GameKDM_{A}^{1}[MAC,1]=1]-Pr[GameFake_{A}[Mac,1]=1]}$ negligible. To this end, the enemy${\displaystyle ~B}$ for Game ${\displaystyle ~IV_{k}}$ for ${\displaystyle ~k=1}$ It is generated as follows. And receives inputs ${\displaystyle ~(s,N,g)}$, chooses randomly ${\displaystyle ~x\gets ^{\}[2^{\zeta }\cdot [N/4]]}$ ,and sends${\displaystyle ~prm\gets (s,N,g),pk\gets f\gets g^{x}}$ to ${\displaystyle ~A}$. If${\displaystyle ~A}$ makes a request ${\displaystyle ~D}$,then ${\displaystyle ~B}$computes ${\displaystyle ~(a_{j})_{j\in [0,...,d]}}$,satisfying${\displaystyle ~f_{D}(Y)=\sum {}{}_{j}a_{j}Y^{j}modN^{}s}$. Note that ${\displaystyle ~B}$ can be calculated from these values ${\displaystyle ~D}$. ${\displaystyle ~B}$ sets

${\displaystyle ~\delta _{j}=-\sum {k=j+1}{d}a_{k}x^{k-(j+1)}}$

sends requests and receives the appropriate responses (where). Next, in selected, it calculates, computes when and sends them back to A

If A takes a bit b ', then B and outputs it stops. A-priory B, the difference between the two probabilities and insignificant. Algorithms in GameHide, ie KgHide and EncHide, defined as follows.

- KgHide (prm): Take and displayed. (It sets for aux zero line). - EncHide (prm, PK, aux): Shares prm and PK as the (s, N, g) and pk = h. Beret and calculated for. Calculates and displays "hidden text"

Namely, EncHide prints.

We show that the difference is negligible. To this end, the enemy game IVk B for k = 2 is generated as follows. B receives the input (s, N, g, h) passes to A. If A makes a request D, then. Then, in a predetermined

sends requests and receives responses (where), and sends back to A

If A takes a bit b ', then B and outputs it stops. A-priory B, the difference between the two probabilities and insignificant. By Theorem 6, our scheme KDM safe.

### The essence of the proof for the general case

In this version of the work, we present only the main ideas of the proof. They also prove useful for in Section 6.2, except that we reduce${\displaystyle ~n}$secrets${\displaystyle ~(sk_{j})_{j\in [n]}}$ to a secret ${\displaystyle ~\mu }$ for KgFake and EncFake.

In particular, KgFake for this proof takes${\displaystyle ~prm=(s,N,g)}$and the number of keys${\displaystyle ~n}$as input, selected at random${\displaystyle ~\mu \gets ^{\}[[N/4]]}$ , and ${\displaystyle ~a_{1},...,a_{n}\gets ^{\}[2^{\xi }\cdot [N/4]]}$outputs

${\displaystyle ~sk_{j}\gets x_{j}\gets \mu +a_{j}}$,${\displaystyle ~pk_{j}\gets h_{j}\gets g^{x_{j}}}$ for ${\displaystyle ~j\in [n]}$,${\displaystyle ~aux\gets (a_{j})_{j\in [n]}}$

In other words, ${\displaystyle ~(sk_{j})_{j\in [n]}}$ It is charged only for one secret ${\displaystyle ~\mu }$. Proof thus reduced to the case where the number of secrets is equal to${\displaystyle ~1}$. Description cFake also changed to be consistent with the new KgFake. In particular, it takes EncFake${\displaystyle ~prm=(s,N,g)}$,${\displaystyle ~(pk_{j})_{j\in [n]}=(h_{j})_{j\in [n]}}$ and request ${\displaystyle ~(i,D)}$ and calculates the enemy${\displaystyle ~(a_{j})_{j\in [0,...,d]}\gets Coeff_{prm}(aux,i,D)}$ . Here ${\displaystyle ~(a_{j})_{j\in [o,...,d]}=Coeff_{prm}(aux,i,D)}$ is set ${\displaystyle ~Z_{N^{a-1}}}$, satisfying the following equations for ${\displaystyle ~Y}$. ${\displaystyle ~d}$ here means the total level for${\displaystyle ~f_{D}}$

${\displaystyle ~f_{D}(Y+\alpha _{1},...,Y+\alpha _{n})=\sum _{j=0}^{d}aj(Y+\alpha _{i})^{j}modN^{s-1}}$.

cFake then outputs a "fake encryption"

${\displaystyle ~C_{Fake}=(u_{d}^{-1},T^{a_{d}}u_{d-1}^{-1}v_{d},...,T^{a_{1}}U_{0}^{-1}v_{1},T^{a_{0}}v_{0})}$

where${\displaystyle ~(u_{k},v_{k})=(g^{r_{k}},h_{i}^{r_{k}})}$ for${\displaystyle ~r){k}\gets ^{\}[N/4]}$ . (We emphasize that${\displaystyle ~v_{k}}$ It is calculated using the i-th public key${\displaystyle ~h_{i}}$ , where${\displaystyle ~i}$ this part of the request ${\displaystyle ~(i,D)}$

Lemma 2
Taking${\displaystyle ~aux=(\alpha _{j})_{j\in [n]},i\in [n]}$ MACD and description,${\displaystyle ~Coeff_{prm}(aux,i,D)}$It can be computed in polynomial time.

KgHide EncHide and can be constructed similarly. Evidence of indistinguishable games${\displaystyle ~GameKDM_{A}^{1}[MAC,n],GameFake_{A}[MAC,n],GameHide_{A}[MAC,n]}$ similar to section 6.2.

## Thanks

We thank Zvikov brokerage and Eugene Vahlina for help in some discussion of the problem. We also thank the Zvíkov, Shafi Goldwasser, Yael Tauman Kalaya and anonymous reviewers for useful conference Eurocrypt comments about our work.

## Literature

1. [AR00] Abadi, M., Rogaway, P.: Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption). In: Watanabe, O.,Hagiya, M., Ito, T., van Leeuwen, J., Mosses, P.D. (eds.) TCS 2000. LNCS,vol. 1872, pp. 3–22. Springer, Heidelberg (2000); J. Cryptology 15(2), 103–127 (2002), J. Cryptology 20(3), 395 (2007)
2. [ABBC10] Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic Agility and Its Relation to Circular Encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403–422. Springer, Heidelberg (2010)
3. [ABHS05] Ad˜ao, P., Bana, G., Herzog, J., Scedrov, A.: Soundness of Formal Encryption in the Presence of Key-Cycles. In: di Vimercati, S.d.C., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 374–396.Springer, Heidelberg (2005)
4. [A11] Applebaum, B.: Key-Dependent Message Security: Generic Amplification and Completeness Theorems. In: Paterson, K.G. (ed.) EUROCRYPT 2011.LNCS, vol. 6632, pp. 506–525. Springer, Heidelberg (2011)
5. [ACPS09] Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems.In: C 2009, pp. 595–618 (2009)
6. [BDU08] Backes, M., D¨urmuth, M., Unruh, D.: OAEP Is Secure under Key-Dependent Messages. In: Pieprzyk, J.(ed.) ASIACRYPT 2008. LNCS,vol. 5350, pp. 506–523. Springer, Heidelberg (2008)
7. [BPS08] Backes, M., Pfitzmann, B., Scedrov, A.: Key-dependent message security under active attacks - BRSIM/UC-soundness of Dolev-Yao-style encryption with key cycles. In: CSF 2007, pp. 112–124 (2008); Journal of Computer Security 16(5), 497–530 (2008)
8. [BHHI10] Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded Key-Dependent Message Security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS,vol. 6110, pp. 423–444. Springer, Heidelberg (2010)
9. [BRS02] Black, J., Rogaway, P., Shrimpton, T.: Encryption-Scheme Security in the Presence of Key-Dependent Messages. In: Nyberg, K., Heys, H.M. (eds.)SAC 2002. LNCS, vol. 2595, pp. 62–75. Springer, Heidelberg (2003)
10. [BG10] Brakerski, Z., Goldwasser, S.: Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back). In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1–20. Springer, Heidelberg (2010), Full paper is available at eprint 2010/226
11. [BGK09] Brakerski, Z., Goldwasser, S., Kalai, Y.: Circular-Secure Encryption Beyond Affine Functions. e-print. 2009/511
12. [BHHO08] Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-Secure Encryption from Decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008)
13. [BV98] Boneh, D., Venkatesan, R.: Breaking RSA May Not Be Equivalent to Factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp.59–71. Springer, Heidelberg (1998)
14. [CCS09] Camenisch, J., Chandran, N., Shoup, V.: A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 351–368. Springer, Heidelberg (2009)
15. [CL01] Camenisch, J., Lysyanskaya, A.: An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001)
16. [CKVW10] Canetti, R., Tauman Kalai, Y., Varia, M., Wichs, D.: On Symmetric Encryption and Point Obfuscation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 52–71. Springer, Heidelberg (2010)
17. [DJ01] Damg˚ard, I., Jurik, M.: A Generalization, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In: Kim, K.- c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001)
18. [G09] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169–178 (2009)
19. [GH10] Green, M., Hohenberger, S.: CPA and CCA-Secure Encryption Systems that are not 2-Circular Secure. e-print. 2010/144
20. [HH09] Haitner, I., Holenstein, T.: On the (Im)Possibility of Key Dependent Encryption. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 202–219. Springer, Heidelberg (2009)
21. [HK07] Halevi, S., Krawczyk, H.: Security under key-dependent inputs. In: ACM CCS 2007, pp. 466–475 (2007)
22. [HU08] Hofheinz, D., Unruh, D.: Towards Key-Dependent Message Security in the Standard Model. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 108–126. Springer, Heidelberg (2008)
23. [KTY09] Kiayias, A., Tsiounis, Y., Yung, M.: Group Encryption. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 181–199. Springer, Heidelberg (2007)
24. [MTY11] Malkin, T., Teranishi, I., Yung, M.: Key Dependent Message Security: Recent Results and Applications. In: ACM CODASPY (2011)
25. [P99] Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)