Authors:

Mukul Agarwal

Date Created:

Not specified

Course Title:

Professor:

Not specified

About Paper:

Embedding elementwise operations on vectors over small fields into arithmetic over large prime fields is a central problem in cryptographic protocol design. A key example is the Schur product, or componentwise multiplication. Efficient embeddings allow multiple such operations to be executed using a single field multiplication. This work focuses on the case where the Schur product is over bits, corresponding to elementwise logical AND, and asks: How densely can this function be embedded into a single prime-field multiplication? Prior approaches, such as those based on the Chinese Remainder Theorem, achieve a packing rate of only log(p)/log log(p) bits into a field of size p, far below the theoretical maximum. We introduce an embedding technique which takes the discrete logarithm in the multiplicative group of the prime field. This construction achieves an asymptotic improvement, packing up to log(p)/log(3) bits per field multiplication-about 63% of the optimal packing rate of log(p)/log(2). An exhaustive search shows no strictly better embedding exists for up to four input bits. While this method is inefficient in practice due to the computational hardness of discrete logarithms, these results demonstrate a significant improvement over existing embeddings. Future work will aim to develop embeddings which maintain computational efficiency by avoiding discrete-logarithm computations and embeddings which do not leak any information beyond the result of the Schur product itself. Keywords: Cryptography; Multi-Party Computation; Reverse Multiplication Embeddings

Source:

Purdue University / 2025

Topics:

No topics listed

Co-authors:

Mukul Agarwal