NDLI: The round complexity of verifiable secret sharing and secure multicast

Please wait, while we are loading the content...

Clustering to minimize the sum of cluster diameters

Approximating min-sum k-clustering in metric spaces

Local search heuristic for k-median and facility location problems

Profit-earning facility location

One-dimensional quantum walks

Quantum walks on graphs

Quantum algorithms for solvable groups

Quantum mechanical algorithms for the nonabelian hidden subgroup problem

Minimax parametric optimization problems and multi-dimensional parametric searching

Algorithms for minimizing weighted flow time

Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

Stackelberg scheduling strategies

Quantum computers that can be simulated classically in polynomial time

Interaction in quantum communication and the complexity of set disjointness

A new protocol and lower bounds for quantum coin flipping

Loss-less condensers, unbalanced expanders, and extractors

Conditions on input vectors for consensus solvability in asynchronous distributed systems

Spatial gossip and resource location protocols

(1 + εΒ)-spanner constructions for general graphs

Approximate distance oracles

Extractor codes

Excellent codes from modular curves

Sparse polynomial approximation in finite fields

Randomness efficient identity testing of multivariate polynomials

Fully-dynamic min-cut

Computing crossing numbers in quadratic time

Euler paths in series parallel graphs

Decidability of string graphs

Learning mixtures of arbitrary gaussians

Learning DNF in time

Sampling algorithms: lower bounds and applications

Testing metric properties

Testing of matrix properties

Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

One line and ε

A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

Lower bounds for intersection searching and fractional cascading in higher dimension

Sharp threshold and scaling window for the integer partitioning problem

A sharp threshold in proof complexity

Regular resolution lower bounds for the weak pigeonhole principle

The complexity of analytic tableaux

Applications of approximation algorithms to cooperative games

Approximation algorithms for constrained for constrained node weighted steiner tree problems

A constant factor approximation for the single sink edge installation problems

Provisioning a virtual private network: a network design problem for multicommodity flow

Explicit lower bound of 4.5n - o(n) for boolena circuits

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

A read-once branching program lower bound of $Ω(2^{n/4})$ for integer multiplication using universal hashing

On the cell probe complexity of membership and perfect hashing

On the integrality ratio of semidefinite relaxations of MAX CUT

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming

Non-approximability results for optimization problems on bounded degree instances

Colouring graphs when the number of colours is nearly the maximum degree

Data-streams and histograms

Optimal static range reporting in one dimension

Biased dictionaries with fast insert/deletes

Anti-persistence: history independent data structures

Dynamic TCP acknowledgement and other stories about e/(e-1)

The price of selfish routing

Buffer overflow management in QoS switches

Almost optimal permutation routing on hypercubes

Online server allocation in a server farm via benefit task systems

Private approximation of NP-hard functions

Concurrent and resettable zero-knowledge in poly-loalgorithm rounds

Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds

The round complexity of verifiable secret sharing and secure multicast

Communication preserving protocols for secure function evaluation

Some perspectives on computational complexity

A sieve algorithm for the shortest lattice vector problem

Fast computation of low rank matrix approximations

Spectral analysis of data

Optimal outlier removal in high-dimensional

Estimating true evolutionary distances between genomes

On optimal slicing of parallel programs

When is the evaluation of conjunctive queries tractable?

The complexity of maximal constraint languages

Quantitative solution of omega-regular games380872

Distribution functions of probabilistic automata

Compatible sequences and a slow Winkler percolation

Edge isoperimetry and rapid mixing on matroids and geometric Markov chains

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

Computing with continuous-time Liapunov systems

Complex tilings

Running time and program size for self-assembled squares

Algorithms, games, and the internet

Automata, circuits and hybrids: facets of continuous time

The round complexity of verifiable secret sharing and secure multicast

Content Provider	ACM Digital Library
Author	Ishai, Yuval Kushilevitz, Eyal Rabin, Tal Gennaro, Rosario
Abstract	The round complexity of interactive protocols is one of their most important complexity measures. In this work we study the exact round complexity of two basic secure computation tasks: Verifiable Secret Sharing (VSS) and Secure Multicast.VSS allows a dealer to share a secret among several players in a way that would later allow a unique reconstruction of the secret. It is a well-studied primitive, which is used as a building block in virtually every general protocol for secure multi-party computation. Secure multicast is perhaps the simplest non-trivial instance of a secure computation. It allows a dealer to securely distribute an identical message to all players in a prescribed subset M. Both types of protocols are parameterized by the number of players, n, and a security threshold, t, which bounds the total number of malicious players (possibly including the dealer).We focus on a standard setting of perfect information-theoretic security, where all players have access to secure point-to-point channels and a common broadcast medium. For both types of primitives we prove, using related techniques, tight tradeoffs between the round complexity and the achievable security threshold. Specifically, for the VSS problem we show:2-round VSS is possible iff n>4t, where the if'' direction is realized by an efficient protocol.3-round VSS is possible iff n>3t, where the if'' direction is realized by an inefficient protocol.4-round efficient VSS is possible if n>3t.For the secure multicast problem we show:2-round secure multicast is (efficiently) possible iff.
Starting Page	580
Ending Page	589
Page Count	10
File Format	PDF
ISBN	1581133499
DOI	10.1145/380752.380853
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-07-06
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in