Abstract We consider the problem of minimizing the communication in single-database private information retrieval protocols in the case where the length of the data to be transmitted is large. We present first rate-optimal protocols for 1-out-of-n computationallyprivate information retrieval (CPIR), oblivious transfer (OT), and strong conditional oblivious transfer (SCOT). These protocols are based on a new optimalrate leveled homomorphic encryption scheme for large-output polynomial-size branching programs, that might be of independent interest. The analysis of the new scheme is intricate: the optimal rate is achieved if a certain parameter s is set equal to the only positive root of a degree-(m + 1) polynomial, where m is the length of the branching program. We show, by using Galois theory, that even when m = 4, this polynomial cannot be solved in radicals. We employ the Newton-Puiseux algorithm to find a Puiseux series for s, and based on this, propose a Θ (logm)-time algorithm to find an integer approximation to s.

We propose a new non-interactive perfect zero-knowledge (NIZK) shuffle argument that, when compared with the only previously known efficient NIZK shuffle argument by Groth and Lu, has a small constant factor times smaller computation and communication, and is based on more standard computational as sumptions. Differently from Groth and Lu who only prove the co-soundness of their argument under purely computational assumptions, we prove computational soundness under a necessary knowledge assumption. We also present a general transformation that results in a shuffle argument that has a quadratically smaller common reference string (CRS) and a small constant factor times longer argument than the original shuffle. This can be interpreted as a general technique of decreasing the offline cost of an arbitrary shuffle argument.

We propose private protocols implementing the Kernel Adatron and Kernel Perceptron learning algorithms, give private classification protocols and private polynomial kernel computation protocols. The new protocols return their outputs - either the kernel value, the classifier or the classifications - in encrypted form so that they can be decrypted only by a common agreement by the protocol participants. We show how to use the encrypted classifications to privately estimate many properties of the data and the classifier. The new SVM classifiers are the first to be proven private according to the standard cryptographic definitions.

This paper presents a method to increase the accountability of certificate management by making it intractable for the certification authority (CA) to create contradictory statements about the validity of a certificate. The core of the method is a new primitive, undeniable attester, that allows som eone to commit to some set S of bitstrings by publishing a short digest of S and to give attestations for any x that it is or is not a member of S. Such an attestation can be verified by obtaining in authenticated way the published digest and applying a verification algorithm to the triple of the bitstring, the attestation and the digest. The most important feature of this primitive is intractability of creating two contradictory proofs for the same candidate element x and digest. We give an efficient construction for undeniable attesters based on authenticated search trees. We show that the construction also applies to sets of more structured elements. We also show that undeniable attesters exist iff collision-resistant hash functions exist.

This paper initiates a study of accountable certificate management methods, necessary to support long-term authenticity of digital documents.Our main contribution is a model for accountable certificate management, where clients receive attestations confirming inclusion/removal of their certificates from the database of valid certificates.We explain why accountability depends on the inability of the third parties to create contradictory attestations.After that we define an undeniable attester as a primitive that provides efficient attestation creation, publishing and verification, so that it is intractable to create contradictory attestations.We introduce authenticated search trees and build an efficient undeniable attester upon them.The proposed system is the first accountable long-term certificate management system.Moreover, authenticated search trees can be used in many security-critical applications instead of the (sorted) hash trees to reduce trust in the authorities, without decrease in efficiency.Therefore, the undeniable attester promises looks like a very useful cryptographic primitive with a wide range of applications.