280 research outputs found
Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms
No full textThere has been recent interest in dynamic string algorithms, i.e. string problems where the input changes dynamically. One such problem is the longest common factor (LCF) problem. It is well known that the LCF of two strings S and D of length n over a fixed constant-sized alphabet Sigma can be computed in time linear in n. Recently, a new challenge was introduced - finding the LCF of two strings in a dynamic setting. The problem is the fully dynamic one sided LCF (FDOS-LCF) problem. In the FDOS-LCF problem we get q consecutive queries of the form , where each such query means: "replace D[i] by alpha, alpha in Sigma and output the LCF of S and (the updated) D. The goal is to initially preprocess S and D so that we do not need O(n) time to compute an LCF for each such query.
The state-of-the-art is an algorithm that preprocesses the two strings S and D in time O(n log^4 n). Subsequently, the algorithm answers in time O(log^3 n) a single query of the form: Given a position i on D and a letter alpha, return an LCF of S and D', where D' is the string resulting from D after substituting D[i] with alpha. That algorithm is not extendable to multiple queries. In this paper we present a tool - Locally Maximal Common Factors (LMCF) - that proves to be quite useful in solving some restricted versions of the FDOS-LCF problem . The versions we solve are the Decremental FDOS-LCS problem, where every change is of the form , omega !in Sigma, and the Periodic FDOS-LCS problem, where S is a periodic string with period length p.
For the decremental problem we provide an algorithm with linear time preprocessing and O(log log n) time per query. For the periodic problem our preprocessing time is linear and the query time is O(p log log n)
Revisiting the Nova Proof System on a Cycle of Curves
No full textNova is an efficient recursive proof system built from an elegant folding scheme for (relaxed) R1CS statements. The original Nova paper (CRYPTO'22) presented Nova using a single elliptic curve group of order p. However, for improved efficiency, the implementation of Nova alters the scheme to use a 2-cycle of elliptic curves. This altered scheme is only described in the code and has not been proven secure. In this work, we point out a soundness vulnerability in the original implementation of the 2-cycle Nova system. To demonstrate this vulnerability, we construct a convincing Nova proof for the correct evaluation of 2^{75} rounds of the Minroot VDF in only 116 milliseconds. We then present a modification of the 2-cycle Nova system and formally prove its security. The modified system also happens to be more efficient than the original implementation. In particular, the modification eliminates an R1CS instance-witness pair from the recursive proof. The implementation of Nova has now been updated to use our optimized and secure system. In addition, we show that the folding mechanism at the core of Nova is malleable: given a proof for some statement z, an adversary can construct a proof for a related statement z', at the same depth as z, without knowledge of the witness for z'
Cryptanalysis of RSA with Private Key d Less Than N^0.292 (Extended Abstract)
No full text) Dan Boneh Glenn Durfee y [email protected] [email protected] Abstract We show that if the private exponent d used in the RSA public-key cryptosystem is less than N 0:292 then the system is insecure. This is the rst improvement over an old result of Wiener showing that when d < N 0:25 the RSA system is insecure. We hope our approach can be used to eventually improve the bound to d < N 0:5 . 1 Introduction To provide fast RSA signature generation one is tempted to use a small private exponent d. Unfortunately, Wiener [10] showed over ten years ago that if one uses d < N 0:25 then the RSA system can be broken. Since then there have been no improvements to this bound. Verheul and Tilborg [9] showed that as long as d < N 0:5 it is possible to expose d in less time than an exhaustive search; however, their algorithm requires exponential time as soon as d > N 0:25 . In this paper we give the rst substantial improvement to Wiener's result. We show that as long as..
Partial Key Exposure Attacks on RSA: Achieving the Boneh-Durfee Bound
No full textThus far, several lattice-based algorithms for partial key exposure attacks on RSA, i.e., given the most/least significant bits (MSBs/LSBs) of a secret exponent and factoring an RSA modulus , have been proposed such as Blömer and May (Crypto\u2703), Ernst et al. (Eurocrypt\u2705), and Aono (PKC\u2709). Due to Boneh and Durfee\u27s small secret exponent attack, partial key exposure attacks should always work for even without any partial information. However, it was difficult task to make use of the given partial information without losing the quality of Boneh-Durfee\u27s attack. In particular, known partial key exposure attacks fail to work for with only few partial information. Such unnatural situation stems from the fact that the additional information makes underlying modular equations involved. In this paper, we propose improved attacks when a secret exponents is small. Our attacks are better than all known previous attacks in the sense that our attacks require less partial information. Specifically, our attack is better than all known ones for and with the MSBs and the LSBs, respectively. Furthermore, our attacks fully cover the Boneh-Durfee bound, i.e., they always work for . At a high level, we obtain the improved attacks by fully utilizing unravelled linearization technique proposed by Herrmann and May (Asiacrypt\u2709). Although Herrmann and May (PKC\u2710) already applied the technique to Boneh-Durfee\u27s attack, we show elegant and impressive extensions to capture partial key exposure attacks. More concretely, we construct structured triangular matrices that enable us to recover more useful algebraic structures of underlying modular polynomials. We embed the given MSBs/LSBs to the recovered algebraic structures and construct our partial key exposure attacks. In this full version, we provide overviews and explicit proofs of the triangular matrix constructions. We believe that the additional explanations help readers to understand our techniques
Cryptanalysis of RSA: A Special Case of Boneh-Durfee’s Attack
No full textBoneh-Durfee proposed (at Eurocrypt 1999) a polynomial time attacks on RSA small decryption exponent which exploits lattices
and sub-lattice structure to obtain an optimized bounds d e = N^α where ε and α are the private and public key exponents respectively) for some α ≤ ε, which satisfy the condition d > φ(N) − N^ε. We analyzed lattices whose basis matrices are triangular and non-triangular using large decryption
exponent and focus group attacks respectively. The core objective is to explore RSA polynomials underlying algebraic structure so that we can improve the performance of weak key attacks. In our solution, we implemented the attack and perform several experiments to show that an RSA cryptosystem successfully attacked and revealed possible weak keys which can ultimately enables an adversary to factorize the RSA modulus
07381 Abstracts Collection – Cryptography
No full textFrom 16.09.2007 to 21.09.2007 the Dagstuhl Seminar 07381 ``Cryptography'' was held
in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available
Modeling olivine CPO evolution with complex deformation histories: Implications for the interpretation of seismic anisotropy in the mantle
No full textInternational audienceRelating seismic anisotropy to mantle flow requires detailed understanding of the development and evolution of olivine crystallographic preferred orientation (CPO). Recent experimental and field studies have shown that olivine CPO evolution depends strongly on the integrated deformation history, which may lead to differences in how the corresponding seismic anisotropy should be interpreted. In this study, two widely used numerical models for CPO evolutionD-Rex and VPSCare evaluated to further examine the effect of deformation history on olivine texture and seismic anisotropy. Building on previous experimental work, models are initiated with several different CPOs to simulate unique deformation histories. Significantly, models initiated with a preexisting CPO evolve differently than the CPOs generated without preexisting texture. Moreover, the CPO in each model evolves differently as a function of strain. Numerical simulations are compared to laboratory experiments by Boneh and Skemer (2014). In general, the D-Rex and VPSC models are able to reproduce the experimentally observed CPOs, although the models significantly over-estimate the strength of the CPO and in some instances produce different CPO from what is observed experimentally. Based on comparison with experiments, recommended parameters for D-Rex are: M*=10, *=5, and =0.3, and for VPSC: =10-100. Numerical modeling confirms that CPO evolution in olivine is highly sensitive to the details of the initial CPO, even at strains greater than 2. These observations imply that there is a long transient interval of CPO realignment which must be considered carefully in the modeling or interpretation of seismic anisotropy in complex tectonic settings
A Unified Framework for Small Secret Exponent Attack on RSA
No full textWe address a lattice based method on small secret exponent
attack on RSA scheme. Boneh and Durfee reduced the attack into
finding small roots of a bivariate modular equation: , where is an RSA moduli and is the RSA
public key. Boneh and Durfee proposed a lattice based algorithm
for solving the problem. When the secret exponent is less than
, their method breaks RSA scheme. Since the lattice used
in the analysis is not full-rank, the analysis is not easy.
Bl¥ omer and May gave an alternative algorithm. Although their
bound is worse than Boneh--Durfee result,
their method used a full rank lattice. However, the proof for
their bound is still complicated. Herrmann and May gave an
elementary proof for the Boneh--Durfee\u27s bound: .
In this paper, we first give an elementary proof for achieving the
bound of Bl¥ omer--May: . Our proof employs
unravelled linearization technique introduced by Herrmann and May
and is rather simpler than Bl¥ omer--May\u27s proof. Then, we
provide a unified framework to construct a lattice that are used
for solving the problem, which includes two previous method:
Herrmann--May and Bl¥ omer--May methods as a special case. Furthermore, we prove that the bound of Boneh--Durfee: is still optimal in our unified framework
Role of beta-galactosidase and elastin binding protein in lysosomal and nonlysosomal complexes of patients with GM1-gangliosidosis
No full textG(M1)-gangliosidosis is a lysosomal storage disorder caused by a deficiency of beta-galactosidase (GLB1). The GLB1 gene gives rise to the GLB1 lysosomal enzyme and to the elastin binding protein (EBP), involved in elastic fiber deposition. GLB1 forms a complex with protective protein cathepsin A (PPCA), alpha neuraminidase (NEU1), and galactosamine 6-sulphate sulfatase (GALNS) inside lysosomes, while EBP binds to PPCA and NEU1 on the cell surface. We investigated the function of the GLB1 and EBP mutated proteins by analyzing the clinical, genetic, and cellular data of 11 G(M1)-gangliosidosis patients. Their molecular analysis, followed by expression studies, lead to the identification of four new and 10 known GLB1 mutations. Some common amino acid substitutions [c.1445G>A (p.Arg482H), c.622C>T (p.Arg208His), c.175C>T (p.Arg59Cys) and c.176G>A (p.Arg59His)] were present in the GLB1 enzyme of several patients, all of Mediterranean origin, suggesting a common origin. Western blotting analyses against GLB1, EBP, and PPCA proteins showed that the identified mutations affect GLB1 enzyme activity and/or stability. The c.1445G>A (p.Arg482His), c.175C>T (p.Arg59Cys), c.733+2T>C, c.1736G>A (p.Gly579Asp), and c.1051C>T (p.Arg351X) GLB1 mutations, affect the stabilization of PPCA probably because they hamper the interaction between GLB1/EBP and PPCA within the multiprotein complex. The amount of EBP was normal, but the detection of impaired elastogenesis in such patients suggests an alteration in its function. We conclude that the presence of genetic lesions in both GLB1 and EBP coding region does not directly predict impaired elastogenesis and that elastic fiber assembly has to be evaluated specifically in each case. Nevertheless, the degree of EBP involvement may be linked to specific clinical findings
Research gaps in diet and nutrition in inflammatory bowel disease. A topical review by D-ECCO working group [Dietitians of ECCO]
No full textAlthough the current doctrine of IBD pathogenesis proposes an interaction between environmental factors and gut microbiota in genetically susceptible individuals, dietary exposures have attracted recent interest and are, at least in part, likely to explain the rapid rise in disease incidence and prevalence. The D-ECCO working group along with other ECCO experts with expertise in nutrition, microbiology, physiology, and medicine reviewed the evidence investigating the role of diet and nutritional therapy in the onset, perpetuation, and management of IBD. A narrative topical review is presented where evidence pertinent to the topic is summarised collectively under three main thematic domains: i] the role of diet as an environmental factor in IBD aetiology; ii] the role of diet as induction and maintenance therapy in IBD; and iii] assessment of nutritional status and supportive nutritional therapy in IBD. A summary of research gaps for each of these thematic domains is proposed, which is anticipated to be agenda-setting for future research in the area of diet and nutrition in IBD
- …
