Quad Chart

Principal Investigator:

Co-Principal Investigator:

Project URL:

Objective

Approach:

Recent Accomplishments:

Voting. We have refined and improved our electronic voting implementation, prepatory to making a larger-scale test. This Web-based voting scheme should prove very usable and versatile.

Group Blind Signatures. We have developed an efficient scheme for group blind digital signatures. In such a scheme, each member of the group can sign for the group---only the group administrator can determine who actually signed. Moreover, the signatures are ``blind'' in that the signer doesn't get to see what he is signing. This has applications in electronic commerce and elsewhere.

Integer Lattice Based Cryptography. There were several exciting developments in our ``alternative foundations for cryptographic primitives'' project which aims to construct cryptographic primitives based on hard computational geometric problems, rather than number theoretic problems:

• We completed the implementation of the Public-Key Cryptosystem (PKC) based on the hardness of the problem of finding the closest vector in an integer lattice, which we proposed last year. The code for the PKC (including key generation, encryption, decryption routines) as well as a list of challenges for breaking this PKC in dimension 200-400, are available at our web site.
• Last year it had been proven (after being open for a decade) that the exact version of the ``shortest vector problem in an integer lattice'' (SVP) is NP-hard. A new result obtained in our group, strengthens that significantly, showing that it is NP-hard to even approximate the SVP problem to within some constant. This means that unless P=NP, it is not feasible to find approximate solutions to that problem. This provides hope that we might be able to design a PKC whose average case hardness is provably as hard as the worst case instance of an NP-hard problem.
• We found simple constant-round zero-knowledge interactive proof systems for problems capturing the approximability, to within a factor of sqrt(n), of optimization problems in integer lattices; specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the ``coNP direction.'' That is, we give an interactive protocol showing that a vector is ``far'' from the lattice (for CVP), and an interactive protocol showing that the shortest-lattice-vector is ``long'' (for SVP). We draw two conclusion: (1) It is thus unlikely that approximating these problems to within a sqrt(n) factor is NP-hard, which puts a bound on the security of a newly proposed PKC by Ajtai-Dwork, and (2) Zero-Knowledge identity protocols can be designed based on the CVP problem.

• Members of our group showed how to transform any interactive proof system which is statistical zero-knowledge (a special kind of interactive proof systems which is useful for identification protocols) with respect to the honest-verifier, into a proof system which is statistical zero-knowledge with respect to any verifier. This is done by limiting the behavior of potentially cheating verifiers, without using computational assumptions or even referring to the complexity of such verifier strategies.
• We considered the problem of proving that your public key is "properly constructed" in zero-knowledge, i.e without revealing the secret key. This comes up, for example, when registering your RSA key N = PQ with a certification authority one might be required for security purposes to prove that N is indeed the product of exactly two primes. Members of our group showed an efficient statistical zero-knowledge proof system to prove that an RSA modulus N=PQ is the product of two "quasi-safe" primes, i.e., primes such that (P-1)/2 and (Q-1)/2 are prime powers, a property useful in practical scenarios where safe-prime products are assumed such as RSA-based undeniable signatures.

• The timing model assumes that all parties have clocks and the adversary is constrained in its control over parties' clocks. The clocks are used by users to decide which messages in a protocol have arrived within the alloted time slot and are permissable. Using timing model we designed a preprocessing protocol, making use of timing, which enables subsequent concurrent execution of a polynomial number of concurrent perfect zero-knowledge arguments for every language in NP without any recourse to timing.
• Another approach we consider is to use the existence of a trusted center who will engage in a preprocessing step with future zero-knowledge protocols participants before concurrent executions. Once a particular prover and verifier have executed the preprocessing protocol, any polynomial number of subsequent executions of a rich class of protocols will be concurrent zero-knowledge.

• We introduced a new paradigm for efficient incremental hashing, and derived from the paradigm various fast collision-free hash functions.
• We have underway an implementation of an incremental signature editor (which generates valid signatures for documents while they are editted). in Emacs (a popular text editor in the UNIX world). This builds on an implementation already completed in the previous year, of an editor that generates Message Authentication Codes (MAC) for documents in an incremental fashion.

Current Plan:

We plan to continue our exploration of encrypted computation---where a server can compute on encrypted data without having to decrypt the data first (the results of the computation are also encrypted). This difficult problem has only been partially addressed in the existing literature; we hope for a general solution.

We plan to expand our study to electronic voting to include very large (state-wide?) elections. The interaction of scalability and security is the planned focus of attention.

We remark that there is still a big gap between the factors for which we can prove the NP-hardness of lattice problems and those required by current lattice-based cryptosystems. Bridging this gap is certainly an extremely challanging but attractive goal, as it would result in a cryptosystem based on the P=/=NP assumption. We are currently working to improve the inapproximability result for CVP and SVP to larger approximation factors.

We plan to finish the implementation (which is underway) of the incremental signature editor (which generates valid signatures for documents while they are editted) and make it accessible via the web.

Given the failure we have found of the so-called ``random oracle methodology'' (see above), it is adequate to proceed by identifying useful (special-purpose) properties of a random oracle, which can be provided by a fully specified function and so yield implementations of certain useful ideal systems. We plan to identify such properties and provide constructions of functions possesing these properties.

Technology Transition:

As noted above, we have implemented an editor which supports an automatic (being computed as the file is being edited) incremental MAC. The code has been posted on our Web site.

As noted above, we have implemented a public-key cryptosystem implementation based on the hardness of the CVP lattice problem. The code has been posted on our web site.

We are currently participating as advisors to a DoD JASON summer study on information protection involving Faculty from Berkeley and USC on how our work on incremental cryptography may be relevant to the problem of dealing with the large-scale key distribution problem in a scalable, incrementable way. The study is being funded by the new CIO of the Department of Defense, charged with the mission of protecting our command and control communications system, and has potential for a big impact.