[go: up one dir, main page]

Ben-Sasson et al., 2018 - Google Patents

Worst-case to average case reductions for the distance to a code

Ben-Sasson et al., 2018

View PDF
Document ID
7716077729239944420
Author
Ben-Sasson E
Kopparty S
Saraf S
Publication year
Publication venue
33rd Computational Complexity Conference (CCC 2018)

External Links

Snippet

Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions vec {u}=(u_1,..., u_k), given as oracles, from a linear error correcting code V. The soundness of such systems relies on methods that act" locally" …
Continue reading at drops.dagstuhl.de (PDF) (other versions)

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3236—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using cryptographic hash functions
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/14—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic
    • H04L63/1408—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic by monitoring network traffic
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/80—Wireless

Similar Documents

Publication Publication Date Title
Ben-Sasson et al. Worst-case to average case reductions for the distance to a code
Pinkas et al. PSI from PaXoS: Fast, malicious private set intersection
Ben-Sasson et al. DEEP-FRI: sampling outside the box improves soundness
Fiore et al. Computing symbolic models for verifying cryptographic protocols
Yan General properties of quantum bit commitments
Cormode et al. Practical verified computation with streaming interactive proofs
Ben-Sasson et al. Linear-size constant-query IOPs for delegating computation
Mitzenmacher et al. Why simple hash functions work: exploiting the entropy in a data stream.
Naor et al. Bloom filters in adversarial environments
Grassi et al. Quantum Algorithms for the-xor Problem
Zhou et al. Optimal single-server private information retrieval
Baumeler et al. Quantum private information retrieval has linear communication complexity
Thaler Semi-streaming algorithms for annotated graph streams
Larsen et al. Lower bounds for multi-server oblivious RAMs
Bartusek et al. On the (in) security of Kilian-based SNARGs
Block et al. Fiat-Shamir security of FRI and related snarks
Ben-Sasson et al. Zero knowledge protocols from succinct constraint detection
Shi et al. A quantum hash function with grouped coarse-grained boson sampling
Chakrabarti et al. Annotations for sparse data streams
Ghoshal et al. On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
Song et al. Secret-shared shuffle with malicious security
Barooti et al. On active attack detection in messaging with immediate decryption
Blais et al. A characterization of constant‐sample testable properties
Ye et al. The MILP-aided conditional differential attack and its application to Trivium
Ghosh et al. Automatic search for bit-based division property