waashk/dblp huggingface dataset:
fast generation of abstracts from general domain text corpora by extracting relevant sentences. this paper describes a system for generating text abstracts which relies on a general, purely statistical principle, i.e., on the notion of "relevance", as it is defined in terms of the combination of feild weights of words in a sentence. the system generates abstracts from newspaper articles by selecting the "most relevant" sentences and combining them in text order. since neither domain knowledge nor text-sort-specific heuristics are involved, this system provides maximal generality and flexibility. also, it is fast and can be efficiently implemented for both on-line and off-line purposes. an experiment shows that recall and precision for the extracted sentences (taking the sentences extracted by human subjects as a baseline) is within the same range as recall/precision when the human subjects are compared amongst each other: this means in fact that the performance of the system is indistinguishable from the performance of a human abstractor. finally, the system yields significantly better results than a default "lead" algorithm does which chooses just some initial sentences from the text.
diasumm: flexible summarization of spontaneous dialogues in unrestricted domains. in this paper, we present a summarization system for spontaneous dialogues which consists of a novel multi-stage architecture. it is specifically aimed at addressing issues related to the nature of the texts being spoken vs. written and being dialogical vs. monological. the system is embedded in a graphical user interface and was developed and tested on transcripts of recorded telephone conversations in english and spanish (callhome).
closed yesterday and closed minds: asking the right questions of the corpus to distinguish thematic from sentential relations. collocation-based tagging and bracketing programs have attained promising results. yet, they have not arrived at the stage where they could be used as pre-processors for full-fledged parsing. accuracy, is still not high enough.to improve accuracy, it is necessary to investigate the points where statistical data is being misinterpreted, leading to incorrect results.in this paper we investigate inaccuracy which is injected when a pre-pocessor relies solely on collocations and blurs the distinction between two separate relations: thematic relations and sentential relations.thematic relations are word paris, not necessarily adjacent, (e.g., adjourn a meeting) that encode information at the concept level. sentential relations, on the other hand, concern adjacent word pairs that form a noun group. e.g., preferred stock is a noun group that must be identified as such at the syntactic level.blurring the difference between these two phenomena contributes to errors in tagging of pairs such as expressed concerns, a verb-noun construct, as opposed to preferred stocks, an adjective-noun construct. although both relations are manifested in the corpus as high mutual-information collocations, they possess different properties and they need to be separated.in our method, we distinguish between these two cases by asking additional questions of the corpus. by definition, thematic relations take on further variations in the corpus. expressed concerns (a thematic relation) takes concerns expressed, expressing concerns, express his concerns etc. on the other hand, preferred stock (a sentential relation) does not take any such syntactic variations.we show how this method impacts preprocessing and parsing, and we provide empirical results based on the analysis of an 80-million word corpus.
an empirically based approach towards a system of semantic features. a major problem in machine translation is the semantic description of lexical units which should be based on a semantic system that is both coherent and operationalized to the greatest possible degree. this is to guarantee consistency between lexical units coded by lexicographers. this article introduces a generating device for achieving wellformed semantic feature expressions.
default reasoning in natural language processing. in natural language, as in other computational task domains it is important to operate by default assumptions. first, many constraints required for constraint propagation are initially unspecified. second, in highly ambiguous tasks such as text analysis, ambiguity can be reduced by considering more plausible scenarios first. default reasoning is problematic for first-order logic when allowing non-monotonic inferences. whereas in monotonic logic facts can only be asserted, in non-monotonic logic a system must be maintained consistent even as previously assumed defaults are being retracted.non-monotonicty is pervasive in natural language due to the serial nature of utterances. when reading text left-to-right, it happens that default assumptions made early in the sentence must be withdrawn as reading proceeds. truth maintenance, which accounts for non-monotonic inferences, can resolve this issue and address important linguistic phenomena. in this paper we describe how in nmg (non-monotonic grammar), by monitoring a logic parser, a truth maintenance system can significantly, enhance the parser's capabilities.
universal quantification in machine translation. this approach has been developed in the context of the eurotra machine translation (mt) project and thus has been designed with respect to a syntax based stratificational translation process. we assume that in a semantic representation determiners are deleted and that their semantic function which is represented by semantic features is percolated into the mothernode. the semantic functions of determiners are explicated. the interaction between grammatical and lexical quantification is outlined. ensemble theory is applied to the "count"/"mass" noun distinction. transfer of quantification between german, english, and french is illustrated with respect to the "count"/"mass" distinction. the article closes with an outlook on the relevance of generalized quantifiers for machine translation.
cbc macs for arbitrary-length messages: the three-key constructions. we suggest some simple variants of the cbc mac that enable the efficient authentication of arbitrary-length messages. our constructions use three keys, k1, k2, k3, to avoid unnecessary padding and mac any message m &#x2208; {0,1}* using max{1, &#x2308; |m|/n&#x2309;} applications of the underlying n-bit block cipher. our favorite construction, xcbc, works like this: if |m| is a positive multiple of n then xor the n-bit key k2 with the last block of m and compute the cbc mac keyed with k1; otherwise, extend m&#x2019;s length to the next multiple of n by appending minimal 10&#x2113; padding (&#x2113; &#x2265; 0), xor the n-bit key k3 with the last block of the padded message, and compute the cbc mac keyed with k1. we prove the security of this and other constructions, giving concrete bounds on an adversary&#x2019;s inability to forge in terms of his inability to distinguish the block cipher from a random permutation. our analysis exploits new ideas which simplify proofs compared with prior work.
private computation - k-connected versus 1-connected networks. we study the role of connectivity of communication networks in private computations under information theoretical settings in the honest-but-curious model. we show that some functions can be 1-privately computed even if the underlying network is 1-connected but not 2-connected. then we give a complete characterisation of non-degenerate functions that can be 1-privately computed on non-2-connected networks. furthermore, we present a technique for simulating 1-private protocols that work on arbitrary (complete) networks on k-connected networks. for this simulation, at most $(1 - k/(n - 1)) \cdot l$ additional random bits are needed, where l is the number of bits exchanged in the original protocol and n is the number of players. finally, we give matching lower and upper bounds for the number of random bits needed to compute the parity function on k-connected networks 1-privately, namely $\lceil (n - 2)/(k - 1) \rceil - 1$ random bits for networks consisting of n players.
a calculus for access control in distributed systems. we study some of the concepts, protocols, and algorithms for access control in distributed systems, from a logical perspective. we account for how a principal may come to believe that another principal is making a request, either on his own or on someone else's behalf. we also provide a logical language for accesss control lists and theories for deciding whether requests should be granted.
searchable encryption revisited: consistency properties, relation to anonymous ibe, and extensions. we identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (peks). we define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of boneh et&#x00a0;al. (advances in cryptology&#x2014;eurocrypt 2004, ed. by c.&#x00a0;cachin, j.&#x00a0;camenisch, pp.&#x00a0;506&#x2013;522, 2004) is computationally consistent, and provide a new scheme that is statistically consistent. we also provide a transform of an anonymous identity-based encryption (ibe) scheme to a secure peks scheme that, unlike the previous one, guarantees consistency. finally, we suggest three extensions of the basic notions considered here, namely anonymous hierarchical identity-based encryption, public-key encryption with temporary keyword search, and identity-based encryption with keyword search.
how to sign given any trapdoor function. we present a digital signature scheme which combines high security with the property of being based on a very general assumption: the existence of trapdoor permutations. previous signature schemes with comparable levels of security were based on assumptions of the computational hardness of particular algebraic problems such as factoring. our contribution is to free this important cryptographic primitive from the fortunes of any specific algebraic problem by establishing a truly general signature scheme.
derandomization in cryptography. we give two applications of nisan-wigderson-type (nw-type) (&ldquo;noncryptographic&rdquo;) pseudorandom generators in cryptography. specifically, assuming the existence of an appropriate nw-type generator, we construct the following two protocols: (1) a one-message witness-indistinguishable proof system for every language in np, based on any trapdoor permutation. this proof system does not assume a shared random string or any setup assumption, so it is actually an &ldquo;np proof system.&rdquo; (2) a noninteractive bit-commitment scheme based on any one-way function. the specific nw-type generator we need is a hitting set generator fooling nondeterministic circuits. it is known how to construct such a generator if $e = dtime(2^{o(n)})$ has a function of nondeterministic circuit complexity $2^{\omega(n)}$. our witness-indistinguishable proofs are obtained by using the nw-type generator to derandomize the zaps of dwork and naor [proceedings of the 41st annual acm symposium on foundations of computer science, 2000, pp. 283-293]. to our knowledge, this is the first construction of an np proof system achieving a secrecy property. our commitment scheme is obtained by derandomizing the interactive commitment scheme of naor [j. cryptology, 4 (1991), pp. 151-158]. previous constructions of noninteractive commitment schemes were known only under incomparable assumptions.
instant ciphertext-only cryptanalysis of gsm encrypted communication. in this paper we present a very practical ciphertext-only cryptanalysis of gsm (global system for mobile communications) encrypted communication, and various active attacks on the gsm protocols. these attacks can even break into gsm networks that use &#x201c;unbreakable&#x201d; ciphers. we first describe a ciphertext-only attack on a5/2 that requires a few dozen milliseconds of encrypted off-the-air cellular conversation and finds the correct key in less than a second on a personal computer. we extend this attack to a (more complex) ciphertext-only attack on a5/1. we then describe new (active) attacks on the protocols of networks that use a5/1, a5/3, or even gprs (general packet radio service). these attacks exploit flaws in the gsm protocols, and they work whenever the mobile phone supports a weak cipher such as a5/2. we emphasize that these attacks are on the protocols, and are thus applicable whenever the cellular phone supports a weak cipher, for example, they are also applicable for attacking a5/3 networks using the cryptanalysis of a5/1. unlike previous attacks on gsm that require unrealistic information, like long known-plaintext periods, our attacks are very practical and do not require any knowledge of the content of the conversation. furthermore, we describe how to fortify the attacks to withstand reception errors. as a result, our attacks allow attackers to tap conversations and decrypt them either in real-time, or at any later time. we present several attack scenarios such as call hijacking, altering of data messages and call theft.
multiparty computation with faulty majority. the problem of performing a multiparty computation when more than half of the processors are cooperating byzantine faults is addressed. it is shown how to compute any boolean function of n inputs distributively, preserving the privacy of inputs held by nonfaulty processors and ensuring that faulty processors obtain the function value if and only if the nonfaulty processors do. if the nonfaulty processors do not obtain the correct function value, they detect cheating with high probability. the solution is based on a new type of verifiable secret sharing in which the secret is revealed not all at once but in small increments. this process ensures that all processors discover the secret at roughly the same time. the solution assumes the existence of an oblivious transfer protocol and uses broadcast channels. the processors are not required to have equal computing power.
identity-based encryption from the weil pairing. we propose a fully functional identity-based encryption (ibe) scheme. the scheme has chosen ciphertext security in the random oracle model assuming a variant of the computational diffie--hellman problem. our system is based on bilinear maps between groups. the weil pairing on elliptic curves is an example of such a map. we give precise definitions for secure ibe schemes and give several applications for such systems.
primality proving via one round in ecpp and one iteration in aks. in august 2002, agrawal, kayal and saxena announced the first deterministic and polynomial-time primality-testing algorithm. for an input n, the agarwal-kayal-saxena (aks) algorithm runs in time $\tilde{o}(\log^{7.5} n)$ (heuristic time $\tilde{o}(\log^6 n)$). verification takes roughly the same amount of time. on the other hand, the elliptic curve primality proving algorithm (ecpp) runs in random heuristic time $\tilde{o}(\log^{6} n)$ (some variant has heuristic time complexity $\tilde{o}(\log^4 n)$) and generates certificates which can be easily verified. however, it is hard to analyze the provable time complexity of ecpp even for a small portion of primes. more recently, berrizbeitia gave a variant of the aks algorithm, in which some primes (of density $o({ 1 / {\log}^2\,n })$) cost much less time to prove than a general prime does. building on these celebrated results, this paper explores the possibility of designing a randomized primality-proving algorithm based on the aks algorithm. we first generalize berrizbeitia's algorithm to one which has higher density ($\omega( {1/{\log}\log n })$) of primes whose primality can be proved in time complexity $\tilde{o}(\log^{4} n)$. for a general prime, one round of ecpp is deployed to reduce its primality proof to the proof of a random easily proved prime, thus we achieve heuristic time complexity $\tilde{o}(\log^{4} n)$ for all primes.
on the bounded sum-of-digits discrete logarithm problem in finite fields. in this paper, we study the bounded sum-of-digits discrete logarithm problem in finite fields. our results are concerned primarily with fields fqn, where n|q - 1. the fields are called kummer extensions of fq. it is known that we can efficiently construct an element g with order exponential in n. let $s_q(\bullet)$ be the function from integers to the sum of digits in their q-ary expansions. we first present an algorithm that, given ge (0 $\leq$ e qn), finds e in random polynomial time, provided that sq (e) n. we then show that the problem is solvable in random polynomial time for most of the exponent e with sq (e) n by exploring an interesting connection between the discrete logarithm problem and the problem of list decoding of reed--solomon codes and applying the guruswami--sudan algorithm. as far as we are aware, our algorithm is the first one which can solve discrete logarithms of $2^{\log^{1-\epsilon}{q^n}}$ many instances in polynomial time for infinite many constant characteristic fields fqn. furthermore, since every finite field has an extension of reasonable degree, which is a kummer extension, our result reveals an unexpected property of the discrete logarithm problem, namely, the bounded sum-of-digits discrete logarithm problem in any given finite field becomes polynomial-time solvable in certain low degree extensions. as a side result, we obtain a sharper lower bound on the number of congruent polynomials generated by linear factors than the one based on the stothers--mason abc-theorem. we also prove that, in the field fqq-1, the bounded sum-of-digits discrete logarithm with respect to g can be computed in random time o(f(w)log4 (qq-1)), where f is a subexponential function and w is the bound on the q-ary sum-of-digits of the exponent; hence the problem is fixed parameter tractable. these results are shown to be generalized to artin--schreier extension fpp, where p is a prime.
lower and upper bounds on obtaining history independence. history independent data structures, presented by micciancio, are data structures that possess a strong security property: even if an intruder manages to get a copy of the data structure, the memory layout of the structure yields no additional information on the history of operations applied on the structure beyond the information obtainable from the content itself. naor and teague proposed a stronger notion of history independence in which the intruder may break into the system several times without being noticed and still obtain no additional information from reading the memory layout of the data structure. an open question posed by naor and teague is whether these two notions are equally hard to obtain. in this paper we provide a separation between the two requirements for comparison-based algorithms. we show very strong lower bounds for obtaining the stronger notion of history independence for a large class of data structures, including, for example, the heap and the queue abstract data structures. we also provide complementary upper bounds showing that the heap abstract data structure may be made weakly history independent in the comparison based model without incurring any additional (asymptotic) cost on any of its operations. (a similar result is easy for the queue.) thus, we obtain the first separation between the two notions of history independence. the gap we obtain is exponential: some operations may be executed in logarithmic time (or even in constant time) with the weaker definition, but require linear time with the stronger definition.
pricing via processing or combatting junk mail. we present a computational technique for combatting junk mail, in particular, and controlling access to a shared resource, in general. the main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. to this end we suggest several pricing functions, based on, respectively, extracting square roots modulo a prime, the fiat-shamir signature scheme, and the ong-schnorr-shamir (cracked) signature scheme.
an efficient existentially unforgeable signature scheme and its applications. a signature scheme is existentially unforgeable if, given any polynomial (in the security parameter) number of pairs (m>sub<1>/sub<, s(m>sub<1>/sub<)), (m>sub<2>/sub<, s(m>sub<2>/sub<)), ... (m>sub<k>/sub<, s(m>sub<k>/sub<)) where s(m) denotes the signature on the message m, it is computationally infeasible to generate a pair (m>sub<k+1>/sub<, s(m>sub<k+1>/sub<)) for any message m>sub<k+1>/sub< i {m>sub<1>/sub<, ... m>sub<k>/sub< }. we present an existentially unforgeable signature scheme that requires at most 6 times the amount of time needed to generate a signature using rsa (which is not existentially unforgeable), and point out applications where its use is desirable.
efficient non-malleable commitment schemes. non-malleability protects against man-in-the middle attacks on cryptographic protocols. non-malleable commitment schemes, for example, assure that a commitment of a message does not help to produce a commitment of a related message. here we present efficient constructions of such commitment schemes in the common reference string model, based on standard assumptions such as rsa, factoring or discrete logarithm. our protocols require only three rounds and a few modular exponentiations, and provide statistical or even perfect secrecy of committed values. we also discuss differences between the notion of non-malleable commitment schemes used in previous works by dolev, dwork and naor and by di&#x00a0;crescenzo, ishai and ostrovsky. the former definition requires that it is infeasible to find a commitment such that there exists an encapsulated message which is related to another committed value (non-malleability with respect to commitment). the second approach allows the existence of such messages, but then it is hard to find them and to output them in the opening phase (non-malleability with respect to opening). we note that our solutions are of the second type.
rsa-oaep is secure under the rsa assumption. recently victor shoup noted that there is a gap in the widely believed security result of oaep against adaptive chosen-ciphertext attacks. moreover, he showed that, presumably, oaep cannot be proven secure from the one-wayness of the underlying trapdoor permutation. this paper establishes another result on the security of oaep. it proves that oaep offers semantic security against adaptive chosen-ciphertext attacks, in the random oracle model, under the partial-domain one-wayness of the underlying permutation. therefore, this uses a formally stronger assumption. nevertheless, since partial-domain one-wayness of the rsa function is equivalent to its (full-domain) onewayness, it follows that the security of rsa-oaep can actually be proven under the sole rsa assumption, although the reduction is not tight.
on the security of multi-party ping-pong protocols. we define a p-party ping-pong protocol and its security problem, along the lines of dolev and yao's definition for twoparty ping-pong protocol. in the case of two parties, it was assumed, with no loss of generality, that there exists a single saboteur in the net and the protocol was defined to be secure iff it was secure against the active interventions of one saboteur. we show that for more than 2 parties this assumption can no longer be made and that for p parties 3(p-2) + 1 is a lower bound on the number of saboteurs which should be considered for the security problem. on the other hand we establish a 3(p-2) + 2 upper bound on the number of saboteurs which should be considered. we conclude that for a fixed p, p-party ping-pong protocols can be tested for security in 0(n3) time and 0(n2) space, when n is the length of the protocol. we show that if p, the number of participants in the protocol, is part of the input then the security problem becomes np-hard. relaxing the definition of a ping-pong protocol so that operators can operate on half words (thus introducing commutativity of the operators) causes the security problem to become undecidable.