It's worth noting that conservatives, liberals, libertarians and federalism (assuming you're referring to American politics, if not, it basically means anyone who supports government regulation) is more of a 2D grid than a line.
Libertarians have a party separate from Republicans
For example, in American politics, Libertarians, who believe in the reduction of government control over property, have their own political party, separate from Republicans, who are seen as conservative. This shows the goals of conservatives don't always necessarily align with libertarian values.
What is a conservative, really?
A conservative is a person who essentially is conservative about change (IE they believe a pre-existing system is better or fewer changes are needed), and thus is more about (but not strictly!) maintaining the status quo. So the current status quo is prostitution is illegal, so passing laws maintains that.
This makes them fundamentally opposed to liberalism because, in theory, liberalism is about allowing more liberal ideals, in practice, liberalism often seems to involve government regulation. And thus, when conservatives undo liberal work, it appears as though conservative ideals are opposed to government regulation.
For example, taxation used to fund social programmes devised under a liberal government would be rolled back under a conservative government. Likewise, if the conservative government implemented any government regulations, it's likely a liberal government would roll those back. Such is politics.
What about free-market arguments?
Within conservatism you might find some that argue that supply-demand and economic forces should dictate companies, corporations behaviours, which often mandates that government regulation of corporations be curtailed.
That said, some level of government interference is necessary even within a 'free market', for example, to prevent collusion, price-fixing, anti-trust, and monopolies squeezing out competition (which is anti-thetical to the idea of free-market competition).
I think in truth, you will find some conservatives in favour of government regulation, and some against, with others being on the fence (depending on topic). It'd be similar in any other party, unless of course the party is either anarchist or libertarian.
It's probably worthwhile not to treat politics as being a linear line of either 'left or right' but a diverse mixture of many views.