26838 research outputs found
Sort by
Secure showing of partial attributes
Get PDFAnonymous Attribute-Based Credentials (ABCs) allow users to
prove possession of attributes while adhering to various authen-
tication policies and without revealing unnecessary information.
Single-use ABCs are particularly appealing for their lightweight
nature and practical efficiency. These credentials are typically built
using blind signatures, with Anonymous Credentials Light (ACL)
being one of the most prominent schemes in the literature. However,
the security properties of single-use ABCs, especially their secure
showing property, have not been fully explored, and prior defini-
tions and corresponding security proofs fail to address scenarios
involving partial attribute disclosure effectively. In this work, we
propose a stronger secure showing definition that ensures robust
security even under selective attribute revelation. Our definition
extends the winning condition of the existing secure showing ex-
periment by adding various constraints on the subsets of opened
attributes. We show how to represent this winning condition as a
matching problem in a suitable bipartite graph, thus allowing for
it to be verified efficiently. We then prove that ACL satisfies our
strong secure showing notion without any modification. Finally,
we define double-spending prevention for single-use ABCs, and
show how ACL satisfies the definition
Infinite-horizon Fuk-Nagaev inequalities
No full textWe develop explicit bounds for the tail of the distribution of the all-time supremum of a random walk with negative drift, where the increments have a truncated heavy-tailed distribution. As an application, we consider a ruin problem in the presence of reinsurance
Biologically plausible reinforcement learning of deep cognitive processing
No full textCan we enable biologically plausible neural networks to learn complex cognitive functions? In this thesis, I developed novel learning rules and training methods that are inspired from neuroscience and investigated how well artificial neural networks trained with these techniques align with the behaviour and neural activity from animals performing the same tasks. In the second chapter, I designed a simplified model trained with a local learning rule to perform tasks that require the flexible use of memory, both within trials and across learning experiences through meta-learning. I demonstrated that these networks exhibit important characteristics also observed in animals trained on these tasks. In the third chapter, I extended this learning rule to deeper architectures to investigate how memories are represented and maintained through the different layers of the network. In the fourth chapter, I accelerated and improved the learning dynamics of networks trained with reinforcement learning so they can scale to larger, more complex problems such as ImageNet. Finally, I summarise these findings and discuss how to place them in a broader context, delineating which challenges and opportunities remain for the field. Overall, the chapters in this thesis contribute to the advancement of more flexible and scalable biologically plausible neural networks for deep cognitive control
Hidden convexity, optimization, and algorithms on rotation matrices
Get PDFThis paper studies hidden convexity properties associated with constrained optimization problems over the set of rotation matrices SO(n). Such problems are nonconvex because of the constraint X ∈ SO(n). Nonetheless, we show that certain linear images of SO(n) are convex, opening up the possibility for convex optimization algorithms with provable guarantees for these problems. Our main technical contributions show that any two-dimensional image of SO(n) is convex and that the projection of SO(n) onto its strict upper triangular entries is convex. These results allow us to construct exact convex reformulations for constrained optimization problems over SO(n) with a single constraint or with constraints defined by low-rank matrices. Both of these results are maximal in a formal sense
Wagner’s algorithm provably runs in subexponential time for SIS∞
Get PDFAt CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LWE) in slightly subexponential time for modulus q=nΘ(1) and narrow error distribution, when given enough LWE samples. Taking a modular view, one may regard BKW as a combination of Wagner’s algorithm (CRYPTO 2002), run over the corresponding dual problem, and the Aharonov-Regev distinguisher (JACM 2005). Hence the subexponential Wagner step alone should be of interest for solving this dual problem – namely, the Short Integer Solution problem (SIS) – but this appears to be undocumented so far. We re-interpret this Wagner step as walking backward through a chain of projected lattices, zigzagging through some auxiliary superlattices. We further randomize the bucketing step using Gaussian randomized rounding to exploit the powerful discrete Gaussian machinery. This approach avoids sample amplification and turns Wagner’s algorithm into an approximate discrete Gaussian sampler for q-ary lattices. For an SIS lattice with n equations modulo q, this algorithm runs in subexponential time exp(O(n/loglogn)) to reach a Gaussian width parameter of, say, s=q/polylog(n) only requiring m=n+ω(n/loglogn) many SIS variables. For instance, this directly provides a provable algorithm for solving the Short Integer Solution problem in the infinity norm (SIS∞) for norm bounds β=q/polylog(n). This variant of SIS underlies the security of the NIST post-quantum cryptography standard ML-DSA, also known as Dilithium. Despite its subexponential complexity, Wagner’s algorithm does not appear to threaten ML-DSA’s concrete security
First-order hybrid separation logic
Get PDFThe basic set-theoretic interpretation of the separating connectives of first-order separation logic allows for an effective, sound and complete axiomatization in a hybrid extension
MMSys '25: Proceedings of the 16th ACM Multimedia Systems Conference
No full textWe are delighted to announce the technical program for the 16th ACM Multimedia Systems Conference (MMSys'25). While other venues focus on specific aspects related to multimedia systems, MMSys serves as an inclusive and interdisciplinary forum, spanning a broad range of topics related to multimedia systems such as networking, operating systems, real-time systems, databases, mobile computing, distributed systems, computer vision, and middleware communities. This provides a unique opportunity to investigate the intersections and the interplay of the various approaches and solutions developed across these domains
Scalable and fine-tuned privacy pass from group verifiable random functions
No full textAnonymous token schemes are cryptographic protocols for limiting the access to online resources to credible users. The resource provider issues a set of access tokens to the credible user that they can later redeem anonymously, i.e., without the provider being able to link their redemptions. When combined with credibility tests such as CAPTCHAs, anonymous token schemes can significantly increase user experience and provider security, without exposing user access patterns to providers.Current anonymous token schemes such as the Privacy Pass protocol by Davidson et al. rely on oblivious pseudorandom functions (OPRFs), which let server and user jointly compute randomly looking access tokens. For those protocols, token issuing costs are linear in the number of requested tokens.In this work, we propose a new approach for building anonymous token schemes. Instead of relying on two-party computation to realize a privacy-preserving pseudorandom function evaluation, we propose to offload token generation to the user by using group verifiable random functions (GVRFs). GVRFs are a new cryptographic primitive that allow users to produce verifiable pseudorandomness. Opposed to standard VRFs, verification is anonymous within the group of credible users. We give a construction of group VRFs from the Dodis-Yampolskiy VRF and EquivalenceClass Signatures, based on pairings and a new Diffie-Hellman inversion assumption that we analyze in the Generic Group Model. Our construction enjoys compact public keys and proofs, while evaluation and verification costs are only slightly increased compared to the Dodis-Yampolskiy VRF.By deploying a group VRF instead of a OPRF, we obtain an anonymous token scheme where communication as well as server-side computation during the issuing phase is constant and independent of the number of tokens a user requests. Moreover, by means of our new concept of updatable token policies, the number of unspent tokens in circulation can retrospectively (i.e., even after the credibility check) be decreased or increased in order to react to the current or expected network situation. Our tokens are further countable and publicly verifiable. This comes at the cost of higher computational efforts for token redemption and verification as well as somewhat weaker unlinkability guarantees compared to Privacy Pass
Derivative-free stochastic bilevel optimization for inverse problems
Get PDFInverse problems are key issues in several scientific areas, including signal processing and medical imaging. Data-driven approaches for inverse problems aim for learning model and regularization parameters from observed data samples, and investigate their generalization properties when confronted with unseen data. This approach dictates a statistical approach to inverse problems, calling for stochastic optimization methods. In order to learn model and regularisation parameters simultaneously, we develop in this paper a stochastic bilevel optimization approach in which the lower level problem represents a variational reconstruction method formulated as a convex non-smooth optimization problem, depending on the observed sample. The upper level problem represents the learning task of the regularisation parameters. Combining the lower level and the upper level problem leads to a stochastic non-smooth and non-convex optimization problem, for which standard gradient-based methods are not straightforward to implement. Instead, we develop a unified and flexible methodology, building on a derivative-free approach, which allows us to solve the bilevel optimization problem only with samples of the objective function values. We perform a complete complexity analysis of this scheme. Numerical results on signal denoising and experimental design demonstrate the computational efficiency and the generalization properties of our method