Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSecure Grouping Protocol Using a Deck of Cards
80
0
0.0
(
0
)
Added by
Koji Nuida
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider a problem, which we call secure grouping, of dividing a number of parties into some subsets (groups) in the following manner: Each party has to know the other members of his/her group, while he/she may not know anything about how the remaining parties are divided (except for certain public predetermined constraints, such as the number of parties in each group). In this paper, we construct an information-theoretically secure protocol using a deck of physical cards to solve the problem, which is jointly executable by the parties themselves without a trusted third party. Despite the non-triviality and the potential usefulness of the secure grouping, our proposed protocol is fairly simple to describe and execute. Our protocol is based on algebraic properties of conjugate permutations. A key ingredient of our protocol is our new techniques to apply multiplication and inverse operations to hidden permutations (i.e., those encoded by using face-down cards), which would be of independent interest and would have various potential applications.
rate research
Read More
The problem of $A$ privately transmitting information to $B$ by a public announcement overheard by an eavesdropper $C$ is considered. To do so by a deterministic protocol, their inputs must be correlated. Dependent inputs are represented using a deck of cards. There is a publicly known signature $(a,b,c)$, where $n = a + b + c + r$, and $A$ gets $a$ cards, $B$ gets $b$ cards, and $C$ gets $c$ cards, out of the deck of $n$ cards. Using a deterministic protocol, $A$ decides its announcement based on her hand. Using techniques from coding theory, Johnson graphs, and additive number theory, a novel perspective inspired by distributed computing theory is provided, to analyze the amount of information that $A$ needs to send, while preventing $C$ from learning a single card of her hand. In one extreme, the generalized Russian cards problem, $B$ wants to learn all of $A$s cards, and in the other, $B$ wishes to learn something about $A$s hand.
In the generalized Russian cards problem, we have a card deck $X$ of $n$ cards and three participants, Alice, Bob, and Cathy, dealt $a$, $b$, and $c$ cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their hands to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathys ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak $1$-security) to not gaining any probabilistic advantage in guessing the fate of some set of $delta$ cards (perfect $delta$-security). As we demonstrate, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly $delta$-secure strategies and $(c+delta)$-designs on $n$ points with block size $a$, when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect $1$-security against Cathy when $c=2$. We leverage a known combinatorial design to construct a strategy with $a=8$, $b=13$, and $c=3$ that is perfectly $2$-secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak $delta$-security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of $c = lfloor frac{a-delta}{2} rfloor$ cards. Alternatively, the construction yields solutions for arbitrary $delta$, $c$ and any $a geq delta + 2c$.
A protocol for two-party secure function evaluation (2P-SFE) aims to allow the parties to learn the output of function $f$ of their private inputs, while leaking nothing more. In a sense, such a protocol realizes a trusted oracle that computes $f$ and returns the result to both parties. There have been tremendous strides in efficiency over the past ten years, yet 2P-SFE protocols remain impractical for most real-time, online computations, particularly on modestly provisioned devices. Intels Software Guard Extensions (SGX) provides hardware-protected execution environments, called enclaves, that may be viewed as trusted computation oracles. While SGX provides native CPU speed for secure computation, previous side-channel and micro-architecture attacks have demonstrated how security guarantees of enclaves can be compromised. In this paper, we explore a balanced approach to 2P-SFE on SGX-enabled processors by constructing a protocol for evaluating $f$ relative to a partitioning of $f$. This approach alleviates the burden of trust on the enclave by allowing the protocol designer to choose which components should be evaluated within the enclave, and which via standard cryptographic techniques. We describe SGX-enabled SFE protocols (modeling the enclave as an oracle), and formalize the strongest-possible notion of 2P-SFE for our setting. We prove our protocol meets this notion when properly realized. We implement the protocol and apply it to two practical problems: privacy-preserving queries to a database, and a version of Dijkstras algorithm for privacy-preserving navigation. Our evaluation shows that our SGX-enabled SFE scheme enjoys a 38x increase in performance over garbled-circuit-based SFE. Finally, we justify modeling of the enclave as an oracle by implementing protections against known side-channels.
Secure Function Evaluation (SFE) has received recent attention due to the massive collection and mining of personal data, but remains impractical due to its large computational cost. Garbled Circuits (GC) is a protocol for implementing SFE which can evaluate any function that can be expressed as a Boolean circuit and obtain the result while keeping each partys input private. Recent advances have led to a surge of garbled circuit implementations in software for a variety of different tasks. However, these implementations are inefficient and therefore GC is not widely used, especially for large problems. This research investigates, implements and evaluates secure computation generation using a heterogeneous computing platform featuring FPGAs. We have designed and implemented SIFO: Secure computational Infrastructure using FPGA Overlays. Unlike traditional FPGA design, a coarse grained overlay architecture is adopted which supports mapping SFE problems that are too large to map to a single FPGA. Host tools provided include SFE problem generator, parser and automatic host code generation. Our design allows re-purposing an FPGA to evaluate different SFE tasks without the need for reprogramming, and fully explores the parallelism for any GC problem. Our system demonstrates an order of magnitude speedup compared with an existing software platform.
We discuss a procedure, which should be called Lenstras fix, for producing secure RSA moduli even when the random number generation is very poor.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
