In this work, we explore the recent developments related to lattice‐based signature and preimage sampling, and specify a compact identity‐based signature (IBS) on an ideal lattice for practical use. Specifically, we first propose an ellipsoid version of the G + G signature scheme (Asiacrypt 2023) that achieves slightly better signature size and higher security. Then, by adapting a specific preimage sampling algorithm to the modified G + G signature, we obtain an efficient IBS scheme. In addition, we prove its security in the quantum random oracle model (QROM), following the paradigm introduced by Zhangdry (Crypto 2012). Finally, a complete specification of the IBS, featuring three distinct parameter sets, is accompanied by a proof‐of‐concept implementation. We believe that the combination of the preimage sampling with the Fiat–Shamir transformation holds potential for application in the other advanced digital signature schemes.

Universal composability (UC) is a primary security flavor for designing oblivious transfer (OT) due to its advantage of arbitrary composition. However, the study of UC‐secure OT over lattices is still far behind compared with constructions over prequantum assumptions. Relying on the learning with errors (LWE) assumption, Quach proposes a dual‐mode encryption scheme (SCN’20) for deriving a two‐round OT whose security is provably UC‐secure in the common reference string (CRS) model. Due to its use of a randomized rounding function proposed by Benhamouda et al. (PKC’18), this OT can only be limited to transmitting single‐bit messages. Therefore, conducting trivial repetitions of Quach’s OT when transmitting multibit strings would be very costly. In this work, we put forward a modified dual‐mode encryption cryptosystem under the decisional LWE assumption, from which we can derive a UC‐secure string OT with both full‐fledged dual‐mode security and better efficiency on transmitting strings. The key technique we adopt is a key reconciliation scheme proposed by Jiang et al. (PKC’20), which is utilized to extend the single‐bit symmetric encryption key (produced by the aforementioned rounding function) to a multibit case. Through a comprehensive performance analysis, we demonstrate that our proposal can indeed strike a balance between security and efficiency.

Lattice‐based encryption schemes are significant cryptographic primitives to defend information security against quantum menace, and the decryption failure rate is related to both theoretical and realistic security. We quantitatively analyze how the floating‐point arithmetic and neglecting small probabilities impact the precision, and propose a new effective and efficient test of the failure probability. Therein explicit criteria are given to select the floating‐point datatype and to decide which small probabilities should be abandoned. Furthermore, the outcome is theoretically ensured to meet a given precision. Moreover, by combining the heuristic estimate and the precise simulation, this test is more efficient than previously neglecting small probabilities in a practical way.

We consider a price-based revenue management problem with reusable resources over a finite time horizon $T$. The problem finds important applications in car/bicycle rental, ridesharing, cloud computing, and hospitality management. Customers arrive following a price-dependent Poisson process and each customer requests one unit of $c$ homogeneous reusable resources. If there is an available unit, the customer gets served within a price-dependent exponentially distributed service time; otherwise, she waits in a queue until the next available unit. The decision maker assumes that the inter-arrival and service intervals have an unknown linear dependence on a $d_f$-dimensional feature vector associated with the posted price. We propose a rate-optimal online learning and pricing algorithm, termed Batch Linear Confidence Bound (BLinUCB), and prove that the cumulative regret is $\tilde{O}( d_f \sqrt{T } )$. In establishing the regret, we bound the transient system performance upon price changes via a coupling argument, and also generalize linear bandits to accommodate sub-exponential rewards.

We consider a price-based network revenue management problem with multiple products and multiple reusable resources. Each randomly arriving customer requests a product (service) that needs to occupy a sequence of reusable resources (servers). We adopt an incomplete information setting where the firm does not know the price-demand function for each product and the goal is to dynamically set prices of all products to maximize the total expected revenue of serving customers. We propose novel batched bandit learning algorithms for finding near-optimal pricing policies, and show that they admit a near-optimal cumulative regret bound of $\tilde{O}(J\sqrt{XT})$, where $J$, $X$, and $T$ are the numbers of products, candidate prices, and service periods, respectively. As part of our regret analysis, we develop the first finite-time mixing time analysis of an open network queueing system (i.e., the celebrated Jackson Network), which could be of independent interest. Our numerical studies show that the proposed approaches perform consistently well.

Abstract For the purpose of improving the efficiency of the cryptosystems built upon lattice trapdoors, Chen, Genise and Mukherjee at ASIACRYPT 2019 modified the gadget trapdoor (G‐trapdoor) to an approximate trapdoor, which enables one to sample short preimages approximately from a discrete Gaussian distribution. The implementation shows that the sizes of the hash‐and‐sign signature scheme can be reduced to 3.67 kB for an estimation of 81.67‐bit security, and 9.97 kB for an estimation of 168.81‐bit security. In this study, the spherical sampling method is adapted to the non‐spherical setting, without leaking any information about the trapdoor. Due to the fact that the signature size and the concrete security are closely related to the Gaussian parameter of the sampling algorithm, this technique provides a tradeoff between them. Specifically, two modes of parameters were set up for different goals. (a) Mode 1 admits to achieve the ‘win–win’ scenario, that is, gain concrete security and simultaneously reduce the signature size. Our proof‐of‐concept implementation shows that for an estimation of 94.5‐ and 185.88‐bit security, the signature sizes can be reduced to 3.3 and 6.98 kB. (b) Mode 2 aims mainly to further reduce the signature sizes, without a decrease in the security level. The implementation shows that the signature size can be reduced to 2.35 kB for an estimation of 81.67‐bit security, and 5.75 kB for an estimation of 168.82‐bit security.

For group signature (GS) supporting membership revocation, verifier-local revocation (VLR) mechanism seems to be a more flexible choice, because it requires only that verifiers download up-to-date revocation information for signature verification, and the signers are not involved. As a post-quantum secure cryptographic counterpart of classical number-theoretic cryptographic constructions, the first lattice-based VLR group signature (VLR-GS) was introduced by Langlois et al. (2014). However, none of the contemporary lattice-based VLR-GS schemes provide backward unlinkability (BU), which is an important property to ensure that previously issued signatures remain anonymous and unlinkable even after the corresponding signer (i.e., member) is revoked. In this study, we introduce the first lattice-based VLR-GS scheme with BU security (VLR-GS-BU), and thus resolve a prominent open problem posed by previous works. Our new scheme enjoys an $${\cal O}\left( {\log \,N} \right)$$ factor saving for bit-sizes of the group public-key (GPK) and the member’s signing secret-key, and it is free of any public-key encryption. In the random oracle model, our scheme is proven secure under two well-known hardness assumptions of the short integer solution (SIS) problem and learning with errors (LWE) problem.

A lower bound for a finite-scenario-based chance-constrained program is the quantile value corresponding to the sorted optimal objective values of scenario subproblems. This quantile bound can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. The quality of the bound depends on how the scenarios are grouped. In this paper, we formulate a mixed-integer bilevel program that optimally groups scenarios to tighten the quantile bounds. For general chance-constrained programs, we propose a branch-and-cut algorithm to optimize the bilevel program, and for chance-constrained linear programs, a mixed-integer linear-programming reformulation is derived. We also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results demonstrate that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root-node gaps and better performance of scenario decomposition for solving chance-constrained 0-1 programs. Also, the optimal grouping bounds can be greatly strengthened using larger group size. Summary of Contribution: Chance-constrained programs are in general NP-hard but widely used in practice for lowering the risk of undesirable outcomes during decision making under uncertainty. Assuming finite scenarios of uncertain parameter, chance-constrained programs can be reformulated as mixed-integer linear programs with binary variables representing whether or not the constraints are satisfied in corresponding scenarios. A useful quantile bound for solving chance-constrained programs can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. In this paper, we develop algorithms for optimally and heuristically grouping scenarios to tighten the quantile bounds. We aim to improve both the computation and solution quality of a variety of chance-constrained programs formulated for different Operations Research problems.