52 research outputs found
Horizontal isogeny graphs of ordinary abelian varieties and the discrete logarithm problem
No full textFix an ordinary abelian variety defined over a finite field. The ideal class group of its endomorphism ring acts freely on the set of isogenous varieties with same endomorphism ring, by complex multiplication. Any subgroup of the class group, and generating set thereof, induces an isogeny graph on the orbit of the variety for this subgroup. We compute (under the Generalized Riemann Hypothesis) some bounds on the norms of prime ideals generating it, such that the associated graph has good expansion properties.
We use these graphs, together with a recent algorithm of Dudeanu, Jetchev and Robert for computing explicit isogenies in genus 2, to prove random self-reducibility of the discrete logarithm problem within the subclasses of principally polarizable ordinary abelian surfaces with fixed endomorphism ring. In addition, we remove the heuristics in the complexity analysis of an algorithm of Galbraith for explicitly computing isogenies between two elliptic curves in the same isogeny class, and extend it to a more general setting including genus 2
Computing Cyclic Isogenies between Principally Polarized Abelian Varieties over Finite Fields
No full textAbelian varieties are fascinating objects, combining the fields of geometry and arithmetic. While the interest in abelian varieties has long time been of purely theoretic nature, they saw their first real-world application in cryptography in the mid 1980's, and have ever since lead to broad research on the computational and the arithmetic side. The most instructive examples of abelian varieties are elliptic curves and Jacobian varieties of hyperelliptic curves, and they come naturally equipped with some additional structure, called a principal polarization. Morphisms between abelian varieties that respect both the geometric and the arithmetic structure are called isogenies. In this thesis we focus on the computation of isogenies with cyclic kernel between principally polarized abelian varieties over finite fields.GR-JETMATHGEO
Generalized Norm-compatible Systems on Unitary Shimura Varieties
No full textWe define and study in terms of integral Iwahoriâ Hecke algebras a new class of geometric operators acting on the Bruhat-Tits building of connected reductive groups over p-adic fields. These operators, which we call U-operators, generalize the geometric notion of "successors" for trees with a marked end. The first main contributions of the thesis are:
(i) the integrality of the U-operator over the spherical Hecke algebra using the compatibility between Bernstein and Satake homomorphisms,
(ii) in the unramified case, the U-operator attached to a cocharacter is a right root of the corresponding Hecke polynomial.
In the second part of the thesis, we study some arithmetic aspects of special cycles on (products of) unitary Shimura varieties, these cycles are expected to yield new results towards the Blochâ Beilinson conjectures. As a global application of (ii), we obtain:
(iii) the horizontal norm relations for these GGP cycles for arbitrary n, at primes where the unitary group splits.
The general local theory developed in the first part of the thesis, has the potential to result in a number of global applications along the lines of (iii) (involving other Shimura varieties and also vertical norm relations) and offers
new insights into topics such as the Blasiusâ Rogawski conjecture as well.GR-JETMATHGEO
Computational Aspects of Jacobians of Hyperelliptic Curves
No full textNowadays, one area of research in cryptanalysis is solving the Discrete Logarithm Problem (DLP) in finite groups whose group representation is not yet exploited. For such groups, the best one can do is using a generic method to attack the DLP, the fastest of which remains the Pollard rho algorithm with -adding walks. For the first time, we rigorously analyze the Pollard rho method with -adding walks and prove a complexity bound that differs from the birthday bound observed in practice by a relatively small factor. There exist a multitude of open questions in genus cryptography. In this case, the DLP is defined in large prime order subgroups of rational points that are situated on the Jacobian of a genus~ curve defined over a large characteristic finite field. We focus on one main topic, namely we present a new efficient algorithm for computing cyclic isogenies between Jacobians. Comparing to previous work that computes non cyclic isogenies in genus~, we need to restrict to certain cases of polarized abelian varieties with specific complex multiplication and real multiplication. The algorithm has multiple applications related to the structure of the isogeny graph in genus~, including random self-reducibility of DLP. It helps support the widespread intuition of choosing \emph{any} curve in a class of curves that satisfy certain public and well studied security parameters. Another topic of interest is generating hyperelliptic curves for cryptographic applications via the CM method that is based on the numerical estimation of the rational Igusa class polynomials. A recent development relates the denominators of the Igusa class polynomials to counting ideal classes in non maximal real quadratic orders whose norm is not prime to the conductor. Besides counting, our new algorithm provides precise representations of such ideal classes for all real quadratic fields and is part of an implementation in Magma of the recent theoretic work in the literature on the topic of denominators.LACA
Random
No full textself-reducibility and bit security of the elliptic curve Diffie–Hellman secret key
How to Fake Auxiliary Input
No full textAbstract. Consider a joint distribution (X,A) on a set X ×{0, 1}ℓ. We show that for any family F of distinguishers f: X × {0, 1}ℓ → {0, 1}, there exists a simulator h: X → {0, 1}ℓ such that 1. no function in F can distinguish (X,A) from (X,h(X)) with advantage ǫ, 2. h is only O(23ℓǫ−2) times less efficient than the functions in F. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ǫ> 0 is negligible and F consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt’09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem.
XorSHAP: Privacy-Preserving Explainable AI for Decision Tree Models
No full textExplainable AI (XAI) refers to the development of AI systems and machine learning models in a way that humans can understand, interpret and trust the predictions, decisions and outputs of these models. A common approach to explainability is feature importance, that is, determining which input features of the model have the most significant impact on the model prediction. Two major techniques for computing feature importance are LIME (Local Interpretable Model-agnostic Explanations) and SHAP (SHapley Additive exPlanations). While very generic, these methods are computationally expensive even in plaintext. Applying them in the privacy-preserving setting when part or all of the input data is private is therefore a major computational challenge.
In this paper, we present - the first practical privacy-preserving algorithm for computing Shapley values for decision tree ensemble models in the semi-honest Secure Multiparty Computation (SMPC) setting with full threshold. Our algorithm has complexity , where is the number of decision trees in the ensemble, is the depth of the decision trees and is the maximum of the number of features and (the number of leaf nodes of a tree), and scales to real-world datasets. Our implementation is based on Inpher\u27s framework and simultaneously computes (in the SMPC setting) the Shapley values for 100 samples for an ensemble of trees of depth and features in just 7.5 minutes, meaning that the Shapley values for a single prediction are computed in just 4.5 seconds for the same decision tree ensemble model.
Additionally, it is parallelization-friendly, thus, enabling future work on massive hardware acceleration with GPUs
Hardness of Computing Individual Bits for One-way Functions on Elliptic Curves
No full textWe prove that if one can predict any of the bits of the input to an elliptic curve based one-way function over a finite field, then we can invert the function. In particular, our result implies that if one can predict any of the bits of the input to a classical pairing-based one-way function with non-negligible advantage over a random guess then one can efficiently invert this function and thus, solve the Fixed Argument Pairing Inversion problem (FAPI-1/FAPI-2). The latter has implications on the security of various pairing-based schemes such as the identity-based encryption scheme of Boneh–Franklin, Hess’ identity-based signature scheme, as well as Joux’s three-party one-round key agreement protocol. Moreover, if one can solve FAPI-1 and FAPI-2 in polynomial time then one can solve the Computational Diffie--Hellman problem (CDH) in polynomial time. Our result implies that all the bits of the functions defined above are hard-to-compute assuming these functions are one-way. The argument is based on a list-decoding technique via discrete Fourier transforms due to Akavia--Goldwasser–Safra as well as an idea due to Boneh–Shparlinski.LASECLACA
Analysis of non-uniform magnetic flux distribution in conical rotor double-speed induction motors
No full textXorSHAP: Privacy-Preserving Explainable AI for Decision Tree Models
No full textExplainable AI (XAI) refers to the development of AI systems and machine learning models in a way that humans can understand, interpret and trust the predictions, decisions and outputs of these models. A common approach to explainability is feature importance, that is, determining which input features of the model have the most significant impact on the model prediction. Two major techniques for computing feature importance are LIME (Local Interpretable Model-agnostic Explanations) and SHAP (SHapley Additive exPlanations). While very generic, these methods are computationally expensive even when the data is not encrypted. Applying them in the privacy-preserving setting when part or all of the input data is private is therefore a major computational challenge. In this paper, we present XorSHAP - the first practical data-oblivious algorithm for computing SHAP values for decision tree ensemble models. The algorithm is applicable in various privacy-preserving settings such as SMPC, FHE and differential privacy. Our algorithm has complexity , where is the number of decision trees in the ensemble, is the depth of the decision trees and is the maximum of the number of features and (the number of leaf nodes of a tree), and scales to real-world datasets. We implement the algorithm in the semi-honest Secure Multiparty Computation (SMPC) setting with full threshold using Inpher\u27s Manticore framework. Our implementation simultaneously computes the SHAP values for 100 samples for an ensemble of trees of depth and features in just 7.5 minutes, meaning that the SHAP values for a single prediction are computed in just 4.5 seconds for the same decision tree ensemble model. Additionally, it is parallelization-friendly, thus, enabling future work on massive hardware acceleration with GPUs. </p
- …
