Generic lower bounds for root extraction and signature schemes in general groups

DOI10.1007/3-540-46035-7_17MaRDI QIDQ4737249zbMATH OpenFDO

Authors Maciej Koprowski, Ivan B. Damgård

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2332/23320256.htm

Mathematics Subject Classification ID

Finite abelian groups (20K01) Analysis of algorithms and problem complexity (68Q25) Authentication, digital signatures and secret sharing (94A62)

Recommendations

• A signature scheme based on the intractability of computing roots
• On the Equivalence of Generic Group Models
• Lower bounds on generic algorithms in groups
• On the cryptographic value of the \(q^{th}\) root problem
• A note on security proofs in the generic model

Cited in

(32)

• A signature scheme based on the intractability of computing roots
• Generic hardness of inversion on ring and its relation to self-bilinear map
• Transparent SNARKs from DARK compilers
• Compact zero-knowledge proofs for threshold ECDSA with trustless setup
• Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions
• Time- and space-efficient arguments from groups of unknown order
• On the analysis of cryptographic assumptions in the generic ring model
• Fine-grained forward-secure signature schemes without random oracles
• Incrementally aggregatable vector commitments and applications to verifiable decentralized storage
• Breaking RSA may be as difficult as factoring
• Efficiency limitations for -protocols for group homomorphisms
• Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems
• Parallel repetition of computationally sound protocols revisited
• Programmable hash functions and their applications
• On the cryptographic value of the \(q^{th}\) root problem
• On the Equivalence of Generic Group Models
• Breaking RSA Generically Is Equivalent to Factoring
• Zero-knowledge arguments for subverted RSA groups
• \textsf{Dew}: a transparent constant-sized polynomial commitment scheme
• Inner product functional commitments with constant-size public parameters and openings
• Computing primitive idempotents in finite commutative rings and applications
• On time-lock cryptographic assumptions in abelian hidden-order groups
• A Trustless GQ Multi-signature Scheme with Identifiable Abort
• Efficient transparent polynomial commitments for zk-SNARKs
• Zero-knowledge functional elementary databases
• Root extraction in finite abelian groups
• Breaking RSA generically is equivalent to factoring, with preprocessing
• DewTwo: a transparent PCS with quasi-linear prover, logarithmic verifier and 4.5KB proofs from falsifiable assumptions
• Behemoth: transparent polynomial commitment scheme with constant opening proof size and verifier time
• A new approach to generic lower bounds. Classical/quantum MDL, quantum factoring, and more
• The structured generic-group model
• Improved constant-sized polynomial commitment schemes without trusted setup

This page was built for publication: Generic lower bounds for root extraction and signature schemes in general groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4737249)