| Detecting compromised ballots -> Monitor Keywords |
|
|
  Detecting compromised ballotsUSPTO Application #: 20070189519Title: Detecting compromised ballots Abstract: A facility for discerning corruption of an electronic ballot is described. The facility sends from a first computer system to a second computer system an encrypted ballot that reflects a ballot choice selected by a voter. The facility then sends a confirmation from the second computer system to the first computer system, which serves to convey the decrypted contents of the encrypted ballot as received at the second computer system, and which is generated without decrypting the encrypted ballot. In the first computer system, the facility uses the confirmation to determine whether the decrypted contents of the encrypted ballot as received at the second computer system match the ballot choice selected by the voter. (end of abstract)
Agent: Perkins Coie LLP Patent-sea - Seattle, WA, US Inventor: C. Andrew Neff USPTO Applicaton #: 20070189519 - Class: 380030000 (USPTO) Related Patent Categories: Cryptography, Particular Algorithmic Function Encoding, Public Key The Patent Description & Claims data below is from USPTO Patent Application 20070189519. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS REFERENCE TO RELATED APPLICATIONS [0001] This application is a continuation of U.S. patent application Ser. No. 10/038,752, filed Dec. 31, 2001, now U.S. Pat. No. 7,099,471 issued Aug. 29, 2006, which claims the benefit of U.S. Provisional Application No. 60/270,182 filed Feb. 20, 2001, and U.S. patent application Ser. No. 10/038,752 is a continuation-in-part of each of U.S. patent application Ser. No. 09/534,836, filed Mar. 24, 2000; U.S. patent application Ser. No. 09/535,927, filed Mar. 24, 2000; and U.S. patent application Ser. No. 09/816,869 filed Mar. 24, 2001. Each of these applications is incorporated by reference in its entirety. TECHNICAL FIELD [0002] The present invention is directed to the fields of election automation and cryptographic techniques therefor. BACKGROUND [0003] The problems of inaccuracy and inefficiency have long attended conventional, manually-conducted elections. While it has been widely suggested that computers could be used to make elections more accurate and efficient, computers bring with them their own pitfalls. Since electronic data is so easily altered, many electronic voting systems are prone to several types of failures that are far less likely to occur with conventional voting systems. [0004] One class of such failures relates to the uncertain integrity of the voter's computer, or other computing device. In today's networked computing environment, it is extremely difficult to keep any machine safe from malicious software. Such software is often able to remain hidden on a computer for long periods of time before actually performing a malicious action. In the meantime, it may replicate itself to other computers on the network, or computers that have some minimal interaction with the network. It may even be transferred to computers that are not networked by way of permanent media carried by users. [0005] In the context of electronic secret ballot elections, this kind of malicious software is especially dangerous, since even when its malicious action is triggered, it may go undetected, and hence left to disrupt more elections in the future. Controlled logic and accuracy tests ("L&A tests") monitor the processing of test ballots to determine whether a voting system is operating properly, and may be used in an attempt to detect malicious software present in a voter's computer. L&A tests are extremely difficult to conduct effectively, however, since it is possible that the malicious software may be able to differentiate between "real" and "test" ballots, and leave all "test" ballots unaffected. Since the requirement for ballot secrecy makes it impossible to inspect "real" ballots for compromise, even exhaustive L&A testing may prove futile. The problem of combating this threat is known as the "Client Trust Problem." [0006] Most existing methods for solving the Client Trust Problem have focused on methods to secure the voting platform, and thus provide certainty that the voter's computer is "clean," or "uninfected." Unfortunately, the expertise and ongoing diligent labor that is required to achieve an acceptable level of such certainty typically forces electronic voting systems into the controlled environment of the poll site, where the client computer systems can be maintained and monitored by computer and network experts. These poll site systems can still offer some advantages by way of ease of configuration, ease of use, efficiency of tabulation, and cost. However, this approach fails to deliver on the great potential for distributed communication that has been exploited in the world of e-commerce. [0007] Accordingly, a solution to the Client Trust Problem that does not require the voting platform to be secured against malicious software, which enables practically any computer system anywhere to be used as the voting platform, would have significant utility. BRIEF DESCRIPTION OF DRAWINGS [0008] FIG. 1 is a high-level block diagram showing a typical environment in which the facility operates. [0009] FIG. 2 is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility executes. [0010] FIG. 3 is a flow diagram showing steps typically performed by the facility in order to detect a compromised ballot. DETAILED DESCRIPTION [0011] A software facility for detecting ballots compromised by malicious programs ("the facility") is provided. The approach employed by the facility is unique in that it does not make any attempt to eliminate, or prevent the existence of malicious software on the voting computer. Instead, it offers a cryptographically secure method for the voter to verify the contents of the voter's ballot as it is received at the vote collection center, without revealing information about the contents (ballot choices) to the collection center itself. That is, the vote collection center can confirm to the voter exactly what choices were received, without knowing what those choices are. Thus, the voter can detect any differences between the voter's intended choices, and the actual choices received at the vote collection center (as represented in the transmitted voted ballot digital data). Further, each election can choose from a flexible set of policy decisions allowing a voter to re-cast the voter's ballot in the case that the received choices differ from the intended choices. A. The Simplest Secret Value Confirmation Setting [0012] In order to understand the key cryptographic protocol that makes secret value confirmation possible, we first describe a simplified embodiment of the facility. In accordance with this embodiment, the ballot consists of a single yes or no question. The challenge then is to have the voter secretly communicate the voter's choice--yes or no--to the vote collection center, and then further confirm that what was actually received at the vote collection center was exactly what the voter intended. In other words, if a "yes" vote was somehow changed to a "no" vote, or a "no" vote was somehow changed to a "yes" vote, the facility informs the voter of this fact. [0013] An electronic vote representation is used to represent the contents of the voter's ballot. Suitable electronic vote representations include those described in the patent applications identified in the related application section. [0014] 1. Ballot Construction: A set of cryptographic "election parameters" are agreed upon by election officials in advance of the election start, and made publicly known by wide publication or other such means. These parameters include encryption group, generator, ElGamal public key, and decision encoding scheme. Most commonly these consist of: [0015] (a) The encryption group: A large prime, p. [0016] (b) The generator: An integer (or, technically, an integer residue class) g.di-elect cons.Z.sub.p, which has prime multiplicative order q, with the property that q is a multiplicity 1 divisor of p-1. [0017] (c) The ElGamal public key: Another integer residue class, h.di-elect cons.<g>. That is, h=g.sup.s for some integer value of s. [0018] (d) The decision encoding scheme: A partition of <g> into "yes", "no" and "invalid" group elements. That is, <g>=S.sub.y.orgate.S.sub.n.orgate.S.sub.i, where the S.sub.y,S.sub.n,S.sub.i are pairwise disjoint subsets of <g>--the "yes" messages, "no" messages, and "invalid" messages respectively. However, other groups and elements can be used. In particular, the facility may be implemented using Elliptic Curves rather than Z.sub.p groups. [0019] 2. Vote Submission: Each voter encrypts the voter's decision, "yes" or "no", as an ElGamal pair, (X.sub.i,Y.sub.i)=(g.sup..alpha.,h.sup..alpha.m), where .alpha..di-elect cons.Z.sub.q is chosen randomly by the voter, m.di-elect cons.S.sub.y if the voter wishes to choose "yes" and m.di-elect cons.S.sub.n if the voter wishes to choose "no". Any other message (i.e., m .di-elect cons.S.sub.i) is considered invalid. This encrypted value is what is digitally signed by the voter, and then transmitted to the vote collection center. For now, we will consider a simple decision encoding scheme in which S.sub.y={G.sub.y}, S.sub.n={G.sub.n}, and S.sub.i=<g>-{G.sub.y,G.sub.n}. However, with obvious small modifications, the discussion that follows applies equally well to more general settings. [0020] If the voter was computing these values himself--say with pencil and paper--this protocol would essentially suffice to implement a secret-ballot, universally verifiable election system. (Depending on the tabulation method to be used, some additional information, such as a voter proof of validity may be necessary.) However, since the voter only makes choices through a user interface, it is in many cases unrealistic to expect him/her to check the actual value of the bits sent and compare them to the voter's intent. In short, malicious software can ignore voter intent and submit a "no" vote when the voter specified "yes", or submit a "yes" vote when the voter specified "no". B. Creating a Secret Value Confirmation [0021] We differentiate two types of vote corruption, directed and undirected. Continue reading... Full patent description for Detecting compromised ballots Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Detecting compromised ballots patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Detecting compromised ballots or other areas of interest. ### Previous Patent Application: Data transmission apparatus, data receiving apparatus and data communication method Next Patent Application: Diffused asymmetric encryption/decryption method Industry Class: Cryptography ### FreshPatents.com Support Thank you for viewing the Detecting compromised ballots patent info. IP-related news and info Results in 0.67885 seconds Other interesting Feshpatents.com categories: Medical: Surgery , Surgery(2) , Surgery(3) , Drug , Drug(2) , Prosthesis , Dentistry |
||
