## CryptoDB

### Helger Lipmaa

#### Publications

**Year**

**Venue**

**Title**

2021

ASIACRYPT

Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge
Abstract

An extractable one-way function (EOWF), introduced by Canetti and Dakdouk (ICALP 2008) and generalized by Bitansky et al. (SIAM Journal on Computing vol. 45), is an OWF that allows for efficient extraction of a preimage for the function.
We study (generalized) EOWFs that have a public image verification algorithm.
We call such OWFs verifiably-extractable and show that several previously known constructions satisfy this notion.
We study how such OWFs relate to subversion zero-knowledge (Sub-ZK) NIZKs by using them to generically construct a Sub-ZK NIZK from a NIZK satisfying certain additional properties, and conversely show how to obtain them from any Sub-ZK NIZK.
Prior to our work, the Sub-ZK property of NIZKs was achieved using concrete knowledge assumptions.

2021

ASIACRYPT

Efficient NIZKs for Algebraic Sets
Abstract

Significantly extending the framework of (Couteau and Hartmann, Crypto 2020), we propose a general methodology to construct NIZKs for showing that an encrypted vector $\vec{\chi}$ belongs to an algebraic set, i.e., is in the zero locus of an ideal $\mathscr{I}$ of a polynomial ring. In the case where $\mathscr{I}$ is principal, i.e., generated by a single polynomial $F$, we first construct a matrix that is a ``quasideterminantal representation'' of $F$ and then a NIZK argument to show that $F (\vec{\chi}) = 0$. This leads to compact NIZKs for general computational structures, such as polynomial-size algebraic branching programs. We extend the framework to the case where $\IDEAL$ is non-principal, obtaining efficient NIZKs for R1CS, arithmetic constraint satisfaction systems, and thus for $\mathsf{NP}$. As an independent result, we explicitly describe the corresponding language of ciphertexts as an algebraic language, with smaller parameters than in previous constructions that were based on the disjunction of algebraic languages. This results in an efficient GL-SPHF for algebraic branching programs.

2021

ASIACRYPT

Gentry-Wichs Is Tight: A Falsifiable Non-Adaptively Sound SNARG
Abstract

By the impossibility result of Gentry and Wichs, non-falsifiable assumptions are needed to construct (even non-zero-knowledge) adaptively sound succinct non-interactive arguments (SNARGs) for hard languages. It is important to understand whether this impossibility result is tight. While it is known how to construct adaptively sound non-succinct non-interactive arguments for $\mathsf{NP}$ from falsifiable assumptions, adaptively sound SNARGs for $\mathsf{NP}$ from non-falsifiable assumptions, and adaptively sound SNARGs for $\mathsf{P}$ from falsifiable assumptions, there are no known non-adaptively sound SNARGs for $\mathsf{NP}$ from falsifiable assumptions. We show that Gentry-Wichs is tight by constructing the latter. In addition, we prove it is non-adaptively knowledge-sound in the algebraic group model and Sub-ZK (i.e., zero-knowledge even if the CRS is subverted) under a non-falsifiable assumption.

2020

PKC

On QA-NIZK in the BPK Model
📺
Abstract

Recently, Bellare et al. defined subversion-resistance (security in the case the CRS creator may be malicious) for NIZK. In particular, a Sub-ZK NIZK is zero-knowledge, even in the case of subverted CRS. We study Sub-ZK QA-NIZKs, where the CRS can depend on the language parameter. First, we observe that subversion zero-knowledge (Sub-ZK) in the CRS model corresponds to no-auxiliary-string non-black-box NIZK in the Bare Public Key model, and hence, the use of non-black-box techniques is needed to obtain Sub-ZK. Second, we give a precise definition of Sub-ZK QA-NIZKs that are (knowledge-)sound if the language parameter but not the CRS is subverted and zero-knowledge even if both are subverted. Third, we prove that the most efficient known QA-NIZK for linear subspaces by Kiltz and Wee is Sub-ZK under a new knowledge assumption that by itself is secure in (a weaker version of) the algebraic group model. Depending on the parameter setting, it is (knowledge-)sound under different non-falsifiable assumptions, some of which do not belong to the family of knowledge assumptions.

2020

ASIACRYPT

Succinct Functional Commitment for a Large Class of Arithmetic Circuits
📺
Abstract

A succinct functional commitment (SFC) scheme for a circuit class $\mathbf{CC}$ enables, for any circuit $\mathcal{C}\in \mathbf{CC}$, the committer to first succinctly commit to a vector $\vec{\alpha}$, and later succinctly open the commitment to $\mathcal{C} (\vec{\alpha}, \vec{\beta})$, where the verifier chooses $\vec{\beta}$ at the time of opening. Unfortunately, SFC commitment schemes are known only for severely limited function classes like the class of inner products. By making non-black-box use of SNARK-construction techniques, we propose a SFC scheme for the large class of semi-sparse polynomials. The new SFC scheme can be used to, say, efficiently (1) implement sparse polynomials, and (2) aggregate various interesting SFC (e.g., vector commitment and polynomial commitment) schemes. The new scheme is evaluation-binding under a new instantiation of the computational uber-assumption. We provide a thorough analysis of the new assumption.

2013

ASIACRYPT

2010

EPRINT

On E-Vote Integrity in the Case of Malicious Voter Computers
Abstract

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

Private Branching Programs: On Communication-Efficient Cryptocomputing
Abstract

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

On CCA1-Security of Elgamal And Damg{\aa}rd Cryptosystems
Abstract

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

On CCA1-Security of Elgamal And Damg{\aa}rd's Elgamal
Abstract

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

New Communication-Efficient Oblivious Transfer Protocols Based on Pairings
Abstract

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

Cryptographically Private Support Vector Machines
Abstract

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

On the Feasibility of Consistent Computations
Abstract

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

Black-Box Knowledge Extraction Revisited: Universal Approach with Precise Bounds
Abstract

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

A New Protocol for Conditional Disclosure of Secrets And Its Applications
Abstract

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

EPRINT

An Oblivious Transfer Protocol with Log-Squared Communication
Abstract

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

EPRINT

Interleaving Cryptography and Mechanism Design: The Case of Online Auctions
Abstract

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

Cryptographic Randomized Response Techniques
Abstract

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

On Diophantine Complexity and Statistical Zero-Knowledge Arguments
Abstract

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

On Optimal Hash Tree Traversal for Interval Time-Stamping
Abstract

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

EPRINT

Efficient Algorithms for Computing Differential Properties of Addition
Abstract

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

Statistical Zero-Knowledge Proofs from Diophantine Equations
Abstract

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

Secure Vickrey Auctions without Threshold Trust
Abstract

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

EPRINT

Accountable Certificate Management using Undeniable Attestations
Abstract

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.

#### Program Committees

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

#### Coauthors

- Behzad Abdolmaleki (2)
- Andris Ambainis (2)
- N. Asokan (1)
- Karim Baghery (1)
- Fabrice Benhamouda (1)
- Florian Bourse (1)
- Ahto Buldas (3)
- Geoffroy Couteau (1)
- Philippe Dumas (1)
- Edith Elkind (1)
- Prastudy Fauzi (4)
- Jens Groth (1)
- Sven Heiberg (1)
- Markus Jakobsson (2)
- Emilia Käsper (1)
- Aggelos Kiayias (1)
- Filip Van Laenen (1)
- Peeter Laud (2)
- Sven Laur (5)
- Taneli MielikÃ¤inen (1)
- Shiho Moriai (2)
- Valtteri Niemi (1)
- Roberto Parisella (1)
- Kateryna Pavlyk (2)
- Berry Schoenmakers (1)
- Janno Siim (3)
- Johan Wallén (1)
- Jan Willemson (1)
- Michał Zając (1)
- Michal Zajac (4)
- Bingsheng Zhang (1)
- Arne Tobias Ødegaard (2)