Search

Card-based cryptography is a secure computation protocol realized by using physical cards. There are two models on card-based cryptography: public and private models. We adopt private one that allows players to handle cards privately. While much of the existing works for card-based cryptography use two-colored cards, it is also a vital task to construct an efficient protocol with playing cards. In the public model, 2n cards are necessary for any n-bit input protocol since at least two cards are required to express a Boolean value. It holds true for both two-colored and playing-card settings. On the other hand, the private model enables us to construct a protocol with fewer than 2n cards. However, all existing protocols that achieve such properties are only in the two-colored setting. This paper shows that the private model enables us to construct a protocol with fewer than 2n cards using the playing cards. We first show two-bit input protocols with fewer than four cards for logical operations, AND, OR, and XOR. Furthermore, we show a three-input majority voting protocol using only three cards, which is constructed by combining our AND and OR protocols. Notably, our proposed protocols require no randomness. All operations are deterministic and depend only on players' private inputs. [ABSTRACT FROM AUTHOR]

Surrounding the problems that most of the current electronic voting schemes are centralized and unable to achieve anonymous voting, a secure electronic voting scheme based on blockchain and short linkable ring signature is proposed. By designing a short linkable ring signature scheme and combining with blockchain technology, a specific, secure and efficient electronic voting scheme is constructed. The system model, the formal definition of the algorithms, and the detailed description are provided. Compared with the existing schemes, this scheme allows for large ‐ scale voting, and supports multiple voting options and automatic counting of votes. The security analysis and experimental results show that this scheme can meet more security goals such as anonymity, unforgeability, and privacy, while still with advantages in terms of computational overhead. [ABSTRACT FROM AUTHOR]

We present a linear-time, space and communication data-oblivious algorithm for securely merging two private, sorted lists into a single sorted, secret-shared list in the two party setting. Although merging two sorted lists can be done insecurely in linear time, previous secure merge algorithms all require super-linear time and communication. A key feature of our construction is a novel method to obliviously traverse permuted lists in sorted order. Our algorithm only requires black-box use of the underlying additively homomorphic cryptosystem and generic secure computation protocols for comparison and equality testing. [ABSTRACT FROM AUTHOR]

Data mining has received many applications in diverse areas such as banking, marketing, healthcare and fraud detection. One of the valuable tools in data mining is principal component analysis (PCA). Computing PCA over data belonging to several data owners with respect to their privacy is a need in many industries such as healthcare. Here, we propose a privacy-preserving multi-party protocol to compute PCA over horizontally and vertically distributed data using QR matrix decomposition and homomorphic encryption. Our protocol is the first privacy-preserving PCA computation scheme which is applicable for both horizontally and vertically partitioned data and finds all of the principal components. Our protocol is secure against collusion of the data owners in the semi-honest security model. In the performance analysis, we show that in the horizontal settings increasing the number of data owners will decrease the computation overhead of each of data owners, but it will increase the communication and the computation overhead of the server. We also show that the time consumption of using our proposed scheme on Australian data set of size 690 × 14 , distributed horizontally among 50 data owners, is 4.38 s. On the Ionosphere data set of size 351 × 34 , distributed horizontally among 10 data owners, it takes 31.8 s. In the vertical distribution, the time consumption of using our scheme on Gait data set of size 48 × 321 distributed among 7 data owners and on Gastrointestinal Lesions data set of size 76 × 698 distributed among 10 data owners is 4.4 h and 15.7 h, respectively. [ABSTRACT FROM AUTHOR]

A multi-client functional encryption (MCFE ) scheme [Goldwasser–Gordon–Goyal 2014] for set intersection is a cryptographic primitive that enables an evaluator to learn the intersection from all sets of a predetermined number of clients, without need to learn the plaintext set of each individual client. Using these schemes, it is impossible to compute the set intersections from arbitrary subsets of clients, and thus, this constraint limits the range of its applications. To provide such a possibility, we redefine the syntax and security notions of MCFE schemes, and introduce flexible multi-client functional encryption (FMCFE ) schemes. We extend the aIND security of MCFE schemes to aIND security of FMCFE schemes in a straightforward way. For a universal set with polynomial size in security parameter, we propose an FMCFE construction for achieving aIND security. Our construction computes set intersection for n clients that each holds a set with m elements, in time O (n m) . We also prove the security of our construction under DDH1 that it is a variant of the symmetric external Diffie–Hellman (SXDH) assumption. [ABSTRACT FROM AUTHOR]

Homomorphic encryption (HE) method can be used to realize arithmetic operations on encrypted data. This method, however, is limited owing to its low efficiency in performing certain functions, especially those involving several multiplications. As a solution, this paper proposes a new HE-based secure computation scheme, termed as the HE for stochastic computing (HESC); this scheme can homomorphically evaluate both the stochastic addition and multiplication operations, without any bootstrapping. This HESC scheme is constructed based on additive/multiplicative HE, which only supports homomorphic addition/multiplication, and realizes the homomorphic evaluation of stochastic multiplication. The HESC employs the features of stochastic computing (SC) for homomorphic stochastic operations, where stochastic additions and multiplications are performed using random multiplexing and bit-parallel logic operations, respectively. This paper first presents a basic HESC scheme based on additive/multiplicative HE. It then presents an efficient HESC scheme that utilizes the parallelism of lattice-based cryptography (i.e., plaintext packing and vectorized homomorphic evaluation). A new stochastic addition operation is also introduced in this study, which can be used for the HESC instantiated by lattice-based cryptography. This new stochastic addition operation significantly improves the accuracy of the HESC, albeit with the trade-off of increased ciphertext size. Accordingly, this paper also proposes a technique that can reduce the size of ciphertexts, while maintaining the accuracy of the scheme. The basic performance of the HESC implemented with various HEs is demonstrated, along with its applications in polynomial functions and an oblivious inference with a neural network. Lastly, the results thus obtained indicate that the proposed scheme is more advantageous than the conventional schemes. This paper is concluded with some implications/research directions for HESC from perspectives of cryptography and HE implementations. [ABSTRACT FROM AUTHOR]

In a modern era where data-driven insights are the foundation of technological advancements, preserving the privacy and security of sensitive information while harnessing the collective intelligence of multiple parties is imperative. This research presents a Secure Collaborative Learning Algorithm (SCLA) that facilitates efficient multi-party machine learning without compromising data privacy. Our research focus is on leveraging existing, secure databases without requiring an additional data collection process. SCLA integrates homomorphic encryption and Federated Learning (FL) to enable secure data collaboration among various stakeholders. The proposed algorithm aggregates model updates in a privacy-preserving manner, demonstrating enhanced model accuracy, competitive convergence speed, and robust scalability. By carefully balancing privacy preservation and learning efficiency, the SCLA showcases a promising avenue for privacy-focused collaborative learning using existing data repositories.

Homomorphic encryption (HE) is a cryptosystem that allows the secure processing of encrypted data. One of the most popular HE schemes is the Brakerski-Fan-Vercauteren (BFV), which supports somewhat (SWHE) and fully homomorphic encryption (FHE). Since overly involved arithmetic operations of HE schemes are amenable to concurrent computation, GPU devices can be instrumental in facilitating the practical use of HE in real world applications thanks to their superior parallel processing capacity. This paper presents an optimized and highly parallelized GPU library to accelerate the BFV scheme. This library includes state-of-the-art implementations of Number Theoretic Transform (NTT) and inverse NTT that minimize the GPU kernel function calls. It makes efficient use of the GPU memory hierarchy and computes 128 NTT operations for ring dimension of 214 only in $176.1 ~\mu s$ on RTX 3060Ti GPU. To the best of our knowledge, this is the fastest implementation in the literature. The library also improves the performance of the homomorphic operations of the BFV scheme. Although the library can be independently used, it is also fully integrated with the Microsoft SEAL library, which is a well-known HE library that also implements the BFV scheme. For one ciphertext multiplication, for the ring dimension 214 and the modulus bit size of 438, our GPU implementation offers 63.4 times speedup over the SEAL library running on a high-end CPU. The library compares favorably with other state-of-the-art GPU implementations of NTT and BFV operations. Finally, we implement a privacy-preserving application that classifies encrypted genome data for tumor types and achieves speedups of 42.98 and 5.7 over CPU implementations using single and 16 threads, respectively. Our results indicate that GPU implementations can facilitate the deployment of homomorphic cryptographic libraries in real-world privacy-preserving applications.

We describe the components of the Trusted Data Space, the data-distribution infrastructure that will support society when the Innovative Optical and Wireless Network (IOWN) is widespread and all information is used by digital twins and artificial intelligence. We also describe a group of technologies (data sandbox technology, secure computation technology, secure matching technology) for achieving governance over data processing by conducting calculations in an encrypted state. [ABSTRACT FROM AUTHOR]

A private intersection-sum (PIS) scheme considers the private computing problem of how parties jointly compute the sum of associated values in the set intersection. In scenarios such as electronic voting, corporate credit investigation, and ad conversions, private data are held by different parties. However, despite two-party PIS being well-developed in many previous works, its extended version, multi-party PIS, has rarely been discussed thus far. This is because, depending on the existing works, directly initiating multiple two-party PIS instances is considered to be a straightforward way to achieve multi-party PIS; however, by using this approach, the intersection-sum results of the two parties and the data only belonging to the two-party intersection will be leaked. Therefore, achieving secure multi-party PIS is still a challenge. In this paper, we propose a secure and lightweight multi-party private intersection-sum scheme called SLMP-PIS. We maintain data privacy based on zero sharing and oblivious pseudorandom functions to compute the multi-party intersection and consider the privacy of associated values using arithmetic sharing and symmetric encryption. The security analysis results show that our protocol is proven to be secure in the standard semi-honest security model. In addition, the experiment results demonstrate that our scheme is efficient and feasible in practice. Specifically, when the number of participants is five, the efficiency can be increased by 22.98%. [ABSTRACT FROM AUTHOR]

The development of quantum computers has been progressing rapidly in recent years based on principles fundamentally different from those of conventional computers. It is known that they can be used to break many of the encryption schemes that are now in actual use. To counter this threat, there is a need for "post-quantum cryptography" that cannot be broken even by quantum computers. In this interview, we asked NTT Distinguished Researcher Takashi Yamakawa to tell about his research in solving such social issues using cryptography. [ABSTRACT FROM AUTHOR]

Garbling schemes, invented in the 80’s by Yao (FOCS’86), have been a versatile and fundamental tool in modern cryptography. A prominent application of garbled circuits is constant round secure two-party computation, which led to a long line of study of this object, where one of the most influential optimizations is Free-XOR (Kolesnikov and Schneider ICALP’08), introducing a global offset Δ for all garbled wire values where XOR gates are computed locally without garbling them. To date, garbling schemes were not studied per their side-channel attacks (SCA) security characteristics, even though SCA pose a significant security threat to cryptographic devices. In this research we, demonstrate that adversaries utilizing advanced SCA tools such as horizontal attacks, mixed with advanced hypothesis building and standard (vertical) SCA tools, can jeopardize garbling implementations. Our main observation is that garbling schemes utilizing a global secret Δ open a door to quite trivial side-channel attacks. We model our side-channel attacks on the garbler’s device and discuss the asymmetric setting where various computations are not performed on the evaluator side. This enables dangerous leakage extraction on the garbler and renders our attack impossible on the evaluator’s side. Theoretically, we first demonstrate on a simulated environment, that such attacks are quite devastating. Concretely, our attack is capable of extracting Δ when the circuit embeds only 8 input non-linear gates with fifth/first-order attack Success-Rates of 0.65/0.7. With as little as 3 such gates, our attack reduces the first-order Guessing Entropy of Δ from 128 to ∼ 48-bits. We further demonstrate our attack via an implementation and power measurements data over an STM 32-bit processor software implementing circuit garbling, and discuss their limitations and mitigation tactics on logical, protocol and implementation layers.

Consumers in electricity markets are becoming more proactive because of the rapid development of demand–response management and distributed energy resources, which boost the transformation of peer-to-peer (P2P) energy-trading mechanisms. However, in the P2P negotiation process, it is a challenging task to prevent private information from being attacked by malicious agents. In this paper, we propose a privacy-preserving, two-party, secure computation mechanism for consensus-based P2P energy trading. First, a novel P2P negotiation mechanism for energy trading is proposed based on the consensus + innovation (C + I) method and the power transfer distribution factor (PTDF), and this mechanism can simultaneously maximize social welfare and maintain physical network constraints. In addition, the C + I method only requires a minimum set of information to be exchanged. Then, we analyze the strategy of malicious neighboring agents colluding to attack in order to steal private information. To defend against this attack, we propose a two-party, secure computation mechanism in order to realize safe negotiation between each pair of prosumers based on Paillier homomorphic encryption (HE), a smart contract (SC), and zero-knowledge proof (ZKP). The energy price is updated in a safe way without leaking any private information. Finally, we simulate the functionality of the privacy-preserving mechanism in terms of convergence performance, computational efficiency, scalability, and SC operations. [ABSTRACT FROM AUTHOR]

In this paper, we propose CryptMed, a system framework that enables medical service providers to offer secure, lightweight, and accurate medical diagnostic service to their customers via an execution of neural network inference in the ciphertext domain. CryptMed ensures the privacy of both parties with cryptographic guarantees. Our technical contributions include: 1) presenting a secret sharing based inference protocol that can well cope with the commonly-used linear and non-linear NN layers; 2) devising optimized secure comparison function that can efficiently support comparison-based activation functions in NN architectures; 3) constructing a suite of secure smooth functions built on precise approximation approaches for accurate medical diagnoses. We evaluate CryptMed on 6 neural network architectures across a wide range of non-linear activation functions over two benchmark and four real-world medical datasets. We comprehensively compare our system with prior art in terms of end-to-end service workload and prediction accuracy. Our empirical results demonstrate that CryptMed achieves up to respectively 413x, 19x, and 43x bandwidth savings for MNIST, CIFAR-10, and medical applications compared with prior art. For the smooth activation based inference, the best choice of our proposed approximations preserve the precision of original functions, with less than 1.2% accuracy loss and could enhance the precision due to the newly introduced activation function family. [ABSTRACT FROM AUTHOR]

Secure computation can be divided into those using homomorphic encryption and secret sharing. The advantage of the former method is that the computation can be performed on a single computing server and the computation process can be made public if the encryption key used is securely managed. However, the latter is computationally light and capable of high-speed processing, but it requires multiple independently managed computing servers, and processes of $k$ or more servers cannot be disclosed. When considering a business model for implementing secure computation that uses secret sharing, private information can be leaked if computing servers are managed by the same organization. Therefore, we need a complex business model in which multiple companies without conflicts of interest manage each computing server independently and make a profit. However, this approach is difficult to implement in practice. In this study, we proposed a secure computation using secret sharing. Moreover, by effectively using TTP, we demonstrated that it is possible to realize secure computation with a single computing server. In addition, we demonstrated that, if the security keys used are securely managed, the entire computational process can be made public. In other words, we realize a method that addresses all the drawbacks of the aforementioned methods, and it is possible to realize faster and more secure computations than conventional methods using secret sharing.

Secure computation enables n mutually distrustful parties to compute a function over their private inputs jointly. In 1988, Ben-Or, Goldwasser, and Wigderson (BGW) proved that any function can be computed with perfect security in the presence of a malicious adversary corrupting at most t < n / 3 parties. After more than 30 years, protocols with perfect malicious security, and round complexity proportional to the circuit’s depth, still require (verifiably) sharing a total of O (n 2) values per multiplication. In contrast, only O(n) values need to be shared per multiplication to achieve semi-honest security. Sharing Ω (n) values for a single multiplication seems to be the natural barrier for polynomial secret-sharing-based multiplication. In this paper, we construct a new secure computation protocol with perfect, optimal resilience and malicious security that incurs (verifiably) sharing O(n) values per multiplication. Our protocol requires a constant number of rounds per multiplication. Like BGW, it has an overall round complexity that is proportional only to the multiplicative depth of the circuit. Our improvement is obtained by a novel construction for weak VSS for polynomials of degree 2t, which incurs the same communication and round complexities as the state-of-the-art constructions for VSS for polynomials of degree t. Our second contribution is a method for reducing the communication complexity for any depth 1 sub-circuit to be proportional only to the size of the input and output (rather than the size of the circuit). This implies protocols with sub-linear communication complexity (in the size of the circuit) for perfectly secure computation for important functions like matrix multiplication. [ABSTRACT FROM AUTHOR]

The rapidly growing scale and variety of biomedical data repositories raise important privacy concerns. Conventional frameworks for collecting and sharing human subject data offer limited privacy protection, often necessitating the creation of data silos. Privacy-enhancing technologies (PETs) promise to safeguard these data and broaden their usage by providing means to share and analyze sensitive data while protecting privacy. Here, we review prominent PETs and illustrate their role in advancing biomedicine. We describe key use cases of PETs and their latest technical advances and highlight recent applications of PETs in a range of biomedical domains. We conclude by discussing outstanding challenges and social considerations that need to be addressed to facilitate a broader adoption of PETs in biomedical data science.

The rapid growth of the globalized integrated circuit (IC) supply chain has drawn the attention of numerous malicious actors that try to exploit it for profit. One of the most prominent targets of such parties is the third-party intellectual property (3PIP) vendors and their circuit designs. With the increasing number of transactions between vendors and system integrators, the threat of IP reuse and piracy has become a significant consideration for the IC industry. What is more, the correctness of 3PIP designs should be verified before integration, imposing another challenge for 3PIP vendors since they have to prove the functionality of their designs to system integrators while protecting the privacy of the circuit implementations. To eliminate this deadlock, we utilize the cryptographic technique of “zero-knowledge proofs” to enable 3PIP vendors to convince system integrators about various functional properties of a circuit (e.g., area, power, and frequency) without disclosing its netlist (i.e., in zero-knowledge). Our approach comprises a circuit compiler that transforms arbitrary netlists into a zero knowledge-friendly format and a library of modules that provide cryptographic guarantees for various properties of the netlist while hiding the actual gates. We evaluate our method using combinational and sequential circuits from the ISCAS and ITC benchmark suites. [ABSTRACT FROM AUTHOR]

We introduce cryptographic protocols for securely and efficiently computing the cardinality of set union and set intersection. Our private set-cardinality protocols (PSC) are designed for the setting in which a large set of parties in a distributed system makes observations, and a small set of parties with more resources and higher reliability aggregates the observations. PSC allows for secure and useful statistics gathering in privacy-preserving distributed systems. For example, it allows operators of anonymity networks such as Tor to securely answer the questions: Howmany unique users are using the network? and Howmany hidden services are being accessed? We prove the correctness and security of PSC in the Universal Composability framework against an active adversary that compromises all but one of the aggregating parties. Although successful output cannot be guaranteed in this setting, PSC either succeeds or terminates with an abort, and we furthermore make the adversary accountable for causing an abort by blaming at least one malicious party. We also show that PSC prevents adaptive corruption of the data parties from revealing past observations, which prevents them from being victims of targeted compromise, and we ensure safe measurements by making outputs differentially private. We present a proof-of-concept implementation of PSC and use it to demonstrate that PSC operates with lowcomputational overhead and reasonable bandwidth. It can count tens of thousands of unique observations from tens to hundreds of data-collecting parties while completing within hours. PSC is thus suitable for daily measurements in a distributed system. [ABSTRACT FROM AUTHOR]

Secure outsourced computation is a key technique for protecting data security and privacy in the cloud. Although fully homomorphic encryption (FHE) enables computations over encrypted data, it suffers from high computation costs in order to support an unlimited number of arithmetic operations. Recently, secure computations based on interactions of multiple computation servers and partially homomorphic encryption (PHE) were proposed in the literature, which enable an unbound number of addition and multiplication operations on encrypted data more efficiently than FHE and do not add any noise to encrypted data; however, these existing solutions are either limited in functionalities (e.g., computation on natural numbers only) or leak information of the underlying data. To tackle these shortcomings, this paper proposes Secure Outsourced Computation on Integers (SOCI) based on PHE and a twin-server architecture. Compared with the existing solutions, SOCI supports computations on encrypted integers (vs. natural numbers) and greatly improves the security and correctness of the computations. Results of theoretical analysis and experimental evaluation show that SOCI outperforms existing solutions in computation and communication efficiencies. [ABSTRACT FROM AUTHOR]

With the development of machine learning, it is popular that mobile users can submit individual symptoms at any time anywhere for medical diagnosis. Edge computing is frequently adopted to reduce transmission latency for real-time diagnosis service. However, the data-driven machine learning, which requires to build a diagnosis model over vast amounts of medical data, inevitably leaks the privacy of medical data. It is necessary to provide privacy preservation. To solve above challenging issues, in this article, we design a lightweight privacy-preserving medical diagnosis mechanism on edge, called LPME. Our LPME redesigns the extreme gradient boosting (XGBoost) model based on the edge-cloud model, which adopts encrypted model parameters instead of local data to remove amounts of ciphertext computation to plaintext computation, thus realizing lightweight privacy preservation on resource-limited edge. In addition, LPME provides secure diagnosis on edge with privacy preservation for private and timely diagnosis. Our security analysis and experimental evaluation indicates the security, effectiveness, and efficiency of LPME. [ABSTRACT FROM AUTHOR]

A pile-scramble shuffle is one of the most effective shuffles in card-based cryptography. Indeed, many card-based protocols are constructed from pile-scramble shuffles. This paper aims to study the power of pile-scramble shuffles. In particular, for any directed graph G, we introduce a new protocol called "a graph shuffle protocol for G", and show that it can be implemented using pile-scramble shuffles only. Our proposed protocol requires 2 (n + m) cards, where n and m are the numbers of vertices and edges of G, respectively. The number of pile-scramble shuffles is k + 1 , where 1 ≤ k ≤ n is the number of distinct degrees of vertices of G. As an application, a random cut for n cards, which is also an important shuffle, can be implemented by 3n cards and two pile-scramble shuffles. [ABSTRACT FROM AUTHOR]

Card-based cryptography is a variant of multi-party computation using physical cards like playing cards. There are two models on card-based cryptography, called public and private models. The public model assumes that all operations are executed publicly, while the private model allows the players private operations called private permutations (PP, for short). Much of the existing card-based protocols were developed under the public model. Under the public model, 2n cards are necessary for every protocol with n-bit input since at least two cards are required to express a bit. In this paper, we propose n-bit input protocols with fewer than 2n cards by utilizing PP, which shows the power of PP. In particular, we show that a protocol for (n-bit input) threshold function can be realized with only n + 1 cards by reducing the threshold function to the majority voting. Toward this end, we first offer that two-bit input protocols for logic gates can be realized with fewer than four cards. Furthermore, we construct a new protocol for three-input majority voting with only four cards by observing the relationship between AND/OR operations. This protocol can be easily extended to more participants, and to the protocol for threshold functions. [ABSTRACT FROM AUTHOR]

Card-based protocols allow to evaluate an arbitrary fixed Boolean function f on a hidden input to obtain a hidden output, without the executer learning anything about either of the two (e.g., [12]). We explore the case where f implements a universal function, i.e., f is given the encoding ⟨ P ⟩ of a program P and an input x and computes f (⟨ P ⟩ , x) = P (x) . More concretely, we consider universal circuits, Turing machines, RAM machines, and branching programs, giving secure and conceptually simple card-based protocols in each case. We argue that card-based cryptography can be performed in a setting that is only very weakly interactive, which we call the "surveillance" model. Here, when Alice executes a protocol on the cards, the only task of Bob is to watch that Alice does not illegitimately turn over cards and that she shuffles in a way that nobody knows anything about the total permutation applied to the cards. We believe that because of this very limited interaction, our results can be called program obfuscation. As a tool, we develop a useful sub-protocol sort Π X ↑ Y that couples the two equal-length sequences X , Y and jointly and obliviously permutes them with the permutation π ∈ Π that lexicographically minimizes π (X) . We argue that this generalizes ideas present in many existing card-based protocols. In fact, AND, XOR, bit copy [37], coupled rotation shuffles [30] and the "permutation division" protocol of [22] can all be expressed as "coupled sort protocols". [ABSTRACT FROM AUTHOR]

López-Alt et al.(STOC12) put forward a primitive called multi-key fully homomorphic encryption (MKFHE), in which each involved party encrypts their own data using keys that are independently and randomly chosen whereby arbitrary computations can be performed on these encrypted data by a final collector. Subsequently, several superior schemes based on the standard assumption (LWE) were proposed. Most of these schemes were constructed by expanding a fresh GSW-ciphertext or BGV-ciphertext under a single key to a new same-type ciphertext of the same message under a combination of associated parties’ keys. Therefore, the new ciphertext’s size grew more or less linearly with an increase in the number of parties. In this paper, we proposed a novel and simple scheme of MKFHE based on LWE without increasing the size of the ciphertext in the two non-collusion server model. In other words, each party first independently shares their own data between two servers and each server only needs a one-round communication with another to construct a ciphertext of the same plaintext under a sum of associated parties’ keys. Our new ciphertext under multiple keys has the same size as that of the original one with only one-round communication between two servers. The communication complexity is O(kmlogq)- bit, where k is the number of input ciphertexts involved, m is the size of a GSW-ciphertext and q is a modulus. In conclusion, we proved that our scheme is CPA-secure against semi-honest adversaries. [ABSTRACT FROM AUTHOR]

Despite the fact that the majority of applications encountered in practice today are captured more efficiently by RAM programs, the area of secure two-party computation (2PC) has seen tremendous improvement mostly for Boolean circuits. One of the most studied objects in this domain is garbled circuits. Analogously, garbled RAM (GRAM) provide similar security guarantees for RAM programs with applications to constant round 2PC. In this work we consider the notion of gradual GRAM which requires no memory garbling algorithm. Our approach provides several qualitative advantages over prior works due to the conceptual similarity to the analogue garbling mechanism for Boolean circuits. We next revisit the GRAM construction from (In STOC (2015) 449–458) and improve it in two orthogonal aspects: match it directly with tree-based ORAMs and explore its consistency with gradual ORAM. [ABSTRACT FROM AUTHOR]

Despite the fact that the majority of applications encountered in practice today are captured more efficiently by RAM programs, the area of secure two-party computation (2PC) has seen tremendous improvement mostly for Boolean circuits. One of the most studied objects in this domain is garbled circuits. Analogously, garbled RAM (GRAM) provide similar security guarantees for RAM programs with applications to constant round 2PC. In this work we consider the notion of gradual GRAM which requires no memory garbling algorithm. Our approach provides several qualitative advantages over prior works due to the conceptual similarity to the analogue garbling mechanism for Boolean circuits. We next revisit the GRAM construction from (In STOC (2015) 449–458) and improve it in two orthogonal aspects: match it directly with tree-based ORAMs and explore its consistency with gradual ORAM. [ABSTRACT FROM AUTHOR]