On the Untapped Potential of Encoding Predicates by Arithmetic Circuits and Their Applications

Explore the innovative research on encoding predicates using arithmetic circuits and their potential applications in this 22-minute conference talk presented at Asiacrypt 2017. Delve into Shuichi Katsumata's paper, which introduces two primitives and examines ways to improve upon existing methods. Learn about Boolean Representation Systems (BRS) and Vector eXtension Representation (VXR), their syntax, and pseudorandom properties. Discover the main observations, including the Online 17 Scheme and Boolean Circuit Representation, as well as the concept of high-degree polynomials. Gain insights into the Missile Hash Function and its good traits. Conclude with a recap of the key findings and their implications for the field of cryptography.

Introduction
Two Primitives
Can We Do Better
Summary
Overview
What are BRS VXR
Proof
Syntax
Pseudorandom
Preparation
Previous Works
Evaluation
Verify
Missile Hash Function
Good Traits
Our Work
Main Observation
Online 17 Scheme
Boolean Circuit Representation
High Degree Polynomial
Recap
Conclusion