Fully Homomorphic Encryption for Private and Fair Electoral Districting

Michael Pak, Nathaniel Rocks

August 14th, 2024

Data silos, driven largely by individual privacy concerns and regulatory measures, pose a major challenge to the advancement of AI. In an effort to address this, in April this year (2024), the US House passed the Privacy Enhancing Technology Research Act that requires NSF and NIST to support research and development of privacy enhancing technologies or PETs. In June this year, the National Science Foundation (NSF) announced the Privacy-Preserving Data Sharing in Practice (PDaSP) program to promote the development and adoption of PETs. In September, NIST is holding a first workshop on Privacy Enhancing Cryptography (PEC) for multidisciplinary participants to share insights about PEC capabilities, use-cases, real-world deployment, and related topics.

As the US government begins to ramp up development and adoption of PETs, this CryptoLab write-up introduces a PET technology named Fully Homomorphic Encryption (FHE), and explains how it can help mitigate a 200-year-old controversial political problem, gerrymandering, while preserving voter privacy. FHE is a recent form of cryptography that enables the processing and analysis of encrypted data.  Also, we introduce CryptoLab developed FHE-leveraging statistics toolkit, HEaaN.stat, which is already available for carrying out privacy-preserving statistical analysis, including analysis of private and fair electoral districting. Additionally, CryptoLab announces the availability of HEaaN.stat to non-profit organizations at free of charge.

Gerrymandering

Gerrymandering is the practice of setting boundaries of electoral districts to favor specific political interests within legislative bodies, often resulting in districts with convoluted, winding boundaries rather than compact areas. The term "gerrymandering" was coined after a review of Massachusetts's redistricting maps of 1812 set by Governor Elbridge Gerry noted that one of the districts looked like a mythical salamander. 

An electoral district, also known as an election district or precinct, is a geographic area represented by a specific number of elected officials in a legislative body. These districts are used to allocate seats in legislatures or other governing bodies during elections. The concept of electoral districts is not unique to the United States; many countries worldwide use them to organize elections and ensure representation in their legislative bodies.

For example, in Canada, electoral districts are called "ridings" or "constituencies." Canada uses a system similar to the U.S., with single-member districts electing representatives to the House of Commons. Similarly, in the United Kingdom, electoral districts are known as "constituencies," with each constituency electing one Member of Parliament (MP) to the House of Commons.

United States

In the United States, electoral district redistricting takes place in each state about every ten years, after the decennial census. It defines geographical boundaries, with each district within a state being geographically contiguous and having about the same number of state voters. The resulting map affects the elections of the state's members of the United States House of Representatives and the state legislative bodies. 

Redistricting has always been regarded as a political exercise and in most states, it is controlled by state legislators and sometimes the governor (in some states the governor has no veto power over redistricting legislation, while in some states, the veto override threshold is a simple majority). When one party controls the state's legislative bodies and governor's office, it is in a position of strength to  gerrymander district boundaries to advantage its side and to disadvantage its political opponents. Since 2010, detailed maps and high-speed computing have facilitated gerrymandering by political parties in the redistricting process, in order to gain control of state legislation and congressional representation and potentially to maintain that control over several decades, even against shifting political changes in a state's population.

There are mainly three types of  gerrymandering cases in the United States:

  1. Partisan gerrymandering is the practice of drawing electoral district boundaries to favor one political party unfairly. This is done by packing opposing party voters into a few districts or spreading them thinly across many, aiming to maximize the party in power's seats while minimizing those of the opposition, regardless of voter distribution.

  2. Bipartisan gerrymandering happens when both major political parties collaborate to draw electoral district boundaries that protect their incumbents and decrease electoral competition. Unlike partisan gerrymandering, this aims to ensure both parties' safe seats, reducing competitive districts. This can reduce accountability and voter choice since incumbents are less likely to face challenges for their seats.

  3. Racial gerrymandering refers to the deliberate manipulation of electoral district boundaries based on racial demographics to either dilute the voting power of racial minority groups or concentrate them into certain districts to affect electoral outcomes. This practice can undermine fair representation and is often scrutinized under civil rights laws and constitutional protections.

In the past, federal courts have deemed extreme cases of gerrymandering to be unconstitutional, but have struggled with how to define the types of gerrymandering and the standards that should be used to determine which redistricting maps are unconstitutional. In 1995 the Supreme Court came to a 5–4 decision during Miller v. Johnson that racial gerrymandering is a violation of constitutional rights and upheld decisions against redistricting that is purposely devised based on race.

Around the World

Gerrymandering is a global issue, but its prevalence and impact vary significantly across different countries. For example:

  • France: There have been occasional accusations of gerrymandering in France, particularly regarding the drawing of cantonal boundaries. The process is overseen by the Constitutional Council, which provides some checks against manipulation.

  • South Korea: Despite the presence of an independent commission, there have been reported instances of controversy and allegations of gerrymandering in South Korea.

  • United Kingdom: While reported gerrymandering is less common in the UK, there have been instances and allegations, particularly with the drawing of constituency boundaries in Northern Ireland during the mid-20th century.

  • Australia: Australia's use of independent electoral commissions at both the federal and state levels significantly reduces the risk of gerrymandering. These commissions draw boundaries based on criteria aimed at ensuring fair representation, such as population equality and community interests.

  • Mexico: Mexico has experienced gerrymandering issues, especially in the past. Reforms and the establishment of the National Electoral Institute (INE) have aimed to create fairer electoral processes, including the redistricting process.

In general, countries with independent or non-partisan redistricting bodies tend to have fewer issues with gerrymandering compared to those where politicians control the process.

Homomorphic Encryption

Before we discuss how Fully Homomorphic Encryption (FHE) can help mitigate gerrymandering, let's take a look at what homomorphic encryption is and why FHE is so special.

Homomorphic encryption is a cryptographic technique that allows computations to be performed on encrypted data without decrypting it first. This means that sensitive information can be processed or analyzed while remaining encrypted, preserving privacy and security. It enables secure data handling in various applications, such as cloud computing, healthcare, and financial services, where data needs to be protected but also manipulated. 

In 1978, Ron Rivest, Leonard Adleman, and Michael Dertouzos (Rivest and Adleman are two of the three inventors of RSA encryption that is credited for establishing trust, confidentiality, and integrity on the Internet) proposed the idea of performing computations on encrypted data without needing to decrypt it first in their paper "On Data Banks and Privacy Homomorphisms." For the following 30 years, cryptographers around the world have embarked on a quest to construct an encryption scheme that would enable arbitrary computation on encrypted data.

A survey on homomorphic encryption schemes

Homomorphic encryption schemes can be largely divided into three categories:

  • Partial homomorphic encryption (PHE) allows only one type of operation with no bound on the number of usages. RSA encryption is an example of PHE - the result of the multiplication of two RSA encrypted ciphertexts when decrypted is the same as the product of the plaintexts.

  • Somewhat Homomorphic Encryption (SWHE) is considered an improvement over PHE and allows multiple types of operations for a limited number of times.

  • Fully Homomorphic Encryption (FHE) is often called the “holy grail” of cryptography. It allows arbitrary operations for an unlimited number of times.

Fully Homomorphic Encryption (FHE)

For 30 years after Rivest, Adleman, and Dertouzos proposed the concept of “privacy homomorphism,” Fully Homomorphic Encryption remained elusive until Craig Gentry introduced the first construction of a FHE scheme in his doctoral thesis in 2009. Gentry’s achievement revolutionized the field of cryptography by demonstrating the theoretical possibility of performing arbitrary computations on encrypted data without decrypting it first. 

Since Gentry’s 2009 groundbreaking doctoral thesis, three generations of FHE schemes were developed, each with increased performance and usability.

Four generations of FHE with their applications

Fully Homomorphic Encryption transforms the way we approach data privacy and security, offering unprecedented capabilities to protect sensitive information and enable new types of secure interactions and applications. Here are several reasons why FHE is regarded as a paradigm shift in computing:

  • Computational Universality: FHE allows for arbitrary computations on encrypted data without needing to decrypt it first. This means any function computable on plaintext data can also be computed on encrypted data, making FHE extremely powerful and versatile.

  • Preserving Data Privacy: FHE enables computations to be performed on encrypted data while it stays encrypted. This ensures that sensitive information, such as personal health data can be processed without exposure to the entity performing the computation.

  • Secure Outsourcing: FHE allows secure outsourcing of computations to untrusted third parties. This is particularly valuable in cloud computing, as data owners can delegate computations on their encrypted data without compromising privacy.

  • Secure Data Sharing: FHE enables multiple parties to share and analyze encrypted data securely. For example, in collaborative research, participants can derive insights from shared datasets while keeping proprietary or sensitive information private to the data owner.

  • New Applications: FHE enables new applications and protocols not feasible with conventional cryptography and security controls. Examples include privacy-preserving AI/ML, and collaborative data analysis in healthcare and finance.

  • Regulatory Compliance: FHE helps organizations comply with privacy and data protection laws by ensuring sensitive data remains encrypted during processing. This reduces the risk of data breaches and supports compliance with regulations like HIPAA, GDPR, CCPA, and others.

FHE for Electoral Districting

So why does all of this matter? Well, Fully Homomorphic Encryption (FHE) can help mitigate gerrymandering in multiple ways by enabling secure and privacy-preserving analysis of redistricting data.

Privacy-Preserving Analysis

Voter demographic and geographic data are encrypted using FHE to protect individual privacy.

  • Encrypted Data Analysis: FHE enables computations on encrypted data, preserving the privacy of sensitive information like voter demographics and preferences.

  • Secure Statistical Analysis: Statistical metrics used to detect gerrymandering, such as population distribution, demographic characteristics, and partisan voting patterns, can be calculated on encrypted data without decrypting it.

Fairness Metrics Calculation

FHE allows calculating fairness metrics such as the efficiency gap and partisan symmetry directly on encrypted data. These metrics assess gerrymandering by analyzing the voter distribution of district boundaries.

Transparent and Auditable Redistricting

  • Independent Verification: FHE enables third parties like advocacy groups, researchers, and regulators to independently verify redistricting plans for legal compliance and fairness, all while preserving data privacy.

  • Public Accountability: The use of FHE in redistricting increases transparency and accountability by providing verifiable results of fairness assessments, thus enhancing public trust in the integrity of the electoral process.

Collaborative and Secure Multi-Party Computation (SMPC)

Stakeholders participate in collaborative redistricting discussions using encrypted data analysis to propose and refine district boundaries.

  • Collaborative Decision-Making: FHE enables Secure Multi-Party Computation (SMPC), allowing political parties, community organizations, and experts to work together on redistricting plans while keeping their data private.

  • Consensus Building: Through SMPC, stakeholders can collectively analyze FHE encrypted data, propose alternative district maps, and agree on fair boundaries that reflect community interests rather than partisan advantages.

Algorithmic Redistricting

  • Fair Algorithm Development: FHE enables the use of fair and transparent algorithms for automated redistricting, allowing algorithms to generate district boundaries from encrypted input data, ensuring unbiased and objective decisions.

  • Verification of Algorithm Outcomes: The use of FHE allows verification of algorithmic outcomes by computing fairness metrics on encrypted results, ensuring that redistricting plans adhere to legal and ethical standards.

Fully Homomorphic Encryption offers a promising approach to combating gerrymandering around the globe by enabling objective fairness assessments, promoting transparency, and fostering collaborative decision-making in the redistricting process. These capabilities can contribute to more equitable electoral outcomes and strengthen democratic principles.

HEaaN.stat

HEaaN.stat is a CryptoLab-developed privacy-preserving statistics analysis toolkit that leverages the 4th generation FHE scheme CKKS.  It provides a comprehensive set of statistics functions with performance that scales linearly with the dataset size - linear scalability allows systems to handle larger datasets predictably, making it easier to plan for and scale resources as needed.

Using HEaaN.stat, data analysts/scientists can carry out some of the aforementioned analysis and help mitigate gerrymandering without risking the privacy of the voters.

Statistics functions included in HEaaN.stat

FHE typically incurs significant computational overhead, especially when processing large amounts of data. However, the computational efficiency of the CKKS scheme combined with hardware acceleration makes it a viable tool for statistical and other data analytics (e.g., AI/ML). For example, computing the average of 10 million CKKS encrypted elements takes less than 0.2 second and 1 second for 10 million elements. Below HEaaN.stat latency measurements are obtained using a system utilizing a GPU.

CryptoLab plans to make HEaaN.stat available free of charge to select nonprofit non-governmental organizations. Please email info@cryptolab.co.kr to inquire about HEaaN.stat.