waashk/acm huggingface dataset:
the soft heap: an approximate priority queue with optimal error rate  a simple variant of a priority queue, called a soft heap, is introduced. the data structure supports the usual operations: insert, delete, meld, and findmin. its novelty is to beat the logarithmic bound on the complexity of a heap in a comparison-based model. to break this information-theoretic barrier, the entropy of the data structure is reduced by artifically raising the values of certain keys. given any mixed sequence of n operations, a soft heap with error rate ε (for any 0 < ε ≤ 1/2) ensures that, at any time, at most εn of its items have their keys raised. the amortized complexity of each operation is constant, except for insert, which takes 0(log 1/ε)time. the soft heap is optimal for any value of ε in a comparison-based model. the data structure is purely pointer-based. no arrays are move items across the data structure not individually, as is customary, but in groups, in a data-structuring equivalent of "car pooling." keys must be raised as a result, in order to preserve the heap ordering of the data structure. the soft heap can be used to compute exact or approximate medians and percentiles optimally. it is also useful for approximate sorting and for computing minimum spanning trees of general graphs.  bernard chazelle
a digital multisignature scheme using bijective public-key cryptosystems  a new digital multisignature scheme using bijective public-key cryptosystems that overcomes the problems of previous signature schemes used for multisignatures is proposed. the principal features of this scheme are (1) the length of a multisignature message is nearly equivalent to that for a singlesignature message; (2) by using a one-way hash function, multisignature generation and verification are processed in an efficient manner; (3) the order of signing is not restricted; and (4) this scheme can be constructed on any bijective public-key cryptosystem as well as the rsa scheme. in addition, it is shown that the new scheme is considered as safe as the public-key cryptosystem used in this new scheme. some variations based on the scheme are also presented.  tatsuaki okamoto
a national debate on encryption exportability  traditionally, cryptography has been an exclusively military technology controlled by the national security agency (nsa). therefore, u.s. international traffic in arms regulations (itars) requires licenses for all export of modern cryptographic methods. some methods, such as the data encryption standard (des), are easily obtained for export to the coordinating committee for multilateral export controls (cocom) countries, but not soviet block countries, or most third world nations.  clark weissman
efficient generation of shared rsa keys we describe efficient techniques for a number of parties to jointly generate an rsa key. at the end of the protocol an rsa modulus _n_ = _pq_ is publicly known. none of the parties know the factorization of _n_. in addition a public encryption exponent is publicly known and each party holds a share of the private exponent that enables threshold decryption. our protocols are efficient in computation and communication. all results are presented in the _honest but curious_ scenario (passive adversary). dan boneh matthew franklin
cryptography and data security overview of panel discussion  cryptography is the science of secret writing. it has been used since the dawn of writing itself to conceal messages from an adversary. throughout history, the use of cryptography has been largely confined to diplomatic and military communications. but in the last 10 years the tremendous advances in communication technology have created a serious need for cryptographic protection of private sector communications. electronic funds transfer systems and satellite voice/digital networks are particularly vulnerable to compromise, without the use of cryptography. recognizing the need for data protection apart from national security concerns, the national bureau of standards issued a call for a data encryption algorithm in 1973. during the subsequent discussions and debates, the mathematicians and computer scientists involved realized that cryptography was not an established science in the unclassified literature. they began the task of creating the foundations for this young discipline. in 1977, the nbs published the data encryption standard (des). its use is required to protect sensitive governmental information not related to national security. several national and international standards organizations have also adopted the des.  michael willett
public cryptography outlook  ten years ago last march, the national bureau of standards issued its first solicitation for an algorithm to be used in public cryptography. while significant progress has been made in the development of the technology in this field, the public's use of cryptography has proceeded more slowly than some had originally expected. yet, looking back, it seems surprising that anyone would have thought that public cryptography could have developed any faster than it has.  when the des was published as a standard in january, 1977, the private and non-classified government communities knew little about cryptography and its capabilities. open publications were primarily academic papers, and consequently the public had a poor understanding of what problems cryptography could solve and what problems were beyond its scope.  miles e. smid
a locally adaptive data compression scheme  a data compression scheme that exploits locality of reference, such as occurs when words are used frequently over short intervals and then fall into long periods of disuse, is described. the scheme is based on a simple heuristic for self-organizing sequential search and on variable-length encodings of integers. we prove that it never performs much worse than huffman coding and can perform substantially better; experiments on real files show that its performance is usually quite close to that of huffman coding. our scheme has many implementation advantages: it is simple, allows fast encoding and decoding, and requires only one pass over the data to be compressed (static huffman coding takes two passes).  jon louis bentley daniel d. sleator robert e. tarjan victor k. wei
how to simultaneously exchange secrets by general assumptions  the simultaneous secret exchange protocol is the key tool for contract signing protocols and certified mail protocols. this paper proposes efficient simultaneous secret exchange protocols (or gradual secret releasing protocols) that are based on general assumptions such as the existence of one-way permutations and one-way functions, while the existing efficient simultaneous secret exchange protocols are based on more constrained assumptions such as specific number theoretic problems and the existence of oblivious transfer primitives (or trap-door one-way permutations). moreover, while the existing simultaneous secret exchange protocols have an additional requirement that the underlying commit (encryption) function is "ideal", the above-mentioned "general assumptions" are provably sufficient for our schemes. therefore, our protocols are provably secure under the general assumptions. in addition, our protocols are at least as efficient as the existing practical protocols, when efficient one-way permutations and one-way functions are used.  tatsuaki okamoto kazuo ohta
information leakage of boolean functions and its relationship to other cryptographic criteria  this paper presents some results on the cryptographic strength of boolean functions from the information theoretic point of view. it is argued that a boolean function is resistant to statistical analysis if there is no significant static and dynamic information leakage between its inputs and its output(s). in particular we relate information leakage to nonlinearity, higher order sac, correlation immunity and resilient functions. it is shown that reducing information leakage increases resistance to the differential attack and the linear attack. we note that some conventional cryptographic criteria require zero static or dynamic information leakage in only one domain. such a requirement can result in a large information leakage in another domain. to avoid this weakness, it is better to jointly constrain all kinds of information leakage in the function. in fact, we claim that information leakage can be used as a fundamental measure of the strength of a cryptographic algorithm.  m. zhang s. e. tavares l. l. campbell
an unknown key-share attack on the mqv key agreement protocol the mqv key agreement protocol, a technique included in recent standards, is shown in its basic form to be vulnerable to an unknown key-share attack. although the attack's practical impact on security is minimal---a key confirmation step easily prevents it---the attack is noteworthy in the principles it illustrates about protocol design. first, minor efficiency improvements can significantly alter the security properties of a protocol. second, protocol analysis must consider potential interactions with all parties, not just those that are normally online. finally, attacks must be assessed in terms of system requirements, not just in isolation. burton s. kaliski
dense multiway trees  b-trees of order m are a "balanced" class of m-ary trees, which have applications in the areas of file organization. in fact, they have been the only choice when balanced multiway trees are required. although they have very simple insertion and deletion algorithms, their storage utilization, that is, the number of keys per page or node, is at worst 50 percent. in the present paper we investigate a new class of balanced m-ary trees, the dense multiway trees, and compare their storage utilization with that of b-trees of order m.  surprisingly, we are able to demonstrate that weakly dense multiway trees have an  (log2 n) insertion algorithm. we also show that inserting mh \\- 1 keys in ascending order into an initially empty dense multiway tree yields the complete m-ary tree of height h, and that at intermediate steps in the insertion sequence the intermediate trees can also be considered to be as dense as possible. furthermore, an analysis of the limiting dynamic behavior of the dense m-ary trees under insertion shows that the average storage utilization tends to 1; that is, the trees become as dense as possible. this motivates the use of the term "dense."  k. culik th. ottmann d. wood
data structures: pointers vs. arrays. when, where and why  in the inevitable search for the "perfect" structure, the beginning programmer is faced with a multitude of possibilities. stacks, arrays, queues, linked lists, trees, and, on a higher level, the decision whether the "best" choice would involve a physical implementation of arrays or pointers. the choice, particularly for the novice, is not easy. the purpose of the abstract is to facilitate that choice.  having perused a dozen textbooks dealing with introduction to data structures (the greater majority of which employ pascal) one finds the "expected" comparative analysis between dynamic and static variables. the prevalent tendency indicates that the utilization of pointer (dynamic) variables more effectively controls memory allocation with the result being a generally more effective, possibly more expedient execution.  the strange occurrence that i could not help the questioning was involved with the reasons why most treatments of data structures devote more time to the static approach as opposed to the dynamic one. and, on a different note, why so few textbooks actually compared the two parallel approaches for the same problem.  to alleviate this, i considered solving a simple problem both ways. we wish to create a binary search tree from a list of up to 50000 numbers and, in addition, remove any duplicates from the list. a reasonable approach to this would be to statically declare an array of 50000 nodes, using subroutines to "getnode" (using an available pool of nodes created within the program), create a tree (i.e., the root), setleft and setright (to properly place an item in the tree). such a program involves 5 modules, about 80 lines of code, a run time of under 2 seconds, 1089 page faults, and a peak page file (indicating the use of memory) of 3253.  on the other hand, if one writes the program using pointer variables, the "getnode" procedure mentioned above can be replaced by a simple "new" function (for obtaining a new node), no storage for the numbers is required within the program and we see the following results: 72 lines of code, 4 modules, a run time of under 2 seconds, 861 page faults, and a peak page file of 924.  an interesting observation is that the only "significant" difference in the "statistics" of the two versions is in the peak page file. there was emphatically no difference in run time.  it would seem useful, therefore, to allow the novice programmer the option of attempting both approaches, while encouraging such comparisons as the one noted above. the "best" approach may not be an acceptable one for a particular user who feels burdened by a concept not fully understood. thus, the when, where, and why can only be asked and answered by the programmer who truly experiences the greatest magnitude.  domenick j. pinto
unconditional security in quantum cryptography  basic techniques to prove the unconditional security of quantum crypto graphy are described. they are applied to a quantum key distribution protocol proposed by bennett and brassard [1984]. the proof considers a practical variation on the protocol in which the channel is noisy and photos may be lost during the transmission. each individual signal sent into the channel must contain a single photon or any two-dimensional system in the exact state described in the protocol. no restriction is imposed on the detector used at the receiving side of the channel, except that whether or not the received system is detected must be independent of the basis used to measure this system.
a polynomial time generator for minimal perfect hash functions  a perfect hash function phf is an injection f from a set w of m objects into the set consisting of the first n nonnegative integers where n m. if n = m, then f is a minimal perfect hash function, mphf. phfs are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language.  the mincycle algorithm for finding phfs executes with an expected time complexity that is polynomial in m and has been used successfully on sets of cardinality up to 512. given three pseudorandom functions h0, h1, and h2, the mincycle algorithm searches for a function g such that f(w) = (h0(w) + g h1(w) + g h2(w)) mod n is a phf.  thomas j. sager
deterministic skip lists  we explore techniques based on the notion of a skip list to guarantee logarithmic search, insert and delete costs. the basic idea is to insist that between any pair of elements above a given height are a small number of elements of precisely that height. the desired behaviour can be achieved by either using some extra space for pointers, or by adding the constraint that the physical sizes of the nodes be exponentially increasing. the first approach leads to simpler code, whereas the second is ideally suited to a buddy system of memory allocation. our techniques are competitive in terms of time and space with balanced tree schemes, and, we feel, inherently simpler when taken from first principles.  j. ian munro thomas papadakis robert sedgewick
optimal single row router  the single row approach represents a systematic suboptimal approach to the general multilayer rectilinear wire problem. with this approach, the single row wiring problem (i.e., one where all the points are collinear) forms the backbone of the general multilayer wiring problem. we consider the problem of generating minimum width layout for single row wiring problems. our algorithm, which is not grid-based, is enumerative and uses a strong bounding criterion.  raghunath raghavan sartaj sahni
a linear time algorithm for residue computation and a fast algorithm for division with a sparse divisor  an algorithm is presented to compute the residue of a polynomial over a finite field of degree n modulo a polynomial of degree o(log n) in o(n) algebraic operations. this algorithm can be implemented on a turing machine. the implementation is based on turing machine procedure that divides a polynomial of degree n by a sparse polynomial with k nonzero coefficients in o(kn) steps. this algorithm can be adapted to compute the residue of a number of length n modulo a number of length o(log n) in o(n) bit operations.  michael kaminski
on the completeness of object-creating database transformation languages  object-oriented applications of database systems require database transformations involoving nonstandard functionalities such as set manipulation and object creation, that is, the introduction of new domain elements. to deal with thse functionalities, abiteboul and kanellakis [1989] introduced the "determinate" transformations as a generalization of the standard domain-preserving transformations. the obvious extensions of complete standard database programming languages, however, are not complete for the determinate transformations. to remedy this mismatch, the "constructive" transformations are proposed. it is shown that the constructive transformations are precisely the transformations that can be expressed in said extensions of complete standard languages. thereto, a close correspondence between object creation and the construction of hereditarily finite sets is established.  a restricted version of the main completeness result for the case where only list manipulations are involved is also presented.  jan van den bussche dirk van gucht marc andries marc gyssens
computing a centerpoint of a finite planar set of points in linear time  the notion of a centerpoint of a finite set of points in two and higher dimensions is a generalisation of the concept of the median of a (finite) set of points on the real line. in this paper, we present an algorithm for computing a centerpoint of a set of n points in the plane. the algorithm has complexity o(n) which significantly improves the o(n log3 n) complexity of the previously best known algorithm. we use suitable modifications of the ham- sandwich-cut algorithm and the prune-and-search technique to achieve this improvement.  shreesh jadhav asish mukhopadhyay
three logics for branching bisimulation  three temporal logics are introduced that induce on labeled transition systems the same identifications as branching bisimulation, a behavioral equivalence that aims at ignoring invisible transitions while preserving the branching structure of systems. the first logic is an extension of hennessy-milner logic with an "until" operator. the second one is another extension of hennessy- milner logic, which exploits the power of backward modalities. the third logic is ctl* without the next-time operator. a relevant side-effect of the last characterization is that it sets a bridge between the state- and action-based approaches to the semantics of concurrent systems.  rocco de nicola frits vaandrager
detection is easier than computation (extended abstract)  perhaps the most important application of computer geometry involves determining whether a pair of convex objects intersect. this problem is well understood in a model of computation where the objects are given as input and their intersection is returned as output. however, for many applications, we may assume that the objects already exist within the computer and that the only output desired is a single piece of data giving a common point if the objects intersect or reporting no intersection if they are disjoint. for this problem, none of the previous lower bounds are valid and we propose algorithms requiring sublinear time for their solution in 2 and 3 dimensions.  bernard chazelle david p. dobkin
two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations  any boolean straight-line program which computes the transitive closure of an nxn boolean matrix by successive squaring requires time exceeding any polynomial in n if the space used is o(n). this is the first demonstration of a "natural" algorithm which (1) has a polynomial time implementation and (2) has a small (e.g., o(log2n)) space implementation, but (3) has no implementation running in polynomial time and small space simultaneously. it is also shown that any implementation of warshall's transitive closure algorithm requires Ω(n) space.  martin tompa
separating and collapsing results on the relativized probabilistic polynomial- time hierarchy  the probabilistic polynomial-time hierarchy (bph) is the hierarchy generated by applying the bp-operator to the meyer-stockmeyer polynomial-time hierarchy (ph), where the bp-operator is the natural generalization of the probabilistic complexity class bpp. the similarity and difference between the two hierarchies bph and ph is investigated. oracles a and b are constructed such that both ph(a) and ph(b) are infinite while bph(a) is not equal to ph(a) at any level and bph(b) is identical to ph(b) at every level. similar separating and collapsing results in the case that ph(a) is finite having exactly k levels are also considered.  ker-i ko
two tapes are better than one for nondeterministic machines  it is known that k tapes are no better than two tapes for nondeterministic machines. we show here that two tapes are better than one. in fact, we show that two pushdown stores are better than one tape. also, k tapes are no better than two for nondeterministic reversal-bounded machines. we show here that two tapes are better than one for such machines. in fact, we show that two reversal- bounded pushdown stores are better than one reversal-bounded tape. we also show that for one-tape nondeterministic machines, unrestricted machines are better than reversal-bounded machines.  pavol d zvi galil
distributed bisimulations  a new equivalence between concurrent processes is proposed. it generalizes the well-known bisimulation equivalence to take into account the distributed nature of processes. the result is a noninterleaving semantic theory; concurrent processes are differentiated from processes that are non- deterministic but sequential. the new equivalence, together with its observational version, is investigated for a subset of the language ccs, and various algebraic characterizations are obtained.  ilaria castellani matthew hennessy
on contention resolution protocols and associated probabilistic phenomena  consider an on-line scheduling problem in which a set of abstract processes are competing for the use of a number of resources. further assume that it is either prohibitively expensive or impossible for any two of the processes to directly communicate with one another. if several processes simultaneously attempt to allocate a particular resource (as may be expected to occur, since the processes cannot easily coordinate their allocations), then none succeed. in such a framework, it is a challenge to design efficient contention resolution protocols.  two recently-proposed approaches to the problem of pram emulation give rise to scheduling problems of the above kind. in one approach, the resources (in this case, the shared memory cells) are duplicated and distributed randomly. we analyze a simple and efficient deterministic algorithm for accessing some subset of the duplicated resources. in the other approach, we analyze how quickly we can access the given (nonduplicated) resource using a simple randomized strategy. we obtain precise bounds on the performance of both strategies. we anticipate that our results with find other applications.  p. d. mackenzie c. g. plaxton r. rajaraman