Abstract Since the advent of Bitcoin, cryptocurrencies have gained substantial popularity, and crypto wallets have evolved into the predominant tool for safeguarding and managing cryptographic keys to access cryptocurrency funds. Deterministic wallets are proposed as an advanced wallet mechanism to provide benefits such as low-maintenance, easy backup and recovery, and support for functionalities required by cryptocurrencies. Alkeilani Alkadri et al. (ACM CCS’20) presented the first post-quantum secure deterministic wallet scheme, but it exhibits a gap to bridge before achieving practical applicability, as reflected in both their concrete parameters size and computational efficiency. In this paper, we propose an efficient post-quantum secure deterministic wallet scheme. In particular, we present a new construction method for deterministic wallets, prove the security in the quantum random oracle model, and provide an efficient instantiation. The comparison result, with the work of Alkeilani Alkadri et al. (ACM CCS’20), shows our work has a comprehensive improvement on efficiency, e.g., the pk size is $$\approx 40.7$$ ≈ 40.7 times shorter, sk is $$\approx 9.2$$ ≈ 9.2 times shorter, and the signing time is $$\approx 3.1$$ ≈ 3.1 times faster.

At present, with the popularity of Internet of things (IoT), a huge number of datasets generated by IoT devices are being uploaded to the cloud storage in remote data management service, but a series of security and privacy defects also arises, where one of the best ways for preventing data disclosure is encryption. Among them, searchable encryption (SE) is considered to be a very attractive cryptographic technology, since it allows users to search records in an encrypted form and to protect user’s data on an untrusted server. For the sake of enhancing search permission, attribute-based keyword search (ABKS) is an efficient method to provide secure search queries and fine-grained access authentications over ciphertexts. However, most existing ABKS schemes concentrate on single keyword search, which usually returns redundant and irrelevant results, so it would cost some unnecessary computation and communication resources. Furthermore, existing work in the literature mostly only supports unshared multiowner where a specific data owner owns each file, which is not able to satisfy more desired expressive search. In this work, we propose a novel attribute-based multikeyword search for shared multiowner (ABMKS-SM) primitive in IoT to achieve enhanced access control for users; meanwhile, it can support multikeyword search over ciphertexts and give a formal security analysis in the adaptive against chosen keyword attack (IND-CKA) model. Finally, we have also implemented this prototype to show efficiency when compared with some previous schemes.

A model predictive control with online inductance estimator (OIEMPC) for three-phase VIENNA rectifiers is presented in this paper. An OIE adopting the dynamic filtering method and least square algorithm is proposed to further improve system robustness. In this OIE, the VIENNA rectifier pole voltages are obtained by computation utilizing the gate signals of the switching devices, AC current direction and the DC voltage, so that no additional voltage sensors are needed. Compared to the conventional MPC with finite control set (FCS-MPC), the proposed strategy can have better control performance, which effectively improves the robustness of the system. The effectiveness and correctness of the proposed OIEMPC method are demonstrated by the results of Simulink experiments.

Search engine users always endeavor to formulate proper search queries during online search. To help users accurately express their information need during search, search engines are equipped with query suggestions to refine users' follow-up search queries. The success of a query suggestion system counts on whether we can understand and model user search intent accurately. In this work, we propose Click Feedback-Aware Network (CFAN) to provide feedback-aware query suggestions. In addition to modeling sequential search queries issued by a user, CFAN also considers user clicks on previous suggested queries as the user feedback. These clicked suggestions, together with the issued search query sequence, jointly capture the underlying search intent of users. In addition, we explicitly focus on improving the robustness of the query suggestion system through adversarial training. Adversarial examples are introduced into the training of the query suggestion system, which not only improves the robustness of system to nuisance perturbations, but also enhances the generalization performance for original training data. Extensive experiments are conducted on a recent real search engine log. The experimental results demonstrate that the proposed method, CFAN, outperforms competitive baseline methods across various situations on the task of query suggestion.

Reserve price becomes a critical issue in mechanism design of keyword auctions mostly because of the potential revenue increase brought up by it. In this paper, we focus on a sub-problem in reserve pricing, that is, how to estimate the bids distribution from the truncated samples and further calculate the optimal reserve price in an iterative setting. To the best of our knowledge, this is the first paper to discuss this problem. We propose to use maximum likelihood estimate (MLE) to solve the problem, and we prove that it is an unbiased method for distribution estimation. Moreover, we further simulate the iterative optimal reserve price calculating and updating process based on the estimated distribution. The experimental results are interpreted in terms of the robustness of MLE to truncated sample size and initial reserve price (truncated value), and the convergence of subsequent optimal reserve price in the iterative updating process is also discussed. We conclude that MLE is reliable enough to be applied in real-world optimal reserve pricing in keyword auctions.

Many applications of collaborative filtering (CF), such as news item recommendation and bookmark recommendation, are most naturally thought of as one-class collaborative filtering (OCCF) problems. In these problems, the training data usually consist simply of binary data reflecting a user's action or inaction, such as page visitation in the case of news item recommendation or webpage bookmarking in the bookmarking scenario. Usually this kind of data are extremely sparse (a small fraction are positive examples), therefore ambiguity arises in the interpretation of the non-positive examples. Negative examples and unlabeled positive examples are mixed together and we are typically unable to distinguish them. For example, we cannot really attribute a user not bookmarking a page to a lack of interest or lack of awareness of the page. Previous research addressing this one-class problem only considered it as a classification task. In this paper, we consider the one-class problem under the CF setting. We propose two frameworks to tackle OCCF. One is based on weighted low rank approximation; the other is based on negative example sampling. The experimental results show that our approaches significantly outperform the baselines.

We consider the budget-constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple-choice) knapsack problem. We design both deterministic and randomized algorithms for the online (multiple-choice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget-constrained advertiser. Our bidding strategy for revenue maximization is oblivious (i.e., without knowledge) of other bidders' prices and/or click-through-rates for those positions. We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding performance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a performance ratio above 90% against the optimum by the omniscient bidder.

We model budget-constrained keyword bidding in sponsored search auctions as a stochastic multiple-choice knapsack problem (S-MCKP) and design an algorithm to solve S-MCKP and the corresponding bidding optimization problem. Our algorithm selects items online based on a threshold function which can be built/updated using historical data. Our algorithm achieved about 99% performance compared to the offline optimum when applied to a real bidding dataset. With synthetic dataset and iid item-sets, its performance ratio against the offline optimum converges to one empirically with increasing number of periods.

We study vindictive bidding, a strategic bidding behavior in keyword auctions where a bidder forces his competitor to pay more without affecting his own payment. We show that most Nash equilibria (NE) are vulnerable to vindictive bidding and are thus unstable. There always exists a pure strategy Nash equilibrium (PSNE) if there is only one pair of vindictive players; however PSNE may not exist when there are at least three players who are all vindictive with each other. Given the set of vindictive bidding pairs, we show how to compute a PSNE if one exists. Preliminary data analysis suggests that vindictive bidding is prevalent in real-world keyword auctions. As an ongoing work, we also propose several interesting open problems related to vindictive bidding.

This article presents a design for the Denali-2 superoptimizer, which will generate minimum-instruction-length machine code for realistic machine architectures using automatic theorem-proving technology: specifically, using E-graph matching (a technique for pattern matching in the presence of equality information) and Boolean satisfiability solving.This article presents a precise definition of the underlying automatic programming problem solved by the Denali-2 superoptimizer. It sketches the E-graph matching phase and presents a detailed exposition and proof of soundness of the reduction of the automatic programming problem to the Boolean satisfiability problem.

No abstract available.

We describe a new class of utility-maximization scheduling problem with precedence constraints, the disconnected staged scheduling problem (DSSP). DSSP is a nonpreemptive multiprocessor deadline scheduling problem that arises in several commercially-important applications, including animation rendering, protein analysis, and seismic signal processing. DSSP differs from most previously-studied deadline scheduling problems because the graph of precedence constraints among tasks within jobs is disconnected, with one component per job. Another difference is that in practice we often lack accurate estimates of task execution times, and so purely offline solutions are not possible. However we do know the set of jobs and their precedence constraints up front and therefore some offline planning is possible.Our solution decomposes DSSP into an offline job selection phase followed by an online task dispatching phase. We model the former as a knapsack problem and explore several solutions to it, describe a new dispatching algorithm for the latter, and compare both with existing methods. Our theoretical results show that while DSSP is NP-hard and inapproximable in general, our two-phase scheduling method guarantees a good performance bound for many special cases. Our empirical results include an evaluation of scheduling algorithms on a real animation-rendering workload; we present a characterization of this workload in a companion paper. The workload records eight weeks of activity on a 1,000-CPU cluster used to render portions of the full-length animated feature film Shrek 2 in 2004. We show that our improved scheduling algorithms can substantially increase the aggregate value of completed jobs compared to existing practices. Our new task dispatching algorithm LCPF performs well by several metrics, including job completion times as well as the aggregate value of completed jobs.

We consider the problem of approximate range counting over streams of d-dimensional points. In the data stream model, the algorithm makes a single scan of the data, which is presented in an arbitrary order, and computes a compact summary (called a sketch). The sketch, whose size depends on the approximation parameter ε, can be used to count the number of points inside a query range within additive error εn, where n is the size of the stream. We present several results, deterministic and randomized, for both rectangle and halfplane ranges.

We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with or, more generally, as the pth power of the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared to the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to 1 + 2/√3 ≈ 2.15. We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L2 norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.

Structural comparison of large trees is a difficult task that is only partially supported by current visualization techniques, which are mainly designed for browsing. We present TreeJuxtaposer, a system designed to support the comparison task for large trees of several hundred thousand nodes. We introduce the idea of "guaranteed visibility", where highlighted areas are treated as landmarks that must remain visually apparent at all times. We propose a new methodology for detailed structural comparison between two trees and provide a new nearly-linear algorithm for computing the best corresponding node from one tree to another. In addition, we present a new rectilinear Focus+Context technique for navigation that is well suited to the dynamic linking of side-by-side views while guaranteeing landmark visibility and constant frame rates. These three contributions result in a system delivering a fluid exploration experience that scales both in the size of the dataset and the number of pixels in the display. We have based the design decisions for our system on the needs of a target audience of biologists who must understand the structural details of many phylogenetic, or evolutionary, trees. Our tool is also useful in many other application domains where tree comparison is needed, ranging from network management to call graph optimization to genealogy.

Reasoning precisely about the side effects of procedure calls is important to many program analyses. This paper introduces a technique for specifying and statically checking the side effects of methods in an object-oriented language. The technique uses data groups, which abstract over variables that are not in scope, and limits program behavior by two alias-confining restrictions, pivot uniqueness and owner exclusion. The technique is shown to achieve modular soundness and is simpler than previous attempts at solving this problem.

We develop a combinatorial algorithm for determining a minimum volume simplex enclosing a set of points in ${\cal R}^3$. If the convex hull of the points has n vertices, then our algorithm takes $\Theta(n^4)$ time. Combining our exact but slow algorithm with a simple but crude approximation technique, we also develop an $\varepsilon$-approximation algorithm. The algorithm computes in $O(n + 1/\varepsilon^6)$ time a simplex whose volume is within $(1 + \varepsilon)$ factor of the optimal for any $\varepsilon > 0$.

Bounding boxes are commonly used in computer graphics and other fields to improve the performance of algorithms that should process only the intersecting objects.A bounding-box-based heuristic avoids unnecessary intersection processing by eliminating the pairs whose bounding boxes are disjoint.Empirical evidence suggests that the heuristic works well in many practical applications, although its worst-case performance can be bad for certain pathological inputs.What is a pathological input, however, is not well understood, and consequently there is no guarantee that the heuristic will always work well in a specific application.In this paper, we analyze the performance of bounding box heuristic in terms of two natural shape parameters, aspect ratio and scale factor.These parameters can be used to realistically measure the degree to which the objects are pathologically shaped.We derive tight worst-case bounds on the performance for bounding box heuristic.One of the significant contributions of our paper is that we only require that objects be well shaped on average.Somewhat surprisingly, the bounds are significantly different from the case when all objects are well shaped.