## CryptoDB

### Helger Lipmaa

#### Publications

Year
Venue
Title
2017
PKC
2017
ASIACRYPT
2017
ASIACRYPT
2016
ASIACRYPT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2013
ASIACRYPT
2012
TCC
2010
PKC
2010
PKC
2010
EPRINT
Norway has started to implement e-voting (over the Internet, and by using voters' own computers) within the next few years. The vulnerability of voter's computers was identified as a serious threat to e-voting. Therefore, in this paper, we study the vote integrity of e-voting when the voter computers cannot be trusted. For this, we first make a number of assumptions---that arose from the discussion with the representatives of Norwegian government, and have been approved by them---about the available infrastructure. In particular, we assume the existence of two out-of-band channels that do not depend on the voter computers. The first channel is used to transmit integrity check codes to the voters prior the election, and the second channel is used to transmit a check code, that corresponds to her vote, back to a voter just after his or her e-vote vast cast. For this we also introduce a new cryptographic protocol. We present the new protocol with enough details to facilitate an implementation, and also present the timings of an actual implementation.
2008
EPRINT
We polish a recent cryptocomputing method that makes it possible to cryptocompute every language in $\mathbf{L/poly}$. We give several nontrivial applications, including: (a) A CPIR protocol with log-squared communication and sublinear server-computation by giving a secure function evaluation protocol for Boolean functions with similar performance, (b) A protocol that makes it possible to compute (say) how similar is client's input to an element in server's database, without revealing any information to the server, (c) A protocol for private database updating with low amortized complexity.
2008
EPRINT
Denote by $X^{Y[i]}$ the assumption that the adversary, given a non-adaptive oracle access to the $Y$ oracle with $i$ free variables cannot break the assumption $X$. We show that Elgamal is CCA1-secure under the $DDH^{CCH[1]}$ assumption. We then give a simple proof that the Damg{\aa}rd cryptosystem is CCA1-secure under the $DDH^{DDH[2]}$ assumption, where the proof uses a recent trapdoor test trick by Cash, Kiltz and Shoup.
2008
EPRINT
We establish the complete complexity landscape surrounding CCA1-security of Elgamal and Damg{\aa}rd's Elgamal (DEG). Denote by $X^{Y[i]}$ the assumption that the adversary, given a non-adaptive oracle access to the $Y$ oracle with $i$ free variables cannot break the assumption $X$. We show that the CCA1-security of Elgamal is equivalent to the $DDH^{CDH[1]}$ assumption. We then give a simple alternative to Gj{\o}steen's proof that DEG cryptosystem is CCA1-secure under the $DDH^{DDH[2]}$ assumption. We also provide several separations. We show that $DDH$ cannot be reduced to $DDH^{CDH[1]}$ in the generic group model. We give an irreduction showing that $DDH$ cannot be reduced to $DDEG^{CDEG[2]}$ (unless $\DDH$ is easy), $DDEG^{CDEG[2]}$ cannot be reduced to $DDH^{DDH[2]}$ (unless $DDEG^{CDEG[2]}$ is easy) and $DDH^{DDH[2]}$ cannot be reduced to the $DDH^{CDH[1]}$(unless $DDH^{DDH[2]}$ is easy). All those irreductions are optimal in the sense that they show that if assumption $X$ can be reduced to $Y$ in polynomial time then $X$ has to be solvable in polynomial time itself and thus \emph{both} assumptions are broken.
2007
EPRINT
We construct two simple families of two-message $(n,1)$-oblivious transfer protocols based on degree-$t$ homomorphic cryptosystems with the communication of respectively $1+\lceil n/t\rceil$ and $3+\lceil n/(t+1)\rceil$ ciphertexts. The construction of both families relies on efficient cryptocomputable conditional disclosure of secret protocols; the way this is done may be of independent interest. The currently most interesting case $t=2$ can be based on the Boneh-Goh-Nissim cryptosystem. We show how to reduce the communication of virtually any existing oblivious transfer protocols by proposing a new related communication-efficient generic transformation from computationally-private information retrieval protocols to oblivious transfer protocols.
2006
EPRINT
We study the problem of private classification using kernel methods. More specifically, 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 also 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.
2006
EPRINT
In many practical settings, participants are willing to deviate from the protocol only if they remain undetected. Aumann and Lindell introduced a concept of covert adversaries to formalize this type of corruption. In the current paper, we refine their model to get stronger security guarantees. Namely, we show how to construct protocols, where malicious participants cannot learn anything beyond their intended outputs and honest participants can detect malicious behavior that alters their outputs. As this construction does not protect honest parties from selective protocol failures, a valid corruption complaint can leak a single bit of information about the inputs of honest parties. Importantly, it is often up to the honest party to decide whether to complain or not. This potential leakage is often compensated by gains in efficiency---many standard zero-knowledge proof steps can be omitted. As a concrete practical contribution, we show how to implement consistent versions of several important cryptographic protocols such as oblivious transfer, conditional disclosure of secrets and private inference control.
2006
EPRINT
Rewinding techniques form the essence of many security reductions including proofs for identification and signature schemes. We propose a simple and modular approach for the construction of such proofs. Straightforward applications of our central result include, but are not limited to, the security of identification schemes, generic signatures and ring signatures. These results are well known, however, we generalise them in such a way that our technique can be used off-the-shelf for future applications. We note that less is more: as a side-effect of our less complex analysis, all our proofs are more precise; for example, we get a new proof of the forking lemma that is $2^{15}$ times more precise than the original result by Pointcheval and Stern. Finally, we give the first precise security analysis of Blum's coin flipping protocol with $k$-bit strings, as yet another example of the strength of our results.
2005
EPRINT
Many protocols that are based on homomorphic encryption are private only if a client submits inputs from a limited range $S$. Conditional disclosure of secrets (CDS) helps to overcome this restriction. In a CDS protocol for a set $S$, the client obtains server's secret if and only if the client's inputs belong to $S$ and thus the server can guard itself against malformed queries. We extend the existing CDS protocols to work over additively homomorphic cryptosystems for every set from $NP/poly$. The new construction is modular and easy to apply. As an example, we derive a new oblivious transfer protocol with log-squared communication and a millionaire's protocol with logarithmic communication. We also implement private, universally verifiable and robust multi-candidate electronic voting so that all voters only transmit an encryption of their vote. The only hardness assumption in all these protocols is that the underlying public-key cryptosystem is IND-CPA secure and the plaintext order does not have small factors.
2004
FSE
2004
PKC
2004
EPRINT
We propose a one-round $1$-out-of-$n$ computationally-private information retrieval protocol for $\ell$-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication $\Theta(k\cdot\log^2{n}+\ell\cdot\log{n})$, where $k$ is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private $1$-out-of-$n$ oblivious-transfer protocol for $\ell$-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.
2003
ASIACRYPT
2003
ASIACRYPT
2003
EPRINT
We propose a new cryptographically protected multi-round auction mechanism for online auctions. This auction mechanism is designed to provide (in this order) security, cognitive convenience, and round-effectiveness. One can vary internal parameters of the mechanism to trade off bid privacy and cognitive costs, or cognitive costs and the number of rounds. We are aware of no previous work that interleaves cryptography explicitly with the mechanism design.
2003
EPRINT
We develop cryptographically secure techniques to guarantee unconditional privacy for respondents to polls. Our constructions are efficient and practical, and are shown not to allow cheating respondents to affect the tally'' by more than their own vote --- which will be given the exact same weight as that of other respondents. We demonstrate solutions to this problem based on both traditional cryptographic techniques and quantum cryptography.
2003
EPRINT
We show how to construct practical honest-verifier statistical zero-knowledge \emph{Diophantine} arguments of knowledge (HVSZK AoK) that a committed tuple of integers belongs to an arbitrary language in bounded arithmetic. While doing this, we propose a new algorithm for computing the Lagrange representation of nonnegative integers and a new efficient representing polynomial for the exponential relation. We apply our results by constructing the most efficient known HVSZK AoK for non-negativity and the first constant-round practical HVSZK AoK for exponential relation. Finally, we propose the outsourcing model for cryptographic protocols and design communication-efficient versions of the Damg{\aa}rd-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi $(b+1)$st-price auction scheme that work in this model.
2002
EPRINT
Skewed trees constitute a two-parameter family of recursively constructed trees. Recently, Willemson proved that suitably picked skewed trees are space-optimal for interval time-stamping. At the same time, Willemson proposed a practical but suboptimal algorithm for nonrecursive traversal of skewed trees. We describe an alternative, extremely efficient traversal algorithm for skewed trees. The new algorithm is surprisingly simple and arguably close to optimal in every imaginable sense. We provide a detailed analysis of the average-case storage (and communication) complexity of our algorithm, by using the Laplace's method for estimating the asymptotic behavior of integrals. Since the skewed trees can be seen as a natural generalization of Fibonacci trees, our results might also be interesting in other fields of computer science.
2001
FSE
2001
EPRINT
In this paper we systematically study the differential properties of addition modulo $2^n$. We derive $\Theta(\log n)$-time algorithms for most of the properties, including differential probability of addition. We also present log-time algorithms for finding good differentials. Despite the apparent simplicity of modular addition, the best known algorithms require naive exhaustive computation. Our results represent a significant improvement over them. In the most extreme case, we present a complexity reduction from $\Omega(2^{4n})$ to $\Theta(\log n)$.
2001
EPRINT
A family $(S_t)$ of sets is $p$-bounded Diophantine if $S_t$ has a representing $p$-bounded polynomial $R_{S,t}$, s.t. $x\in S_t \iff (\exists y)[R_{S}(x;y)=0]$. We say that $(S_t)$ is unbounded Diophantine if additionally, $R_{S,t}$ is a fixed $t$-independent polynomial. We show that $p$-bounded (resp., unbounded) Diophantine set has a polynomial-size (resp., constant-size) statistical zero-knowledge proof system that a committed tuple $x$ belongs to $S$. We describe efficient SZK proof systems for several cryptographically interesting sets. Finally, we show how to prove in SZK that an encrypted number belongs to $S$.
2001
EPRINT
We argue that threshold trust is not an option in most of the real-life electronic auctions. We then propose two new cryptographic Vickrey auction schemes that involve, apart from the bidders and the seller $S$, an auction authority $A$ so that unless $S$ and $A$ collude the outcome of auctions will be correct, and moreover, $S$ will not get any information about the bids, while $A$ will learn bid statistics. Further extensions make it possible to decrease damage that colluding $S$ and $A$ can do, and to construct $(m+1)$st price auction schemes. The communication complexity between the $S$ and $A$ in medium-size auctions is at least one order of magnitude less than in the Naor-Pinkas-Sumner scheme.
2000
PKC
2000
EPRINT
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.
1998
CRYPTO

PKC 2020
PKC 2019
Asiacrypt 2019
Asiacrypt 2018
Eurocrypt 2010
Eurocrypt 2006
FSE 2003