Expand-and-Randomize: An Algebraic Approach to Secure Computation.

Area of Science:

• Cryptography and Secure Computation
• Information Theory
• Algebraic Structures in Computer Science

Background:

• Secure computation enables multiple parties to jointly compute a function over their private inputs without revealing the inputs themselves.
• Existing protocols often require complex constructions or significant communication overhead.
• A minimal model is considered, focusing on the core problem of secure function evaluation between two parties.

Purpose of the Study:

• To propose a novel and efficient coding scheme for the minimal secure computation problem.
• To ensure that no additional information beyond the function's output is leaked to the computing party.
• To implement the scheme using practical algebraic structures.

Main Methods:

• A two-step 'expand-and-randomize' coding scheme is introduced.
• The 'expansion' step prepares the function for recovery, potentially allowing information leakage.
• The 'randomization' step obfuscates the expanded function to protect sensitive information.
• Implementation utilizes finite fields and modulo rings of integers.
• Addition is used for the expansion step, and multiplication for the randomization step.

Main Results:

• The proposed expand-and-randomize scheme effectively computes the desired function securely.
• The randomization step successfully protects against the leakage of additional information.
• Demonstrated feasibility using addition for expansion and multiplication for randomization in finite fields and modulo rings.

Conclusions:

• The novel expand-and-randomize coding scheme offers a viable solution for minimal secure computation.
• The use of fundamental algebraic operations provides an efficient and practical approach.
• This method enhances data privacy in distributed computing scenarios.